基于改进蚁群算法的农业机器人路径规划研究

朱铁欣，董桂菊，颜丙学，郭凯敏，谢学刚，郭志强

(东北农业大学，哈尔滨　150030)



基于改进蚁群算法的农业机器人路径规划研究

朱铁欣，董桂菊，颜丙学，郭凯敏，谢学刚，郭志强

(东北农业大学，哈尔滨150030)

摘要：针对农业机器人路径规划实时性和稳定性差的问题，采用人工势场法，并结合Memetic算法与精英排序法优化基本蚁群算法。该算法用势场法获得路径初始化种群，对每代路径进行Memetic算法中的交叉组合操作，将每代蚂蚁产生的路径分别进行优化排序，根据蚂蚁路径的优劣程度，对信息素进行更新；同时，加入精英小组蚂蚁产生的信息素，从而加快了算法的收敛速度，提高了算法的稳定性。实验表明：改进后算法的平均最优路径长度提高了12.56%，收敛代数提高55.86%，算法用时提高了65.3%，最优解百分比增加了40%。本算法能够快速有效地规划出最优路径，提高了农业机器人的工作效率。

关键词：农业机器人；Memetic算法；路径规划；蚁群算法；精英排序；人工势场

0引言

随着科技的发展，智能机器人在农业领域的应用日益广泛，而路径规划是农业机器人研究领域的重要内容之一，是实现机器人智能作业的必要基础。路径规划一般分为环境地图完全已知的静态路径规划和环境地图部分已知或全部未知的动态路径规划，本文主要对前者进行研究分析。对于这个问题，已经有大量学者进行研究和探索，并提出了很多解决方法。其中，蚁群算法的应用最为突出，该算法具有分布式计算、信息正反馈和启发式搜索的特征，非常适合求解移动机器人的路径规划问题。但基本蚁群算法的执行过程依赖于大量的迭代和循环，缺乏实时性；运行过程中信息素不断地累积，优质路径不突出，对于最优解的求取有着很大的影响。针对这些问题，文献[1]在算法停滞阶段，引入交叉操作，并调整α、β和ρ的值，改善了算法的搜索效率；文献[2]采用遗传算法对蚁群算法的基本参数进行优化和配置，增强了算法的稳定性；文献[3]采用人工势场法融合蚁群算法，构建并加入了权重可调的引力概率函数作为启发式因子，提高了算法的运行速度。为了减少算法运行时间，提高算法收敛速度和稳定性，本文融合了人工势场、Memetic算法、精英小组和优化排序法以得到问题的更优解。

1基本蚁群算法

蚁群算法(Ant colony optimization,ACO)是意大利学者Dorigo等人，从蚂蚁群体的觅食过程中受到启发，于1991年提出的一种模拟自然界中蚁群行为的模拟进化算法[4]。以下为基本蚁群算法的主要过程。

(1)

蚂蚁完成一次循环，各生成路径上的信息素按下式进行调整，有

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

(2)

(3)

按照信息素增量表达方式的区别，基本蚁群算法可以分为蚁周系统、蚁量系统和蚁密系统。本文选用使用全局信息素更新策略的蚁周系统。轨迹信息素增量为

(4)

其中，Q为蚂蚁k经过路径(i,j)后，每单位长度释放的信息素量；Lk为蚂蚁k在本次循环所经过的路径长度。蚂蚁按照这一规则，循环往复进行，最终得到从起始点到目标点的最优路径。

2改进算法设计

2.1　种群初始化

人工势场法是由Khatib提出的一种虚拟力法。该算法应用在路径规划问题中时，将工作环境抽象为力场，目标点对移动机器人产生“引力”，障碍物对移动机器人产生“斥力”，机器人距离目标位置越近，所受“引力”的影响越大，反之越小。

设Xd为小车当前位置点，Xe为目标点，Xz为障碍物，共n个障碍物，车与障碍物的夹角为

(5)

其中，i=1,2,…,n；dzd为各障碍物与小车当前位置间距离。

目标对车的引力为

(6)

其中，y为引力增益系数；dde为当前位置与目标位置的距离；θe为当前位置与目标位置的夹角。

当路径点与障碍物间距离大于预先设置的障碍物影响距离P0时，该障碍物对小车的斥力为0；否则，障碍物对车的斥力为

(7)

其中，c为斥力增益系数。

将位引力与斥力对应求和，则机器人在该合力的指引下寻找下一路径点。

2.2　路径更新

为了扩大路径点的选择范围，减少锁死和早熟现象的发生，在路径更新的过程中融入Memetic算法。Memetic算法(也有文献将其称为文化基因算法)的概念在1989年由Moscato首次提出，并将其归为一种基于群体的混合全局启发式搜索算法[6]。Memetic算法采用的框架和操作流程与遗传算法相似，应用在路径规划时，结合了遗传算法和局部搜索算法的优点，全局寻优能力强，收敛性较高，能够获得高质量解。本文主要应用Memetic算法中的交叉操作。

在蚂蚁完成一次迭代之后，随机打乱一代中全部m只蚂蚁的路径顺序，然后取第i条路径和第m-i条路径作为父代，将两父代中所有路径点合并，取出不重复的路径点，且各路径点首次出现的位置不变，作为子代新生路径。下面进行举例说明。

设路径s1为(1 9 15 18 24 65)，路径s2为(4 9 18 20 35 43)，合并路径s1和s2，得到路径s3为(1 9 15 18 24 65 4 9 18 20 35 43)，剔除重复路径点并保持各点相对位置不变，得到子代路径sz为(1 9 15 18 24 65 4 20 35 43)。

2.3　信息素更新

2.3.1优化排序

在完成算法一次迭代后，将本次循环中所有蚂蚁形成的有效路径，按照从大到小(L1≥L2≥L3≥…≥Lm)的顺序进行排列，路径长度越长，排名越靠前，则对该路径上的信息素增加较小；反之，较短路径会对信息素的更新做出较大贡献。

本设计采用冒泡排序(Bubble Sort)法[7]，是一种稳定的排序算法。它重复地走访要排序的数列，一次比较两个元素，若顺序与设置不同，则交换两个元素，直到完成最后两个元素的比较，排序完成。同时，在排序过程中加入swap变量，它的作用是如果某次比较路径长度Ln=Ln+1，不用将其交换，即可视为排序已完成，就会直接做结束处理。如此，便得到从大到小的路径排序，将此排序翻转，则得到算法所需顺序，即从小到大。排序过程流程图如图1所示。其中，lengh(Lm)为可行路径数量。

2.3.2精英小组

在信息素更新时，在对所有可行路径增加信息素的基础上，加入精英蚁群小组。精英蚁群小组指在算法执行过程中，得到最短路径的蚂蚁小组。使用精英蚂蚁小组可以更快、更好地找出最优解。然而，如果精英蚂蚁的选择太多，搜索将迅速地集中在其周围的最佳值附近，这样将会导致过早收敛；选用精英蚂蚁过少，对算法的优化则难以达到预期的效果。经大量实验分析，精英数量小组数量jj取3~6时效果较好。部分实验数据如表1所示。

图1　冒泡路径排序流程图

样本号mkjj18035425010063403544505046503537508048406039454031035453

3算法的实现

应用人工势场、Memetic算法和精英排序改进蚁群算法的算法流程图如图2所示。

算法步骤为以下8步。

Step1：算法基本参数设置。

Step2：初始化禁忌表、信息素等，人工势场法初始化蚂蚁爬行路经。

Step3：设置评价函数，本文以起始位置到目标位置间直线距离的倒数作为启发式因素。

Step4：按轮赌法寻找蚂蚁运行路径点。

Step5 ：Memetic算法更新所得路径，将所得路径进行交叉组合操作。

Step6：优化排序和精英小组信息素更新。

Step7：全局信息素更新。

Step8：判断是否满足终止条件，即是否获得最优路径，或达到最大迭代次数，满足则运行结束，不满足则返回Step4。

图2　改进蚁群算法流程图

4实验研究

4.1　仿真环境

W.H.Howden提出的栅格法[8]在处理路径规划问题时，可视地图简单、清晰。并且，栅格法易于实现计算机的建模、存储、处理、更新与分析。实验中将图片进行栅格化处理，障碍区域用1表示，可行区域用0表示，并将栅格按照从左到右、从上到下的顺序进行编码，格栅个序号与坐标的关系为

S=(j-1)×20+i

(10)

其中，i，j分别为栅格的横纵坐标。

本实验采用20×20的障碍栅格模拟实际农田环境，分别采用复杂障碍、中等复杂障碍、简单障碍环境，每种环境进行20次仿真。此仿真过程中，将障碍物尺寸增加机器人半径长度，即视机器人为质点；障碍物不满一栅格，按一栅格处理。

4.2　仿真结果分析

取基本蚁群算法参数迭代次数K=100，蚁群数量M=50，信息素激励因子α=1.5，启发式激励因子β=9，信息素强度Q=1，信息素挥发系数ρ=0.31；改进算法中取K=35，引力增益系数y=8，斥力增益系数c=4，障碍影响距离P0=1.8，势场步长b=2.1，并加入精英小组jj=3。表2为各障碍环境下的仿真数据结果。图3为算法改进前后各数据结果柱状图。

表2　算法改进后仿真数据结果

图3　算法改进前后结果对比图

图3中，改进前后最优路径长度、收敛代数、算法用时皆为3种环境规模平均值，改进前分别为32.64、48.33、19.54，最优解百分比为48%；改进后为28.54、21.33、6.78，最优解百分比为88%，这4个评价参数分别提高了12.56%、55.86%、65.3%、40%，在收敛速度和算法用时上最为显著，达到了本文的目的。图4为算法改进后不同障碍环境路径结果图。从图4中可以直观地看到，对于不同的环境模型，该改进算法都可以找到最优路径。

复杂障碍 　　　　　　　　　　　　　　 中等复杂障碍 　　　　　　　　　　　　　　 简单障碍

5结论

由于基本蚁群算法迭代次数多、运行速度慢，容易产生锁死现象，本文采用一种基于人工势场、冒泡排序和精英小组的改进蚁群算法，并融入Memetic算法。该算法在初始时刻产生优质初始值，路径更新过程加入交叉操作，信息素更新时，突出优质蚂蚁对算法规划的影响，增加优质路径搜索范围，从而使后来蚂蚁能够更快地找到优质路径，加快了算法的收敛速度，进而可以减少迭代次数，提高算法效率。

仿真结果表明：与基本蚁群算法相比，改进算法在运行用时和收敛速度上皆有大幅度的提高，具有更高的稳定性和有效性，说明本文中的算法改进是有效可行的，提高了农业机器人运动过程中的稳定性和实时性。基于此改进效果，该算法可以应用于自主移动农业机器人，为其智能移动进行采摘、喷药等工作的实施提供了理论依据。

参考文献：

[1]张琦,马家辰,谢玮，等.基于改进蚁群算法的移动机器人路径规划研究[J].东北大学学报：自然科学版,2013,34(11):1521.

[2]Wang Zhangqi, Zhu Xiaoguang, Han Qingyao.Mobile robot path planning based on parameter optimization ant colony algorithm[J].Procedia Engineering, 2011,15(8):2738-2741.

[3]孙纯哲,桂贵生,韩东，等.基于蚁群算法的移动机器人路径规划研究与应用[J].合肥工业大学学报：自然科学版,2006,29(10):1208

[4]李世勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社,2004:29-31.

[5]段海滨.蚁群算法原理及其应用[M].北京：北京科学出版社,2005:36-48.

[6]陈颖频,王灵芝,吴金峰，等.基于选择思想和反序标识的改进冒泡排序算法[J].泉州师范学院学报,2014,32(6):89.

[7]段海滨,张祥银,徐春芳.仿生智能计算[M].北京：科学出版社,2011:130-143.

[8]吴登峰,梅志千,尹立伟，等.一种未知环境下移动机器人路径规划新算法[J].机电工程,2015,32(3):390.

Research for the Path Planning of the Agricultural Robot Based on the Improved Ant Colony Algorithm

Zhu Tiexin， Dong Guiju，Yan Bingxue， Guo Kaimin， Xie Xuegang， Guo Zhiqiang

(Northeast Agricultural University, Harbin 150030, China)

Abstract：In response to the problems of agricultural robot path planning bad real-time and stability,artificial potential field, elite sorting method combined with Memetic algorithm is adopted. This algorithm initialize the path population with potential field method,optimizes the sorting of each generation ants path. And also updates the pheromone according to the superiority of the ants path. At the same time, with the help of the pheromone of the elite ants, and using crossover and mutation operation of the memetic algorithm on each generation path,so as accelerate the convergence speed of the algorithm, improves the stability of it.The simulation results show that the improved algorithm of the optimal path length on average increased by 12.56%,the convergence generation increased by 55.86%, the algorithm time increased by 65.3%,and the optimal solution percentage increased by 40%,this shows that the mentioned algorithm can plan the optimal path in a quick and efficient way, improving the efficiency of agricultural robot.

Key words：agricultural robot; memetic algorithm; path planning; ant colony algorithm; elite sorting; artificial potential field

中图分类号：S24

文献标识码：A

文章编号：1003-188X(2016)09-0048-05

作者简介：朱铁欣(1990-)，女，黑龙江五营人，硕士研究生，(E-mail)1254904178@qq.com。通讯作者：董桂菊(1967-)，女，哈尔滨人，副教授，硕士生导师。

基金项目：国家“863计划”项目(810028)

收稿日期：2015-08-26