An Integrated Traveling Salesman and Coverage Path Planning Problem for Unmanned Aircraft Systems
An Integrated Traveling Salesman and Coverage Path Planning Problem for Unmanned Aircraft Systems
复制标题
DOI：
10.1109/lcsys.2018.2851661
复制
发表时间：
2019-01-01
影响因子：
3
通讯作者：
Jin, Lei
中科院分区：
文献类型：
--
作者：
Xie, Junfei;Carrillo, Luis Rodolfo Garcia;Jin, Lei
无人驾驶飞机系统（UAS）在陆地监测、3D测绘、搜索和救援等方面得到了极大的普及。在这些任务中，关于无人机系统路径规划的现有研究仅考虑要检查的单个区域。然而，在执行真实的生命使命时，经常遇到需要考虑多个区域的情况。如何为无人机系统设计覆盖多个区域的最佳路径至关重要。从战略的角度来看，这样的问题可以被认为是旅行商问题（TSP）的一个变种，并与覆盖路径规划（CPP）问题相结合。虽然TSP和CPP已经被广泛研究，但其组合，在这里被命名为TSP-CPP，尚未受到任何关注。本文就如何制定和解决这一问题进行了初步探讨。两种新的方法，包括基于网格的方法和基于动态规划的方法被引入到寻找（近）最优解。数值分析和仿真研究证明和说明所提出的TSP-CPP方法的最优性和效率。
Unmanned aircraft systems (UASs) have gained great popularity in land monitoring, 3-D mapping, search and rescue, among others. Existing studies on UAS path planning in these missions consider only a single region to be examined. However, it is frequently encountered that multiple regions need to be considered while performing a real life mission. How to design the optimal path for the UAS to cover multiple regions is then critical. From a strategical point of view, such a problem can be considered as a variant of the traveling salesman problem (TSP) combined and enhanced with the coverage path planning (CPP) problem. Although TSP and CPP have been studied extensively, its combination, which here is given the name TSP-CPP, hasn't received any attention. In this letter, a preliminary study on how to formulate and solve this problem is conducted. Two novel approaches including a grid-based approach and a dynamic programming based approach are introduced to find the (near) optimal solution. Both numerical analysis and simulation studies are conducted to prove and illustrate the optimality and efficiency of the proposed TSP-CPP approaches.