基于改进蚁群算法的线缆路径规划技术研究

吴保胜，郭 宇，王发麟，宋 倩

南京航空航天大学 机电学院，南京 210016

1 引言

随着以航空、航天、船舶、电子、兵工等大型电气系统的飞速发展，现代电气系统日益复杂化、集成化。大量的电气设备密集于系统平台上，用于各设备和部件连接的线缆所传送的信号越来越多，频率越来越高，消耗的功率也越来越大，对线缆的敷设提出了更高的要求和挑战。线缆敷设路径规划是一类特殊的带性能约束的布局问题，其中待定参数多、可行空间复杂，线缆的布局合理性和装配质量直接关系到产品最终的整机性能和可靠性[1-2]。美国通用电器公司分析归纳飞机发动机发生故障的原因，其中因为线缆管路损坏或失效而产生故障的比例达到了50%[3]。传统的线缆模装试验方法需要大量的人工干预，大大影响了线缆装配的效率。虚拟环境下的线缆布线设计的出现，能够实现线缆自动避障，生成满足工程规则的布线路径，为解决线缆装配的布线不合理、效率低下等问题提供了一条有效的解决途径[4]。

线缆自动敷设的核心是路径搜索算法。使用智能算法完成线缆路径的自动求解具有效率高等特点，是当前的研究热点。国内外的学者对此进行了相关的研究，如Park等[5]在1992年提出了基于Agent的线缆二维设计方法。CONRU等[6]将并行工程的方法应用到线缆的自动布局设计中，并使用遗传算法进行全局最优路径的搜索。ILKNUR等[7]针对复杂环境下线缆的布局问题，提出了一种布线路径的搜索算法，该算法进行约束采样，然后利用随机路径图法计算出初始路径，再采用动力学法对布线路径进行优化，取得了良好的计算效果。韩明晶[8]将A*算法应用到电子制造装备的三维路径搜索中，开发了基于UG的布线模块。白晓兰等[9]提出了基于工程规则和离散空间的航空发动机管路布局方法。蔡毅等[10]提出了“按面自动布线”和“贴壁干涉自动调整”的方法，但由于布线路径多、路径空间交汇复杂等原因，结果仍存在干涉、算法耗时较高等问题。王成恩等[11]提出了一种基于计算几何、微分几何和智能优化等思想，实现了对管系的敷设顺序与管路路径的自动求解，取得了较好的效果。徐联杰等[12]提出了一种基于障碍物碰撞检测的RRT算法，利用基于碰撞信息进行节点扩展策略和快速绕障，有效解决了复杂结构条件下沿结构件表面的管路自动布局问题。吴宏超等[13]提出了一种基于改进A*算法的管路自动布局方法，将工程规则作为约束条件，分别添加在路径搜索和路径优化两个阶段，能较快地获得一条满足工程约束的路径，但是仍未考虑管路之间的相互影响。

近年来，蚁群优化算法（Ant Colony Optimization，ACO）作为一种启发式搜索算法，具有较强的鲁棒性，在路径搜索问题方面获得了大量的应用。但基本蚁群算法在三维环境下进行路径搜索时路径点容易出现发散现象，为解决该问题，本文提出了一种改进的蚁群算法来完成线缆的路径规划，通过引入重力规则来对路径点进行约束，让线缆路径点满足贴壁规则，然后在抽象化的求解空间里，运用改进的蚁群算法进行路径搜索，从而规划出一条合理的布线路径。为了对本文算法进行测试和验证，通过实例模型和实验作了仿真分析。

2 问题描述

布线路径的求解是线缆布线问题的核心，即在三维环境中求解出一条连接起始点和终点，并满足布线规范的通路。线缆的路径求解也可以看作碰撞球干涉检测问题，即在三维环境中，以路径离散点为球心，线缆直径为球直径，进行碰撞球干涉检测。如果碰撞球在沿路径进行扫掠时，不与环境中的障碍物发生干涉或碰撞，那么这条路径是安全可靠的。为获取布线空间的环境信息，首先需要对布线空间进行环境建模，建立障碍物和路径点的抽象模型；为解决基本蚁群算法在三维环境下进行路径搜索时路径点的发散性，引入重力规则来对路径点进行约束，让线缆路径点满足贴壁规则，然后在抽象化的求解空间里，运用改进的蚁群算法进行路径搜索，从而规划出一条合理的布线路径。图1给出了基于改进蚁群算法的线缆路径规划技术总体思路。

图1 基于改进蚁群算法的线缆路径规划技术总体思路

3 布线空间环境建模

3.1 分段式空间划分

在复杂机电产品中，由于结构件的种类繁多，大小形状不一，使得布线空间不规则，因此需要对布线环境进行三维空间环境建模。首先对布线空间进行网格化，将三维空间抽象为包含几何模型空间位置信息的节点，这样可以更有效地描述线路可能经过的空间点。需要指出的是，如果对整个布线空间进行栅格化，当空间模型较大时，将会占用较大的计算存储空间，从而降低计算效率。因此，为提高算法效率，先对布线空间进行分段式划分，然后再对特定的空间区域进行栅格化，而不是对整个空间进行栅格划分。

将布线空间划分为若干个子空间的并集：A=A1⋃A2⋃A3⋃…,其中A表示整个布线空间，Ai(i=1,2,3…)为划分出的各个子空间，如图2所示。当Ai为线缆布线的固定路径段时（如线缆的固定卡槽等），线缆经过这段区域将具有直接连通性，在进行路径搜索时可以跳过该区域。A3作为集线器，当线缆经过该结构时，该路径段可以看作入口端T1和出口端T2的直接连通，在求解S1S2之间的布线路径时，无需在此路径段作过多的算法耗费。这样S1S2之间的路径搜索可以简化为S1T1与S2T2两段的布线路径搜索，A1⋃A2便是本文算法的求解空间。通过对求解空间进行栅格化划分将大大节约算法的存储空间。

图2 布线空间的分段式划分示意图

3.2 布线空间栅格化

本文采用文献[14]提出的空间等分网格法。如图3所示，首先从产品结构模型中抽象出三维空间模型，将左下角的顶点作为三维空间的坐标原点A，在点A中建立三维坐标系A-xyz。在该坐标系中以A为顶点，沿x轴方向取产品三维结构模型的最大长度AB，沿y轴方向取产品三维结构模型的最大长度AA′，沿z轴方向取产品三维结构模型的最大长度AD，由此构造包含产品三维结构模型的立方体区域ABCD-A′B′C′D′，该区域即为三维布线路径的规划空间，如图3（a）所示。为得到抽象环境模型，需在上述规划空间ABCDA′B′C′D′的基础上进行等分操作：沿边 AB 进行 n 等分，得到n+1个平面Πi(i=0,1,2,…,n)，然后对这n+1个平面沿边AD进行m等分，沿边AA′进行l等分，并且求解出里面的交点，平面划分如图3（b）所示。

图3 三维空间环境建模过程

4 基于改进蚁群算法的线缆路径规划

4.1 基本蚁群算法

蚁群算法是由Dorigo提出的一种群体智能算法，描述了蚂蚁在蚁巢和食物之间寻找出最短路径的合作行为，蚂蚁之间通过信息素的浓度来选择行驶路径，该算法具有较强的鲁棒性、优良的分布式计算机制、易与其他方法结合等优点[15]。

蚂蚁的移动方向是根据各条路径上信息素的量来决定的，同时根据信息素的量和启发信息来计算状态转移概率。位于节点i的蚂蚁通过公式（1）给出的规则选择下一个将要移动到的节点 j：

其中S根据公式（2）得到：

其中q是在[0,1]区间均匀分布的随机数；q0的大小决定了利用先验知识与探索新路径之间的相对重要性；i、j分别是某一段路径的起点和终点；ηij=1/dij为能见度，是两节点i和 j路径距离的倒数；τij(t)为时间t时由i到 j的信息素强度；allowedk为尚未访问过的节点集合；α,β为两常数，分别表示信息素和能见度的加权值。上述状态转移规则被称为伪随机比例规则。每只蚂蚁在走完一步或者到达目标点之后需要对信息素进行更新，路径( )i,j上信息素按式（3）和（4）进行更新：

其中0＜ρ≤1为信息素的蒸发率，Δτij为第k只蚂蚁在路径i到 j所留下来的信息素。

4.2 线缆路径规划

线缆作为具有一定质量的实体，在实际敷设中，线缆的敷设路径不可能出现没有附着面的悬空现象。线缆的敷设一般需要依附于一定的实体表面，即有种“重力趋势”贴近物体表面。如图4所示，（1）路径中出现悬空的路径段，路径规划不合理；（2）路径考虑线缆自重，敷设路径全程依附于物体表面，符合实际规范，为优质解。故在三维环境中定义重力吸引规则（gravity attraction rule），让线缆路径规划时的空间姿态更满足实际情况。

图4 重力规则示意图

在对线缆或者管路自动敷设路径求解时，通常的研究方法是先用智能算法求解出线缆起始点至终点的通径，然后将“贴壁”等诸多规则作为路径优化的约束条件，以达到敷设线缆实际敷设规范的走线路径，而本文是在研究线缆实际敷设时的空间姿态基础上，将“贴壁”以重力约束的形式，直接融合到蚁群算法中，而非将其作为约束条件再对走线路径进行二次优化。

将蚂蚁看作有“质量”的实体，则其运动轨迹必须依附于一定的物体表面或者在地面活动，在选择路径点时不仅需要考虑避障，还需考虑路径点的实际位置。根据重力场的概念：其中，mant表示蚂蚁的质量，m0表示网格点的质量，r表示蚂蚁与可视域内网格点的距离，k、f表示引力系数。

定义障碍物表面与地面的重力场值为：

将每个网格点看作单位质量的点，则m0=1；将蚂蚁看作单位质量的蚂蚁，则mant=1；当网格点位于障碍物表面时，为了防止出现分母为0的情况，故在分母中加1；则重力可看作为：

引力随着距离的变化呈现抛物线式的变化，随着越来越靠近目标物体，则引力急剧增加，所以引力场也可以表示为：

其中q=(i , j,k)表示任意路径点的位置，dobs&gro为当前节点垂直方向上距离最近障碍物或地面的距离，且有：

在建立布线空间的抽象化模型时，对障碍物进行了“膨化”处理，蚂蚁在障碍物表面进行路径搜索时，布线路径与障碍物不会发生干涉。G的值按以下情况确定：

（1）当蚂蚁在障碍物表面或者地表上运动时，G=0；

（2）当蚂蚁在自由位置点时，G=∞。

蚂蚁朝目标点运动，也可看作是一种趋向性运动，故定义目标点的引力场为：

其中ddes=‖q- qdes‖,qdes代表目标点，ddes即当前点到目标点的欧氏距离。重力场的吸引可以表示为：

4.2.1 搜索策略

如图5所示，若当前点为 pnow(i , j,k)，而平面α为蚂蚁搜索下一路径点的所在平面，则可供选择的下一路径点的集合为：

图5 允许列表示意图

根据每个网格节点的信息，选取安全的节点写入允许列表allowed中。

在改进的蚁群算法中，第k只蚂蚁从节点i转移到下一路径点 j的选择概率为：

传统的蚁群算法的启发信息ηij为该节点到目标点距离的倒数，距离目标点越近ηij的值越大。而使用G(q)不仅使路径点的选择更倾向于地表或障碍物表面，而且还能加强算法在获取最优解时的收敛性。

4.2.2 信息素的表示及更新策略

布线求解空间是由网格节点表征的，这些网格节点即为蚁群算法进行路径搜索的路径点。如果将各个离散点间的连接线段作为信息素的连接载体，则会大大增加算法的空间复杂度。为避免这种情况，本文使用节点表示法：将信息素储存在环境模型的离散点上，任意点对应一个信息素值，而信息素量的大小代表了该离散点对蚂蚁的吸引程度。这种信息素的表示方法将大大降低算法的空间复杂度[16]。信息素的更新采用局部更新和全局更新相结合的更新规则。当蚂蚁选定下一个路径点(i , j,k)时，按公式（15）立即更新该路径点上的信息素值：

其中，0＜ε＜1，ε为一常数。τ0为原始信息素值。

当一次迭代完成，找出本次迭代所得出的最优路径后，对该路径进行信息素更新：

lbest为最优路径的长度值。

5 算法测试与仿真

测试时基于如下运行环境：Intel Core i7-3770，3.40 GHz处理器；内存为4 GB；操作系统为Win7；仿真软件为MATLAB R2012b。

实验1对本文所提出的重力吸引规则进行仿真实验，并和没有使用该规则的蚁群算法进行了对比，以验证该方法的有效性和实用性。

建立两障碍物的空间模型，中心坐标分别为（40，420，75）和（450，40，40）；两障碍物的长宽高分别为（80，80，150）和（100，80，80）。起始点和终点的位置分别为（0，425，150）和（500，0，80）。表1给出了本次实验中所使用蚁群算法的主要参数。

表1 参数设置

图6 实验1仿真结果

从图6的仿真结果中可以看出，将基本蚁群算法直接应用到三维空间的线缆敷设时，虽然能搜索出一条连接起始点且不与障碍物发生干涉的布线路径，但是路径点大多处于自由状态，这不符合实际布线的规范和标准。而结合重力规则的蚁群算法所搜索出的路径始终依附于固定面，布线路径更加符合线缆敷设的实际规范，路径规划效果较好。

实验2对本文所给出的算法进行仿真。建立障碍物的包围盒模型，中心位置和长宽高分别如表2所示，其他参数设置参照实验1中的数据。

表2 障碍物模型参数

图7（a）、（b）分别从主视图和俯视图展示了实验2仿真的结果；图7（c）为算法所对应的适应度变化曲线图。从图7中可以看出，在多障碍物的环境模型下，改进蚁群算法能较快地搜索出一条安全、合理的布线路径。三维环境下重力规则的应用，使得整个布线路径都依附于一定的平面，进一步验证了改进算法的优越性。

蚁群算法作为群体智能算法，在路径点的选取中采用可视域内的启发式搜索，求解出的不一定是全局最优路径，但却是符合线缆实际规范的可行解。线缆的自动敷设设计主要是为线缆的实际敷设提供一个可行、优化的敷设方案，即在特定的应用环境或者工作条件下使线缆满足敷设的约束条件，最短路径不一定就是最优路径。在图7（b）中绿色虚线表示连接S、T之间的理论最优路径，虽然满足最短路径，但是横跨空间模型的路线，占据了很大的空间，而且在线缆的实际敷设过程中也不方便固定，而采用改进算法求解出的图中红色路径虽然牺牲了线缆长度，但更满足贴壁的约束规范，有利于卡箍的装配和线缆的固定等操作。本文算法求解得出的路径并不是直接作为线缆的实际敷设的最终路径，还应对路径点进行选取，使线缆达到平滑顺直的空间布局姿态。图7（d）所示的电器柜模型中线缆实际走线路径图，红色线缆所表示的路径2虽然达到了路径最短，但是多数路径点处于悬空位置，并不符合线缆的空间物理姿态，而且空间占据大，不便于设备的维护操作。蓝色线缆所表示的路径1虽然长度较长，但是走线依附于机柜壁板，这样有利于后续卡箍等紧固件的安装，路径1的走线方式相比较之下更为合理。

6 结束语

（1）本文针对线缆敷设问题，提出了一种基于改进蚁群算法的线缆路径规划方法，通过在算法中引入重力规则，能够较好地完成线缆路径的搜索；对所提出的方法进行了仿真验证，取得了良好的效果。

图7 实验2仿真结果

（2）三维空间的网格化建模，存在模型的计算量和存储量较大的缺点。网格的划分越细则空间的抽象化表示越精确，但数据量也会随之急剧增大。如何权衡考虑空间精确化和数据量之间的矛盾，是下一步将要进行的研究工作。

（3）本文所给出的算法并未考虑到线缆的机械性能和电气性能，如何考虑多约束条件下的线缆三维路径规划技术也是下一步要研究的内容。

：

[1]宁汝新，刘检华，唐承统，等.虚拟装配技术及其应用[J].国防制造技术，2009，4（2）：22-29.

[2]尚炜，宁汝新，刘检华，等.复杂机电产品中的柔性线缆装配过程仿真技术[J].计算机辅助设计与图形学学报，2012，24（6）：822-831.

[3]孔瑞莲.航空发动机可靠性工程[M].北京：航空工业出版社，2006.

[4]王发麟，廖文和，郭宇，等.线缆虚拟装配关键技术研究现状及其发展[J].中国机械工程，2016，27（6）：839-851.

[5]Park H，Lee H，Cutkosky M R.Computational support for concurrent engineering of cable harness[C]//Proceedings of the International Computers in Engineering Conference and Exhibit，San Francisco，USA，1992：261-268.

[6]Conru A B.A genetic approach to the cable harness routing problem[C]//Proceedings of the IEEE Conference on Evolutionary Computation，Orlando，USA，1994：200-205.

[7]Ilknur K，Russell G，Ming C，et al.Cable route planning in complex environments using constrained sampling[C]//Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling，2007：395-402.

[8]韩明晶.基于A*算法的电子制造装备布线研究[D].武汉：华中科技大学，2009.

[9]白晓兰，张禹.航空发动机管路智能布局[J].机械设计与制造，2013（9）：56-59.

[10]蔡毅，王彦伟，黄正东.基于UG的三维电气自动布线技术研究[J].计算机工程与应用，2012，48（8）：68-72.

[11]王成恩，柳强，白晓兰，等.航空发动机复杂约束空间内管路敷设技术[J].计算机集成制造系统，2010，16（11）：2327-2332.

[12]徐联杰，刘检华，何永熹，等.一种基于改进快速搜索随机树算法的管路自动布局方法[J].图学学报，2016，37（1）：1-10.

[13]吴宏超，刘检华，唐承统，等.基于改进A*算法的管路自动布局设计与优化方法[J].计算机集成制造系统，2016，22（4）：945-954.

[14]胡小兵，黄席樾.基于蚁群算法的三维空间机器人路径规划[J].重庆大学学报：自然科学版，2004，27（8）：132-135.

[15]Dorigo M，Gambardella L M.Ant colonies for the traveling salesman problem[J].BioSystems，1997，43（2）：73-81.

[16]刘利强，于飞，戴运桃.基于蚁群算法的水下潜器三维空间路径规划[J].系统仿真学报，2008，20（14）：3712-3716.