Combining Geometric and Information-Theoretic Approaches for Multi-Robot Exploration
This addresses the challenge of efficient multi-robot exploration in structured environments, though it appears incremental as it builds on existing single-robot and tree exploration methods.
The paper tackles the problem of exploring an orthogonal polygon with a team of robots by combining geometric and information-theoretic approaches, resulting in an algorithm with exploration time competitive with the offline optimal as a function of the number of robots.
We present an algorithm to explore an orthogonal polygon using a team of $p$ robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. We show that the exploration time of our algorithm is competitive (as a function of $p$) with respect to the offline optimal exploration algorithm. The algorithm is based on a single-robot polygon exploration algorithm, a tree exploration algorithm for higher level planning and a submodular orienteering algorithm for lower level planning. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot.