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

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

作　　者：周成平[1] 陈前洋[1] 秦筱楲[2] 

机构地区：[1]华中科技大学图像识别与人工智能研究所,湖北武汉430074 [2]中国航天科工集团三院研发中心,北京100074

出　　处：《华中科技大学学报（自然科学版）》2005年第5期42-45,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

摘　　要：提出三维稀疏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.

关 键 词：稀疏A＊算法 航迹规划 并行算法 

分 类 号：TP75[自动化与计算机技术—检测技术与自动化装置]