Efficient Online Multi-robot Exploration via Distributed Sequential Greedy Assignment

Authors: Micah Corah, Nathan Michael

This work addresses the problem of efficient online exploration and mapping using multi-robot teams and distributed computation. We propose a new distributed algorithm for planning for multi-robot exploration—distributed sequential greedy assignment (DSGA)—based on the sequential greedy assignment (SGA) algorithm. SGA admits 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 using a fixed number of rounds while robots plan in parallel. DSGA retains similar suboptimality bounds as SGA with the addition of a term describing suboptimality introduced due to redundant sensor information that may have been avoided using a fully sequential algorithm. 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 additive suboptimality terms introduced by the distributed planning rounds remain near zero in practice when using as few as two or three distributed planning rounds, and that therefore DSGA achieves similar or better objective values and entropy reduction as SGA while providing a 2–7 times computational speedup for multi-robot teams ranging from 4 to 32 robots.