5.2.2 航迹规划搜索算法
路径规划算法有很多种，分类标准不同，分类结果也不同。
根据规划的范围来划分可以分为全局航迹规划和局部航迹规划。全局规划是根据已经获得的环境信息，为旋翼飞行机器人规划出一条可行且优化的路径，相关经典算法有基于栅格的A* 算法。局部规划算法的环境信息完全未知或者部分未知，通过传感器和摄像头等设备对工作环境进行探测并不断更新，以获取障碍物的位置、形状和尺寸等信息来进行路径规划。局部规划算法主要有人工势场法、遗传算法、神经网络法和模拟退火法等。
根据几何学方法不同可以分为基于图形的算法与基于栅格的算法。基于图形的算法如概率地图法（PRM），处理结果较为准确，但是收敛时间长；基于栅格的A* 算法采用最佳优先规则，收敛时间短。
根据是否需要进行环境建模划分，不需要进行环境建模的算法有人工势场法、快速扩展随机树等。
根据实时环境进行划分，可分为蚁群算法（AC）、粒子群算法（PSO）、概率地图法（PRM）和快速扩展随机树（RRT）法等。
本书根据国内外最新研究调研得出五类无人机航迹规划方法：基于抽样的算法、基于节点的优化算法、基于数学模型的算法、生物启发算法、基于复合方法的算法。
基于抽样的算法：这种算法需要预先知道无人机所在的工作信息。通常对环境进行抽样得到一组节点或其他形式，然后映射环境或随机搜索找到最优路径。其中包括被动算法，如PRM，K-PRM，S-PRM，可视图法等；主动算法，如RRT，人工势场法。
基于节点的优化算法：通过利用一组节点生成路径，搜索一组节点图或者地图。地图已经对传感器获取的先验信息进行了处理，该类算法有Dijkstra算法、A* 算法、动态A* 等。
基于数学模型的算法：包括线性规划、非线性规划、最优控制等。这些方法对环境和机体建立数学模型，并且将无人机的运动学约束和动力学约束考虑在内，然后利用不等式和代价函数方程实现一个最优解决方案。
生物启发算法：该算法通过仿生物的行为来解决实际问题。这个路径规划方法可用于构建复杂环境模型，并对目标搜索具有较强收敛性。生物启发算法一般分为进化算法和神经网络法。进化算法包括遗传算法、蚁群算法、粒子群算法，根据环境、无人机性能、任务目标等，评价每个个体的适应度，适应度最好的个体解码为最优路径。神经网络法的目标是为神经活动生成一个动态图，是一种模仿生物神经网络结构和功能的数学模型。
基于复合方法的算法：当前三维路径规划倾向于与其他算法结合，目的是规划出最优路径（长度、时间、能耗或威胁最优）。单独一种算法无法达到最好的规划效果。例如人工势场法，若没有与导航函数或者其他方法组合，往往会陷入局部最优；A* 算法处理高维问题时复杂度高，需要组合其他算法进行降维和提速。
本书将在下面的小节中介绍几种在旋翼无人机中应用广泛且具有良好性能的实用算法。