Multi-Agent Planning - Multi-Agent 2D/3D Exploration
We consider the problem of determining paths for one or many robots to navigate in an unknown a priori environment, so that the robots can be directed to sweep their sensors thoroughly to make a representation, i.e., map, of the target area. This project aims at developing algorithms that enable a team of robot to efficiently explores an unknown region, where efficiency is measured by both explored volume over time and computational runtime.
Much prior work in exploration based their approach either on a choice of representation for the environment or the means by which new information is acquired. These approaches tend to be “greedy” in that they look for the closest frontier or closest local minimum in entropy to achieve exploration. In practice, the “greedy” methods can be inefficient in exploring large and complex environments.
The issue of time efficiency is more complicated when considering multiple robots that have limited communication among them. In this work, we explicitly require robots to be physically within a distance range in order to share information. Such planning requires deliberate consideration in order to ensure time optimality when exploring with multiple robots. Existing strategies for maintaining inter-robot communication are mostly based on heuristics, which disregard whether the information exchange can expedite or hamper the overall exploration.
In this project, we developed a novel two-layered approach that improves time optimality by balancing the use of high-resolution information located near the robot and the low-resolution global information across the entire environment [1]. Leveraging such a world representation, we further bring forward the “pursuit” strategy for inter-robot communication, where robots opportunistically pursue each other to communicate if the information exchange can lead to faster exploration. Finally, we develop and open source a software platform to facilitate developing and benchmarking algorithms for autonomous exploration [2].
In both simulation and real-world experiments, for single-robot exploration, our method produces 80% higher exploration time efficiency than three other state-of-the-art methods in more than 300 runs. Meanwhile, the computational runtime of our method is 50% lower than that of others. For multi-robot exploration, our “pursuit” strategy produces higher exploration time efficiency compared to the conventional rendezvous-based strategies in 2000 simulation runs with up to 20 robots. We further showcase the deployment of our method in the SubT Finals, where it achieved the fastest and the most complete exploration among all teams, winning the “Most Sectors Explored Award”.
Figure: Left: Our method was deployed in the DARPA Subterranean Challenge Final Event, which took place in Louisville Mega Cavern, Kentucky, in September 2021. Three ground vehicles (blue, green, and red curves) running our method collaboratively explored the environment. The resulting point cloud map and robot trajectories are shown. The environment includes convoluted topology, rough terrains and cluttered obstacles. Our method achieved the fastest and the most complete exploration among all teams. Right: 20 robots explore a simulated tunnel environment using our “pursuit” strategy. Coordinate frames show the robots’ positions. Circles show the communication range (30m) with color code showing the communication status of 1. Out-of-comms with any robots (red) 2. In-comms with at least one robot (green), and 3. Pursuing other robots to deliver information (yellow).
[1] Cao, C., Zhu, H., Choset, H., & Zhang, J. TARE: A Hierarchical Framework for Efficiently Exploring Complex 3D Environments. Robotics: Science and Systems (RSS), 2021.
[2] Cao, C., Zhu, H., Yang, F., Xia, Y., Choset, H., Oh, J., & Zhang, J. Autonomous exploration development environment and the planning algorithms. International Conference on Robotics and Automation (ICRA), 2022.