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

徐联杰， 刘检华， 何永熹， 吴宏超， 刘佳顺

(北京理工大学机械与车辆学院，北京 100081)

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

徐联杰， 刘检华， 何永熹， 吴宏超， 刘佳顺

(北京理工大学机械与车辆学院，北京 100081)

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

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

管路是复杂机械产品重要组成部分，管路布局质量可直接影响管路产品的可靠性。随着CAD技术的发展，国内外学者尝试采用自动布局技术提高管路布局设计效率和质量。

管路自动布局设计是在给定的几何、拓扑、技术和规则等约束中求解可行管路布置结果的过程。从几何意义上看，是在限定的布置空间中，从指定起点开始寻找出一条与其他物体不发生干涉，满足各种约束条件且到指定终点的路径，该问题与三维空间的机器人路径寻优问题类似，属于NP-hard组合优化问题。

管路自动布局问题经历了从二维空间的简单避开障碍物发展到三维空间内的满足多目标、多约束[1]路径求解的过程。国外方面，1975年Rourke[2]首次将迷宫算法用于管路自动布局，并使用矩形框包围障碍物的屏蔽技术解决碰撞干涉问题，该算法基于波的连续扩散原理找到一条最短路径，但是求解所需的存储空间大、操作速度慢。Ito[3-4]应用遗传算法在二维平面内搜索管路的最优路径，取得了突破性的进展，但其在处理遗传算法的编码方式和遗传算子上不太理想。2002年Park和Storch[5]利用单元生成法解决多约束目标的管路敷设问题，通过假定的敷设模式来产生管线的单元；当空间约束繁杂时，建立基本路径和改进空间路径并不容易。国内方面，北京航空航天大学的樊江等[6-7]针对航空发动机三维复杂管路系统的自动布局问题进行了深入地研究，实现了管路敷设智能化，并进行了很多有价值的探索。东北大学的王成恩等[8]针对航空发动机中的复杂管路，基于计算几何、微分几何以及智能优化的思想提出了一系列管路布局算法，并取得了较好的效果。大连理工大学的范小宁[9]采用基于蚁群算法和协作式互利共生类协同进化算法对船舶空间多管路的并行敷设问题进行求解，并在算法的协作机制中采用了优良个体构造小环境的方法，避免了在管路数目较多时出现组合爆炸现象。上海交通大学的曲艳峰等[10-11]采用八叉树模型进行环境建模，并用蚁群算法进行路径搜索，以较高的效率实现了三维管路路径规划问题求解。

虽然目前针对管路自动布局问题已经有了一系列的研究成果，但是在路径搜索算法中一般需要对搜索空间进行栅格化建模，在栅格数量较多时会出现组合爆炸的问题。快速搜索随机树(rapidly- exploring random tree，RRT)算法是一种增量的路径规划算法，其不需要进行栅格化建模，且改进具有很高的灵活性，因此在路径搜索中具有明显的优势。到目前为止，RRT算法已经有很多经典的改进方法，其改进主要集中在采样策略、扩展策略以及多树扩展 3个方面。其中，采样策略改进的经典算法主要有 RRT-GoalBais[12]、RRT-GoalZoom、RRT-Local等；扩展策略改进的经典算法主要有RRT-Con[13]、RRT-blossom[14]等；RRT算法还存在多树扩展[15]的改进策略，主要有RRT-ExtExt、RRT-ExtCon、RRT-ConCon等改进算法。此外，RRT算法的其他改进也在实际中得到了使用，如机器人自动导航[16]、无人机路径规划[17]、机械臂避障抓取运动规划[18]等。虽然这些改进算法在计算中具有较高的效率，并且有些已经进入了实际的运用，但是由于管路自动布局问题的复杂性，RRT算法有时(如需要沿障碍物表面敷设的管路)不能直接用来进行自动布局，还需进行进一步地改进。

本文根据RRT算法在路径搜索中的特性，结合管路自动布局中的约束问题，在现有RRT算法双树扩展的基础上，对其进行改进，提出了一种管路自动布局方法，开发了管路自动布局设计原型系统，并通过实例对算法进行了测试与验证。

1　管路自动布局求解问题分析

1.1基于改进RRT算法的管路自动布局总体思路

基于改进 RRT算法的管路自动布局方法的总体解决方案，如图1所示。

图1　管路自动布局总体解决方案

在图1的解决方案中，①获取三维管路布局结构模型，构建三维管路自动布局环境，在此基础上开展管路布局路径求解；②对管路的约束信息进行分析，并对部分工程约束进行数学建模，转化为管路路径规划过程中的约束条件，在RRT算法的初始化和改进中集中体现，然后利用该算法在可行空间中找到一条初始路径；③根据管路约束对利用RRT算法得到的初始路径进行优化，得到最终的管路路径；④根据路径可以直接生成虚拟三维实体管路模型。此外，在进行路径搜索以及路径优化的过程中，需要调用碰撞模型进行碰撞检测以保证路径始终处于可行空间中。

1.2管路自动布局问题描述

管路自动布局问题可以看作是一个刚性机器人在布局空间中进行运动规划，并找到一条从起点到终点的无碰路径，其数学描述如图2所示。

图2　管路布局问题描述

管路路径问题的工作空间用W表示，3W⊂R，该状态空间不仅包含初始产品所有的机械零件、装配夹具和卡具以及工作台等，还包括已经完成布局的管路及其附件等。其中，作运动规划的刚性机器人用 A表示，规划空间中的障碍物用 O表示，A、O⊂W。

一般来说，管路的截面都为恒定的圆形，因此可将进行路径规划的刚性机器人设定为一个球形刚体，其球心的运动轨迹即为管路的中心线，刚体运动扫掠的轨迹即为管路的初始路径。在管路路径求解计算过程中，球形刚体变换所产生的流形为三维流形，因此求解该路径规划问题的状态空间是三维的，用Cspace表示，Cspace=R3。Cfree是刚性机器人在状态空间中所有可行解的集合，该空间称为自由空间。在Cfree中的任意一个解用x表示，x∈Cfree。

在进行管路路径求解计算之前，先输入一个起点xinit和一个终点xgoal(xinit，xgoal∈Cfree)，经过计算得到一系列离散的路径节点，其包含了球形刚体的位姿信息，对这些离散点进行优化处理即可得到最终的管路路径。

1.3管路自动布局中考虑的约束

在管路自动布局过程中，通常应考虑到工程中的敷管规则。本文主要考虑了沿结构件表面布局的约束，其针对某些特定的管路，如较长或振动较强的管路，需要利用管卡等进行固定以获得较好的力学特性，为满足这一约束对RRT算法进行了相关的改进。同时，管路与结构件表面之间及管路之间均需预留一定的间隙，以满足管路的可装配性约束(柔性管可以贴壁敷设，不需考虑此约束)。此外，在优先考虑这两个约束的基础上，还需考虑其他管路设计规则：

(1) 管路不能与障碍物(零部件、附件、管路)干涉，即路径可行；

(2) 管路两端为直管段，直管段的长度不小于管径的2.5倍，以满足可装配性约束；

(3) 管路应平直且尽可能短，以减轻重量，减少流体损失；

(4) 管路弯头数应尽可能的少，以减少压降；

(5) 管路弯曲角度应不小于90°，以满足可加工性约束。

2　基于障碍物碰撞信息的RRT算法改进

本文提出的基于障碍物碰撞信息的 RRT改进算法，针对管路需要沿着结构件表面敷设的约束进行相关的数据设定与算法改进，使其在搜索空间中能较快地找到一条沿结构件表面从起点到终点的路径。算法主要针对节点的扩展、绕开障碍物以及随机树的收敛性3个方面进行改进，包括：基于碰撞信息的节点扩展策略、快速绕障算法以及基于概率思想的节点扩展策略。

2.1基本RRT算法

RRT算法首先由美国伊利诺伊大学 LaValle[19]提出，是一种适用于在高维空间中搜索路径的方法。该算法的路径节点扩展过程如图 3所示，在RRT算法进行路径规划之前需设置基本的相关参数，如路径搜索的起点xinit、终点 xgoal位置，路径点扩展步长ρ、终止循环数K等。在设置好参数后，算法会先创建一个空的扩展树T，并将起点xinit放入T中作为T的根节点，并对T进行如下循环扩展：

(1) 通过均匀随机采样函数得到一个随机点xrand；

(2) 在T的所有节点中找到距离xrand最近的节点xnear；

(3) 沿xnear指向xrand的方向，在与xnear的距离为步长ρ的位置，得到一个新的路径点xnew；

(4) 从xnear到xnew进行干涉检测，若发生干涉，则进入下一次循环；

(5) 若从xnear到xnew不干涉，则将新得到的节点加入T中，并判断该节点是否足够接近终点，若足够接近，则直接与终点相连，算法结束，否则继续循环。

若以上循环执行 K次之后仍然无法找到可行路径，则说明当前参数设置不合适，待求解问题无可行解或者陷入局部最优解等情况，需要重新设置算法参数。

图3　RRT算法的扩展过程

RRT算法的5个主要特点：①能在有限时间内返回一个可行解；②在算法中障碍物不需要显示表达；③不需要对空间进行预处理建模；④具有概率完备性，当采样基数无限大时，找到可行解的概率趋近 100%；⑤能够有效解决高维空间和复杂约束的运动规划问题，求解速度快。

由于RRT算法具有以上的特点，在管路路径规划中具有很大的优势，然而由于该算法具有扩展到未探索区域的趋势，如果将其直接用于管路自动布局，不仅计算效率低，且不能满足管路布局中的工程约束，因此基于RRT良好的适应性，对其采样和扩展等方面进行改进以应用于管路自动布局设计。

2.2算法初始化

为满足管路的相关约束，在进行路径求解之前，需要对相关的数据进行设定，主要包括球形刚体半径的确定、算法起始点位置的确定等。

根据可装配性约束的要求，管路的两端设计为直管段，且直管段的长度不小于管径的2.5倍。针对该约束，在确定RRT算法的起始点和终止点的位置时，将选定管接口的圆心沿接口平面外法向方向移动距离d(d的值为管路外径的2.5倍)，将移动后得到的位置点分别设为起点和终点。

此外，利用三角面片模型对规划空间中所有的物体包括刚体小球与障碍进行碰撞检测。碰撞检测模型在规划算法中作为一个黑盒来使用，在每次碰撞检测中，若检测到碰撞，则返回本次碰撞相关的信息。

2.3基于碰撞信息的节点扩展策略

文献[20]提出了一种基于边界约束的 RRT算法，该算法能够利用边界约束使随机树沿障碍物表面扩展，采用传感器检测障碍物边界，而在管路自动布局中障碍物边界需要调用大量的碰撞检测来探测，因此并不适用。本文根据文献[21]中OBRRT的节点扩展的思想，在路径搜索时利用刚性机器人与环境中的障碍物的碰撞信息构造边界约束，这些碰撞信息包括发生碰撞的碰撞点位置以及障碍物表面的外法向量，在扩展过程中基于该信息确定扩展方向，并且将障碍物表面的外法向量作为方向属性添加到当前节点中。其中，确定节点扩展方向主要有获取碰撞信息和计算扩展方向两部分。

(1) 获取碰撞信息。碰撞信息的获取主要是刚性机器人在待扩展节点位置沿着某一向量进行碰撞检测，根据检测到的碰撞获得障碍物表面的碰撞位置点xc以及该点所在表面的外法向量n。在该过程中，需要解决的问题是如何构造碰撞检测向量，使待扩展节点在其附近能够快速地检测到碰撞。其中向量的长度为定值l，其大小设为节点扩展步长ρ 的3倍(当待扩展节点为根节点时，l的大小为10 ρ)。

本文针对向量ξ的构造，依次采用如图4所示的3种方法：通过生成的随机采样点xrand构造从xnear到xrand的向量，如图4(a)所示；构造从xnear到xgoal的向量ξ，如图4(b)所示；利用父节点xpar的位置信息，构造从xpar到xnear的向量，如图4(c)所示。当任意一步构造的向量检测到碰撞时，即可获取碰撞信息。

图4　基于节点信息构造碰撞检测方向向量ξ

若上述方法无法检测到碰撞，则构造一个循环，该循环通过随机生成一个向量ξ进行碰撞检测，若检测到碰撞时，即可获取碰撞信息进行下一步扩展；若循环次数达到20，结束循环，当前节点扩展失败。

(2) 计算扩展方向。在随机树贴近障碍物表面的扩展过程中，不仅要保证节点能够快速有效地搜索到一条可行路径，而且根据路径节点生成管路走向还需要尽量与结构件表面保持平齐，基于该约束，随机树中贴近障碍物表面扩展的随机树既要能够快速找到一条连通路径，还要与障碍物之间保持稳定的距离，因此确定扩展方向是很有必要的。

在确定节点扩展方向的过程中，主要分以下2种情况进行处理：

夫妻离婚争孩子，老婆理直气壮说：“孩子从我肚子里出来的，当然归我！”老公说：“笑话！简直是胡说八道！取款机里取出来的钱能归取款机吗？还不是谁插卡归谁！”

①当待扩展节点xnear与发生碰撞的障碍物表面的距离等于d时，其中d为管路半径的1.3倍，如图5(a)所示，根据碰撞得到的障碍物表面法向量n，计算出垂直于n的向量ξn，取沿ξn方向，距离xnear长度为扩展步长ρ的坐标点为新节点xnew的位置，若从xnear到xnew之间无碰撞，则将xnew加入到随机树T中，扩展成功，否则扩展失败；

②若扩展节点xnear与障碍物表面的距离不等于d时，如图5(b)所示，根据碰撞得到的碰撞点位置xc和障碍物表面外法向n，可以计算得到垂直于 n的向量ξn，并且在xnear到障碍物表面的垂线上计算出与障碍物距离为d的点xt，取沿ξn方向，距离xt长度为扩展步长ρ的坐标点为新节点xnew的位置，若从xnear到xnew之间无碰撞，则将xnew加入到随机树T中，扩展成功，否则扩展失败。

图5　xnear与障碍物表面的距离是否等于d时扩展方向的计算

在进行扩展的过程中，根据得到的碰撞信息，可采用2种方法得到向量ξn，这2种方法能够引导随机树的节点沿障碍物表面向随机方向和终点方向扩展，2种方向分别以0.5的概率生成，既能保证随机树快速向终点方向生长，同时也具有沿障碍物表面探索其他可行路径的能力。

随机方向。如图6(a)所示，根据得到的障碍物表面法向量n，可以得到垂直于n的一个平面，在该平面内的任意一个向量都垂直于向量n，因此令该向量为ξn=(x,y,z)，则n·ξn=0，在区间(0,1)内通过均匀随机的方法得到x，y的值，进而计算出z的大小，通过单位化即可得到一个随机向量ξn。

终点方向。如图6(b)所示，利用已有的xnear、xgoal的位置信息，构造向量 ξgoal，则可以在经过垂直于向量n的平面中计算出一个与ξgoal夹角最小的单位向量ξn，从而使随机树向终点方向扩展。

图6　向量ξn的确定

具体计算方法是根据ξn与向量n、ξgoal之间的几何关系，构造式(1)所示的方程组：

解式(1)，即可计算出向量ξn的值。沿障碍物表面扩展的RRT算法伪代码如图7所示。

2.4快速绕障算法

在路径搜索过程中，由于RRT算法采用基于终点信息扩展的策略进行节点的扩展，因此当该算法在沿着障碍物表面扩展时需要绕开其他障碍物，可能会产生搜索节点过多或搜索路径沿另一障碍物表面扩展的问题，不仅影响算法的搜索效率，而且得到的路径可能无法满足管路敷设的约束要求。因此本文提出一种基于障碍物表面法向量的快速绕障算法，该方法能基于上一节点的碰撞信息进行下一节点的定向扩展，使节点能够更加快速地绕过障碍物，具体来说，当沿障碍物扩展的节点处于以下2种情况时：①节点在扩展失败时检测到碰撞，计算得到其障碍物表面法向量 nc与待扩展节点的方向属性向量n的夹角大于45°；②待扩展节点在获取碰撞信息中得到的碰撞向量与待扩展节点的方向属性向量n的夹角大于45°。将向量nc作为当前节点的第二个属性向量添加到节点中，如图8所示。

根据节点的两个属性向量确定扩展方向，进行循环扩展过程如下：

图7　沿障碍物表面扩展的RRT算法伪代码

图8　具有两个属性向量的节点

(1) 当前节点具有第二个属性向量时，根据 n 与nc的值，计算出方向向量ξe=±(n×nc)，如图9(a)所示，该向量垂直于向量n和nc，ξe取与向量ξgoal夹角为锐角的值；

(2) 节点 xnear沿 ξe方向扩展一个步长 ρ得到xnew，此时若 xnear到 xnew方向不发生碰撞，则扩展成功，否则退出循环；

(3) 在扩展得到新的节点 xnew后，如图 9(b)所示，将节点xnew作为待扩展节点，根据父节点的方向属性向量 n和 nc的反方向进行碰撞检测，若 2个方向都发生碰撞，计算得到节点xnew的2个方向属性向量n和nc，则按照上述1、2循环进行节点扩展，在循环扩展过程中，为避免节点的扩展发生反向的情况，ξe的方向还应该与父节点到待扩展节点的方向向量的夹角成锐角，否则结束循环；

(4) 当循环扩展过程中节点 xnew没有得到方向向量nc时，如图9(c)所示，则沿nc方向(或者沿–nc方向，取与ξgoal夹角为锐角的方向)扩展一个临时节点xnew2，若扩展失败，则退出循环；若扩展成功，则该节点的属性向量n与xnew的向量n相同，并在该节点通过随机生成至多k个方向进行碰撞检测，若不存在 nc，则删除节点 xnew2并结束循环，若存在，则按照上述循环继续进行节点扩展；

(5) 对于进行快速绕障算法扩展的节点，为避免在后续的节点扩展中重复利用该方法，利用快速绕障算法扩展的节点以及在这些节点一定范围内的其他节点不再调用该方法进行扩展，为保证节点的可扩展性，该节点依然可以利用原来的方法进行扩展。

快速绕障算法的伪代码如图10所示。

图9　基于障碍物表面法向量的快速绕障算法

2.5基于概率的节点扩展策略

在管路路径规划中，虽然管路是沿着结构件表面敷设，而在某些无法检测到碰撞的情况时，如管路接口处于悬臂状态、路径需跨越窄缝等，随机树需要在自由空间中进行扩展。因此针对RRT算法在路径搜索的过程中，既需要保证随机树在沿着结构件表面向目标点收敛的同时，还需要保留算法一定的发散性，并保证随机树能向自由空间扩展，因此本文采用基于概率的思想进行节点的扩展，对每个节点赋予一个概率值，针对随机树中的待扩展节点，通过在区间［0,1］内生成的一个随机数与当前节点的概率值进行比较，当该值小于或等于当前节点的扩展概率时，对该节点进行扩展，否则不扩展。

图10　快速绕障算法伪代码

本文针对2种情况对节点概率进行赋值：

(1) 若某个节点在待扩展时检测到与障碍物发生碰撞，则认为该节点位于障碍物表面附近，将其扩展概率设为1；

(2) 若某个节点在待扩展时未检测到碰撞，则认为该节点附近没有障碍物，将其扩展概率设为p(p∈[0,1])。

在管路自动布局的过程中，p的大小根据实际情况确定，当沿障碍物扩展敷设的要求不严格时，p值较大，反之较小，一般设置为0.25左右。基于概率思想的节点扩展的流程图如图11所示。

图11　基于概率的节点扩展流程

3　基于关键节点的路径优化

在采用本文算法得到的初始路径，是通过具有固定步长的树节点得到的，因此该路径对与管路来说具有较多的冗余节点，并不能直接用来生成管路模型，需要对其进行优化。在优化过程中保证管路沿结构件表面敷设的前提下，还需要保证管路长度尽量短并且弯头数应尽可能的少，因此需采用一种基于关键节点的路径优化方法。

由于在路径搜索过程中，随机树中大部分的节点都是根据障碍物表面外法向量进行扩展的，且节点中保存有相关的扩展信息，因此在管路布局中路径优化的方法是利用路径中的节点信息确定关键节点，并基于这些关键节点剔除其他的冗余节点。关键节点的判断依据包括：

(1) 路径的起点和终点；

(2) 从路径起点开始，第一个具有方向属性的节点；

(3) 快速绕障算法所生成路径的起点、终点和拐点；

(4) 从具有属性向量n的关键节点开始向后搜索，当出现属性向量与该关键节点的属性向量夹角大于 30°的节点时，说明该路径节点位置附近的障碍物表面很可能出现了较大凸凹现象，为保证路径始终处于障碍物附近，将该节点设为路径的关键节点，如图12所示的节点xk2。

根据关键节点的定义，需确定、保留路径中的关键节点，并剔除路径中的冗余点，与此同时，引入插值碰撞检测对路径进行优化。其优化过程为：从路径起点开始，将路径中不属于关键节点的路径点剔除，保留关键节点，再对每个关键节点之间进行插值碰撞检测，若两个节点之间发生碰撞，则在原路径的基础上对后一关键节点进行回溯碰撞检测，如图13所示，节点1到10为原路径中的节点，其中关键节点为1、10，由于两个关键节点之间发生碰撞，因此先在节点 1、9之间进行插值碰撞检测，若仍然发生碰撞，继续在 1、8之间进行插值碰撞检测，直到节点7未发生碰撞时，将该节点保存下来，然后以节点7为起点，继续按照上述方法进行优化。

图12　拐角位置关键节点的判断

在管路布局中，为保证敷设管路的可加工性，还需要对路径节点的弯曲角度进行局部优化处理，如图14所示：根据与控制点1相连的两个控制点2、3得到两个单位向量V12、V13，当其夹角α小于90°时，则计算出α角平分线的单位向量V1，将控制点1沿V1方向以一定的步长λ逐步平移，直到弯曲角度大于90°。

图13　引入碰撞检测的节点优化过程

图14　弯曲角度的调整

图15为路径节点优化示意图，图15(a)所示路径为根据改进RRT算法得到的初始路径点，xinit与xgoal分别为路径的起点和终点，经过优化后得到的最终路径如图15(b)所示。

图15　路径节点优化示意图

4　实例验证

利用三维造型引擎ACIS和三维显示交互工具包HOOPS，自主设计并开发了管路自动布局系统，该系统在Microsoft Visual Studio2005上利用C++语言开发，开发硬件为HP Z400图形工作站，CPU为2.67 GHz Intel Xeon W3520，内存4 G (3.48 G可用)，显卡为 Nvidia Quadro 5000，操作系统为Windows 7专业版。

为了验证算法的计算效率与布局质量，对提出改进的RRT算法进行了测试，测试结果与双树扩展中3种经典的算法RRT-ExtExt、RRT-ConCon以及RRT-ExtCon进行了对比，测试结果如图16所示；计算结果如表1所示。通过综合对比可以看出，改进的RRT算法在保证搜索成功率的同时，能够在较短的时间内搜索出符合管路约束的路径。

为验证该算法沿结构件表面敷设的效果，在如图 17所示模型(管路接口已隐藏)中的凹形区域进行实例测试，求解得到的双树节点如图17(a)所示，其中红色高亮节点为得到的初始路径点，生成的实体管路模型如图17(b)所示。

图16　测试对比实例

图17　管路沿结构件表面布局效果

表1　算法测试结果

运用提出的改进 RRT算法进行管路自动布局设计，在自主开发的管路布局系统上对某产品进行了验证，根据选定的接口位置信息自动求解出管路路径，并生成实体管路模型，如图18所示。

图18　某产品管路自动布局结果

5　结论及展望

(1) 本文提出了一种基于障碍物碰撞检测的RRT算法，其主要针对节点的扩展、绕开障碍物以及随机树的生长趋势3个方面进行改进，并采用基于关键节点的路径优化方法对求解到的路径进行了优化，在较短的时间内搜索出了符合限定约束条件下的管路路径，有效地解决复杂结构条件下的沿结构件表面的管路自动布局问题。

(2) 在算法中利用快速绕障算法，避免了障碍物表面生成过多的冗余节点，提高了算法的搜索效率。

(3) 该算法能够得到较好的布局方案，但是由于管路布局的复杂性，并没有全面考虑工程约束，这些都需要在以后的工作中进一步探索。

[1] Sandurkar S, Chen W. GAPRUS—genetic algorithms based pipe routing using tessellated objects [J]. Computers in Industry, 1999, 38(3): 209-223.

[2] Rourke P W. Development of a three-dimensional pipe routing algorithm [D]. Benthlehem: Lehigh University, 1975.

[3] Ito T. A genetic algorithm approach to piping route path planning [J]. Journal of Intelligent Manufacturing, 1999, 10(1): 103-114.

[4] Ito T. Piping layout wizard: basic concepts and its potential for pipe route planning [M]. Methodology and Tools in Knowledge-Based Systems. Springer Berlin Heidelberg, 1998: 438-447.

[5] Park J H, Storch R L. Pipe-routing algorithm development: case study of a ship engine room design [J]. Expert Systems with Applications, 2002, 23(3): 299-309.

[6] 樊江, 马枚, 杨晓光. 航空发动机外部管路自动敷设研究[J]. 机械设计, 2003, 20(7): 21-23.

[7] 樊江, 马枚, 杨晓光. 基于协进化的管路系统智能寻径[J]. 航空动力学报, 2004, 19(5): 593-597.

[8] 王成恩, 柳强, 白晓兰, 等. 航空发动机复杂约束空间内管路敷设技术[J]. 计算机集成制造系统, 2010, 16(11): 327-332.

[9] 范小宁. 船舶管路布局优化方法及应用研究[D]. 大连:大连理工大学, 2006.

[10] 曲艳峰, 蒋丹. 基于八叉树建模和ACA的三维管路路径规划[J]. 计算机工程, 2011, 37(23): 4-7.

[11] Qu Y F, Jiang D, Liu B. A multi-pipe path planning by modified ant colony optimization [J]. Computer Aided Drafting, Design and Manufacturing, 2011, 21(1): 1-7.

[12] LaValle S M, Kuffner J J. Randomized kinodynamic planning [J]. The International Journal of Robotics Research, 2001, 20(5): 378-400.

[13] Kuffner J J, LaValle S M. RRT-connect: an efficient approach to single-query path planning [C]//Robotics and Automation, 2000. Proceedings. ICRA’00. IEEE International Conference on. IEEE, 2000: 995-1001.

[14] Kalisiak M, van de Panne M. RRT-blossom: RRT with a local flood-fill behavior [C]//International Conference on Robotics & Automation. IEEE, 2006: 1237-1242.

[15] Zucker M, Kuffner J, Branicky M. Multipartite RRTs for rapid replanning in dynamic environments [C]//Robotics and Automation, 2007 IEEE International Conference on. IEEE, 2007: 1603-1609.

[16] 贾菁辉. 移动机器人的路径规划与安全导航[D]. 大连:大连理工大学, 2009.

[17] 刘伟, 郑征, 蔡开元, 等. 快速平滑收敛策略下基于QS-RRT的UAV运动规划[J]. 中国科学: 信息科学, 2012, 42(11): 1403-1422.

[18] 杨宇盟, 聂斌, 方红根, 等. 虚拟人手臂避障抓取运动规划[J]. 计算机辅助设计与图形学学报, 2014, 26(8): 1362-1373.

[19] LaValle S M. Rapidly-exploring random trees a new tool for path planning [R]. Technical Report No. 98-11. 1998.

[20] 吕伟新, 赵立军, 王珂, 等. 基于边界约束RRT的未知环境探索方法[J]. 华中科技大学学报: 自然科学版, 2011, 39(S2): 366-369.

[21] Rodriguez S, Tang X, Lien J M, et al. An obstacle-based rapidly-exploring random tree [C]//Robotics and Automation, ICRA 2006. Proceedings 2006 IEEE International Conference on. IEEE, 2006: 895-900.

A Method for Pipe Auto Layout Based Improved RRT Algorithm

Xu Lianjie,Liu Jianhua,He Yongxi,Wu Hongchao,Liu Jiashun

(School of Mechanical Engineering, Beijing Institute of Technology, Beijing 100081, China)

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.

pipe; rapidly-exploring random tree; collision detection; fast bypassing obstacle algorithm; key nodes

TP 391.9

10.11996/JG.j.2095-302X.2016010001

A

2095-302X(2016)01-0001-10

2015-09-24；定稿日期：2015-10-09

国家自然科学基金项目(51275047)；“十二五”国防基础科研项目(A2220110008)

徐联杰(1990–)，男，湖南常德人，硕士研究生。主要研究方向为管路自动布局技术。E-mail：xulianjie1234@163.com

刘检华(1977–)，男，江西萍乡人，教授，博士，博士生导师。主要研究方向为数字化装配与检测。E-mail：jeffliu@bit.edu.cn