基于蚁群粒子群融合的多机器人协同路径规划算法

黄 骏，朱 强

(芜湖职业技术学院 智能制造学院，安徽 芜湖 241006)

随着科技的不断发展，智能机器人被应用到工业、物流业、电力行业等越来越多的领域。规划科学合理的避障路径是决定智能机器人作业效率及作业执行效果的关键[1]。多机器人在协同作业过程中，易发生相互碰撞，极大影响作业效率。李洋等[2]基于自适应步长快速扩展随机树的方法提出了一种双臂机器人协同路径规划算法，提高了碰撞检测的有效性。董朝瑞等[3]设计了一种基于预约格栅方法的多机器人动态路径规划算法，提高了仓储机器人协同作业的系统效率。彭湘等[4]通过引入半自由栅格和半障碍栅格概念，融合蚁群算法得到了多地形情况下移动机器人的最佳路径规划。刘剑等[5]以拣货智能机器人为研究对象，结合所设定的能耗与移动间距等目标函数，构建出3层布谷鸟模型，进而得到机器人协同路径规划。该方法虽然可以快速得到不同类型食品拣货机器人规划作业路径，却不能完全避免机器人间的碰撞，协同规划效果不佳。万逸飞等[6]以降低机器人运行耗时、提升路径平滑度等为研究目标,采用多目标及协同算法,对多目标函数的协调路径规划问题进行求解,得到了多机器人协同路径规划。此方法所规划的协同路径虽然在避障与避碰撞方面均表现良好,但所用算法的运算过程过于烦琐,整体规划效率较低。

粒子群算法是通过对鸟群搜索食物的过程实施仿真而产生的一种全局性优化算法，该算法具有搜索速度快、全局搜索性能强、平稳性好等特点，但针对组合优化问题的处理效果稍差[7]。而蚁群算法是通过对蚁群搜索食物的过程实施仿真的一种算法，同时也是一种通过概率搜索最优路径的启发式全局优化算法。该算法搜索最优路径时主要依据路径的信息素与启发函数2种参数值[8-9]。蚁群算法具有收敛性能好、鲁棒性及搜索准确性高等特点，尤其适用于处理组合优化问题，其缺点主要为搜索效率稍差、运算量高、易陷入局部最优等[10]。为此，本研究通过融合粒子群算法与蚁群算法，获得蚁群粒子群融合算法，在暂不考虑机器人间干扰的情况下，确定各机器人全局最优避障路径，再结合多机器人协同作业避碰规则，规划出免碰撞的最佳机器人间协同路径，为多机器人协同作业效率与安全性的提升提供保障。

1 多机器人协同路径规划算法

多机器人协同路径规划要解决的主要问题是避障路径规划和协同作业避碰，最终获得可避障与避碰的多机器人最优协同路径。

1.1 多机器人协同作业的环境建模与机器人约束条件设定

1.1.1 建立多机器人协同作业环境的栅格模型

在规划多机器人协同路径之前，先选用栅格法构建多机器人协同作业环境模型[11]。在建模之前，对相关条件进行设定：

1)各机器人均以1.18 m/s的速度移动；

2)机器人的实际规格不予以考量；

3)以各个栅格的中点坐标作为各自栅格的坐标；

4)当障碍物的大小小于单个栅格时，也视其为一个栅格；

5)机器人的作业运动环境为二维空间。

按上述设定条件创建多机器人协同作业环境栅格模型，其结构如图1所示。

在图1中，白色栅格与黑色栅格分别代表自由区域与障碍物区域，各机器人作业运动时需避开全部障碍物区域，在自由区域内完成作业运动。其中，栅格j与二维空间内的坐标(xj，yj)相对应，将栅格空间内按着横、纵坐标方向的行、列栅格数量设定为Mx与My。将图内左上角第1个栅格设定为首个栅格，其坐标为(0.5,5.5);将首个栅格右侧的栅格依次设定为栅格2～6,并按条件设定栅格的坐标。每个栅格坐标同其序号之间的关联式为

(1)

式中,mod(j/Mx)与cell(j/My)分别为j/Mx的余数和j/My的整数。

栅格经过二维平面化处理后,经由各机器人自身传感器实时采集作业环境信息,通过膨化操作处理作业环境内的各个障碍物,令其占据若干个栅格[12-13]。设Ai(x0,y0)与Qi(x1,y1)为第i个机器人的运动初始点与终点坐标,以栅格信息为依据,在两点之间为机器人查询符合约束条件的最佳路径。按此方法获取全部机器人的最佳路径。

1.1.2 设定机器人约束条件

在规划机器人路径的过程中，需设定位移、避障、结束运动等约束条件[14]。设Bi为第i个机器人的路径，它包含多个栅格序号，即Bi=(bi1，bi2，…，bik)，其中，k为路径中的总栅格数。该机器人最短路径长度Di为

(2)

式中，n为机器人的总数量。

机器人约束条件设定如下：

1)位移约束条件：此约束条件是对机器人的运动方向实施约束，设定其仅可朝向左、右、前、后4个方向产生平面位移运动与暂停，且单次位移运动只能选择一个方向。约束条件表示为

(3)

式中：(xc，yc)为机器人行走至第c步时所对应的坐标，l为常数。

2)避障约束条件：该约束条件是对机器人距障碍物的间距实施约束，约束条件表示为

(4)

式中，(xe，ye)为障碍物栅格的坐标。

3)结束运动约束条件：该约束条件约定机器人抵达目标点时才可以结束路径的搜索。约束条件表示为

(5)

由公式(2)可知，如果机器人由c-2步至c-1步的过程中所行走的步数为1，且不考虑是向前还是向后运动，那么，当机器人由c-1步至c步时，既能够待在原地不动(也就是步数为0)，也能够继续运动1步。但是，如果机器人由c-2步至c-1步的过程中的步数为0时，即机器人待在原地不动，则此时机器人留在此处。

1.2 基于蚁群粒子群融合的多机器人避障路径规划过程

1.2.1 粒子群算法下多机器人最优参考路径预规划

初始阶段任意分布在解区间的一组粒子构成了算法的起始状态，其作用是为了提高后续迭代的效率及效果。在通过粒子群算法预规划各机器人最优参考路径过程中，可采取对各粒子的速度与位置持续更新的方式获得最优解，即各机器人的最优参考路径。粒子位置与速度更新的表达式为

(6)

式中:Xij(t)为第(i,j)个粒子的初始位置,Xij(t+1)为t+1时刻更新后的位置;Vij(t)与Vij(t+1)为粒子的初始速度与更新之后的速度;μ为加权系数;σ1与σ2为学习因子;rand(·)为随机数,且其取值范围为(0,1);hB与Bi j,B分别为当前粒子群的全局最优解与第(i,j)个粒子的最优解。

在建立的栅格模型内,确定障碍物、终点、初始点的坐标,并将各粒子视为对应机器人,对全部粒子的位置与速度、粒子群算法的各参数均进行初始化处理。运用公式(6)持续更新各粒子的位置与速度,连续迭代至最高迭代次数,μ值缓慢降低,实现全局最优解及个体最优解的反复更新调整。得到的最优解即为各机器人的最优参考路径,从而完成了各机器人的路径预规划。

1.2.2 蚁群算法下多机器人全局最优避障路径

(7)

在规划路径过程中，蚂蚁栅格路径的启发函数和信息素浓度这2类参数值可正向决定蚂蚁选择此栅格作为可行栅格的概率。在初始栅格处放置蚂蚁，在公式(7)的基础上，蚂蚁由所处栅格j向之后栅格j+1运动的概率Pj+1的计算公式为

(8)

式中：δj为启发函数，γ为期望启发因子，Ji为蚂蚁所处栅格j的全部后续可行栅格集合，m为该集合的总数量。由此，2个栅格之间路径的启发函数δj，j+1的计算公式为

(9)

式中：Lj，j+1为所处栅格j与可行栅格j+1的间距，ω1为Lj，j+1的权重系数，Lj+1，Q为可行栅格j+1距目标栅格Q的距离，ω2为Lj+1，Q的权重系数。

(10)

(11)

最佳路径上的信息素浓度与迭代次数成正比关系，当达到最高迭代次数之后，结束路径搜索过程，确定全局最优避障路径。

1.3 基于作业避碰规则的多机器人协同路径规划

为有效防止各机器人相互之间的碰撞，需进一步规划出多机器人协同避碰路径，实现多机器人的协同作业。为实现此目标，需设定多机器人协同作业避碰规则[15]，并以此规则得到最佳或者接近最佳的路径组合，即多机器人最佳协同路径，最终实现多机器人协同路径规划目标。

(12)

由此，根据式(2)可完成多机器人协同路径规划。

2 实验仿真与结果分析

以某变电站的多个智能巡检机器人为例，运用本文所提算法对此类机器人巡检作业中的协同路径实施规划，通过规划结果检验本文所提算法的实际应用性能。

从该变电站的智能巡检机器人中抽选出2个尺寸规格相同的机器人A和B,在MATLAB 2017软件环境下进行仿真实验,实验关键参数设定见表1。

表1 实验关键参数设定

在上述实验条件下,先通过本文所提算法创建2个实验机器人协同作业环境的栅格模型(图2)。

2.1 路径规划效果测试

使用本文算法中的基础粒子群算法预规划出各机器人的最优参考路径。预规划效果如图3所示。

注：灰色栅格—机器人的初始点与目标点；灰色实线—机器人A的路径；黑色虚线—机器人B的路径。

以路径预规划结果为基础，继续融合蚁群算法继而获得各机器人的全局最优避障路径，结果如图4所示。

由图3和图4可知，预规划最优参考路径与全局最优避障路径均能够有效避开所有障碍栅格，但预规划的2个机器人的最优参考路径的长度均高于融合蚁群算法规划所得的路径。可见，本文所提算法规划所得的最优避障路径更为理想。

由于运用本文所提算法所得的2个机器人全局最优避障路径存在重合碰撞路径，所以依据作业避碰规则得到2个机器人的最终协同路径规划结果(图5)。

由图5可知,运用本文所提算法最终得到的2个机器人协同路径中,通过令机器人A在黑色实线路径上[坐标范围为(14.5,13.5)～(16.5,13.5)]折返一次,可将2个机器人的重合碰撞路径消除掉,同时未改变最优路径,从而实现了多机器人协同路径规划。

2.2 耗时测试

为进一步检验本文所提算法的综合性能，对规划过程中各阶段的耗时进行统计，结果见表2。

表2 规划过程中各阶段耗时统计结果 单位：ms

由表2可知，本文所提算法对2个机器人路径规划的整体耗时结果相差不大，且平均耗时低于200 ms。

3 结语

在多机器人共同作业情况下，科学合理的多机器人协同路径是保障作业效率与效果的关键。本文以粒子群算法预规划所得最优参考路径作为蚁群算法的信息素加强值，实现了多个机器人最优全局避障路径的规划；在此基础上，为避免协同作业时多个机器人之间产生的相互碰撞，引入作业避碰规则，消除了各机器人协同作业时的碰撞路径，获得了最终多机器人协同路径。实验仿真结果表明，本文所提算法规划效率较高，能保障多机器人协同路径规划的时效性，综合性能表现较好。