关键词: 管路, 快速扩展随机树, 碰撞检测, 快速绕障, 关键节点

Abstract: An improved rapidly-exploring random tree algorithm is proposed based on collision
information for the problem of non-orthogonal pipe automatic routing. This algorithm has three main
improved methods: node expansion based collision information, fast bypassing obstacle algorithm
and node expansion based on the thinking of node’s probability. It could search out a path to walk
along the surface of structure parts in comparably short time. On the basis of the three methods, the
optimization strategy based key nodes is used to optimize the obtained path and form the final result
of pipe routing layout. A prototype system is developed and the feasibility of the algorithm by
instance is verified.

Key words: pipe, rapidly-exploring random tree, collision detection, fast bypassing obstacle algorithm;
key nodes