基于改进蚁群算法的移动机器人路径规划

2022-11-04周敬东高伟周杨文广戚得众周天

科学技术与工程 2022年28期

周敬东，高伟周，杨文广，戚得众，周天

(1.湖北工业大学机械工程学院，武汉 430068； 2.湖北工业大学农机工程研究设计院，武汉 430068； 3.武汉沐沃霖科技发展有限公司，武汉 430068)

随着机器人技术的迅速发展，移动机器人受到各领域广泛的应用。路径规划作为机器人行走的重要部分[1-2]。迄今为止，中外研究人员对移动机器人的路径规划算法开展了大量的研究[3]，如遗传算法[4]、神经网络算法[5]、粒子群算法[6]、蚁群算法[7]、A*算法[8]以及Dijkstrta算法[9]等各类算法。由于蚁群算法的鲁棒性强和自组织性好，并且是一种并行算法，被广泛应用在机器人路径规划问题[10]。

针对蚁群算法出现的收敛速度慢、易发生死锁等不足，许多研究人员提出了大量的解决对策。袁福龙等[10]通过构造数学模型、引入区域安全信息函数和转角启发信息函数等策略，采用“狼群分配策略”方法避免陷入局部最优和加快最优路径的收敛，能够有效避开静态和动态环境中的障碍物而迅速找到一条较平滑的最优路径。曹新亮等[11]通过在栅格地图中划出优选区域对初始信息素浓度差异化设置，尽管建立新的数学模型能有效地加快算法前期搜索的速度和减少了最优迭代次数，但是算法建立复杂的数学模型以及选取比值节点会很大地增加了算法的运算量和运行时间。史恩秀等[12]针对蚁群算法中的启发因子α等主要参数对路径规划效率的影响进行了仿真实验分析，综合考虑找到了改进蚁群算法最佳匹配参数。牛龙辉等[13]通过引入自适应信息素挥发系数方法解决中寻优能力不足和算法多样性低等问题，以加强全局寻优能力，提高了算法多样性。以上学者在蚁群算法理论方面做了研究改进，对算法做了优化，具有一定的适用性，但对机器人实际运行效果研究较少，依然需要进行优化算法，提高改进蚁群算法的实用性。

为了优化路径规划，在已有的研究基础上，提出一种新的蚁群算法，改变原有的初始信息素分配方式为阶梯分配，融合A*算法作为路径搜索的启发式信息改进启发函数，加强最优解对蚂蚁的吸引力,设置蚁群回退策略，避免蚁群陷入“陷阱”后无法退回，引入蚂蚁优化排序，使算法路径规划更短、迭代次数更少的理想效果。通过MATLAB 软件仿真和使用树莓派六足机器人实验，期望改进后的蚁群算法在路径长度、迭代次数和转折点数等方面性能优越于传统蚁群算法。

1 蚁群算法

1.1 基本蚁群算法

蚁群算法是由一种基于种群的启发式随机搜索算法[14]。蚁群在觅食的过程中，起点从蚁巢位置，食物位置为终点，通过多次搜索行走路径，在已走的路径上留下信息素[15]，避开障碍物选择最佳路径行走。蚁群觅食过程如图1所示。

图1 蚁群觅食过程Fig.1 Ant colony foraging process

1.2 改进的蚁群算法

1.2.1 初始化信息素浓度的改变

传统蚁群算法初始化信息素浓度是采取均匀分配在各个栅格的方式，这样会降低蚂蚁的搜索效率。蚁群在行走路径的过程中，每只蚂蚁是从起点出发搜索选择最短路径到达终点。为了避免蚁群在寻优路径中出现“原地不动”现象，通过设置信息素轨迹量在[τmin,τmax]这个区间，合理安排路径上的轨迹量，有利于避免初期盲目搜索的行为。故在设定信息素浓度矩阵Tau时，在起点与终点的最短路径以及周围路劲信息素值按照逐渐递减方式设定。这样可以有利于蚁群在初期对最优路径方向搜索，有效地提高了收敛速度。

1.2.2 启发函数的改进

传统蚁群算法中启发函数ηij(t)=1/dij(其中dij为栅格节点i,j之间的距离)表明蚂蚁从节点i行走至栅格j的期望程度与节点之间的距离相关联，在运行过程中，出现迭代次数过少且无法找到最优路径，算法耗时比较长，导致收敛速度较慢[16]。针对此缺陷对启发函数进行改进，融合A*算法作为路径搜索的启发式信息，从而获得较好的路径。已知A*算法的评价函数表达式为

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

(1)

式(1)中：f(n)为由起始点到达结束点的总代价值；g(n)为f(n)的前一部分代价，即起始点到当前点的代价；h(n)为f(n)的后一部分代价，即当前点到结束点的代价。

改进后启发算子ηij(t)为

(2)

改进后的启发函数提高了算法的有效性，提高了算法的寻优能力，大大减少了算法收敛时间，使蚁群朝着最优路径方向快速搜索前进。

1.2.3 蚁群回退策略的设置

为了避免蚁群在行走的过程中陷入H形、U形等障碍后没有选择的地步，采用蚂蚁回退策略来应对。通过加进蚂蚁回退策略，使蚂蚁进入“陷阱”后，有能力摆脱困境，发挥蚂蚁的搜索作用，完成搜索任务。图2为U形障碍物的栅格地图，当一只蚂蚁到达N10位置时,这只蚂蚁无法前进，此时被迫需要退回N7位置，同时要更新禁忌表记录的蚂蚁k当前已走过的位tabuk中的数据，删除N10位置信息，然后在选取合适路径行走，假如这只蚂蚁仍然无法前进，则选择继续回退，这只蚂蚁仍需从tabuk中删除N7位置信息，蚂蚁回退到N3位置，重新选择前进路径。

蚁群回退策略的设置，使蚂蚁在前进搜索过程中摆脱“陷阱”困境，充分发挥每只蚂蚁的搜索作用，大大增强了算法的健壮性以及蚁群对环境的适应能力。

黑色阴影栅格为障碍物；带数字栅格为蚂蚁可通行区域(无障碍)，其中数字表示位置顺序，如“1”表示N1图2 U形障碍物的栅Fig.2 Grid map of U-shaped obstacle

1.2.4 优化排序的引入

为了加快蚁群找到最优解速度，在每次蚁群完成行走路径后，标记信息素最优解[17]。每只蚂蚁完成路径搜索后，蚂蚁行走的路径长度不同。在修改信息素路径前，按照蚂蚁的长度由短到长进行排序L1≤L2≤…≤Lm，每只蚂蚁释放的信息素量和排名相乘。已知在每次循环中，只有排名前h-1位的蚂蚁和精英蚂蚁才允许在行走路径上释放信息素[18]。已知的最优路径给以最强的反馈，和系数h相乘，排名第k位的蚂蚁则乘系数h-k。则信息素表达式为

(3)

(4)

(5)

式(5)中：Lbs为已知最优路径Tbs的长度。

2 算法运行流程

2.1 环境建模

环境建模有栅格地图法和数字序列法等方法，使用栅格法建立移动机器人的环境模型[19]。栅格法采用“0”“1”表示栅格地图中有无障碍，0表示此处无障碍物，机器人可以自由通过，1表示此处有障碍，机器人无法通过。设置移动机器人的移动范围为20×20大小的栅格方形，单位长度为1，如图3所示。

S为起始点；E为目标点图3 20×20栅格地图Fig.3 20×20 grid map

机器人前进必须占用栅格，考虑到移动机器人在真实环境下会有很多方向可供选择，为了简化移动方向，规定机器人停在每个活动区域的中心点为准，每一步移动可供参考的方向只有8种，分别为左前、左后、右前、右后4个斜方向和前后左右4个直行方向。机器人的移动方向，如图4所示。

图4 机器人移动方向Fig.4 Direction of robot movement

2.2 算法执行步骤

蚁群算法应用于机器人路径规划时主要由初始化、解构建和信息素更新三部分组成[15,20-21]。参数初始化主要对时间、循环次数、信息素、迭代次数等参数设置初始值。蚂蚁根据状态转移概率公式计算出的概率选择元素j并前进，最终完成搜索路径到达目标点[21]。通过不断修改禁忌表指针和更新每条路径上的信息量方法，找到一条最优行走路径。蚁群算法的执行步骤流程图，如图5所示。

图5 蚁群算法的执行步骤流程图Fig.5 Flow chart of the execution steps of ant colony algorithm

(6)

式(6)中：Jk={1,2,…,n}-tabuk为蚂蚁k在下一步可以选择的位置集合，其中tabuk为禁忌表记录的蚂蚁k当前已走过的位置；ηij为一个启发因子，表示蚂蚁从位置i转移到位置j的期望程度；α为信息素的相对重要程度；β为期望启发因子的相对重要程度；τij为栅格节点i,j之间的信息素浓度；τis为位置点i到初始点的信息素浓度；ηis为位置点i到初始点的启发函数。

在所有蚂蚁完成一次从起点到终点后，各路径信息素开始更新，信息素更新公式为[18]

τij(t+n)=(1-ρ)τij(t)+Δτij

(7)

式(7)中：ρ为路径上信息素的蒸发系数，0<ρ<1；1-ρ为信息素的持久性系数；Δτij为本次迭代中边ij上信息素的增量。

Δτij可表示为[18]

(8)

(9)

式(9)中：Q为正常数；Lk为第k只蚂蚁在本次迭代中所走过路径的长度。

3 仿真与评价

为了验证算法优化后的效果，在MATLAB 2016a上对改进蚁群算法进行多次仿真，与传统蚁群算法作对比分析。利用已建成20x20的栅格地图运行程序，设定机器人初始坐标为(0.5，19.5)，终点坐标为(19.5，0.5)。程序仿真参数设置如表1所示。

图6、图7分别为在传统蚁群算法和改进蚁群算法仿真的路径轨迹和迭代次数结果。

由图6可知，传统蚁群算法在初期无法确定搜索方向，盲目性大，迭代次数高达40次以上，最短路径长度为32.5。

由图7可知，改进蚁群算法的搜索效率较高，迭代次数少于40次，最短路径长度只有29.2。分析表2数据可知：所提的改进蚁群算法在多方面评价参数优于传统蚁群算法。

表1 参数设置

图6 传统蚁群算法Fig.6 Traditional ant colony algorithm

为验证所提出的改进算法的先进性和有效性，通过创建带有不同的障碍物栅格环境(20×20)，进行多次仿真验证。表3为随机选取6组在不同的障碍物栅格地图环境对两类蚁群算法仿真的结果。

通过对6组带有不同的障碍物环境仿真结果分析可以得出，改进蚁群算法的迭代次数平均减少了30.24%，规划出的路径平均缩短了9.03%，运行时间平均减少了16.19%。仿真结果表明，改进蚁群算法的路径规划长度与传统蚁群算法相比更短，迭代效率更高效，尤其在大尺寸地图和障碍物多的情况下。

图7 改进蚁群算法Fig.7 Improved ant colony algorithm

表2 蚁群算法改进前后仿真结果对比

表3 两类蚁群算法仿真结果

4 实验

为了验证改进的蚁群算法仿真结果的正确性以及体现改进算法在实际应用中的实用性和有效性，采用树莓派(SpiderPi)六足机器人为研究对象[20]。为了有效地对作业环境进行全局把控，本次实验采用人工拍摄的方式提前将机器人的行走环境采集，达到全局监控的效果。树莓派(SpiderPi)六足机器人，如图8所示。

实验环境如图9所示，实验场地为3 m×3 m的方形环境地图。在实验环境内，六足机器人处于起始位置，有各种障碍物分布，从起点爬行到终点。实验环境处理后为边长为15 cm、大小为20×20的栅格模型环境，如图10所示。

设定六足机器人的起始位置为(0.5，19.5),终点位置为(19.5，0.5)。把改进后的蚁群算法和传统蚁群算法分别应用在六足机器人的开发板中，让机器人自主寻找路径行走。在两种蚁群算下行走的路径轨迹如图11、图12所示。