基于改进蚁群算法的果蔬采摘机器人三维路径规划

黄　玲，胡蔚蔚

( 1.广东工程职业技术学院 信息工程学院，广州　510520；2.山东女子学院 信息技术学院，济南　250300)



基于改进蚁群算法的果蔬采摘机器人三维路径规划

黄玲1，胡蔚蔚2

( 1.广东工程职业技术学院 信息工程学院，广州510520；2.山东女子学院 信息技术学院，济南250300)

摘要：近年来，我国“农民荒”问题越演越烈，大量年轻劳动力外出务工，农村土地荒置越来越多。我国人口高龄化严重，农业人口的减少，劳动力缺口过大，导致对农业机器人的需求极为迫切。随着农业机械和自动化技术的快速发展，农业机器人也在不断发展，其可以更好地适应生物技术种植产业发展，过去传统的采摘方式将会有很大改变，农民种植的侧重点即将改善。为此，基于改进蚁群算法，设计和规划了果蔬采摘机器人行走的三维路径，并增加在前进过程中的自适应调整功能。实验仿真结果表明：基于改进蚁群算法的果蔬采摘移动机器人三维空间路径规划在路径和转弯个数上都做到了最小化，能够很好地满足采摘机器人运行需求。

关键词：改进蚁群算法；采摘机器人；三维空间；路径规划

0引言

随着信息技术、微电子技术与农业机械化的高速发展，农业机器人的研究也获得了极大突破，开始在各个生产领域中应用，不断推进农业生产朝着自动化和智能集成化发展。在果蔬种植过程中，采摘是最重要的一个部分，水果蔬菜一般采摘期短、采摘任务大、采摘要求高，对采摘人员的体力消耗很大。目前，我国水果蔬菜的采摘主要以人工为主，导致经济成本较高，采摘质量低下，直接影响果农的经济收入。随着机器人技术的逐渐成熟，我国现阶段已经开始加大对农业机器人研究的投入，以实现对采摘过程的自动化，这对解放农村劳动力、提高采摘的效率和质量有着重要的意义。路径规划是采摘机器人作业过程中最重要的部分，采摘机器人的智能自动化主要体现在对运动范围、作业空间的规划上。果林中环境地势一般较为复杂，采摘机器人在其中前行作业需要对运动路径具有很好的规划技术，这样可以节省一定的采摘时间、减少采摘机器人行进过程的三维路径计算优化，并采用环境模型来仿真预测采摘机器人在作业中可能发生的某些碰撞以成功避开障碍物，实现果蔬采摘机器人作业运动路径最优。

1改进型蚁群算法

20世纪90年代，意大利研究者Dorigo受到蚂蚁找食物的启示，提出了一种仿生的蚁群算法。研究者发现：蚂蚁在觅食过程中会留下作为信息素的分泌物，且在某条路线走过蚂蚁越多，则后面蚂蚁选择该路径的机会就越大，产生这一奇特的正反馈现象就是蚁群算法的由来。简化的蚂蚁寻找食物过程如图1所示。

图1　蚂蚁寻找食物示意图

图1中：(a)是表示蚂蚁寻找食物路线的距离；(b)是t=0时两条寻找食物路线上蚂蚁的数量，最开始两条路线信息素是一样的，蚂蚁选择两条路线的概率相同；(c)是t=1时两道寻找食物路线上的蚂蚁数量，路线短的蚂蚁更多。蚂蚁从起点A到终点F，有ABCEF和ABDEF两条距离不同的线路，因为ABCEF的路径短，时间越长该线路走过的蚂蚁越多，路上的分泌物也越多，则后面蚂蚁选择ABCEF短线路的机会就会越大。

假设短路线为S，长路线为L，KS和KL分别为经过S和L的蚂蚁数目，则

K=KS+KL

(1)

当K只蚂蚁走过两条路径以后，第K+1只蚂蚁走S路径的概率为

(2)

PL(K)=1-PS(K)

(3)

其中，m和h是具体的参数。在第K+1只蚂蚁选择前，计算出PS(K)，然后再求到一个在[0,1]的随机概率φ，若φ≤PS(K)，则选择路线S，否则选择路线L。

2三维空间路径规划

三维空间路径规划是机器人人工智能的核心问题，机器人可以根据三维空间路径规划在三维空间中自主识别一条从起始点到目标点距离最优、障碍最少的路径。与二维相比，三维空间路径规划的算法复杂度更高，限制性条件和外在因素更多，其效果一般很难达到设计者的预期。改进蚁群算法具有智能群体和广泛分布的优势，在三维空间路径规划算法上有很大的优越性。山林地形三维空间立体结构如图2所示。

图2　山林三维空间立体结构图

对三维路径的规划需要建立三维模型，即从复杂的果林地形中得到抽象的三维空间模型，具体的方法为：先取一点作为三维空间的原点O，并且在原点O建立直角坐标系，X轴与Y轴形成的平面XOY平行于海平面，Z轴则垂直于海平面。三维模型如图3所示。

图3中，从起点B到目的地F有无数条路径可走，这样就需要利用蚁群算法求解最优路线。首先建立三维空间模型，然后用栅格法将三维空间等分为体积大小相同的栅格，即获得整个三维点的集合，且各类栅格表示一定的环境，每个栅格都代表一个节点值，计算出三维空间所有可能的路线，并通过搜索每一个可能的路径求出最优者。用以上算法可以求出从B到F的最优路径是BHF，而BAEF和BCGF相对来说距离比较远。改进蚁群算法在这些三维集合点上比较计算，求出起点到终点满足距离最优的路线。该方法简单实用，为路径规划的最优性提供了很多方便。

图3　三维空间模型图

3改性蚁群算法的三维地形路径规划

首先将三维地形模型分为N个节点，然后将M个蚂蚁任意的分配给N个节点，则节点i的第K只蚂蚁去节点j的概率为

(4)

其中，λ(i,j)是边(i,j)区间上的信息素，μ(i,j)=1/d(i,j) ；t是该蚂蚁已经到达过的列表信息。

在果林中选择一片100m×100m×100m的山地，采用蚁群算法在其间进行果实采摘作业，并求出从起点到目的地的最优路径，并在采摘作业中成功避开果林中的障碍物。如图4所示，设定A(18,20,22)为起点，D(98,60,86)为终点。蚁群算法的搜索范围为图4中整片山地。

图4　山地环境规划

在求最优采摘路径的过程中，改进蚁群算法解决问题的程序流程如图5所示。

图5　改进蚁群算法程序流程图

具体的算法流程如下：

1)建立规划环境模型，设定采摘起点和终点，并准确确定其在规划环境模型的三维坐标。

2)初始化蚁群算法参数，格式化所有信息素，清空迭代次数储存信息，清空禁忌表。

3)初始化蚂蚁，将蚂蚁全部置于A。

4)蚂蚁按照概率在节点间移动，并将移动的次数计数。

5)对于移动次数小于软件设置最大次数，且蚂蚁没有成功到达终点D时，回到第4步重新开始，对于移动次数大于等于软件设置最大次数，且蚂蚁没有成功到达终点D时，初始化蚂蚁所有数据，重新放回起点A；否则，判定该蚂蚁数据信息无效。

6)统计成功到达D的蚂蚁行走路径P。

7)比较所有成功到达D的蚂蚁行走路径P，并求出最优值。

8)输出最优路径。

4三维地形路径规划软件仿真设计

MatLab是矩阵实验室，是面对科学计算和可视化的高科技计算环境，为工程设计的数值计算提供了极大地方便。用MatLab对三维地形路径规划进行仿真求优，采用蚁群动态寻路算法。蚁群算法在采摘机器人进行路径最短规划的主程序如下：

1)状态初始化。

W=S;Path=S;爬行路线初始化

PLkm=0;爬行路线长度初始化

TABUkm=ones(1,N);禁忌表初始化

TABUkm(S)=0;已经在初始点了，因此要排除

DD=D;邻接矩阵初始化

2)下一步可以前往的节点。

DW=DD(W,:);

DW1=find(DW

for j=1:length(DW1)

if TABUkm(DW1(j))==0

DW(j)=inf;

LJD=find(DW

Len_LJD=length(LJD);可选节点的个数

3)转轮赌法选择下一步怎么走。

PP=zeros(1,Len_LJD);

For i=1:Len_LJD

PP(i)=(Tau(W,LJD(i))^Alpha)*(Eta(LJD(i))^Beta);

PP=PP/(sum(PP));建立概率分布

4)状态更新和记录。

Path=[Path,to_visit];路径增加

PLkm=PLkm+DD(W,to_visit);路径长度增加

W=to_visit;蚂蚁移到下一个节点

for kk=1:N

if TABUkm(kk)==0

5)记下所有蚂蚁觅食路线和路线长度。

ROUTES{k,m}=Path;

PL(k,m)=PLkm;

6)更新信息素。

Delta_Tau=zeros(N,N);更新量初始化

TS=length(ROUT)-1;跳数

PL_km=PL(k,m);

Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;

Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;

5仿真与结果分析

为了验证基于改进蚁群算法的果蔬采摘机器人三维路径规划的可行性，运用MatLab进行仿真实验。该机器人在山林中停止进行采摘作业的次数很多，选择最优路线进行作业可以节约时间，减少资源浪费，本文中选取300个路径节点为机器人必须经过的地点。假设整个规模为500次，软件设定最大移动次数为10 000，交互概率为0.75。运用MatLab计算10次，在第4次得到最优解7 456.353，所求最优路径如图6所示。最优路径迭次曲线如图7所示。

图6　三维空间最优路径

图7　最优路径迭次曲线

如图7所示，基于改进蚁群算法规划了成功避开障碍物且为长度最短最优的路径。随着迭代次数的增加，算法更加趋近最优路径，大大地提高了路径质量，而且波动非常小，说明改进蚁群算法稳定性强，可靠性高。

6结束语

针对采摘机器人在采摘作业过程中行走路径过长及效率低的问题，设计了以改进蚁群算法为核心的果蔬采摘机器人三维最优路径规划，采用栅格法建立了环境模型，并实时根据实际出现的问题再次进行局部规划调整，结合机器人转弯次数制定最优路径。研究过程中运用MatLab进行仿真实验分析，并提出改进方案，使机器人运行效率有较大的提高；同时加强了运行过程中的稳定性，为果农节省了大量时间和成本，证实了路径规划方案的可靠性。

参考文献：

[1]马强.苹果采摘机器人关键技术研究[D].北京：中国农业机械化科学研究院,2012.

[2]柳军.爬壁机器人的电机控制与路径规划[D].沈阳：东北大学,2010.

[3]周婷.基于改进蚁群算法的移动机器人路径规划及实现[D].长沙：中南大学,2010.

[4]刘亮.基于势场蚁群算法的移动机器人路径规划研究[D].南昌：南昌大学,2013.

[5]范志超.基于PSO和弹性绳算法的水下潜器三维空间路径规划方法研究[D].哈尔滨：哈尔滨工程大学,2013.

[6]范路桥,段班祥,周文琼.应用于机器人路径规划中的蚁群算法的改进策略研究[J].现代计算机,2013(5):3-8.

[7]贾祥素,吴菁.基于改进蚁群算法服装运输车辆路径优化研究[J]. 浙江纺织服装职业技术学院学报,2013(3):68-72.

[8]潘攀.足球机器人路径规划算法的研究及其仿真[J].计算机仿真,2012(4):181-184.

[9]马军煜,成旭华,叶学义.基于蚁群算法的可信网络路由[J].电子技术应用,2010(1):91-94.

[10]卢冰,王梦兰.一种改进蚂蚁算法在TSP问题中的应用[J].科技创业月刊,2010(6):128-129.

[11]苑严伟,张小超,胡小安.苹果采摘路径规划最优化算法与仿真实现[J].农业工程学报,2009(4): 141-144.

[12]成旭华,赵知劲,叶学义.基于改进蚁群算法的网络路由重组[J]. 计算机工程,2009(13):90-92.

[13]王俊峰.基于改进蚁群算法的机器人路径规划[D].南京：南京师范大学,2005.

[14]黎田.基于改进蚁群算法的移动机器人路径规划[D].西安：西安科技大学,2011.

[15]侯文静.混合蚁群算法及其应用研究[D].西安：西北师范大学,2011.

[16]黄佰川.改进蚁群算法在船舶锅炉蒸汽压力控制系统中的应用研究[D].哈尔滨：哈尔滨工程大学,2011.

[17]孙宇.基于蚁群算法的通信线路最佳抢修路径问题的研究[J].电脑知识与技术,2011(7):1619- 1621.

[18]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011(5):1220-1224.

[19]傅奥.多目标资源受限项目调度问题蚁群算法研究[D].杭州：浙江大学,2008.

[20]毛琳波,刘士荣,俞金寿.移动机器人路径规划的一种改进蚁群算法[J].华东理工大学学报：自然科学版,2006(8):997-1001.

[21]王崇宝.蚁群算法熵收敛性分析与应用[D].成都：四川师范大学,2009.

[22]尹向东.基于蚂蚁优化的QoS约束分布式多播路由算法研究与实现[D].长沙：中南大学,2008.

[23]陈杰.基于蚁群算法的机器人路径规划研究[D].南京：南京理工大学,2009.

[24]任春明,张建勋.基于优化蚁群算法的机器人路径规划[J].计算机工程,2008(15):1-3,35.

[25]龚雨兵,李泉永.蚂蚁算法在工件排序问题中的应用[J].桂林电子工业学院学报,2004(2):68-71.

[26]胡小兵,袁锐,黄席樾,等.蚁群算法原理的仿真研究[J].计算机仿真,2004(8):125-128.

[27]廖兴新.蚂蚁算法在TSP问题中的应用与研究[D].成都：四川大学,2006.

[28]朱国玺.嵌入式计算机系统热分析及热优化研究[D].西安：西安电子科技大学,2007.

[29]胡小兵,黄席樾.蚁群算法在迷宫最优路径问题中的应用[J].计算机仿真,2005(4):114-116,161.

Three Dimensional Path Planning of Fruit and Vegetable Picking Robot Based on Improved Ant Colony Algorithm

Huang Ling1, Hu Weiwei2

(1.School of Information Engineering,Guangdong Polytechnic College,Guangzhou 510520, China； 2.School of Information Technology,Shandong Women College,Jinan 250300, China)

Abstract：In recent years, the"shortage of farmer" problem plays more more strong in our country,and a large number of young workers migrant workers, rural land fallow more and more. China's population aging is serious, the agricultural population is reduced, the labor gap is too large, which leads to the demand of agricultural robot very urgent. With the rapid development of agricultural machinery and automation technology, agricultural robots are constantly developing, which can better adapt to the development of biotechnology, the past the traditional picking methods will be greatly changed, the focus of farmers planting is about to improve. Based on the improved ant colony algorithm, this paper designs and plans the 3D path of fruit picking robot walking, and increases the adaptive adjustment function in the process of advancing. Experimental simulation results show that the improved ant colony algorithm based 3D space path planning of fruit and vegetable picking robot is the best way to meet the requirements of the picking robot.

Key words：improved ant colony algorithm; picking robot; 3D space; path planning

中图分类号：S225.93；TP242

文献标识码：A

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

作者简介：黄玲(1979-)，女，广西桂林人，讲师，硕士。通讯作者：胡蔚蔚(1980-)，女，济南人，副教授，硕士，(E-mail)huangling1979@sina.com。

基金项目：山东省科技厅科技发展计划项目(2013YD010334)

收稿日期：2015-08-16