Scalable Coverage Path Planning of Multi-Robot Teams for Monitoring Non-Convex Areas
Scalable Coverage Path Planning of Multi-Robot Teams for Monitoring Non-Convex Areas
复制标题
DOI：
10.1109/icra48506.2021.9561550
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Leighton Collins;P. Ghassemi;E. Esfahani;D. Doermann;Karthik Dantu;Souma Chowdhury
中科院分区：
文献类型：
--
作者：
Leighton Collins;P. Ghassemi;E. Esfahani;D. Doermann;Karthik Dantu;Souma Chowdhury
本文提出了一种新的多机器人覆盖路径规划（CPP）算法-又名SCoPP -提供了一个时间效率高的解决方案，工作负载平衡的计划，为每个机器人在多机器人系统中，根据他们的初始状态。该算法考虑了不连续性（例如，禁飞区），并使用离散的、计算高效的最近邻路径规划算法来提供每个机器人的路径点的优化有序列表。该算法包括五个主要阶段，其中包括转换用户的输入作为一组顶点的地理坐标，离散化，负载平衡分区，拍卖的冲突细胞在离散空间，和路径规划过程。为了评估主要算法的有效性，多无人机（UAV）洪水后评估的应用程序被认为是，和算法的性能进行了测试，在三个不同大小的测试地图。此外，我们的方法相比，一个国家的最先进的Guasella等人创建的方法。进一步分析SCoPP的可扩展性和计算时间进行。结果表明，SCoPP在使命完成时间方面具有上级优势，对于由150个机器人组成的团队所覆盖的大地图，其计算时间低于2 min，从而证明了其计算可扩展性。
This paper presents a novel multi-robot coverage path planning (CPP) algorithm - aka SCoPP - that provides a time-efficient solution, with workload balanced plans for each robot in a multi-robot system, based on their initial states. This algorithm accounts for discontinuities (e.g., no-fly zones) in a specified area of interest, and provides an optimized ordered list of way-points per robot using a discrete, computationally efficient, nearest neighbor path planning algorithm. This algorithm involves five main stages, which include the transformation of the user’s input as a set of vertices in geographical coordinates, discretization, load-balanced partitioning, auctioning of conflict cells in a discretized space, and a path planning procedure. To evaluate the effectiveness of the primary algorithm, a multi-unmanned aerial vehicle (UAV) post-flood assessment application is considered, and the performance of the algorithm is tested on three test maps of varying sizes. Additionally, our method is compared with a state-of-the-art method created by Guasella et al. Further analyses on scalability and computational time of SCoPP are conducted. The results show that SCoPP is superior in terms of mission completion time; its computing time is found to be under 2 mins for a large map covered by a 150-robot team, thereby demonstrating its computationally scalability.