Distributed matroid-constrained submodular maximization for multi-robot exploration: theory and practice

Abstract

This work addresses the problem of efficient online exploration and mapping using multi-robot teams via a new distributed algorithm for multi-robot exploration, distributed sequential greedy assignment (DSGA), which is based on sequential greedy assignment (SGA). While SGA permits bounds on suboptimality, robots must execute planning steps sequentially. Rather than plan for each robot sequentially as in SGA, DSGA assigns plans to subsets of robots using a fixed number of sequential planning rounds. DSGA retains the same suboptimality bounds as SGA with the addition of a term that describes the additional suboptimality incurred when assigning multiple plans at once. 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 for teams of 4–32 robots suboptimality due to redundant sensor information introduced in the distributed planning rounds remains small in practice given only two or three distributed planning rounds while providing a 2–8 times speedup over SGA. We also incorporate aerial robots with inter-robot collision constraints and non-trivial dynamics and address subsequent impacts on safety and optimality. Real-time simulation and experimental results for teams of quadrotors demonstrate online planning for multi-robot exploration and indicate that collision constraints have limited impacts on exploration performance.