钱 宇，祝祯祎

(中国民用航空飞行学院，四川 广汉 618307)

1 引言

近几年来，世界范围内出现越来越多的自然灾害，例如洪水、地震、台风等，这些灾害覆盖面积广、房屋摧毁数量多。无人机作为一种新兴无人驾驶技术的载体，具有重量轻、航时长、机动性能好等优势，在救援的过程当中发挥越来越重要的作用[1]。为了满足无人机快速高效地进行定点搜寻工作[2]，需要根据已知的障碍物环境和其物理性能约束规划一条耗时最少、航程最短的航迹。

针对无人机航迹规划技术，国内外学者提出了很多高效的航迹规划算法，主要分为传统经典算法和现代智能算法[3]。传统经典算法包括人工势场法[4](Artificial Potential Field，APF)、模拟退火算法[5](Simulated Annealing Algorithm，SAA)等。这类方法容易陷入局部最优解，在规划空间较大时搜索效率低，相比之下，现代智能算法收敛程度更好，时间复杂度更小，应用范围更广。其中包括A*算法[6]、遗传算法[7](Genetic Algorithm，GA)、蚁群算法[8](ACO)等。经过几十年的发展，这些算法在某些具体场景下仍然有一定的局限性，因此提出了许多改进算法。程泽新等[9]将遗传算法用于无人机航迹规划中，对进化变异的策略进行改进并结合启发式搜索方程，可以加快收敛的速度并更有效地获取可行路径，但是由于是基于概率的选择机制，仍然存在陷入局部最优的可能性。刘永琦等[10]提出在三维环境中修剪扩展节点，降低传统A*算法的网格节点计算量，提高了路径搜索速度，然而并未详细阐释改进A*算法的搜索流程。

动态规划算法(Dynamic Programming，DP)是由美国数学家R.E.Bellma求解多决策问题时提出的一种优化算法，特点在于搜索效率高，结果稳定可靠，从而受到广泛的关注。……