In this paper, a frontier-based exploration is used with a couple of cooperating mobile robots to explore unknown environments. The aim is to decrease the overlap between the robots to minimize the exploration time. The proposed exploration algorithm is based on a bidding function in which a new special parameter was introduced to decrease the overlap between the robots. A large number of experiments have been conducted to analyze the importance of the weight parameters included in the proposed technique. As a result of these experiments, the weight values can be chosen to guarantee short exploration time. The new algorithm has been assessed with different environments with different shapes and different numbers of obstacles. Lastly, the results of our algorithm were compared with the results in the literature. The new technique led to promising results.