基于扇形领域扩展的同步双向A*算法

为提高航空器飞行的安全性和平滑性,解决传统A^*算法拐弯角度过大、搜索路径节点过多等问题,提出一种基于扇形领域扩展的同步双向A^*搜索算法。首先,根据栅格图法扩展危险区域边界;其次,设计了基于同步双向搜索的A^*算法,动态定义正反向搜索的目标节点。针对搜索角度有限问题,提出了在5×5领域内的扇形领域扩展策略,并设计了含有双重权重参数的评价函数以减少冗余点的产生。为验证改进算法的有效性,选取方形和不规则形状危险区进行仿真。结果表明改进的同步双向搜索算法搜索的路径更平滑;与传统双向A^*算法的结果相比,在不同形状的危险区域下,搜索路径长度分别减少了1.65%、13.16%,搜索路径节点个数减少了42.6%、46.81%,具有较强的搜索效率。

Research on synchronous bi-directional A* algorithm based on sector field expansion

In order to improve the safety and smoothness of flight, and solve the problems of excessive turning angle and too many search path nodes in the traditional A* algorithm, this paper proposed a synchronous bi-directional A* search algorithm based on sector field expansion. Firstly, this paper extended the hazardous area boundaries based on the raster map method. Secondly, it designed the A* algorithm based on synchronous bi-directional search, which dynamically defined the target nodes for forward and reverse search. Aiming at the problem of limiting search angles, this paper proposed a sector expansion strategy in 5×5 domain, and designed an evaluation function with double weight parameters to reduce the generation of redundant points. Finally, in order to verify the effectiveness of the improved algorithm, this paper selected square and irregular shape hazard areas for simulation. The results show that the improved algorithm searches for a smoother path. Compared with the results of the traditional bi-directional A* algorithm, the length of its search path reduce by 1.65% and 13.16%, and the number of its search path nodes reduce by 42.6% and 46.81%, respectively, under different shapes of hazard areas, which has a strong search efficiency.