基于稀疏A＊算法的三维航迹并行规划算法

Parallel algorithm of 3D route planning based on the sparse A* algorithm

提出三维稀疏A*算法的规划时间组成,并分析该算法的时间复杂度和并行性,随后给出并行任务划分的不同策略.判断OPEN表中是否存在与新节点相同节点的准则修改为:只比较OPEN表中代价比新节点代价小的节点,新准则可以有效地减少对共享式OPEN,CLOSED表的瓶颈效应.提出的三维航迹并行规划算法在并行机群环境中实现,实验结果表明时间效果改善明显.

The composing of planning tine of 3D sparse A algorithm (3D SAS) was put forward, the time complexity and parallelism of this algorithm were analysed, and several strategies of task allocation proved. Whether there is the same node with the new node in the OPEN list may be determined by selecting nodes whose cost are less than the new node. The new principle can reduce the influence of the bottleneck of shared OPEN and CLOSED lists. The paralleled algorithm is realized in the cluster environment. The experiment results show that the algorithm may remarkably cut down the planning time.