李晓静， 余东满

(河南工业职业技术学院/河南省柔性制造重点实验室，河南南阳 473009)

果蔬采摘机器人是一种集机器人技术与自动化技术于一体的新型多功能农业机械设备，因具有解决劳动力不足、改善农业生产环境、提高作业质量和作业效率等优点，故被广泛应用于现代农业生产中。实际应用中，果蔬采摘机器人如何在复杂多变作业环境中，特别是多丘等特殊地理面貌中，能够快速选择最佳路径实现安全避障完成作业任务，这就涉及到果蔬采摘机器人路径规划问题[1]。针对果蔬采摘机器人路径规划难题，国内外学者经多年攻关研究，相继提出了多种有效算法，如果蝇算法[2]、蝙蝠算法[3]、粒子群算法[4]、A*算法[5]、遗传算法[6]、狼群搜索算法[7]及蚁群算法等。

果蔬采摘机器人路径规划问题属组合优化NP难题，具有问题求解复杂度高、可行解搜索空间大等特点，高效求解该问题仍存在较大挑战，而蚁群算法(ACO)已被证明具有分布计算、信息正反馈、强鲁棒性、强全局寻优能力及易与其他仿生算法融合等特点[8]，且试验证明该算法在一些优化组合问题求解中能取得较好效果，受其影响，最近几年学界学者开始尝试用蚁群算法解决机器人路径寻优问题，如周凌云等在原蚁群算法基础上，设计了一种多启发式信息蚁群优化算法，并用该算法解决了取样送检路径规划问题[9]；Li等利用改进蚁群算法求解了移动机器人全局路径规划问题[10]；游晓明等通过引入一种动态搜索诱导算子改进原蚁群算法，并用改进蚁群算法求解了复杂环境中的移动机器人路径规划问题[11]。

传统蚁群算法会因收敛速度过快及正反馈机制引起的自催化现象而导致算法出现早熟收敛或停滞问题，此外，面对大规模复杂组合优化问题，该算法会存在收敛速度慢、易陷入局部最优及出现早熟收敛等问题，为克服上述缺陷，Yu等通过更改启发函数因子及构建自适应信息素挥发系数对原蚁群算法进行改进，并将改进算法用于求解移动机器人路径规划问题，结果显示，改进算法的收敛速度及搜索效率得到明显改善[12]；饶楚锋等通过自适应调整残留信息素权重因子、启发式信息素权重因子，更改信息素更新方式及引入双向搜索策略对原蚁群算法进行改进，有效提高了算法收敛性能和全局寻优能力[13]。本研究将改进蚁群算法用于求解果蔬采摘机器人路径规划问题，为了使路径搜索更具目的性，设计了新的启发函数因子，并以此为基础，修正了状态转移规则。同时由于原信息素更新规则易使算法陷入局部最优，为增加路径选择多样性，避免算法出现早熟收敛或停滞问题，通过设计新的精英策略和引入新的信息素更新策略对信息素更新规则进行了改进。

1 建立环境模型

研究果蔬采摘机器人最优避障路径规划问题前，需先创建所需环境模型。环境模型建模方法有多种，主要有可视图法、自由空间法、拓扑法和栅格法，相比于其他3种建模方法，栅格法具有建模复杂性低、建模精度高、障碍环境建模适应能力强及易于实现和存储等优点型[14]，故选用栅格法创建果蔬采摘机器人工作环境模。建模前，需对果蔬采摘机器人和其工作环境作如下假设：(1)工作环境为二维静态矩形有限空间，且空间尺寸数据已知；(2)环境模型中仅存在类似小丘陵的静态障碍物，且障碍物形状需根据机器人外形尺寸按一定比例进行膨化处理；(3)为简化问题复杂度，可忽略机器人外形尺寸，用其中心点表示；(4)果蔬采摘机器人工作期间速度恒定，且可在匀速行驶和暂停2种工作模式切换；(5)机器人可由当前位置沿着上、下、左、右、左上、左下、右上和右下8个方向移动，但实际移动方向还需根据相邻位置是否存在障碍物来决定。

栅格法建立的果蔬采摘机器人工作环境模型，为一个复杂多变且有障碍物的多丘场所，如图1所示，采用序号法按照从左向右、自上至下的策略对每个栅格进行编码。坐标系左下角为坐标原点，以原点为起点，水平向右为x轴正方向，竖直向上为y轴正方向，单个栅格尺寸由机器人单位步长及工作区域决定[15]。白色栅格被抽象为可行区域，即果蔬采摘机器人在此区域可自由移动，黑色栅格被抽象为障碍物(可用1个或多个栅格表示，当障碍物所占位置不满足1个栅格时，需按照1个栅格处理)，表示此区域不可通行，点S和E分别表示机器人的起、止位置。

2 改进蚁群算法设计

2.1 基本蚁群算法

在觅食过程中，蚂蚁间信息传递和路径选择的媒介是其遗留在采摘移动路径上的信息素，该物质会随时间推移而逐渐挥发，当后继蚂蚁经过该采摘路径时，路径上信息素浓度就会变高。在路径搜索初期阶段，由于路径上并无残留信息素，此时蚂蚁依据状态转移概率大小决定行进方向，后继蚂蚁则可根据前者遗留在路径上的信息素浓度高低，并综合状态转移概率选择路径。当路径信息素浓度越高时，后继蚂蚁选择该路径概率就越大，反过来也会促进该路径信息素浓度的增加，蚂蚁间正是依靠这种物质进行信息交互并最终搜索出蚁巢和食物间的最优路径。行进中，蚂蚁k由网格i转向网格j的概率可由函数式(1)计算得到[16]：

(1)

式中：allowedk表示蚂蚁k下一步待访问网格集，此集合不包含障碍网格；τij(t)表示蚂蚁k在网格(i，j)间路径上遗留的信息素量，它会随时间推移而逐渐挥发；ηij表示启发函数因子，由网格(i，j)间距离决定，表达式为ηij=1/dij，dij表示网格(i，j)间距离；α和β分别表示τij(t)和ηij(t)对蚂蚁状态转移概率的影响权重因子。

蚁群遗留在路径上的信息素会随时间推移而逐渐挥发，后继蚂蚁经过该条路径又会带来新的信息素，因此，当种群中所有蚂蚁在完成一次循环搜索后，都要利用函数式(2)对路径上的信息素进行更新[17]：

τij(t+1)=(1-ρ)·τij(t)+Δτij(t,t+1)；

(2)

(3)

(4)

式中：τij(t)和τij(t，t+1)分别表示搜索路径上信息素更新前后的浓度；Δτij(t，t+1)表示本次迭代所有蚂蚁遗留在搜索路径上的信息素总量；ρ表示信息素挥发系数；Lk表示本次循环蚂蚁k搜索到的路径的长度；Q表示信息素强度。

2.2 改进蚁群算法

实际问题求解中，相比于其他智能仿生算法，蚁群算法虽然能展现出诸多优势，但面对大规模复杂问题求解时，也存在诸多问题，如收敛速度慢、收敛性能不稳定、搜索效率偏低、易陷入局部最优解，易出现早熟收敛或停滞及达不到特定任务要求等。为了解决上述问题，本研究分别从状态转移规则和信息素更新规则入手，对基本蚁群算法作了如下改进。

2.2.1 状态转移规则改进 在路径搜索初期阶段，由于可行路径上无任何残留信息素，蚂蚁对下一节点选择的随机性比较强(路径选择盲目性比较大)，若因节点选择的盲目性而引起搜索方向出现较大偏差，则会导致算法出现搜索效率低、易陷入局部最优等问题。针对此类问题，综合考虑搜索路径上当前节点、下一节点和目标节点间的几何关系，设计了新的启发函数因子，具体如函数式(5)所示。

(5)

式中：节点i、j和g分别表示蚂蚁的当前网格、下一网格和目标网格；(xj，yj)和(xg，yg)分别表示网格(j，g)中心点的坐标；djg表示网格(j，g)间距离。

将设计的启发函数因子(5)代入函数式(1)，可得新的状态转移规则，具体如函数式(6)所示。

(6)

2.2.2 信息素更新规则改进 路径搜索中，蚂蚁经过一条路径后会释放一定量的信息素，后继蚂蚁会根据信息素浓度强弱自动调整状态转移概率，进而选择路径。基于这种正反馈机制，为了改善算法收敛性能，提高搜索效率，使蚂蚁搜索范围尽可能快地集中在最优路径附近，对信息素更新规则作了如下改进：

2.2.2.1 信息素局部更新 为了增加路径选择多样性，避免算法出现早熟收敛问题，故在蚂蚁每完成1次网格选择后，需按照函数式(7)对访问路段上的信息素进行局部更新：

τij(t+1)=(1-ρ)·τij(t)+ρ·τ0。

(7)

式中：τ0表示初始信息素量。

2.2.2.2 精英策略设计 蚂蚁系统中，精英策略思想是找出目前为止所能搜索到的最优解，并通过奖惩机制为其额外增加一定量的信息素，而后诱导后继蚂蚁路径搜索进程，最终使蚂蚁更好、更快地获取全局最优解[18]。受带精英策略蚂蚁系统影响，为了改善算法收敛性能和增强全局寻优能力，设计了新的精英策略，具体如函数式(8)所示。

(8)

式中：Δτ*表示每次循环最优采摘路径上信息素的额外增量；υi是变量，表示每次循环选取的精英蚂蚁数量，取值与每次循环所获取的最优采摘路径的个数一致；Lib表示本次循环所获取的最优采摘路径的长度；Q1为常数。

2.2.2.3 信息素全局更新 为了使蚂蚁搜索范围主要集中在当前迭代为止所能搜索到的最优采摘路径领域内，当本次迭代中所有蚂蚁均完成路径搜索后，需采用函数式(9)对搜索路径上的信息素作全局更新：

(9)

2.3 算法实现步骤

采用改进蚁群算法求解果蔬采摘机器人路径规划问题的具体步骤如下：步骤1：根据模型尺寸规格，采用栅格法建立果蔬采摘机器人工作环境模型；步骤2：初始化算法各参数，包括最大迭代次数Nmax、蚂蚁数量m、初始信息素量τ0等，并根据任务要求，为机器人设置路径规划的起点和目标点；步骤3：将蚁群中m只蚂蚁置于果蔬采摘机器人工作起点位置，算法开始迭代搜索；步骤4：行进中，蚂蚁由当前网格i向下一网格j转移的概率可由函数式(6)计算得到，待网格j确定后，采用函数式(7)对蚂蚁刚经过的路段(i，j)上的信息素进行局部更新；步骤5：判断所有蚂蚁是否完成本次循环搜索，若是，则找出本次循环最优采摘路径所对应的ID编号，并计算出精英蚂蚁总量，否则，算法搜索过程转至步骤3；步骤6：由步骤5所得数据，结合函数式(8)对最优路径上的信息素进行额外奖励；步骤7：由步骤6所得数据，结合函数式(3)、(4)和(9)对搜索采摘路径上的信息素进行全局更新；步骤8：判断路径搜索循环次数是否达到预设上限值，若是，则路径搜索进程终止，输出结果，否则，转至步骤3。

3 仿真试验与分析

选用Matlab软件作为仿真试验平台，以4种不同规格栅格模型作为果蔬采摘机器人工作环境模型，以路径距离、程序耗时、转折次数及算法收敛代数作为评价指标，在所设计算法下对果蔬采摘机器人路径规划过程作了仿真测试。为了从多个方面论证所设计算法的有效性和优越性，所设计算法分别与4篇文献中所设计的改进蚁群算法作了对比论证。此外，为了使测试数据充分反映算法实际性能，根据测试要求，对每组试验数据均作了多次重复测试，测试结果见表1、表2、表3和表4。

表1为本研究IACO与文献[19]中算法的试验统计结果，是在还原文献[19]中环境模型的基础上，采用本研究IACO与文献[19]中算法经10次仿真测试得到。对比表1数据，从规划路径看，本研究IACO为果蔬采摘机器人搜索的路径的长度主要集中在28 m附近，且搜索路径平均长度和路径所经拐点参数较文献[19]中TACO和IACO均有不同程度减少，其中，平均路径长度减少幅度分别为24.43%和 3.74%，平均拐点参数减少幅度分别为81.08%和36.36%，说明本研究IACO路径寻优能力优于文献[19]中的2种算法。从迭代次数看，本研究IACO搜索到全局最优路径的迭代次数多集中在10代以下，较文献[19]中TACO和IACO有较大幅度改善，且在搜索路径长度35 m下最佳迭代次数上，较文献[19]中2种算法分别减少了81.81%和50%，说明本研究IACO收敛速度快，搜索能力强。从程序平均耗时看，本研究IACO较文献[19]中TACO和IACO分别减少了36.31%和30.14%，说明IACO搜索效率高。

表1 本研究IACO与文献[19]中算法的试验统计结果

表2为本研究IACO与文献[20]中算法的试验统计结果。分析表2数据，对比路径规划结果可以发现，3种算法均能完成路径规划目的。30次仿真试验中，本研究IACO规划路径有20次达到最优路径长度28.627 4 m，规划路径的最优长度和平均长度较文献[20]中常规IACO和新设计IACO均有不同程度减少，其中，最优路径长度分别减少了10.54%和5.56%，平均路径长度分别减少了49.81%和43.63%，说明本研究改进策略有效，能大幅度增强算法全局寻优能力。从迭代次数看，本研究IACO搜索到全局最优路径所需收敛代数≤10的有21次，在最大迭代次数和平均迭代次数上，较文献[20]中常规IACO和新设计IACO均有大幅度减少，其中，最大迭代次数分别减少了75%和66.67%，平均迭代次数分别减少了82.69%和77.5%，说明本研究IACO收敛速度和搜索能力优于文献[20]中的算法。在程序耗时上，本研究IACO虽略高于文献[20]中算法，但因其有较快的收敛速度，搜索到最优路径的折算耗费时间约为1.35 s，能够满足常规路径规划要求。

表3为本研究IACO与文献[21]中算法的试验统计结果。对比表3数据，与文献[21]中TACO和IACO相比，本研究IACO的平均路径长度分别减少了8.34%和0.54%，最大迭代次数分别减少了80.33%和61.29%，平均迭代次数分别减少了81.4%和66.67%。所述数据表明，与文献[21]中算法相比，本研究IACO的全局寻优能力和收敛速度均为最优。

分析表4数据可知，在平均路径长度、最大迭代次数和平均迭代次数方面，本研究IACO较文献[22]中TACO分别减少了1.69%、74.6%和81.4%，较文献[22]中IACO分别减少了0.84%、64.44%和79.49%。对比结果表明，本研究IACO全局寻优能力和收敛速度优于文献[22]中算法。

表2 本研究IACO与文献[20]中算法的试验统计结果

表3 本研究IACO与文献[21]中算法的试验统计结果

表4 本研究IACO与文献[22]算法的试验数据对比

为了对果蔬采摘机器人路径规划过程分析研究，文中给出了基于4种模型的果蔬采摘机器人路径规划结果的其中一组可视化仿真结果，具体见图2、图3、图4和图5(本研究IACO与文献[22]中IACO规划路径轨迹重合)。

图2所示为基于模型1的果蔬采摘机器人路径轨迹迭代图，图2-a为路径轨迹图，图中虚线为文献[19]中IACO搜索路径轨迹，实线为本研究IACO搜索路径轨迹；图2-b为路径长度迭代图，实线为本研究IACO最优路径长度曲线，虚线为本研究IACO平均路径长度曲线。由图1至图4可知，本研究IACO和文献[19-22]中IACO均能在有效避障前提下，为果蔬采摘机器人规划出1条从起点至终点的全局最优或次优路径。分析图2-b、图3-b、图4-b路径长度曲线变化情况，结合仿真数据统计结果可以看出，本研究IACO在保持较快的收敛速度前提下，能快速搜索到全局最优路径。另外，在路径搜索初期阶段，平均路径长度曲线虽有较大波动，但其总体随时间变化呈下降趋势，到一定迭代次数后，该曲线会与最优路径长度曲线重合，说明本研究IACO收敛性能稳定性很强。分析文献[19]中图7和图8、文献[20]中图3和图4及文献[21]中图4和图5可知，在路径搜索初期阶段，文献[19-21]中算法搜索的最优路径长度曲线存在较大波动，虽然后期随时间推移能收敛到全局最优路径，但所需收敛代数均较大且大于本研究IACO。另外，文献[20]中图3和图4及文献[21]中图4和图5显示，在整个路径搜索阶段，文献[20]中2种算法和文献[21]中TACO的平均路径长度曲线一直处于波动状态，文献[21]中IACO的平均路径长度曲线虽然能随时间变化而收敛到与最优路径长度曲线重合，但此时所需迭代次数已达到120次。综上分析可知，与文献[19-22]中算法相比，本研究IACO收敛性能最优，搜索效率最高。

4 结论

通过引入精英策略、设计启发函数因子、修正状态转移规则和更改信息素更新规则对基本蚁群算法进行改进，并基于改进算法求解果蔬采摘机器人路径规划问题。为测试改进算法的有效性和优越性，与其他算法作了对比论证，由测试结果可得结论：本研究改进算法能为果蔬采摘机器人规划出全局最优避障路径；能有效减少路径所经拐点个数，可有效提高机器人工作效率；与对比文献中算法相比，本研究IACO全局寻优能力最强，收敛速度最快，收敛性能最稳定。