基于改进蜂群算法的桥式起重机吊装路径规划*

陈志梅 李孟笑 邵雪卷

太原科技大学电子信息工程学院 太原 030024

0 引言

桥式起重机因其操作灵活、占地资源少和负载能力强的优势而被广泛应用于工厂仓库、港口码头等地，但恶劣的工作环境以及部分不规范的人工操作，使桥式起重机在三维环境中的吊装存在安全隐患。为使桥式起重机能在各种复杂环境完成自动运行，完成吊装任务，路径规划也被逐渐应用到桥式起重机自动运移课题中，故研究桥式起重机三维吊装路径规划具有重要意义[1]。

路径规划是指在存在障碍物的空间中，按照一定评价标准在起始点和终点之间找到一条安全碰撞且最符合评价标准的路径[2]，路径规划算法被应用到机器人、车辆、无人机、起重机等各领域，算法主要有快速扩展随机树(Rapidly—exploring Random Tree，RRT)算法、蚁群算法、遗传算法等。Zhao Y T等[3]对起重机在板库中的路径规划，用网格法对环境建模，通过整合转折点、筛选候选解、动态挥发信息素等对蚁群算法改进，得到起重机安全吊装路径。Cai P P等[4]将起重机路径规划问题转化为包含隐式约束的多目标非线性整数优化问题，设计主从并行遗传算法，优化提升路径的能量成本、时间成本，在复杂环境下生成高质量路径。陈志梅等[5]对桥式起重机在三维复杂环境下的路径规划问题，将RRT算法和粒子群算法相结合，得到符合桥式起重机运行条件的安全路径。Dutta S等[6]基于并行化方法进行碰撞检测和路径规划，并提出路径重新规划策略，解决塔式起重机在含有动态障碍物环境下的路径规划。Lin Y S等[7]对履带起重机进行路径规划，改进RRT算法，从采样池和未开发空间选取样本，引导树向无障碍空间移动，改进树扩展策略，在较短时间内生成无碰撞路径。魏云平等[8]在栅格地图中，将路径拐点数转化为长度，使用遗传算法得到用时较短的二维空间路径。马向华等[9]在传统A*算法中引入节点方向信息启发函数，并加入转向代价函数，规划出的路径拐点少，使之符合桥式起重机运行约束条件。

上述文献对起重机路径规划的研究中所规划出的路径是在固定起重机吊装高度的基础上得到的，忽视障碍物高度而进行路径规划，对所有障碍选择绕行，既浪费吊装时间，所得路径也并非最短，路径拐点也较多。由于实际中障碍物形状、大小、高度不一，起重机吊装高度选择不易确定，且如果每次吊装高度选择最高值并不符合实际吊装。因此，本文在不固定起重机吊装高度的基础上，在三维已知环境中对桥式起重机的智能吊装避障进行研究。

采用空间等分网格法建立三维环境，对环境中凹形障碍作虚拟填充处理，防止规划的路径穿越凹形障碍物。由于人工蜂群算法具有控制参数少、通用性强、易与实际问题结合的特点，已广泛应用于路径规划领域[10，11]、函数优化、信号处理等方面，故选用人工蜂群算法进行已知环境下的起重机路径规划。并对算法进行改进，在观察蜂阶段引入轮盘赌与反轮盘赌并行选择机制，防止算法陷入局部最优，加入节点筛选规则，剔除冗余节点。最后以剩余节点和起始点、目标点为控制点，以不与障碍物碰撞为约束，使用多段Bezier曲线进行平滑优化。为符合实际安全吊装，在算法中还加入障碍物高度判断策略，使算法智能选择绕行或跨越障碍，规划出的路径与障碍物留有间隔裕量，使桥式起重机能安全运行，然后通过仿真验证该方法在桥式起重机安全吊装路径规划上的可行性。

1 三维空间地图建立

在实际中，进行路径规划前要求计算机获得障碍物先验信息，然后使用算法进行路径规划。为模拟三维环境，采用空间等分网格方法，在规划空间建立三维坐标系，并沿x轴、y轴、z轴等分，使空间中任意障碍物都可由三维点集合表示，算法规划出的路径也可由点集合表示出来。为便于仿真，假设x轴、y轴跨度为50 m，z轴高度设置为15 m，设置起始点坐标为(25，0，5)，目标点为(25，50，5)，所建环境如图1所示。

图1 桥式起重机安全吊装规划空间

2 ABC算法

ABC算法是国外学者在2005年提出的基于蜜蜂采蜜行为的启发式算法。算法应用于路径规划领域，其蜂群采蜜行为与路径优化关系对应；蜜蜂采蜜行为对应路径规划问题，蜜源的位置对应可行路径，蜜源的花蜜量对应可行路径质量，寻找花蜜速度对应可行路径优化速度，最大花蜜量对应最优路径。使用人工蜂群算法进行路径规划的基本步骤为：

1）初始化算法参数，设置适应度函数。初始蜜源数N、算法最大迭代次数maxcycle及最大限制次数limit。初始迭代次数iter=1，初始蜜源适应值不变时的限制次数trial=0。计算各蜜源适应度值，并记录最优值，即有

式中：j为D维解向量的某个分量，j={1，2，…，D}；为第j维的上下限；rand(0，1)为[0，1]之间随机数。

2）采蜜蜂搜索方式为每只采蜜蜂按式(2)到蜜源附近搜索，并计算蜜源新适应度值，若优于当前蜜源，依贪婪准则，更新当前蜜源。否则令trial=trial+1。若trial＞limit，该采蜜蜂放弃此蜜源，并转化为侦查蜂，在全局范围内搜索新蜜源。

3）各观察蜂按式(3)选择要跟随的采蜜蜂，选择后观察蜂转化为采蜜蜂继续按式(2)在蜜源附近搜索，若新蜜源优于当前蜜源，依贪婪准则更新当前蜜源，否则令trial=trial+1。若trial＞limit，该采蜜蜂放弃此蜜源，并转化为侦查蜂，在全局范围内按式(4)搜索新蜜源。

式中：f iti为第i个解对应的适应度值，为所有解适应值的和。

4）记录蜂群找到的最优蜜源，保存最优解。

5）迭代次数增加：iter=iter+1，若iter＞maxcycle，记录最优蜜源代表的路径节点，并跳转到Step6，否则跳转到步骤2）。

6）在三维空间表示出最佳路径。

3 改进ABC算法

1) 在标准ABC算法中，在观察蜂选择要跟随的采蜜蜂时，依式(3)选择要跟随的采蜜蜂，这易使算法陷入局部最优。本文在观察蜂选择阶段，以轮盘赌与反轮盘赌并行选择机制代替观察蜂选择方式。首先得出每个采蜜蜂的适应度值占总适应值的概率值，将这些值从0开始依次累加，每累加一次即记录一次值，并将值记录在一个矩阵中，即并随机产生一个[0，1]内的随机数rand1，随机数值落在Q的区间，观察蜂就跟随此区间对应的采蜜蜂进行邻域搜索，得到新适应值并记录。接着计算每个采蜜蜂适应值倒数占采蜜蜂适应度值倒数之和的概率值，依次累加并记录，得到随机产生[0，1]的随机数rand2，记录数值落在哪个区间，观察蜂跟随对应的采蜜蜂进行邻域搜索，得到适应值并记录，得到的2次新适应值与原适应值互相比较，保留适应值最小的。

此机制以并行选择优势，既避免了原算法陷入局部最优，又能以更少的迭代次数找到全局最优解。

2) ABC算法在规划路径时，一个蜜源代表一条路径，每条路径由若干路径节点有序连接组成，节点过多则路径拐点会较多，节点过少则路径会穿越障碍，两者均不符合规划要求。因此，在算法中加入节点筛选规则，使算法能智能排除冗余节点，优化路径。

节点选取规则为：定义距离d，从起点开始计算当前点到下一点的距离与下一点到终点的距离，当前点为(xa,ya,za),下一点为(xb,yb,zb),终点为(xc,yc,zc)。满足式(5)时，再计算式(6)，式(6)确保下一点位于当前点前方且靠近终点。在前点d的范围内，所有优化点均可作为下一点的可行解，此时取Dn值小的点作为下一点，Dn值越小，该点到当前点和终点加权最优。以此规则控制节点的选取，进行二次路径优化。

3)二次路径优化后，节点数减少，但路径仍存在较多拐点，需对优化后的路径进行平滑处理，进行第三次优化。本文将蜂群算法与三次Bezier曲线结合，将算法生成并二次优化的路径节点作为Bezier曲线的控制点，利用多段三次Bezier曲线将节点组成的路线转换成光滑曲线，并以不与障碍物碰撞为约束条件，对路径进行三次优化。

三次Bezier曲线的定义为

式中：pi为第i个控制点坐标。

多段三次Bezier优化路径时，曲线方程为

4 桥式起重机路径规划

本文针对桥式起重机智能安全吊装进行路径规划，首先建立三维空间模型，然后使用改进ABC算法进行路径规划。考虑到人为吊装时不能每次都将重物起升到最高处再进行吊装运行，或通过固定起重高度的方式来运行起重机，应在算法中加入障碍高度判断策略，针对障碍物不同高度，起重机可智能选择跨越或绕行。在吊装高度高于障碍物时，留有安全裕量情况下的起重物将直接越过障碍；在吊装高度低于障碍物时，为安全起见起重机设置上升高度阈值，在高度阈值内，若起重机上升能高于障碍物并留有安全裕量，则跨过障碍物，否则选择绕过障碍物。加入障碍高度判断策略规划出的路径，存在高度维度变化，能解决因固定吊装高度而多次绕行障碍物，导致规划的路径不是最短路径的问题。

由于桥式起重机吊装是由大小车协同吊装，路径若存在过多拐点，大小车需频繁制动，这对桥式起重机寿命影响较大，所以要求规划出的路径平滑，本文将ABC算法和Bezier曲线结合，使得到的路径平滑，满足桥式起重机吊装路径要求。规划出路径后，起重机根据路径进行轨迹跟踪，到达目标点。

本文算法所选择的适应度评价值为路径长度，即

式（9）为相邻2个三维坐标间的距离，式（10）为所有路径节点间距离之和。改进ABC算法流程图如图2所示。

图2 改进ABC算法流程

由于环境地图中存在凹形障碍物，且本文算法中一个蜜源代表一条可行路径，凹形障碍会导致规划路径穿越障碍物，导致路径规划失败。本文对凹形障碍作虚拟填充处理，算法在判断时将凹形障碍可行空间视作障碍空间处理，使规划路径不会穿过此凹形障碍物，如图3所示。

图3 凹形障碍处理前后路径

5 仿真研究

设置三维地图x轴、y轴、z轴跨度分别为[0，50]、[0，50]、[0，15]。地图中障碍物包含1个三棱锥、2个三棱柱、1个五棱柱、1个六棱柱、1个长方体、4个圆柱、1个球体、3个凹形障碍。

在算法中，经过多次参数调整，参数设置为：蜜源数N=20，采蜜蜂和观察蜂各为20只；算法最大迭代次数maxcycle=200，采蜜蜂在同一蜜源处最大搜索次数limit=10，初始路径节点数m=49（不包括起点和终点），经过多次仿真测试，设置d=7.1，且为了起重机吊装安全，要求规划的路径与障碍物之间留有间隔，起重机跨越障碍时的高度不能大于9 m。

标准ABC算法所规划路径如图4所示。路径是由包含起点和终点在内的51个节点有序连接组成，路径长度为75.22 m，且路径拐点多，不平滑。

图4 标准算法路径

本文将粒子群算法应用到此三维复杂环境中进行路径规划，作为比较。其中粒子群算法的参数经过多次仿真测试，选择加速因子c1和c2分别为2，粒子数为200，权重系数w为0.4，评价函数和节点数、迭代次数与标准蜂群算法一样，仿真得到路径如图5所示。

图5 粒子群算法路径

图5中，路径由包含起点和目标点在内的51个节点构成，路径长度为79.24 m，规划路径与障碍物无碰撞，但路径拐点多，与标准蜂群算法一样有冗余节点。

改进ABC算法路径规划一次优化后如图6所示，首先得到节点数为51的路径，其长度为67.09 m，二次优化后剩余16个路径节点，对这16个路径节点组成的路径，以不与障碍物碰撞为条件，经过7段三次Bezier曲线的第三次优化，路径更为平滑，最终所得到的路径长度为58.79m，图7为最终规划路径。图8为标准算法、粒子群算法与本文算法的路径节点都为51时的路径长度变化值。

图6 改进算法初始路径

图7 改进算法最终路径

图8 路径长度曲线变化图

图8比较了粒子群算法、标准蜂群算法、本文算法路径节点均为51、迭代次数均为200时的路径长度变化值，粒子群算法达到最短路径时的迭代次数为127次，标准蜂群算法迭代次数为115次，本文算法迭代次数为57次，且路径更短。改进后的算法能更快收敛。

为验证算法的稳定性，将标准ABC算法、粒子群算法和本文算法各运行数次，从中挑选10组路径长度数据对比，如表2所示。表2数据表明，改进的蜂群算法比原算法和粒子群算法规划的路径更短，且算法更加稳定。

表2 路径长度对比表 m

6 结论

本文给出一种适合桥式起重机在三维已知静态环境下的路径规划新方法。在建立的三维地图模型基础上使用改进人工蜂群算法进行路径规划。改进后的蜂群算法避免了算法易早熟收敛的问题，也改善算法应用于路径规划领域的节点冗余导致的拐点较多的问题，算法还与Bezier曲线结合，使路径更加平滑，仿真证明了改进算法应用于起重机路径规划领域的优越性。算法不仅可以应用于起重机路径规划，还可以用于无人机、车辆、机器人等路径规划。本文改进算法仅适用于已知环境，并不适用于存在动态障碍物的环境中，未来研究方向是把蜂群算法扩展求解更加复杂环境下的路径规划问题。