Distributed matroid-constrained submodular maximization for multi-robot exploration: theory and practice
Distributed matroid-constrained submodular maximization for multi-robot exploration: theory and practice
复制标题
DOI：
10.1007/s10514-018-9778-6
复制
发表时间：
2019-02-01
影响因子：
3.5
通讯作者：
Michael, Nathan
中科院分区：
文献类型：
--
作者：
Corah, Micah;Michael, Nathan
通过一种基于顺序贪婪分配(SGA)的分布式多机器人搜索算法--分布式顺序贪婪分配(DSGA)，解决了利用多机器人团队进行高效在线搜索和测绘的问题。虽然SGA允许次最优性的界限，但机器人必须按顺序执行规划步骤。不是像SGA那样按顺序为每个机器人制定计划，而是使用固定数量的连续计划轮次将计划分配给机器人的子集。该算法保留了与SGA相同的次优界，只是增加了一个描述一次分配多个计划时产生的额外次最优性的术语。利用这一结果，我们将基于蒙特卡洛树搜索的单机器人规划器扩展到多机器人领域，并在受限和杂乱环境的模拟探索中对所得到的规划器进行了评估。实验结果表明，对于4-32个机器人的团队，由于分布式规划轮次中引入的冗余传感器信息，在实际应用中，仅给出两个或三个分布式规划轮次，次最优性仍然很小，而加速比是SGA的2-8倍。我们还结合了具有机器人间碰撞约束和非平凡动力学的空中机器人，并解决了随后对安全性和最佳性的影响。实时仿真和实验结果证明了多机器人探测的在线规划，并表明碰撞约束对探测性能的影响有限。
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.