EFMES: efficient frontier-based multi-robot exploration strategy for unknown environments

Abstract Multi-robot exploration systems are critical for applications in hazardous and GPS-denied environments where external localization infrastructure is unavailable. To address the key challenges of limited inter-robot perception, overlapping exploration areas, and insufficient computational efficiency in existing exploration algorithms, this paper proposes an efficient frontier-based multi-robot exploration strategy (EFMES). The method employs an improved connectivity-based frontier clustering algorithm to rapidly identify frontier centers in the map. A fast multi-robot potential field algorithm is proposed, that calculates gain maps by combining multi-robot repulsion functions with an improved Shortest Path Fast Algorithm. The proposed strategy achieves rapid computation while avoiding redundant exploration. Additionally, the method establishes an auction-based task allocation mechanism through an exploration market paradigm, enabling dynamic coordination between robots based on real-time utility evaluation. The method relies on map merging for multi-robot localization and flexibly enables both independent exploration before map merging and coordinated exploration after map fusion among multiple robots. Extensive simulation experiments across diverse environmental configurations demonstrate that EFMES achieves superior exploration performance compared to state-of-the-art methods. The algorithm improved average exploration efficiency by 24.6% and reduced travel costs by 15.6%–28.6%.