Multi-Regional Coverage Path Planning for Robots with Energy Constraint
Multi-Regional Coverage Path Planning for Robots with Energy Constraint
复制标题
DOI：
10.1109/icca51439.2020.9264472
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Junfei Xie;Jun Chen
中科院分区：
文献类型：
--
作者：
Junfei Xie;Jun Chen
覆盖路径规划(CPP)是实现草坪修剪、房间清洁、土地评估、搜救等需要覆盖区域的机器人应用的关键步骤。然而，多个地区的CPP得到的关注要少得多，这在许多真实场景中都会出现。这种多区域CPP问题可以看作是用CPP改进的旅行商问题(TSP)的一个变种，即TSP-CPP。在本文中，我们扩展了以前对TSP-CPP问题的研究，以进一步考虑机器人的能量约束。针对约束TSP-CPP问题的NP-hard计算复杂性，提出了一种基于逐步选择的启发式算法来求解该问题。仿真实验和对比研究表明，该算法在兼顾最优性和效率方面具有良好的性能。
Coverage path planning (CPP) has been extensively studied in the literature, which is a key step to realize robotic applications that require complete coverage of a region, such as lawn mowing, room cleaning, land assessment, search and rescue. However, CPP for multiple regions has gained much less attention, which arises in many real scenarios. This multiregional CPP problem can be considered as a variant of the traveling salesman problem (TSP) enhanced with CPP, namely TSP-CPP. In this paper, we extend our previous investigation on the TSP-CPP problem to further consider the energy constraint of the robots. As the constrained TSP-CPP problem has an NP-Hard computational complexity, a stepwise selection based heuristic algorithm is developed to solve the problem. Simulation experiments and comparison studies show the good performance of the proposed algorithm in balancing optimality and efficiency.