基于改进A*算法的线缆路径规划方法

姜 康 马世纪

合肥工业大学汽车与交通工程学院，合肥，230009

0 引言

电缆的布置和安装是机电产品开发设计过程中经常遇到的问题，随着机电产品愈加精细复杂，机电产品的性能和可靠性也越来越多地受到线缆布置装配的影响[1]，传统的布线方式已经不适用于复杂的线缆布局设计，因此，使用人工智能算法进行线缆布线规划成为国内外研究的热点。

人工智能布线能够避免传统布线方式的弊端，高效合理地在布线空间中找到一个最优的路径，并使其走向合理、长度最短、固定可靠、检测方便[2]。PARK等[3]、CONRU等[4]利用遗传算法研究了线缆的布置；付宜利等[5]利用粒子群算法进行管路自动敷设，实现了单根管路的自动敷设；权建州等[6]在构建三维可行权值的基础上，运用改进A*算法进行布线路径搜索，并在UG平台上通过二次开发实现了虚拟环境中的自动布线；DAI等[7]针对A*算法的搜索速度和准确度进行分析，提出了动态估价的改进方法；李纯军等[8]通过建立敷设空间模型和敷设约束模型来改进A*算法，得到了合理的布线实现方案。上述研究或侧重于线缆与管道的自动布局设计，或研究算法在寻径过程中的效率和准确性，很少考虑线缆在实际布线中的弯折约束以及布线时的操作空间。

实际工程应用中，最好的经济性固然是布线的一个要求，但线缆的敷设也要尽可能避免过多弯折对线缆性能造成损害，同时考虑布线空间对布线过程的影响。因此，使用人工智能算法进行线缆路径规划时，对线缆弯折情况、布线空间等约束条件的研究是十分必要且有意义的。

本文通过改进A*算法对复杂布线空间环境下的线缆路径搜索问题进行了研究，算法考虑了线缆路径的弯折点与布线空间对路径的影响，通过简单路径仿真与简化布线空间的虚拟布线对算法所求路径进行了验证，实例结果表明，改进A*算法能得到合理的线缆路径规划方案。

1 线缆布线路径规划问题描述

1.1 线缆路径规划概述

路径规划指在有障碍物的工作环境中寻找一条从起点到终点、无碰撞地绕过所有障碍物的运动路径的过程[9]。线缆是机电产品中连接各类电器元件的介质，它在产品空间中的布局和敷设质量是衡量产品整机性能和可靠性的一个重要指标[10]。对线缆进行路径规划时，应该主要考虑线缆与布线空间内其他组件的干涉，以及与其他线缆之间的电气干涉，同时，线缆自身的柔性约束也应该加以考虑。对线缆的路径规划约束做出以下定义。

(1)干涉约束IC表示线缆路径与其他组件的干涉。IC=0表示路径与布线空间内的其他组件无干涉。

(2)电气约束EC表示线缆之间相互的电气干涉。EC=0表示线缆之间不存在电气干涉。

(3)自身柔性约束FC表示线缆自身的柔性特征所带来的约束，包括最小弯曲半径、线缆的直径以及线缆弯曲过程中的受力。

(4) 经济约束LC表示线缆在布线过程中路径的长度，线缆布线的长度越小，经济性越好。

(5)线缆的路径表示为坐标形式，二维栅格图中的路径表示为P=P(x,y)，三维空间中的线缆路径表示为P=P(x,y,z)。

因此，线缆路径规划的数学模型可以表示为

(1)

式中，Fn,C表示所有的线缆柔性约束；Ln,C表示线缆所有的经济性约束；opt(·)表示对所有约束均取最优。

根据式(1)描述的数学模型可知，线缆的路径规划可以归纳为在一定的干涉约束、电气约束、自身柔性约束和经济约束下获得一条最短路径。实际的线缆路径规划还要考虑线缆布线的灵活性、安全性以及操作空间是否满足等条件。

1.2 线缆布线问题

虚拟布线主要利用人工智能算法在一定的布线空间中进行路径搜索，并依据已经规划好的线缆路径，在产品虚拟模型中进行线缆的安装和敷设。其主要过程如下。

(1)模型建立。在三维建模软件中建立机电产品的虚拟数字化模型，构建出线缆路径规划的虚拟布线空间。

(2)干涉检查。主要对虚拟布线空间进行实体干涉检查，利用包围盒理论进行模型的干涉检查，判断模型之间的最小间隙，便于算法寻径。

(3)布线空间处理。对布线空间设定栅格，将所有零件的包容盒视为障碍物。在二维平面内搜索路径时，将障碍物投影至平面；三维布线时，确定障碍物的位置和大小。在线缆直径确定的情况下，判断障碍物间距是否允许线缆通过。

(4)线缆敷设。根据已得到的线缆路径信息，在产品模型的布线空间中进行布线，并通过相关的软件获得线缆长度等信息。

在线缆的实际布线过程中，线缆路径还受到布线工艺的影响，因此，线缆路径在布线工艺的约束下才具有实际意义。常见的典型布线工艺约束有以下几点[11]：①线缆避免悬空，尽量沿刚性实体外壁布置，以便捆扎固定；②布线路径经过处，尽量避免附近存在热源、电磁干扰；③尽量避免在布线位置处存在钣金及尖锐棱角；④线缆路径空间必须大于线缆直径；⑤考虑温度、湿度、穿线空间、振动摩擦等外部因素对线缆的影响；⑥线束过孔时要加保护套。

2 基于A*算法的布线路径搜索

2.1 算法介绍

A*算法结合了Dijkstra算法和BFS算法的优点，将Dijkstra算法靠近终点的节点和BFS算法靠近目标点的节点的信息结合起来，并引入了估价函数F(n)=G(n)+H(n)对搜索的位置节点进行评估，其中，G(n)表示从初始节点到当前节点n的代价，称为代价函数[12]；H(n)表示从当前节点n到目标点的启发式评估代价，称为启发函数。A*算法的关键在于启发函数的确定，不同的启发函数会对A*算法产生不同的效果。一般来说，启发函数应该满足以下条件[13]：

H(n)≤H*(n)

(2)

其中，H*(n)是当前节点n到达目标节点的真实最小代价。因此，只要保证当前节点n到目标节点的估价值不大于真实最小代价，且真实的问题域确有可行解，则A*算法就能找到优解。

2.2 算法的求解流程

A*算法需要2个基本的节点集合：OPEN表和CLOSE表。OPEN表用来存储待检测的节点的信息；CLOSE表用来存储不需要再次检查的节点的信息。A*算法的算法流程见图1。

图1 A*算法流程图Fig.1 Flow chart of A* algorithm

2.3 算法存在的问题

使用A*算法进行路径搜索虽然能得到一条最优的路径，但A*算法存在以下几个问题。

(1)行路径搜索空间一般都会存在空间障碍，机电产品愈加精细，布线空间中的障碍物外形就愈加复杂。利用A*算法进行搜索时，算法往往不能迅速识别障碍物，因此在搜索过程中，算法会产生一定程度的绕路和搜索时间的浪费。

(2)应用智能算法进行路径搜索时，算法给出的路径往往不是实际的可行路径，可能会有较大程度的弯折。这在一般的纯路径规划中是可以接受的，但线缆有最小弯曲半径，实际应用中的弯曲度如果超过线缆的最小弯曲半径，可能会造成线缆绝缘层以及芯线不可逆转的破坏，严重影响线缆性能。

(3)传统的路径搜索算法只考虑最短路径的问题，对真实场景中的线缆装配因素考虑得较少，且没有考虑布线操作空间的影响，导致部分线缆路径规划的结果在理论上可行而实际却不可行，影响布线路径在实际工程布线中的应用。

2.4 算法启发函数的选择

A*算法常用的启发式估价函数有曼哈顿距离函数(MHDF)、对角线距离函数(DGDF)和欧几里得距离函数(ELDF)。MHDF是指两节点南北方向距离与东西方向距离之和，其计算公式为

HMHDF(n)=|xn-xgoal|+|yn-ygoal|

(3)

式中，(xn，yn)为当前节点n的位置；(xgoal，ygoal)为目标节点的位置。

DGDF是指在算法搜索过程中选取节点进行搜索时可以沿对角线方向进行，其计算公式为

HDGDF(n)=max(|xn-xgoal|，|yn-ygoal|)

(4)

ELDF是指在m维空间中两位置节点之间的真实距离，二维平面中ELDF的计算公式为

(5)

比较三种启发函数可知，HMHDF(n)的值最大，HDGDF(n)次之，HELDF(n)最小。启发函数的选取会影响算法搜索路径的整个过程，在使用算法进行路径求解[14-15]的过程中，标准A*算法允许进行对角线节点搜索，实现对当前节点周围8个方向节点的搜索，扩大了搜索空间与范围。对角线搜索可以形成对角线路径，能够以最短距离完成线缆路径的搜索与规划，但在遇到多障碍复杂空间搜索时，容易形成单一的对角线路径。线缆布线的工艺约束[11]要求尽量避免在布线位置处存在钣金或尖锐棱角，而且需要考虑使用过程中的振动。使用对角线搜索形成的路径与障碍物的边角有接触，线缆布线完成之后，布线环境发生振动时，线缆与障碍物棱角发生摩擦，将会加速线缆的磨损失效。本文在算法运行时，只允许算法沿4个方向进行节点的搜索，不沿对角线搜索，因此启发函数不考虑DGDF。对MHDF和ELDF使用图2、图3所示的矩形陷阱模型和弧形陷阱模型进行比较。

图2 矩形陷阱模型Fig.2 Rectangle trap model

图3 弧形陷阱模型Fig.3 Arc trap model

更改启发函数的权重，算法求解路径中的父节点数、搜索节点数、重复搜索节点数、拐点数见表1、表2。

表1 矩形陷阱模型下两种距离函数的比较

表2 弧形陷阱模型下两种距离函数的比较

由表1、表2可以看出，对同一种陷阱模型采用不同的启发函数时，启发函数的权重越大，路径搜索中重复搜索的节点越少，路径产生的拐点越少；权重为1时，搜索的节点和重复搜索的节点最少，路径中的拐点最少。

在矩形陷阱模型中，MHDF路径中的拐点较ELDF更少；在弧形陷阱模型中，MHDF路径中的拐点不多于ELDF路径中的拐点；权重相同时，MHDF具有更少的搜索点和重复搜索点。

在算法求解过程中，减少搜索点和重复搜索点有利于算法更快得到最优的路径解。改进算法针对的是线缆的布线路径问题，而减少弯折点有利于保证线缆功能不受损坏，因此，本文将MHDF作为启发函数，启发函数的权重为1，路径搜索方式为网格地图搜索方式。

3 改进A*算法

A*算法虽可准确有效地获得最短路径，并保证算法的可执行性[6]。但在实际的工程应用中，线缆的敷设不仅要考虑线缆长度所代表的经济性，还要考虑线缆敷设过程中对线缆弯曲半径、线缆装配完毕后的整体美观性、线缆装配操作空间的要求，因此，通过以下几个方面对A*算法进行改进，以更加适应实际工程应用中的需求。

3.1 估价函数的改进

A*算法中的估价函数F(n)=G(n)+H(n)只考虑从初始点到目标点的最短路径，在单纯的寻径问题中能够找到最短路径的精确解，但不适用于线缆布线问题的寻径。线缆的路径规划不仅要求路径较短，还要求美观性且与其他电器元件不干涉等，因此，一般情况下的最短路径并不是最优路径，路径中过多的弯折会增加布线工艺的复杂度，也会降低线缆的性能。本文在原有估价函数的基础上，添加K(n)和L(n)两个估价指标，共同完成路径搜索过程中的代价估计。

(1)K(n)表示搜索到当前节点时路径中的弯折点情况。线缆可以在布线的时候弯折，但线缆的弯折有最小弯曲半径的约束，布线的时候不可以过分弯折线缆。整个线缆的布线路径中，线缆发生弯折的次数越少，线缆弯折引起的损坏或功能失效的可能性越小。因此在算法中对搜索到当前节点时路径中的弯折点的情况进行统计，将其算法的估价函数对路径节点进行评估。

在算法中进行路径弯折点情况统计的具体方法如下：①以当前节点n为初始点，回溯目前所有的路径节点并导入路径节点数组ST；②读取路径节点数组ST中节点的横坐标数据；③数组中第i个节点(i=2，3，…,l-1；l表示数组中节点的个数)开始，根据公式判断路径是否发生弯折；④当Va=Xi-Xi-1，Vb=Xi+1-Xi中有且仅有一个为0时，路径节点STi为弯折点，其中，Xi为数组ST中节点i的横坐标；Xi-1为数组ST中节点i之前一个节点的横坐标；Xi+1为数组ST中节点i之后一个节点的横坐标；⑤累计求得当前路径中所有的弯折点的个数，用K(n)表示。

(2)L(n)表示是否与障碍物及布线空间的边界发生干涉。在一定的布线空间内布线，需要考虑线缆路径与障碍物及布线空间边界的干涉，即线缆的布线路径不可超越布线空间边界，也不能与布线空间中已有的障碍物发生干涉。用L(n)表示搜索节点与障碍物及边界的干涉情况，如果当前节点与布线空间的障碍物及布线空间边界有干涉，则L(n)=1，否则L(n)=0。

由于G(n)和H(n)都表示距离，而K(n)和L(n)为离散的数字，为统一算法执行过程中的单位，需要将K(n)和L(n)所代表的数字信息转换为G(n)和H(n)代表的距离信息。将K(n)和L(n)乘以一个惩罚系数，从而将弯折点的情况和干涉约束情况转换为算法中统一的距离形式。最终的估价函数计算统一使用距离进行比较，通过估价函数F(n)对路径点进行取舍。改进后的A*算法的估价函数为

F(n)=G(n)+H(n)+K(n)+L(n)

(6)

3.2 添加附加值因子

搜索时，OPEN表中可能会出现2个节点的估价函数值相同的情况，为选择更优的路径节点，在算法中添加一个附加值因子来对估价函数值相同的待选节点进行选择。布线空间一定的情况下，算法在确定下一个路径节点的搜索过程中会出现一部分节点被重复搜索的情况，重复搜索的节点越多，算法在当前节点的搜索范围越大。一般情况下，算法搜索的范围越大，该算法具有越大的可能性避免产生局部最优解，因此在算法搜索中遇到2个节点具有相同的估价函数值时，引入重复搜索点数作为算法节点选择的附加值因子。

设n1、n2为算法OPEN表中估价函数值相等的2个节点，且此时的估价函数值为OPEN表中所有节点的最小估价函数值。设M1为算法搜索到节点n1时重复搜索的节点数，M2为算法搜索到节点n2时重复搜索的节点数，则添加附加值因子之后节点的估价函数值为

F*(ni)=F(ni)+A(ni)

(7)

式中，ni为估价函数值相等的节点，i=1，2；A(ni)为节点的附加值。

节点n1、n2对应的附加值分别为

(8)

(9)

当M1=M2时，算法跳出附加值因子的评价，不对原估价函数添加附加值。

3.3 添加刚性因子

在栅格中对线缆的路径进行规划，线缆最初的布线路径采用直角弯折的形式。在连续的2个弯折处，由于存在线缆最小弯曲半径的要求，很容易出现1个弯折角度无法实现的情况，导致1个弯折半径不满足线缆最小弯曲半径的要求。各种线缆的作用和材质不同，其所要求的最小弯曲半径也不相同，为了避免在弯折过程中出现线缆最小弯曲半径不满足的情况，引入刚性因子[16-18]的概念。

刚性因子能够保证线缆在某段路径上的最小长度，限制线缆路径规划过程中线缆方向的随意扩散，保证线缆在连续弯折时的弯折角度满足线缆最小弯曲半径的要求。如图4所示，线缆在2个障碍物之间的路径规划需要连续进行弯折，其中，R为线缆的最小弯曲半径。|PQ|<2R时，PQ段的距离不足以完成线缆的两次弯折。图5中，由于加入了刚性因子，因此|PQ|>2R，2个弯折角都满足线缆最小弯曲半径的要求。图4、图5的结果也表明，带有刚性因子的线缆路径不一定是最短的路径，但却一定是满足线缆最小弯曲半径要求的线缆路径。

图4 未加入刚性因子的路径Fig.4 Path before adding rigidity factor

图5 加入刚性因子后的路径Fig.5 Path after adding rigidity factor

为保证线缆弯折时相邻的2个弯折角度都满足最小弯曲半径的要求，设定刚性因子：

(10)

式中，i为路径中从初始节点开始的弯折点的序号；r为线缆所允许的最小弯曲半径。

3.4 考虑路径的位置因素

线缆布线路径的位置因素主要是布线时的操作空间大小，以线缆路径与其周边的障碍物之间的间距为评估内容。对于平面布线空间中两点之间的布线路径，从初始点到目标点的路径代价是相同的，但线缆的布线路径规划需要考虑布线操作空间和最小弯曲半径。图6所示的布线空间中，3条路径最终达到目标点的路径真实代价是相同的，但在路径避障的时候采取的策略不相同，导致出现了3种可能的线缆路径规划方案。在图6所示的4个弯折点处，3条路径与障碍物的距离不同，导致线缆在避障弯折时受障碍物边角的影响不同，使得线缆在真实布线过程中的不同弯折点产生不同的弯曲半径。

图6 不同布线路径Fig.6 Different routing paths

图7 最小弯曲半径证明Fig.7 Proof of minimum bending radius

3.5 算法的实现

改进A*算法依然存在OPEN表和CLOSE表，它们分别存放已生成但是还未考察过的点和已经访问过的节点。改进A*算法流程如图8所示。

对比图1、图8可知，改进A*算法在进行寻径时与A*算法有以下的不同：①A*算法的F值计算只考虑G(n)和H(n)，改进A*算法添加K(n)和L(n)，预先将干涉因素考虑进算法，路径不需要再经过干涉检验;②在扩张当前节点的邻居节点时考虑刚性因子，舍弃不符合刚性因子条件的节点，减小了算法中节点的搜索范围;③2个节点的F值相同时，通过附加值因子对节点进行取舍，使路径中的每个节点均为当前条件下的最优节点，进而保证整个路径的最优。

4 应用实例

改进A*算法的应用前提是布线空间得到了一定的处理。布线空间的处理结果如下：①布线空间内的设备零部件均为固定件，没有相对位移，也不存在相互干涉；②在误差允许的范围内，线缆路径规划的结果将会以线缆中心线的形式在空间中进行布线，仿真结果以线缆设定的真实直径显示。应尽量避免线缆的悬空布置，减少因为磨损和振动造成的线缆功能失效或寿命缩短；考虑到线缆及周边刚性件的维修便捷性，应该尽量减少线缆对布线空间内其他组件的依附，以便在组件故障时及时更换。基于以上的布线准则，线缆必须尽量固定在基板上。

图8 改进A*算法流程图Fig.8 Flow chart of improved A* algorithm

4.1 算法的仿真结果

使用栅格法搭建一个障碍模型，采用改进A*算法进行线缆路径规划仿真[19]。本文使用直角坐标系法和赋值法相结合的方式进行栅格的标识。选取栅格窗口的左下角顶点为坐标系原点，定义坐标系中水平向右为X轴正方向，竖直向上为Y轴正方向，栅格单元以坐标U(x,y)为唯一标识；V(x,y)表示该栅格单元中的障碍物的情况：

(11)

虚拟障碍空间栅格单元中，起始节点用S表示，目标节点用G表示，将空间障碍信息以上述方法转化为二维数组，调用算法进行路径搜索，A*算法的路径规划结果见图9，改进A*算法求解路径的结果见图10。图9、图10所示算法的布线结果见表3。

图9 A*算法的路径规划结果Fig.9 Path planning results of A* algorithm

图10 改进A*算法的路径规划结果Fig.10 Path planning results of improved A* algorithm

由表3及图9、图10可知，改进A*算法的父节点比A*算法的父节点多，但改进A*算法在搜索节点数、重复搜索节点数和拐点数均有优势。由图9、图10可知，改进A*算法在连续弯折处的2个拐点之间的距离大于A*算法中的距离，在连续弯折时满足线缆最小弯曲半径的要求，且布线路径基本处于障碍物中间，有利于实际布线的操作。

4.2 算法的实际应用

基于改进A*算法进行路径搜索，在三维环境下进行线缆路径规划。在三维环境中创建路径规划空间时，不考虑自由平面的情况，只考虑在模型平面内布线[20-21]。实际的线缆路径规划中，通常以机电设备布线空间的俯视图视角对所布线缆的路径进行规划。对布线空间中的障碍物使用最小包围盒法[22]，将布线空间中的障碍物转换为规则形状，选定底面作为布线的参考平面，以俯视图的形式将障碍物的信息投影到底面，使用前述的栅格法处理空间投影面，将投影平面变换为二维数组的形式，调用改进A*算法，根据算法的路径规划结果在布线参考平面上创建线缆的布线路径。由于线缆路径中的所有弯折点均满足线缆最小弯曲半径的要求，因此将线缆路径中的弯折点圆滑为不小于线缆的最小弯曲半径的圆弧，同时保证布线的美观性和整齐性。

(1)在Creo2.0中建立机柜简化模型，通过改进A*算法求得投影平面内线缆的最优布线路径；使用Creo2.0的布线功能，将求解出的布线敷设到模型中。图11所示为A*算法所敷设的线缆路径，图12所示为改进A*算法敷设的线缆路径。

图11 A*算法在机柜模型中的布线结果Fig.11 Routing results of A* algorithm in cabinet

图12 改进A*算法在机柜模型中的布线结果Fig.12 Routing results of improved A* algorithm in cabinet

根据图11、图12所示的布线结果，将线缆依次编号为1～9，在Creo2.0中对两种布线路径进行对比，结果见表4。

表4 两种布线结果

由表4及图11、图12可知，改进A*算法解决了A*算法不能有效避开障碍物的缺点，减少了线缆路径中的弯折；由于路径规划和实际的布线不同，改进A*算法规划的路径在实际布线中更短，具有更大的经济优势，也避免了A*算法路径规划中线缆紧贴障碍物而带来的线缆或障碍物故障时不便更换的问题。对比图11、图12可知，改进A*算法规划的路径布线能给予布线人员更大的操作空间，在避开障碍物的同时，也避免了线缆连续弯折后线缆最小弯曲半径不满足的情况。

(2)以某军工企业产品的壳体模型内部布线为例，分别调用A*算法和改进A*算法进行路径规划，规划结果分别见图13、图14。根据图13、图14所示的线缆布线结果，将线缆从左上到右下依次编号为1～4，利用Creo2.0对线缆路径的相关数据进行统计，两种线缆布线结果的对比见表5。

图13 A*算法在产品模型中的布线结果Fig.13 Routing results of A* algorithm in product model

图14 改进A*算法在产品模型中的布线结果Fig.14 Routing results of improved A*algorithm in product model

表5 产品模型中两种布线路径结果

由表5及图13、图14可知，改进A*算法能有效减少线缆路径中的弯折点，显著减少布线过程中需要确定的位置点；根据2种布线结果可知，改进A*算法线缆布线整齐美观，同类型线缆尽量集中在一起，方便在线缆集中段对线缆进行归类和整理，也为布线提供了足够的操作空间。但改进A*算法部分线缆的总长度大于A*算法的线缆总长度，在经济性上具有一定的局限性。

5 结论

(1)本文提出了一种基于改进A*算法的线缆路径规划设计方法，在算法寻径时考虑已搜索完成的路径情况和布线空间环境情况，避免了与布线空间内障碍物和空间边界的干涉；加入附加值因子，使得算法更加迅速有效地取舍F值相同节点；算法考虑实际布线中的刚性因子约束和线缆路径的位置因素，保证了所求解的线缆路径有足够的弯折半径和操作空间，算法求得的路径满足路径规划数学模型的要求。

(2)根据对A*算法的改进，在二维栅格障碍空间中进行路径规划仿真，在三维布线空间模型中进行布线仿真。实验的结果表明，改进A*算法能找到一条满足条件的最优路径。

(3)本文所提方法只涉及单一种类的线缆在复杂机电产品中的布线，实际布线的多种线缆布线和交叉布线未考虑，也未考虑线缆的捆扎和分线，这些内容在今后进一步研究。