Efficient online multi-robot exploration via distributed sequential greedy assignment

July 2017

Efficient online multi-robot exploration via distributed sequential greedy assignment

Authors:

M. Corah and N. Michael

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.
@conference{Corah-2017-120104,
author = {M. Corah And N. Michael},
title = {Efficient online multi-robot exploration via distributed sequential greedy assignment},
booktitle = {Proceedings of Robotics: Science and Systems (RSS '17)},
year = {2017},
month = {July},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.