多线程贪婪启发式方法用于无人机几何路径规划

《The Aeronautical Journal》：A multi-threaded greedy heuristic for geometric path planning of unmanned aerial vehicles

　　

无人机（unmanned aerial vehicles，UAV）及其改进型在监视、侦察、监控和作战任务中展现的巨大潜力，吸引了研究人员对解决其相关挑战性问题的关注。其中一个关于上述飞行器的挑战性问题涉及如何通过考虑敌方威胁、燃料或电池消耗以及转向机动的极小化目标或约束来计算飞行路径。最近，来回算法（Back-and-Forth，BaF）被引入作为无人机路径规划问题的求解器，并且其相对于著名的基于元启发式技术的优越性能已得到验证。在本研究中，研究人员将BaF算法的贪婪启发式与多线程系统的计算能力以及精心设计的搜索边界调整策略相结合，开发了一种称为平行规划器（Parallel Planner，PPlanner）的新方法。通过改变并发线程的数量并使用来自三个固定高度战场场景的十二个测试案例，详细研究了PPlanner的性能。此外，将PPlanner计算的路径与BaF算法以及十四种不同的元启发式引导技术计算的路径进行了比较。实验研究表明，虽然PPlanner在十二个案例中的六个案例中获得了比其他所有竞争对手更高质量的路径，但在其余案例中它被列为第二或第三最佳路径规划器，并且即使消耗的函数评估次数至少少三倍，也位于前三名方法之中。

无人机（unmanned aerial vehicle，UAV）及其改进型（如无人作战飞行器，unmanned combat aerial vehicle，UCAV）在监视、侦察、监控和作战任务中展现出巨大潜力，路径规划是决定任务成败的关键第一步。路径需要同时考虑敌方威胁（避免被探测）、燃料消耗和转弯机动限制，然而在无限解空间中高效找到最优路径是一个挑战。近年来，Aslan提出的来回算法（Back-and-Forth，BaF）通过贪婪启发式生成两个骨干路径并合并优势段，显示出优于传统元启发式方法的性能，但其贪婪启发式仍有改进空间，尤其是在利用并行计算能力和动态调整搜索空间方面。因此，研究人员旨在开发一种多线程并行规划器，结合BaF的贪婪启发式、多线程计算能力和精巧的搜索边界调整策略，以进一步提高路径规划的质量和效率。该研究验证了PPlanner在多个战场场景下的优越性，并发表在《The Aeronautical Journal》。

主要关键技术方法包括：1）贪婪启发式算法：继承自BaF，用于从每个子分割线上选择路径点，优先选择距离前一点最近且不在敌方威胁探测范围内的点，以最小化线段长度和转弯角度，保证安全。2）多线程并行架构：每个线程独立执行贪婪启发式，并使用不同的搜索边界（由调整策略根据线程索引计算，使搜索空间重叠且具有不同局部/全局搜索能力）。3）搜索边界调整策略：根据线程索引n，计算下界LB_n和上界UB_n，使得低索引线程搜索较长线段，高索引线程搜索较短线段，从而覆盖不同区域。4）骨干路径生成与更新：每个线程从起点到终点和从终点到起点分别生成两个骨干路径，然后通过取平均点（公式(7)）并检查是否改善路径质量来交换有利线段，最终合并得到更优路径。实验使用三个固定高度战场场景，每个场景有多个敌方威胁（中心、半径、等级），以及不同分割点数（D=10,15,20,25）。PPlanner用C语言和pthreads库实现，在双Intel Xeon E5-2682 v4处理器上运行。

**5.0 Experimental studies**
通过12个测试案例（三个场景各4个不同D值）和不同线程数（1,2,4,6,8,12,16,20,24,32,48,56,64）的实验，研究人员发现：增加线程数通常能提高路径质量，但存在最优配置（如Scenario-1的15D和20D需64线程，Scenario-2的10D和20D需64线程等）。PPlanner的更新程序（公式(7)）使得不同线程配置下的最终路径质量相对稳定，因为有利线段可在骨干路径间转移。将PPlanner（32线程）与BaF及14种元启发式（artificial bee colony，ABC；genetic algorithm，GA；GAPSO；moth flame optimisation，MFO；salp swarm algorithm，SSA；pathfinder algorithm，PFA；stain bowerbird optimisation，SBO；sine cosine algorithm，SCA；ECTLBO；HSGWO-MSOS；CIPSO；grey wolf optimisation，GWO；artificial ecosystem optimiser，AEO；NSEAEO）比较，结果显示：PPlanner在12个案例中6个排名第一，其余排名第二或第三，且消耗的函数评估次数仅为元启发式的1/3.6至1/8.5。执行时间分析表明，PPlanner（32线程）比BaF最多多耗时0.006秒，但性能显著提升。Wilcoxon符号秩检验（ρ=0.05）证实PPlanner在统计上优于13种算法，仅与AEO和NSEAEO无显著差异，但PPlanner仍以更少评估次数获得更好或相当结果。

**6.0 Conclusion**
无人机（UAV）或无人作战飞行器（UCAV）系统任务性能与飞行路线之间的明显关系增加了对强大路径规划技术的需求。BaF算法是一种最新的确定性路径规划技术，它引入了一种高效的贪婪启发式，用于生成骨干路径，随后将它们合并以产生更高质量的候选解。在本研究中，继承自BaF算法的贪婪启发式被专门化，以利用多线程系统的计算能力。每个线程负责在由新引入的调整策略确定的下界和上界内生成骨干路径，然后执行重新设计的组合程序，以连接属于骨干路径的更鲁棒线段。所提出的PPlanner技术通过分配12个不同的常数给线程数进行了研究，并使用来自三个不同战场场景的12个测试案例分析了计算路径质量如何根据敌方威胁属性和问题维度变化。还将PPlanner发现的路径与BaF和其他14种基于元启发式的规划器发现的路径进行了比较。比较研究使得研究人员能够断言，PPlanner在所有测试案例中均优于BaF，并且能够获得比绝大多数考虑的元启发式更好的路径，位列前三名方法。尽管PPlanner需要的函数评估次数少于实验的元启发式，但运行一组并行线程，每个线程具有由所提出的调整策略确定的自己的下界和上界，融合了不同层次的局部和全局搜索特性。此外，新设计的组合程序使得PPlanner能够适当地在贪婪启发式发现的路径之间转移有利线段。未来的研究可以致力于提出PPlanner变体，其中线程从集合或池中选择其组合程序。此外，用于确定下界或上界增减量的数学模型可以替换为随机方法，以处理由敌方武器属性、起点和终点位置以及不同高度引起的不确定性。