面向改进RRT算法的回转空间布线技术研究

李春泉，陈雅琼，黄红艳，郝子宁

（桂林电子科技大学机电工程学院，广西 桂林 541004）

1 引言

线缆是机电设备中不可缺少的重要组成部分，是实现设备之间连接，传输电力和信息的最主要途径，在航天航空、船舶制造、家电产品制造中都具有广泛的应用。合理的线缆布局可以提升产品性能并且缩短研发成本和周期[1]。随着我国现代制造技术的不断提升，尤其是近年来航空航天事业的发展，出现了越来越多的回转体电气设备，由于回转体设备表面曲率变化过大、设备多而复杂，这些问题给布线人员进行线缆布局设计带来了很大的挑战。

自动布线技术[2]是指通过计算机解析接线关系，利用搜索算法、优化算法自动求解出虚拟环境中合理的布线路径，能够有效解决人工布线不合理、效率低下等问题。早在1992年，文献[3]开发了应用于飞机模型上的布线系统，但该系统主要针对二维平面进行设计。文献[4]提出了使用改进的随机路径图算法（Probabilistic Road Maps，PRM）来求解复杂环境中线缆路径问题，并取得了良好的效果。文献[5]针对飞机机舱内部曲面布线，提出基于知识工程（Knowledge Based Engineering）（KBE）和优化线束夹紧点位置的布线方法，通过两步混合优化策略，能够在复杂环境下得到满足设计约束的布线路径。文献[6]针对航空发动机曲面空间布管，采用一种适应度函数和基于三维连接图约束建模的空间处理方法，提出了MMAS-RBPR算法获得管线路径。文献[7]对二维粒子群算法进行改进，使该算法能够完成三维环境路线搜索。蔡毅等以贴壁敷设和布线面干涉检查作为布线研究内容，进行布线系统开发，该系统能够实现布线路径的干涉检测、线缆路径调整和优化等功能。文献[8]针对线缆布线时的贴壁问题，提出了一种障碍物吸引扩展的策略，依据障碍物上的关键节点，将搜索出的线缆路径点向障碍物吸引，并采用二等分式的方法进行贴壁优化，得到满足贴壁约束的线缆路径。

近年来，快速搜索随机树（RRT）算法[9]作为一种基于采样路径搜索算法，无需对空间进行网格划分处理，通过对状态空间中的采样点进行碰撞检测，能够有效地解决高维空间和复杂约束的路径规划问题，在路径搜索方面得到广泛应用。但原始RRT算法中节点采样和扩展具有较大的随机性，且在曲面扩展时易产生干涉，算法效率不高。因此通过结合回转空间布线特点，提出一种改进的RRT算法，使其能够搜索出合理的线缆路径，并通过实例对该算法的合理性和有效性进行验证。

2 回转空间处理

2.1 布线空间建模

针对回转空间特点，为了便于求解线缆路径，首先在三维坐标基础上建立柱坐标系，在柱坐标系下进行布线空间建模。图中：O—柱坐标系的圆点，位于回转体轴线与底部平面的交点处。Z轴与回转体轴线相重合，图中点P的坐标为（r1，θ1，z1）；K—障碍物。如图1所示。

图1 回转柱坐标建立Fig.1 Establishment of Coordinate of Revolving Column

2.2 布线空间划分

在进行线缆路径规划时，通常回转空间中接线端子只在一个较小的局部空间内，当布线空间较大时，会使得路径搜索时向不必要的空间进行探索，增加了整体路径长度，降低了算法的搜索效率，因此根据回转空间中接线端子的位置进行了布线空间划分，减少不必要的布线区域。将包含所有接线端子的最小布线区域作为布线空间。P（ii=1，2，3）为一条线缆组件上的三个接线端子，其柱坐标信息为（ri，θi，zi)，K表示回转表面的障碍物，如图2所示。该线缆组件上的端子只位于一个小范围的布线空间内，因此可以依据端子Pi的位置对该回转空间进行划分。则包含所有端子的布线空间V（图2虚线区域空间）可表示如下：

图2 布线空间划分Fig.2 Wiring Space Partition

式中：（fz）—在θ=0处的回转体表面的母线方程；g（z）—在θ=0处的最外层障碍物K的母线方程；zmin—Pi在z轴上的最小值；zmax—Pi在z轴上的最大值；θmin—组成扇形区域的最小值；θmax—组成扇形区域的最大值。

3 基于改进RRT算法的回转空间线缆路径规划

3.1 基本RRT算法

RRT算法是由美国伊利诺伊大学LaValle提出的，在高维环境中具有较好的搜索效率，广泛应用于机器人路径寻找等方面。其基本思想是构建一个搜索树，通过节点扩展来延伸搜索树的枝干，如图3所示。

其基本流程如下：

（1）定义搜索空间R，设置起点qstart和终点qend，如图3中矩形节点所示。

图3 搜索树扩展示意图Fig.3 Schematic Diagram of Search Tree Expansion

（2）初始化搜索树T，T=∅。将起点qstart设入树T中作为根节点。

（3）通过随机采样得到随机点qrand，qrand∈R。

（4）遍历树T中的所有节点，找到与qrand距离最近的节点qnear。

（5）沿qrand到qnear方向，从qrand扩展一个距离为搜索步长λ的点，记为qnew。

（6）判断qnew到qnear之间是否产生干涉，若干涉则返回（3），进行下次循环；若不干涉，则继续执行下一步。

（7）将节点qnew加入树T中，判断qnew是否足够接近终点qend，若接近则将终点qend加入树T中，否则返回（3），进入下次循环。

3.2 回转空间线缆路径规划

由RRT算法的原理可知，其节点采样和扩展方向都具有较强随机性，因此在进行线缆路径搜索时无法保证线缆沿回转体表面进行扩展。同时考虑到回转体布线整体的美观性，线缆应尽量沿回转体表面周向和轴向敷设，而原始RRT算法无法满足该约束。针对回转体表面曲率变化过大和原始RRT算法在线缆路径搜索中存在的问题，提出了对算法的采样和扩展策略的改进方法。

3.2.1轴向约束角度采样策略

在回转空间环境中，当线缆数量较多时，会使得回转表面线缆布局紊乱，因此考虑到线缆安装和整体布局的美观，线缆应尽量沿着回转体表面进行周向和轴向敷设，同时周向扩展时，回转体表面曲率不变，无需进行大量的干涉检查，因此为避免节点“斜跨”表面扩展过大，引入了轴向约束角度∂（0≤∂≤60o）来限制采样点的范围，∂的取值与扩展点在r轴的值有关，即r值越大，轴向约束角度∂的取值越小。具体方法如下：

随机获得采样点qrand，遍历树T中的节点q，找出与采样点qrand最近的qnear，若qrand与qnear在θ轴之间的夹角θcir＞∂，为防止节点过多的“斜跨”表面扩展，将采样点近似看成沿周向扩展，如图4所示。qnear为qrand最近的扩展点，如图4（a）所示。在二维极坐标中qrand与qnear之间的夹角θcir，如图4（b）所示。当θcir＞∂时，舍去原来的采样点qrand，并将节点qnear周向的矩形节点作为采样点，进行扩展。

图4 基于轴向约束角度采样策略Fig.4 Angle Sample Strategy Based on Axial Constraint

3.2.2 动态步长扩展策略

当采样点qrand与节点qnear在θ轴之间的夹角θcir＜∂时，节点趋于轴向扩展，节点沿某回转体表面轴向扩展示意图，如图5所示。

图5 轴向扩展示意图Fig.5 Schematic Diagram of Axial Expansion

当节点位于L1段时，回转体表面曲率基本无变化，节点q以扩展步长λ扩展，保持沿回转体表面进行扩展且不与表面产生干涉。当节点继续扩展到L2段时，与回转体表面产生干涉，图5中三角点所示。说明此处回转体表面曲率变化较大。为了进一步提高算法的效率，提出动态步长扩展策略。若节点沿轴向扩展5个步长成功，则该处表面可能曲率变化不大或不存在障碍物（如L1），下次扩展增大扩展步长，加快扩展速度。动态扩展步长λi，如式（2）所示。

式中：λi—第i次动态扩展步长数；λ—扩展步长数。

且1≤i≤5，即动态步长λi不得大于5个λ扩展步长数。

在回转体表面沿轴向采用动态步长扩展节点q的情况，如图6所示。虽然不与回转体表面产生干涉，但是该表面处曲率也发生了较大变化，使得线缆产生“悬空”现象，因此在采用动态步长扩展时，引入距离DS来判断扩展的节点与所在表面的距离。即每次以λi扩展一个步长后，判断DS是否满足最大距离约束，当扩展节点与该点所在表面距离大于规定的最小值时，则应该减小动态扩展步长的距离，动态扩展步长λi为可表示如下：

式中：d—单根线缆的最大直径；DS—扩展节点与所在表面的距离。

当扩展的节点到所在表面的距离Ds≥2.5d时，该处斜率发生较大变化，这次扩展的节点不加入树T中，如图6中矩形节点所示，并且下次扩展步长为λ。

图6 线缆沿轴向悬空Fig.6 Cable Suspended in Axial Direction

通过动态步长扩展策略可以知道当扩展节点q扩展时与表面产生干涉或Ds≥2.5d时，在该处回转体表面曲率变化较大，针对曲率变化较大处的节点扩展采用基于障碍物碰撞片面法矢量方向的扩展策略［10（］Obs-Nor RRT Extend）进行扩展。

3.2.3 分支线缆路径搜索

针对分支线缆路径，采用顺序敷设的方法，具体步骤如下：（1）读取在z轴上的分别为zmin和zmax的两个端子为起始点进行路径搜索，并作为主干路径。（2）获得另一个端子的位置信息并作为起点，从主干路径中计算出离该端子周向最近的节点（已布局端子除外），使该节点作为终点（分支点），进行路径搜索。（3）重复上述步骤直到所有端子路径搜索完毕。

4 实例研究

为了验证上述改进算法的效率以及可行性，对算法进行算例测试，测试的计算机硬件环境为：3.40GHz酷睿i3-4130，内存为8GB，显卡为英伟达GT630，如图7所示。

图7 算法测试环境示意图Fig.7 Schematic Diagram of Algorithm Test Environment

在无障碍环境下进行测试并与原始RRT算法、Obs-Nor RRT算法求解结果进行比较，如图7（a）所示。在有障碍物和分支线缆环境下进行算法测试，如图7（b）所示。运行50次后的测试结果，如表1所示。由测试结果可知，提出的改进算法趋于周向和轴向扩展，因此在无障碍环境下，搜索效率较低于Obs-Nor RRT算法，且算法稳定性相差不大，整体搜索时间和路径长度均优于原始RRT算法。而在具有较多障碍物的和分支线缆路径的复杂环境下，改进后的RRT算法由于采用动态步长的扩展策略，相比较其他两种算法，其搜索效率更高，且算法的稳定性更好。

表1 不同布线环境线缆路径搜索测试Tab.1 Cable Path Search Test in Different Wiring Environment

5 结论

对回转空间的线缆敷设问题进行研究，提出了一种面向改进RRT算法的线缆路径规划方法，为避免节点“斜跨”表面敷设过大，采用轴向约束角度采样策略，保证了线缆沿回转体表面的周向和轴向扩展性；节点沿轴向扩展时采用动态步长扩展策略。经过测试比较，在无障碍的环境下，改进后的RRT算法整体搜索效率、稳定性和路径长度均优于原始RRT算法，但其搜索效率比Obs-Nor RRT算法低；在具有较多障碍物的和分支线缆路径的复杂环境下，改进后的RRT算法在保证线缆贴壁敷设的同时，比原始RRT算法和Obs-Nor RRT算法搜索效率更高，并且稳定性也更好。通过实例研究和算法进行对比，证明了该方法的可行性和高效性。