5.4.2　稀疏A* 算法

A* 算法是全方向的扩展搜索，这种搜索方法使得A* 算法的搜索空间大，存在冗余的扩展节点，所以在无人机的航迹上通常使用稀疏A* 算法，可以有效地缩小搜索空间，缩短搜索时间，其流程图如图5.10所示。因为规划出的航迹结合了约束条件，可满足无人机机动性能，所以可直接应用于无人机飞行。

图5.10　基于稀疏A* 算法的航迹规划流程图

稀疏A* 结合无人机的约束条件，在给定最小步长l min、最大转弯角θ 的约束条件下，稀疏A* 算法的扩展区域为扇形区域，扩展角度为2θ，扩展半径为l min，若扩展区域均匀分成N 等份，则扩展点为N ＋1个，如图5.11所示。

其中，P（i－1）表示上一节点，P（i）表示当前节点。

图5.11　稀疏A* 单点扩展图

稀疏A* 算法的搜索过程为：从起点开始，以最小步长l min 为步长进行扩展，在当前点的航迹方向上的2θ扇形区域内，计算出N＋1个待扩展节点的代价评估函数值，选择代价评估函数值最小的节点作为下一个搜索节点，直至最终到达目标点。在稀疏A*算法中加入了最大转弯角和扩展节点以及最小步长的限制，大大缩小了算法的搜索空间并缩短了搜索时间。