Efficient online multi-robot exploration via distributed sequential greedy assignment

Abstract

This work addresses the problem of efficient online exploration and mapping using multi-robot teams via a distributed algorithm for planning for multi-robot exploration— distributed sequential greedy assignment (DSGA)—based on the sequential greedy assignment (SGA) algorithm. SGA permits bounds on suboptimality but requires all robots to plan in series. Rather than plan for robots sequentially as in SGA, DSGA assigns plans to subsets of robots during a fixed number of rounds. DSGA retains the same suboptimality bounds as SGA with the addition of a term describing suboptimality introduced due to redundant sensor information. We use this result to extend a single-robot planner based on Monte-Carlo tree search to the multi-robot domain and evaluate the resulting planner in simulated exploration of a confined and cluttered environment. The experimental results show that suboptimality due to redundant sensor information introduced by the distributed planning rounds remains near zero in practice when using as few as two or three distributed planning rounds and that DSGA achieves similar or better objective values and entropy reduction as SGA while providing a 2–6 times computational speedup for multi-robot teams ranging from 4 to 32 robots.