Abstract
Multi-agent exploration of a bounded 3D environment with unknown initial positions of agents is a challenging problem. It requires quickly exploring the environments as well as robustly merging the sub-maps built by the agents. We take the view that the existing approaches are either aggressive or conservative: Aggressive strategies merge two sub-maps built by different agents together when overlap is detected, which can lead to incorrect merging due to the false-positive detection of the overlap and is thus not robust. Conservative strategies direct one agent to revisit an excessive amount of the historical trajectory of another agent for verification before merging, which can lower the exploration efficiency due to the repeated exploration of the same space. To intelligently balance the robustness of sub-map merging and exploration efficiency, we develop a new approach for lidar-based multi-agent exploration, which can direct one agent to repeat another agent's trajectory in an adaptive manner based on the quality indicator of the sub-map merging process. Additionally, our approach extends the recent single-agent hierarchical exploration strategy to multiple agents in a cooperative manner by planning for agents with merged sub-maps together to further improve exploration efficiency. Our experiments show that our approach is up to 50% more efficient than the baselines on average while merging sub-maps robustly.
Introduction
Efficient exploration of unknown 3D environments using multi-robot teams is critical for applications such as search and rescue or planetary exploration. A significant hurdle in these scenarios is the lack of prior knowledge regarding the relative starting positions of the agents. Robots must independently build local sub-maps and merge them into a unified global representation upon detecting overlaps. Current strategies typically oscillate between two extremes: aggressive merging, which risks map corruption from false-positive matches, and conservative merging, which wastes time on redundant verification. MUI-TARE addresses this by introducing an adaptive merging mechanism and a cooperative hierarchical planner to optimize both robustness and efficiency.
Methodology
System Architecture
The MUI-TARE framework operates on a server-client architecture. Individual agents register lidar scans and follow local waypoints, while the central server manages sub-map merging and global path planning.
Adaptive Sub-map Merging
The core of the merging process is an adaptive verification strategy. When a potential overlap is detected through feature matching, the system evaluates a "verification gain." If the match quality is high, the merge proceeds immediately. If uncertainty exists, the system calculates a specific path for one agent to retrace a portion of another's trajectory to confirm the association. This approach effectively eliminates "wrong associations" (false positives) and corrects "short associations" (minor alignment errors) without the overhead of fixed-length verification.
Cooperative Hierarchical Planning
Once sub-maps are merged, the agents transition from individual exploration to a coordinated team effort. The system employs a hierarchical planning strategy:
- Global Planner: Formulates the exploration task as a multi-depot vehicle routing problem (MDVRP). It assigns unexplored subspaces to agents to minimize the completion time of the slowest robot, thereby balancing the workload.
- Local Planner: Each agent utilizes a local version of the Terrain-Aware Real-time Exploration (TARE) algorithm to compute kinodynamically feasible paths within its assigned subspace, ensuring complete coverage of all surfaces.
Experimental Evaluation
The framework was validated in high-fidelity Gazebo simulations using two complex 3D environments: a large-scale campus model (340m x 340m) and a multi-story parking garage (140m x 130m). These environments tested the system's ability to handle undulating terrain and vertical structures.
Results
MUI-TARE demonstrated significant improvements in exploration efficiency:
- Efficiency Gains: The system was 29% faster than the conservative TRUST-Explorer baseline for 2-agent scenarios and 14% faster for 3 agents.
- Coordination Impact: When compared to a non-cooperative version of TARE, MUI-TARE achieved over 50% higher efficiency, highlighting the value of the MDVRP-based global coordination.
- Robustness: The adaptive mechanism successfully handled false-positive loop closures that caused aggressive baselines to fail, maintaining map integrity throughout the exploration process.
Conclusion
MUI-TARE provides a robust and efficient solution for multi-agent exploration with unknown initial positions. By adaptively balancing verification and exploration, and employing a cooperative hierarchical planner, the framework significantly outperforms existing aggressive and conservative strategies. Future work will focus on decentralizing the architecture to improve resilience in communication-constrained environments.
Summary updated