基于改进A*算法的管路自动敷设研究

陈 岩,李 涛,印明昂

(1.中国兵器科学研究院, 北京 100089; 2.东北大学 机械工程与自动化学院, 沈阳 110819)

在装甲车辆发动机设计中存在大量的管路敷设设计问题，管路自动敷设是提高装甲车辆发动机管路敷设水平、降低敷设成本的重要途径，对提高产品设计质量、缩短制造周期有着重要的意义[1-3]。

A*算法具有可纳性、最优性、应用简便、快捷等优点，广泛应用在电脑游戏、机器人路径规划、无人机航迹规划等领域。管路自动布局设计的本质是路径规划问题，路径规划不仅要求路径可行，还应满足该领域的多项工程约束(如可制造性规则、可装配性规则等)以寻求路径的最优化[4-5]。由于A*算法起源于二维平面，且以估价距离作为启发式信息，针对三维环境下管路自动布局设计这一具体问题，应考虑长度较短、弯曲加工的代价较少、安装方便和安全性等因素，因此需要对算法进行改进。管路一般采用基于控制点的表示方法，通过A*算法得到的路径由一系列分布在不同折线段上的点构成。路径点数目多，难以满足管路的制造要求，因此需要进一步优化[6-10]。尽管国内外学者提出了一系列管路自动布局算法[11-14]，并取得了一些成果，但工程实际中，管路布局还需要考虑整体布局的可行性和最优性，特别是在装甲车辆发动机中存在的布局空间狭小、零部件众多的条件下，管路与管路之间的交叉性、耦合性使得管路布局的先后顺序对布局结果影响较大，如何使整个管路系统的布局达到最优是目前工程中亟待解决的问题。

1 基本A*算法

A*算法以估价函数获得各节点的扩展代价，并从中选择最小代价点进行扩展。节点的估价函数为：

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

(1)

式(1)中，g(n)表示从初始节点S到节点n的最小代价的估计；h(n)表示从节点n到目标节点T的最佳路径的估计代价。A*算法执行过程中也用到Open表和Closed表，其中Open表用于存放刚生成的节点，Closed表用于存放将要扩展或者已经扩展的节点。算法执行步骤为：

步骤1 开始，将起点添加至Open表中。

步骤2 判断Open表是否为空，若不为空，则转步骤3；否则路径搜索失败。

步骤3 考察Open表中具有最小f值的节点n，判断n是否为目标节点，若是则路径搜索成功；否则，转步骤4。

步骤4 生成当前节点n的相邻可行节点n′。若n′为新，则加入Open表中，并设其父节点为n，转步骤2；若n′已在Closed表中，不作任何操作，也转步骤2。若n′已在Open表中，则转步骤5。

2 管路自动布局中的改进A*算法

2.1 管路布局空间栅格化模型

装甲车辆发动机由于管路种类繁多、形状尺寸多样，使得空间不规则，给管路的布局设计带来了限制。本文采用栅格法进行建模，栅格法的实质是将整个布局空间划分为一个三维点阵，它能对布局空间进行精确的表示。为了节约计算机资源，提高算法效率，对于确定的起始点S和终止点T，将管路路径的求解空间围绕起终点进行构造，避免对全空间进行栅格划分。本文采用了正方体几何模型对求解空间进行表达。具体步骤为：

1) 获取以S(xs,ys,zs)和T(xt,yt,zt)为对角顶点的正方体ABCD-EFGH的几何中心O，并计算O到S或S的距离L；

2) 扩展S和S得到H′和B′，其坐标为(xs-λL,ys-λL,zs-λL)，(xt+λL,yt+λL,zt+λL),λ≥1)；

3) 新的正方体求解空间为A′B′C′D′-E′F′G′H′，H′和B′为其对角顶点，如图1(a)所示，显然，新构建的正方体边长为λL。为满足管路与设备间的最小间距dmin要求，设管路的直径为D，则栅格的粒度2a≥D+2dmin，管路布局空间可以划分为[λL/a]×[λL/a]×[λL/a]多个大小相同的正方体，[ ]表示取不大于方括号内的最大整数，如图1(b)所示。λ是为了限定算法的求解空间，减少无用节点的扩展，当该空间内无法找到路径时，可以考虑扩大求解空间，如含障碍陷阱的路径求解，λ可取1.5～3.0。

在完成了管路的路径搜索空间的栅格化模型后，记录栅格节点的信息，主要包含几何信息、归属信息及代价信息这三类，如表1所示。最后采用A*算法完成管路的路径搜索。

2.2 基于方向引导的启发式函数

管路的布局设计不仅要求长度尽量短，还应减少弯头数目。为了能优先选择最优路径上的节点，本文采用结合距离代价、折弯代价和方向引导的启发式函数，如式(2)所示。

(2)

式(2)中，ln为节点n到终点T的距离；N为起点S到节点n的折弯数目；θn为父节点n-1和节点n(n>1)的连线与节点n和终点T连线的夹角；c为单个栅格长度代价，与栅格粒度a相同；W1为折弯与长度代价的转换比；W2为角度与长度代价的转换比，由实验确定。W1与W2决定了搜索的速度与质量，W1取值越大，搜索范围也越大，相应的计算时间也就越长。W2取值越大，搜索范围就越集中。

表1 节点信息组成

2.3 多约束条件下的改进方法

管路布局过程中存在各类约束，其中，安全性约束和贴壁约束是常见的约束形式。基本A*算法并不能直接对该类约束识别，也无法根据约束自动调整路径的搜索。为满足多约束条件下管路自动布局，本文将对算法作针对性改进。

1) 安全性约束下障碍物绕行方法

管路常常要避开滤油器、高温油管等障碍物，这是为了保证布局过程的安全性和导管工作的可靠性。本文在确定危险障碍物前提下，提出建立障碍物的“危险区”，对障碍物建立最小包围盒，并对包围盒进行扩展得到“危险区”，并建立虚拟实体。在进行节点扩展时，处于“危险区”内的节点将是不可行节点，如图2所示。

2) 贴壁约束下节点“吸引”策略

辅助固定是为了便于安装、减小振动等，特别是针对长管路，有必要添加辅助固定平台。添加平台有两种方式：一种是选择平面；另一种是选择障碍物实体。若选择某平面作为固定，如图3所示，定义平面的吸引半径为ρ，算法先获取当前平面的外法向量n，随后将节点沿该向量反向平移ρ个单位，若不发生碰撞，不作任何处理；否则，将当前节点吸引到该障碍物附近(距离为d，d<ρ)得到点Ei，进入子路径的搜索，此时搜索过程变为二维平面，搜索区域是以当前节点为中心，半径为L2的圆(L2是控制点间最小间距)。建立与平面相齐的局部坐标系Ei-UVN，EiT在平面Π的投影直线EiH与圆相交于点Eo，将Eo作为子路径搜索终点，若Eo不可达时，则在小邻域范围内随机选择可行节点作为终点。

对于障碍物实体，如图4所示，为了使路径能够向固定平台靠近，构建辅助固定平台的最小包围盒Ω1:abcd-efgh，将Ω1向外扩展2～3个管径得到扩展包围盒Ω2:ABCD-EFGH，定义ΩA:Ω1≤ΩA≤Ω2为“吸引区”。当扩展的节点进入该吸引区域时，与上类似地进入子路径的构造。子路径构造过程中，子节点的选择范围将限制在该ΩA，当扩展的节点到达距离终点最近的包围盒顶点，子路径搜索完成。子路径是主路径不可缺少的一部分，在获得子路径后，以子路径终点为起点，完成剩余路径的搜索。最后生成的路径由三部分组成，分别是前路径、子路径、后路径，将这些路径顺次连接，即可构成一条可行且满足贴壁约束的管路路径。

3 路径优化方法

3.1 路径节点的筛选

在路径回溯时，不仅存储了路径节点列表，还存储了在各个直线段间的连接点，采用二分法原理筛选路径关键点。二分法的数学原型为：设x1,x2,x3为不在同一直线上的三个点，若x1与x2连线不与障碍物发生碰撞，而x1与x3连线与障碍物发生碰撞，则存在x0∈[x2,x3]使得x1与x0的连线恰好不与障碍物发生碰撞，在给定的精度ε要求下，通过不断对区间二分的方法，最终能找到x0。

管路路径节点的筛选如图5所示。具体执行步骤如下：

步骤1 以1为起点，连接1-4、1-5、1-7均未发生碰撞，连接1-12发生碰撞，取7与12的中位数9；

步骤2 连接1-9，发生碰撞，取7与9的中位数8；

步骤3 连接1-8，不发生碰撞，显然，8是不可缺少的路径关键点，保存8。

步骤4 由于8为“吸引区”的“入口”，12为“吸引区”的“出口”，以8为起点，12为终点，采取相同方法对8-12间的节点进行筛选。

步骤5 在完成“吸引区”内的路径筛选后，返回到主路径的节点筛选过程。取12为起点，连接12-13、12-15、12-16均不碰撞，保存16。从而得到路径的关键点坐标为1-8-12-16，并将这些点将作为管路的初始控制点。

3.2 面向可制造约束的路径优化

在路径优化阶段，本文重点考虑控制点间最小间距约束及相邻直段间的夹角约束。文中根据导管段及导管段之间的相互关系判断约束的满足性，并建立约束违反后的两种处理机制：长度处理机制和角度处理机制。

1) 长度处理机制

2) 角度处理机制

当相邻直段夹角θ1小于90°时，采取添加控制点进行过渡，如图7(b)所示。直段Pi-1Pi与PiPi+1构成平面，过Pi作长度为L2(控制点间距)的垂线PiQi，若不发生碰撞且线段PiQi与QiPi+1构成的夹角θ2满足θ2≥π/2,则添加控制点Qi；否则随机给定Pi-1Pi的垂直向量n，沿n进行扩展得到满足θ2≥π/2的控制点Qi，并添加到控制点列表中，记其为Qi(Pi)，括号内表示新增节点Qi的归属节点为Pi。

在优化过程中，不仅控制点位置发生变化，控制点列表也是动态变化的。这体现在控制点的位置更新或新增控制点时，本文采用“可视图法”删除冗余的控制点，这样既能简化优化过程还能减少折弯数目。此外，针对需要在特定位置固定的导管，可将整个导管在辅助固定导管段的始端和末端进行分割处理，保证每一部分可采用以上机制完成导管的优化过程。为获取较优管路路径，分别采用正向优化和逆向优化相结合的方法。以管长、折弯数和约束违反程度作为评判标准，从中选择一条较为合理的路径作为管路路径。

该优化算法主要包含约束检查和约束处理两大模块，整个优化过程是一个约束检查与约束求解的过程。算法优化的准则是：当前控制点只对未进行约束检查的控制点位置产生影响，而不会对已经优化处理过的点作二次处理。对于不同形式的约束冲突，算法指定了相应的约束处理机制，当该约束不能被求解时，算法将对相应的控制点和导管段进行高亮显示，并提示设计人员进行手动调整。值得注意的是，经过优化后的路径不一定是最短路径，但一定是满足工程约束规则的合理路径。整个系统优化流程如图8所示。

4 应用验证

节选模型发动机的主水管路作为研究对象，管路周围的障碍物如图9所示。管路直径为55 mm，管路与障碍物之间最短距离为6 mm，取栅格粒度为30 mm，对障碍物进行划分，结果如图10所示。

经优化结果如图11所示。其中，管路①为主水管优化后的管路，长度为1 730.89 mm，其附近的黑色阴影管路为原管路，长度为1 835.26 mm。管路②为机油箱管路优化后的管路，长度为700.48 mm，其附近的黑色阴影管路为原管路，长度为693.28 mm。优化后的管路三维模型如图12所示。

5 结论

合理的管路敷设是提高管路敷设效率、降低敷设成本、提高管路系统可靠性的重要途径。现代武器装备多要求在全天候、多地域环境下作战，工作环境越来越恶劣，对装备的功能、性能指标要求越来越高，并要求能够耐受严酷的使用环境。本文研究的基于改进A*算法的装甲车辆发动机管路自动布局敷设技术，解决了装甲车辆型号研制管路系统经验设计中的突出问题，节省了管路布局时间，逐步形成具有指导意义的装甲车辆管路系统自动布局规范，对管路布局优化设计具有一定的军事意义和经济意义。