Autonomous exploration is crucial for applications where environments are often inaccessible or hazardous to humans, such as in search and rescue, surveillance, and planetary exploration. Here, we consider determining paths for one or more robotsto navigate in an a priori unknown environment, such that the robots can be directed to thoroughly sweep their sensors to make a representation, namely, a map, of the target environment. Such a problem is closely related to coverage path planning, which seeks a path that allows sensors to sweep over all objects in an environment. The problem of finding the shortest path to achieve such a complete coverage was shown to be non-deterministic polynomial-time hard (NP-hard). Here, the exploration problem focuses more on discovering the environment and computing the coverage path on the fly. As a result, computing the exploration paths must be performed iteratively and incrementally to process incoming sensor data, which can be more challenging than solving the coverage path planning problem. Sensor noise, state estimation drift, and terrain variation present additional challenges.
Dual-Resolution Time-Efficient Autonomous Exploration
We collaborate with Prof. Zhang’s group at Carnegie Mellon Univeristy, and developed a two-level approach that efficiently explores an unknown region, where efficiency was measured by both explored volume over time and computational runtime. We validated this approach in several large-scale, complex, and cluttered environments both in simulation and in the real world, including the Subterranean (SubT) Challenge held by the Defense Advanced Research Projects Agency (DARPA). To improve the exploration time efficiency, our dual-resolution framework balances the use of high-resolution information located near the robot and the low-resolution global information across the entire environment. We then further extend the approach for multirobot exploration by bringing forward the “pursuit” strategy forinter-robot communication, where robots opportunistically pursue each other to facilitate communication if the information exchange can lead to faster exploration overall. We provide a theoretical analysis of our scheme and evaluated it both in simulation and in real-world experiments. We analyzed the computational complexity and the optimality gap resulting from the dual-resolution representation, specifically, the difference in length between the paths computed with and without the dual-resolution representation. We demonstrated that the optimality gap is bounded by a constant, independent of the environment size.
Empirically, for single-robot exploration, our method produced 80% higher exploration time efficiency than three other state-of-the-art methods in both physical and simulation experiments with more than 300 runs. Meanwhile, the computational runtime of our method was 50% lower than that of others. For multirobot exploration, our pursuit strategy produced higher exploration time efficiency compared with the conventional rendezvous-based strategies in more than 3400 simulation runs with up to 20 robots. More details can be found in [1] or this web.
With Unknown Initial Poses
In collaboration with Prof. Yin We then further consider the multi-robot exploration where the robots have unknown initial poses. In other words, the robots know neither their global coordinates nor the relative pose between any pair of them. This problem requires both quickly exploring the environments and robustly merging the sub-maps built by the agents. Most existing exploration strategies directly merge two sub-maps built by different agents when a single frame observation is matched, which can lead to incorrect merging due to the false-positive detection of the overlap and is thus not robust. In the meanwhile, some recent place recognition methods use sequence matching for robust data association. However, naively applying these sequence matching methods to multi-agent exploration may require one agent to repeat a large amount of another agent’s history trajectory so that a sequence of matched observation can be established, which reduces the overall exploration time efficiency. To intelligently balance the robustness of sub-map merging and exploration efficiency, we develop a new approach for lidar-based multiagent 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 for agents whose sub-maps are merged, to improve exploration efficiency. Our experiments show that our approach is up to 50% more efficient than the baselines while merging sub-maps robustly. More details can be found in [2].
