基于双步构造策略的多无人机覆盖路径规划方法

Multi-UAV Coverage Path Planning Based on Two-step Construction Strategy

摘要:

针对多无人机在草地、大田等复杂场景下协同覆盖作业时面临的路径规划复杂度高、区域边界复杂及机具资源闲置等问题，本文提出了一种高效、负载均衡的多无人机覆盖路径规划框架。首先提出递归分解+变邻域模拟退火算法双步构造策略。该策略以子多边形宽度和最小为阶段性目标，首先利用凹多边形凸分解特性设计递归分解方法使宽度和局部最小；进而，通过将递归分解嵌入可变邻域改进的模拟退火算法，实现宽度和全局最小化。同时提出一种基于无人机性能指数的任务分配方法，该方法依据无人机速度和旁向间距计算性能指数，据此分派作业区域块并结合续航能力规划多架次路径，旨在均衡各机飞行任务时长。仿真试验表明：所提双步构造策略在所有测试案例中均能找到宽度和全局最小凸分解方案，且在5、6、7个凹顶点测试案例中，宽度和较改进遗传算法分别降低9.072、5.169、2.869%；基于性能指数的任务分配方法所得任务时长的变异系数低至4.02%~7.33%，可有效实现飞行任务时长均衡。

Abstract:

Aiming at the challenges of high path planning complexity, complex regional boundaries, and idle aircraft resources faced by multi-UAVs in grasslands, fields, and other complex scenarios, an efficient and load-balanced multi-UAV coverage path planning framework was proposed. The framework consisted of two core elements: first, an innovative two-step construction strategy of “recursive decomposition-variable neighborhood simulated annealing algorithm”. The strategy took the minimization of the total sub-polygon width as the stage goal, firstly, using the convex decomposition property of concave polygons to design the recursive decomposition method to minimize the width and localization, and then, embedding the recursive decomposition into the improved simulated annealing algorithm with variable neighborhood to achieve the width and global minimization. Secondly, a task assignment method based on UAV performance index, which calculated the performance index based on UAV speed and bypass spacing, assigned the operation area blocks accordingly and planned the multi-trip paths in combination with the range capability, aiming to equalize the task duration of each aircraft. Simulation experiments showed that the proposed two-step construction strategy can find the width and the global minimum convex decomposition scheme in all test cases, and the width were reduced by 9.072, 5.169, and 2.869 percentage points, respectively, compared with the improved genetic algorithm in the test cases of 5, 6, 7 concave vertices;the coefficients of variation of the task duration obtained from the performance index-based task assignment method were as low as 4.02%~7.33%, which can effectively realize the equalization of task duration, effectively achieved mission duration equalization.