摘要： 传统的三维管路路径规划算法存在等分栅格建模时间长、占用存储空间大、蚁群算法搜索效率低等问题。为此，提出一种基于八叉树建模和改进蚁群算法的路径规划算法。采用八叉树模型进行环境建模，由动态启发信息指导生成初始解，使搜索路径的概率选择机制更合理，通过更新排列前w位和后h位的蚂蚁路径信息素，缩小算法的存储空间，避免搜索规则过度使用。仿真实验结果证明，该算法收敛快速，求解效率较高。

关键词: 八叉树建模, 动态启发信息, 信息素更新, 三维管路路径规划, 蚁群算法

Abstract: Traditional 3D pipe path planning algorithm has the shortcomings that the grid modeling must take huge storage space for a long time and the search efficiency of Ant Colony System(ACA) is low. This paper proposes a routing algorithm based on octree modeling and modified ACA. It adopts octree model to model environment, generates the primary route through dynamic heuristic information, rationalizes the path selection mechanism, and updates the pheromone of the former w and the latter h, so that the storage space is reduced and excessive use of search rules is avoided. Simulation results show that the algorithm is effective and feasible.

Key words: octree modeling, dynamic heuristic information, pheromone update, 3D pipe path planning, Ant Colony Algorithm(ACA)

中图分类号: 

• TP391