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

孙 浩 原 野 张 琦 张小贝

1.上海大学通信与信息工程学院,上海,2004442.上海飞机设计研究院,上海,201210

0 引言

航空电气线路互联系统(electrical wiring interconnection systems,EWIS)是指安装在飞机上任何区域,在两个或多个端接点之间传输电能(包含数据和信号)的各种导线电缆、端接器件、支撑器件的组合,EWIS的设计与布置直接影响飞机的经济性、可靠性和安全性[1-3]。传统依靠人工的设计方式存在设计周期长、易出错、无法得到最优路径等问题[4]。随着科技的发展,人工智能算法逐渐被应用于自动布线,克服了人工规划的不足。

自动布线的核心是路径搜索算法。虽然迪杰斯特拉算法[5](Dijkstra)、A*算法[6]、快速搜索随机树算法[7](rapidly-exploring random trees,RRT)等传统路径搜索算法可以做到无干涉的最短路径,但显然无法满足实际布线工程的需要,为此国内外学者对传统算法进行了适应性改造,使其满足不同的布线需求。董宗然等[8]将布线约束反映在网格能量值中,代入最短路径快速算法(shortest path faster algorithm, SPFA)距离松弛函数的计算,从而将布线约束纳入考虑,但对布线约束向网格能量值的映射过程缺少详细介绍。刘潇等[9]、刘佳顺等[10]改进RRT算法,使随机树能够贴着障碍物表面拓展,便于线束捆扎固定,又对规划出的路径点进行位置修正,让路径更加平滑,但难考虑更加复杂的约束。吴宏超等[11]改进A*算法的估价函数,使其与弯折和方向有关,通过在设备周围设置吸引区和排除危险设备周围的点,让线缆靠近或远离,具有不错的效果。KANG等[12]先用Dijkstra算法规划避障的最短路径,再用拉普拉斯平滑算法平滑布线路径,使线缆的连续性得到提高,但较为简单,没有考虑更多布线约束。王发麟等[13]以线缆间电磁干扰最小且整体线缆束质量最小为目标,采用改进粒子群算法进行整体寻优并获取线缆的具体路径,但规划过程需要较多迭代,计算时间长,不利于实际应用,且是非确定性算法,可能会产生无效解。如何减少线缆的机械损伤,一直是学者们的研究重点。姜康等[14]在A*算法的估价函数中加入弯折因子、刚性因子以约束线缆弯折,加入干涉因子以避免与障碍物及布线空间的边界发生干涉。杨旭等[15]对线缆的弯折进行了详细分析,综合考虑了弯线槽单位长度的材料成本、工艺成本、质量成本,用以减少线缆弯折损伤,同时对障碍物的棱角做膨胀处理,用以在线缆和障碍物尖锐处留出空隙,以减少线缆磕碰损伤。KIM等[16]在设计船舶管道时以线缆长度和弯折个数为学习目标,使用强化学习规划最为经济安全的路径。综上,国内外学者为线缆路径规划提供了多样化的解决思路,但是上述方法或难获得最优路径,或考虑约束不全面,或算法复杂,难以实际应用,且对更加复杂的电气约束如电磁干扰、线缆间的相互作用等情况的研究甚少。

本文对航空EWIS自动布线技术进行研究,提出了基于改进A*算法的航空线缆路径规划方法。该方法首先采用栅格法将布线空间均匀离散化;之后对栅格点进行权值编码,以描述栅格点周围的环境因素;然后根据线缆受不同环境因素的影响程度,计算表征了不同布线约束的综合权值,用以改进A*算法;同时在A*算法的估价函数中加入弯折因子和刚性因子,以约束线缆的弯折;最后对规划出的路径进行拟合曲线优化调整以适应飞机曲面,从而获得最终的布线结果。所提方法有助于EWIS实现从人工设计向自动化、智能化设计的升级。

1 航空线缆布线问题分析

同所有机电产品的线缆一样,航空线缆路径规划的最基本要求也是在布线空间内自动规划一条避开所有障碍物的端到端的路径。不同的是,飞机飞行时强振动的环境要求线缆必须能够被可靠固定;飞机内部密集的管路、复杂的电磁环境要求线缆尽量避开危险区域;而且相较于立方体结构,飞机接近圆形的机身也为路径规划增加了难度。综合以上因素,在设计航空线缆路径规划算法时,本文主要考虑了如下布线约束:①避障,不与空间中的其他设备发生干涉;②贴近结构件,避免悬空,以便捆扎固定;③保持原方向,尽量避免转弯,转弯半径必须大于线缆的最小弯曲半径;④禁止小于90°的弯折,尽量大转弯角度;⑤尽量避开高温、高湿、强电磁等区域;⑥满足与互斥线缆的隔离距离和尽量与兼容线缆保持共同路径;⑦线路长度尽量短。

如图1所示,本文设计了复杂约束下基于改进A*算法的线缆路径规划方法,主要包括如下步骤。

步骤1:创建布线模型,导入线缆接线表信息。

步骤2:对布线空间模型进行均匀栅格化处理,建立结构件包装盒模型,根据栅格点与结构件包装盒的相对空间位置,为栅格点分配不同的权值。

步骤3:建立接线终端包装盒模型,将布线空间划分为待布线空间区域和非布线空间区域。

步骤4:利用改进的A*算法详细规划线缆路径,并对A*算法输出的线缆路径作拟合曲线处理。

步骤5:遵循线缆模型的绘制方式,将布线结果在CAD软件中驱动生成。

图1 总体流程图

2 布线空间预处理

2.1 布线空间均匀离散化

包装盒算法的基本思想是使用规则的矩形包围不规则图形,从而构造不规则图形的边界,被广泛用于干涉检测等方面[17]。栅格法的基本思想是将连续的二维空间或者三维空间分解成若干个相同大小的离散的基本单元,因其分解快速、操作简单、便于计算而被广泛用于离散环境模型的构建[18]。本文首先使用包装盒算法框定模型范围,再使用均匀密度的栅格线将三维布线空间划分为相同大小的立方体,如图2a所示。采用栅格法对自由空间进行处理不仅可以很好地描述各种复杂的环境,而且可以将布线约束反映到栅格点的权值上[19],以图2b为例(黑色线为设备轮廓,红色线为设备包装盒),赋予盒内的网格点最高的权值,以避免被路径搜索算法采样,达到避障效果。同理,将设备包装盒上的点赋予较低的权值,使其易被采样,从而使线缆能够贴近结构件,便于捆扎固定。实际中飞机线束有很大比例是依附于机身结构固定的,而方形包装盒难以完美地构造圆形机身的轮廓边界,为此本文设计了适用于曲面的扇形包装盒,如图2c所示。采用半径稍小的圆与圆形机身构成一个封闭的扇形,认为到圆心的距离d不小于圆形包装盒半径r且小于机身半径R的点即扇形区内的栅格点是可依附于机身固定的,赋予较低的权值以便于被采样。除避障与贴壁约束外,其他更加复杂的布线约束也可通过进一步的权值划分来更加精细地描述。

为保证路径的精度,需要以较小的粒度划分栅格,但在三维空间中,每个维度上等分的个数每增加1,立方体数就随之增加3n2+3n+1,其中n为粒度改变前每个维度上均匀划分的密度。立方数量的暴增不仅耗费存储空间,更会降低路径搜索算法的效率。为此本文通过构建包含起点和终点的包装盒,将布线空间分为盒内待布线空间和盒外非布线空间,以降低搜索成本,如图2d所示,其计算公式为

(1)

式中,xmin、xmax、ymin、ymax、zmin、zmax为起点和终点坐标的最小、最大值;d为调整包装盒边界范围的参数;X、Y、Z为盒内待布线空间的坐标范围。

(a)均匀栅格化 (b)可依附性

(c)机身包装盒(正视图) (d)布线空间划分图2 空间预处理示意图

2.2 栅格权值编码系统

路径规划本质上是对周围环境信息综合分析的过程,为实现更加复杂的布线约束,需要对自由空间进行精密的描述,对栅格点进行高效的编码,使其携带更多的环境信息。以图3为例,栅格点A受到磁和热的共同作用,同时它还处于设备的可依附点位上。若待规划线缆经过点A,则该点也同时处于与已存在的互斥线缆E产生信号串扰的区间内和被已存在的兼容线缆F吸引的区间内(图中仅标识了磁和热辐射的作用范围)。为在点A同时描述上述信息,采用图4所示的十六进制编码方式对栅格点进行编码。

图3 布线环境

图4 权值编码与解码系统

编码码文由两部分组成:固定区码文和扩展区码文。固定区码文跟布线模型有关,在模型预制好时便已固定下来。鉴于本文所考虑的布线约束,固定区码文主要考虑可依附性、电磁强度、热度3个因素。扩展区码文是根据布线环境变化而变化的,在布线空间中新敷设一条线缆就需更新相应区域的扩展区码文,其主要作用是约束已存在的线缆与待规划线缆之间的位置关系,防止信号串扰和帮助兼容线缆尽可能地走在一起,规整线束。扩展区码文由一系列线缆类型和相隔距离的固定组合构成。

(1)可依附性表示这一栅格点是否易于线缆捆扎固定。布线空间内设备众多,为降低模型预处理后的复杂度,本文只标识3类点,如图2b所示,即不可达点、可依附点、悬空点,分别用F、2、8标识:

(2)

式中,d1为栅格点到设备的最近距离,采用相隔x个栅格来相对刻画;s为可依附性编码。

此点位具有最高的优先级,若此位标记为F,则表示此点位于设备内不可经过,后续的码文也就无需考虑。

(2)电磁强度和热度表示此栅格点受电磁和热源的辐射程度,均采用0-F的递增序列表示从弱到强。准确地获取电缆敷设空间中磁场和温度场的分布对电缆路径规划十分重要,但却十分困难且不是本文分析的重点。本文简单地将强度的变化与距离挂钩加以模拟分析,如图5a所示。假设辐射源中心强度为F,辐射强度i随距离衰减分成4个档位(可根据需求进一步扩展),外围方形包装盒框定了辐射源的作用范围,编码数值计算方式如下:

(3)

空间内可能还存在多个磁场(热度场)叠加的情形,采用线性叠加的方式对编码数值进行加减修改,上限为F,表达式如下:

I=min(i1+i2+,…,+in,F)

(4)

式中,d2为栅格点与电磁辐射源的最近距离;in为电磁辐射源n在栅格点处的强度编码;I为电磁辐射叠加后栅格点的实际编码。热度编码同理。

(3)线缆类型。采用0-F的十六进制编码指示16种线缆。

(4)相隔距离表示当前栅格点与某类线缆的距离大小,如图5b所示。以线缆为中心向外扩张,划分四层作用区间,0-F的递增序列表示距离由远到近,F表示与线缆重合,其编码数值tR的计算方式与式(3)一致。扩展区的编码设计方式考虑了不同类型的线缆,在编码时相互隔离互不影响,而当两个同类线缆共同作用于一个栅格点时选取大值作为此栅格点的编码,如下:

TR=max(t1,R,t2,R,…,tn,R)

(5)

式中,tR为栅格点与线缆R的相隔距离编码;n表示有n条R型线缆共同作用于当前栅格点;TR为线缆作用区间叠加后栅格点的实际编码。

因而,对一个栅格点而言扩展区的线缆类型是不重复的。

(a)辐射分布 (b)线缆作用区间图5 距离场分布

综上,网格划分和编码完成之后,整个模型空间就形成了一个具有不同“势能”的场,用三维数组S[α(x,y,z)]表示,其中α(x,y,z)表示对格点(x,y,z)的编码。以图3中的点A、点B为例,点A可编码为0X299ECFC,点B可编码为0X85CEFF9。

3 基于改进A*算法的路径规划

3.1 A*算法简介

A*算法在搜索过程中加入了与问题有关的启发性信息,缩短了盲目搜索的过程,可以快速找到端到端的最短路径,在路径规划任务中得到了广泛的应用[6]。A*算法搜索的原理是,在周围相邻的点云中选择估价函数最小的节点作为下一步路径,其一般估价函数为

f(n)=g(n)+h(n)

(6)

其中,f(n)为节点n的估价函数,它表示从起点经由节点n到达终点的代价估计,由从起点到达节点n的代价g(n)和从节点n到达终点的最短路径的估计代价h(n)组成。A*算法通过维护Open表和Closed表来实现节点的筛选,Open表为一个按照估价函数升序排列的优先队列,用于存储待扩展的备选节点信息,Closed表用于存储已扩展的节点。具体执行步骤如下:

(1)将起始节点加入Open表中,如果Open表不为空,则循环执行步骤(2)～步骤(4),否则搜索失败,程序退出。

(2)选取Open表中估价函数最小的节点n。

(3)如果节点n为终点,则向前回溯到起点,返回找到的路径,程序退出。

(4)如果节点n不是终点,则将节点n从Open表中删除并加入Closed表。以节点n为中心,遍历节点n的所有邻近节点,如果某个邻近节点已在Closed表中,则忽略该节点,否则计算该节点的g值。之后判断该节点是否已在Open表中,是则与其原有g值比较,选取小的g值作为新g值,并更新其父节点;否则计算该节点的估价函数f,将该节点加入Open表中,并设置其父节点为节点n。

3.2 改进型A*算法

传统A*算法追求的目标只有路径最短,难以满足实际工程需要,因此本文对A*算法的估价函数进行改进,使其兼顾布线约束要求,改进后的估价函数为

(7)

(8)

(9)

q*(n)=

(10)

h(n)=|xn-xgoal|+|yn-ygoal|+|zn-zgoal|

(11)

新的估价函数由二维扩展为三维,并且需要在满足刚性因子p*(n)的条件下。p*(n)=0的主要作用在于保证线缆的弯折半径要大于线缆的最小弯折半径,对于满足的点n,p*(n)=0,否则p*(n)=1。为了弯折得更加平滑,忽略小于90°的弯折点。对于90°到180°的弯折,给一个随角度增加而减小的惩罚q*(n),用于促使线缆增大弯折角度,而且本身作为弯折的惩罚项,可以促使线缆减少弯折,这可以显著减小线缆的损伤。

3.2.1栅格权值解码系统

飞机上的线缆在敷设时,出于安全性和可靠性考虑,要根据导线的电流、电磁场、热场、余度等不同特性进行综合设计,本文通过图4所示的解码码文解构线缆不同的属性。

解码规则与编码规则类似,也是由固定区和扩展区两部分组成。固定区的解码码文与编码码文两相对应,固定区的码文考虑线缆受可依附性、电磁强度、热度的影响程度,通过β1、β2、β3三项加权系数来衡量。扩展区的码文由一系列线缆类型和影响因子的固定组合构成,线缆类型表明待布线缆会受到该类线缆的影响,影响程度由影响因子决定。

(1)β1、β2、β3均为[0,1]常数,数值越大表明受影响程度越严重。由β2、β3的取值可知,受电磁或热度影响的栅格点并非直接排除,即磁场区和热度区也可穿越,一切由数值计算决定。

(2)线缆类型取值0-F,对应编码中的16种线缆。影响因子β则根据线缆间的作用关系而定,同类相吸取值[-1,0],异类相斥取值[0,1]。与编码的数值配合,在计算式(8)时分别给予负向增益和正向增益,从而促使待布线缆靠近或者远离某类线缆。

改进后A*算法的解码流程如图6中标示颜色部分所示。首先依次计算固定区的可依附性权值、电磁强度权值、热度权值;然后检查扩展区解码码文的线缆类型是否在当前栅格点的编码码文中,存在则计算影响权值,否则检查下一项,权值计算方式为,将该项的十六进制编码转化为十进制并与解码的对应权重相乘;最后将所有项求和得到该栅格点的总权重,如式(9)所示。

图6 改进后A*算法搜索流程

3.2.2刚性因子

如图7a中MN段所示,刚性因子[14-15]主要用来解决因两次连续弯折过近而导致无法满足线缆最小弯曲半径的问题。如图7b所示,某一线缆的直径为r0,最小弯曲半径为R0,经过一个角度α的拐角,则两侧至少预留出的直线段长度为

(12)

为避免两次连续弯折过近,需要在弯折时向前搜索到上一拐点(第一个拐点搜索到起点为止)。根据式(12)计算上一拐点的最短预留直线段长度,判断两个拐点之间的距离是否大于此次弯折最短预留直线长度和上一弯折最短预留直线长度之和,否则取消此次弯折。

(a)连续弯折 (b)拐角图7 刚性因子及最小弯折半径

3.3 路径优化处理

前文从弯折数量和弯折角度方面对弯折做出了诸多限制,已可以很大程度上避免连续多次近距离弯折情况,即阶梯形路径。但是由于栅格离散化的原因,搜索得到的路径是由一系列的线段构成的,在贴合机身结构进行布线时,还是会无法避免地产生图8a所示的阶梯形路径。文献[11,20-21]都采用类似可视图的思想减少路径控制点,从而实现对路径的平滑处理,但此类方法不仅会破坏路径的贴壁特性,而且显然无法解决曲面的阶梯路径问题。为此本文根据路径控制点的位置特点,利用相似三角形原理,将机身扇形包装盒内的路径控制点做贴合曲面处理,如图8b所示。已知线缆直径r0,机身圆心A坐标、最小弯曲半径R0、路径控制点B坐标,将路径控制点B沿AB的延长线移动至点C处。考虑线缆本身直径,则AC长度为R0-r0,根据相似三角形原理易得点C坐标:

(13)

式中,xA、yA、zA为点A的坐标值,其余同理。

将点C作为线缆新的路径控制点替换点B。如此检查位于机身包装盒内的所有路径控制点便可获得一圈贴着机身蒙皮的新路径控制点。

(a)阶梯路径 (b)拟合曲线处理图8 贴合机身轮廓处理(正视图)Fig.8 Fit the fuselage contour processing(front view)

4 算法测试与仿真

仿真实验在Windows11 64位系统、CPU AMD R7-5800H、主频3.2 GHz、运行内存16 GB的计算机平台上进行,采用Python3.7作为开发语言。为了验证本文方法的有效性,首先在二维网格图上进行算法性能验证,再在三维飞机数模上进行可行性验证。根据线缆特性,按照严重(|β|∈[1,0.7))、较重(|β|∈[0.7,0.5))、一般(|β|∈[0.5,0.3))、较轻(|β|∈[0.3,0))和无感(|β|∈0)的区间划分线缆受环境因素的影响程度。

4.1 算法性能验证

首先在一定β值下验证算法对布线约束的实现,再以可依附性和热敏感度为例,调整其β值,验证算法对线缆特性的实现。实验结果如图9所示,实验方式采用控制变量法,每次实验都在前一步的基础上进行。假设待规划线缆的半径为2 mm,最小弯曲半径为20 mm,与线缆E互斥,与线缆F兼容。二维网格的分辨率为30 cm × 30 cm。

由图9可以看到,加入弯折因子后,规划路径的弯折数由7个减少为3个,且弯折角度均为大弯角,不仅减少了对线缆的损伤也增加了线缆的平滑度。加入贴壁约束后,线缆选择贴着结构件走线,大大方便了后期的捆扎固定。加入互斥线缆后,线缆会尽量远离该线缆,防止信号串扰。加入兼容线缆后,线缆会尽量地与之走在一起,形成线束。加入温度场后,对热敏感的线缆会尽量远离热源。叠加电磁辐射场后,对磁和热都敏感的线缆会走磁和热相对平衡的路径。加入刚性因子规范后,线缆弯折满足最小弯曲半径。然后分别减小热敏感度β值和增大贴壁性β值以模拟实际情况下不同线缆具有不同特性的情况,算法能够根据参数的变化做出灵敏反应,如图9i和图9j所示。综上,改进后的A*算法能够应对复杂的布线约束,规划满足不同线缆特性需求的路径。

(a)传统A*算法 (b)加入弯折因子

(c)加入贴壁约束 (d)加入互斥线缆隔离

(e)加入兼容线缆吸引 (f)加入热敏感隔离

(g)加入磁敏感隔离 (h)加入刚性因子

4.2 算法可行性验证

应用前文所述的改进A*算法,在图10所示的飞机货舱段模型下进行仿真验证(内部的红色方块和蓝色方块分别用以模拟热源和电磁源,同时为了方便观察隐去了其余设备)。首先采用均匀栅格法将布线空间均匀地分为80 cm×80 cm×40 cm的离散空间并作为算法的搜索空间,三维环境较二维网格图法的搜索方向由8个增加为26个,复杂度大大增大。然后在布线空间中设置6条线缆进行仿真测试,接线关系及线缆参数如表1所示,其中将信号线与电源线视为互斥线缆,要求保持一定隔离距离,而同类线互相兼容,尽量合并。最后基于CATIA二次开发将规划路径可视化。为了展现本文方法的改进效果与优越性,与传统A*算法和文献[11]所提方法进行对比。文献[11]所考虑约束与本文研究相近且具有良好的应用效果。不同方法的布线结果如图10所示,仿真结果中的一些关键参数总结如表2所示。其中,贴壁占比表示贴附于结构件的电缆长度与总长度之比,用于评估是否易于固定,其统计方法如下:

(14)

式中,m为线缆分段总数;li为贴壁段i的长度;Lz为线缆总长度。

是否是贴壁段则通过线段的两端点的权值判断。电缆与辐射源以及互斥电缆之间是否串扰通过它们之间的最近距离来判定,假设距离小于4 cm会发生串扰。是否违反刚性因子则通过式(12)判定。

由图10可以看出,传统A*算法规划线缆存有大量弯折和无法固定的飞线,互斥线缆之间存在重合路径,规划路径不可用。文献[11]方法规划的线缆在弯折和贴壁性上有了很大改善,弯折点数量明显减少且线缆能够沿着设备架和机身结构进行布线,但互斥线缆之间仍存在交叉,沿着圆形机身布线的线缆拟合效果不佳。本文方法规划线缆的平滑度和连续性最好,接近真实线缆效果,且兼容线缆合并走线形成了线束,互斥线缆以及信号线与辐射源之间保持了一定隔离距离。由表2数据分析可得,本文方法因为要满足一些布线约束而无法选择最短路径,在长度上有所增加,但是在布线质量上有了较大改进,较传统A*算法贴壁占比平均增加48.40%,线缆弯折个数平均减少6.50个,线缆均满足隔离要求和最小弯曲半径。对比文献[11],除线缆长度外,本文方法整体上优于文献[11]方法,进一步验证了本文方法的优越性。另外,文献[11]考虑到了线缆和辐射源之间隔离要求,但没有考虑线缆之间的隔离以及合并要求,因而本文方法可以解决的布线约束更加全面。

(a)传统A*算法布线 (b)文献[11]方法布线 (c)本文方法布线

(d)传统A*算法线缆 (e)文献[11]方法线缆 (f)本文方法线缆图10 不同方法布线结果对比

表1 接线表

表2 不同方法布线结果统计

5 结语

为有效解决航空线缆自动化布线过程中面临的各种复杂布线约束,本文提出了基于改进A*算法的航空线缆路径智能规划方法。该方法充分利用布线空间的三维离散栅格地图,将对线缆的避障、贴壁、隔磁、防热、同类合并、异类隔离等约束融入进栅格点的权值中。通过权值编码系统对栅格点进行编码,使其能够携带体现周围环境情况的信息。再通过反映待布线缆属性信息的解码系统从栅格点权值中提取有用信息。通过改进A*算法的估价函数使得编码系统和解码系统能够相互交互,发挥作用。同时在A*算法的估价函数中加入了对弯折角度和转弯半径的考量以减少线缆弯折损伤。最后对规划出的路径进行曲线拟合,以贴合飞机曲面轮廓。仿真结果表明,本文方法能够应对线缆自动化布线过程中的各种复杂布线约束,规划满足实际工程需要的线缆。本文方法较为依赖地图精度,用包装盒算法构建复杂外形设备的轮廓会增加非实体空间,导致在描述设备影响范围时容易有较大误差,因此后续需要进一步研究地图的构建。