一种基于改进快速搜索随机树算法的管路自动布局方法  

A Method for Pipe Auto Layout Based Improved RRT Algorithm

作　　者：徐联杰 刘检华[1] 何永熹[1] 吴宏超[1] 刘佳顺[1] 

机构地区：[1]北京理工大学机械与车辆学院,北京100081

出　　处：《图学学报》2016年第1期1-10,共10页Journal of Graphics

基　　金：国家自然科学基金项目(51275047);"十二五"国防基础科研项目(A2220110008)

摘　　要：针对非正交管路自动布局问题,提出一种基于障碍物碰撞信息的快速搜索随机树改进算法。该算法主要采用基于碰撞信息的节点扩展策略、快速绕障算法以及基于概率思想的节点扩展策略3种方法进行改进,能够在较短的时间内搜索出一条沿结构件表面从起点到终点的路径,在此基础上采用基于关键节点的路径优化策略,对求解得到的布局路径进行优化后形成最终的管路布局结果。开发了原型系统,通过实例验证了该算法的可行性。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.

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

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]