基于势场蚁群算法的温室机器人路径规划

王红君+徐+军+赵辉+岳有军

摘要：针对工作在温室环境下的机器人需要在垄间穿行的难点，建立栅格化环境模型，提出了基于势场蚁群算法的温室机器人路径规划算法。温室环境下的机器人路径规划是要在温室中长有农作物的情况下，使机器人能够寻找到一条从起始点到目标点的连续、无碰撞的路径，其中，机器人走过的路径要包围农作物的生长区域，以方便机器人对农作物进行施肥、摘取果实等行为。路径规划过程中，蚂蚁根据当前节点与可达点之间是否存在障碍物分为确定性方向转移和概率性方向转移2种转移方式，并且重新构造了启发信息，指引蚂蚁搜索。在不同的环境下进行了仿真试验，结果表明，改进势场蚁群算法能有效解决温室环境的路径规划问题。

关键词：温室；机器人；蚁群算法；人工势场；路径规划

中图分类号： TP242 文献标志码： A 文章编号：1002-1302（2017）18-0222-04

收稿日期：2016-04-19

基金项目：天津市农业科技成果转化与推广项目（编号：201203060、201303080）。

作者简介：王红君（1963—），女，天津人，硕士，教授，主要从事工业先进控制技术、微机控制、智能控制等方面的研究。E-mail：hongewang@126.com。

通信作者：徐 军，硕士研究生，主要从事机器人智能控制方面的研究。E-mail：598649947@qq.com。 利用机器人来完成温室内各项工作，不仅可以大幅度减少劳动者的体力劳动，并且可以避免劳动者在高温、高湿甚至有毒的作业环境中受到人身伤害[1]。路径规划是实现机器人自由移动的一项关键技术。目前，温室内各种农用机具的作业路径规划一般是由操作者根据经验、习惯进行选择的，也有学者提出了一些路径规划的方法。陈济勤从农机运营管理和作业工艺角度考虑，提出了针对耕地、播种、收割等不同农田作业方式下的直行、绕行、斜行等作业路径模式[2]。Stoll提出根据地块最长边将田块分割成子地块进行路径优化的方法[3]。以上路径规划方法都是对地块全区域覆盖的路径优化方法，但是目前尚没有一种合理的用于机器人在农作物的垄间狭窄路径中穿行的路径规划方法。目前，用于移动机器人路径规划的方法有模拟退火法、模糊逻辑法、栅格法等。但是随着环境系统的复杂性和任务难度的增加，基于数学模型的传统路径规划已经难以取得理想的效果，于是出现了一些仿生智能算法，如蚁群算法[4]、免疫算法[5]、遗传算法[6-8]等，但是这些方法存在搜索空间大、参数难以确定、搜索效率低及容易产生局部最优等问题。

为了解决在温室环境下机器人的路径规划难题，在本试验中将改进的人工势场算法和蚁群算法进行融合， 利用人工势场的全局性和蚁群算法的正反馈及全局寻优等特点，不仅可以实现机器人的实时避障，而且在复杂的环境中可以较好地改善局部最优、徘徊等问题。

1 基本算法原理

1.1 基于栅格地图的环境建模

假设机器人在二维空间中工作，并且将机器人看作二维空间中的点状移动物体。栅格地图的优点是易于创建和维护，并且机器人感知的每个栅格信息能直接与环境相对应。栅格地图中有障碍物的区域表示非自由区域，无障碍物的栅格表示自由区域，环境中的障碍物映射到栅格地图中覆盖面积不足1个栅格需要按1个栅格处理。

在本试验中栅格地图按照从上到下、从左到右的顺序依次编号为1，2，3，…，n。如图1所示，农作物种植区域表示为障碍区域（黑色部分），障碍区域的栅格中心坐标表示为障碍物的中心点，自由区域（白色部分）的栅格中心点作为机器人可行走的路径点，这样路径规划问题就可以描述为在自由区域中寻找一个连续栅格的子集，使机器人在自由区域中穿行的路径最短，并且机器人所走路径要包围农作物的种植区域。

1.2 蚁群算法原理

蚁群算法是由意大利学者Dorigo等提出的[4]，以后所有改进的蚁群算法都是在此基础上发展起来的。在基本蚁群算法中，第k只蚂蚁在t时刻从节点i转移到节点j的概率为

式中：τij（t）为t时刻节点i与节点j之间残留的信息素浓度；ηij（t）表示t时刻节点i和节点j之间的期望启发函数，在基本蚁群算法中期望启发函数定义为节点i与节点j之间的距离dij的倒数，即ηij=1/dij；α为信息素启发因子，表示前几代蚂蚁走过轨迹的相对重要性[9]；β为期望启发因子，表示能见度的相对重要性[10]；allowedk为蚂蚁k下一步可以选择的节点。

蚂蚁完成1次循环，各路径上的信息素更新规则按公式（2）、公式（3）计算：

式中：ρ为信息素挥发系数，为有效防止信息素无限积累，ρ的取值范围为[0，1）；Δτij（t）表示本次循環中节点i与节点j之间路径上的信息素增量，在初始时刻Δτij（0）=0；Δτijk（t）为第k只蚂蚁在本次循环中残留在节点i与节点j之间的信息素，在本试验中信息素的计算采用Dorigo等提出的Ant-Cycle模型[4]，即

式中：Q为信息素强度，它在一定程度上影响算法的收敛速度；Lk为蚂蚁k在本次循环中所走过路径的总长度，Pk（begin，end）为蚂蚁k在本次循环中从起点到终点所走过的节点。

1.3 人工势场算法原理

人工势场算法是由Khatib提出的一种算法[11]，其基本思想是在机器人的工作环境中利用虚拟势场力信息来指引机器人运动，环境中的障碍物对机器人产生斥力Frep，目标点对机器人产生引力Fatt，斥力和引力形成的合力Ftot指引机器人移动。假设机器人所在当前点为P，目标点对当前点的引力势场函数为Uatt（P），如公式（5）所示，障碍物对当前点的斥力势场函数为Urep（P），如公式（6）所示。

式中：katt和krep分别为引力势场常量、斥力势场常量；d（P，G）为当前点P和目标点G的距离；d（P，O）为当前点P和障碍物O的距离；d0为斥力势场作用半径，只有当机器人在障碍物的作用半径范围内时斥力才起作用。机器人在P点所受的引力和斥力分别如公式（7）、公式（8）所示。endprint

式中：nPG表示移动机器人当前所在位置O指向目标位置G的单位矢量；nOP表示由障碍物位置O指向移动机器人当前所处位置P的单位矢量。根据几何叠加原理可以得到机器人在当前位置所受势场合力为

2 改进算法原理

2.1 改进的势场蚁群算法

由于在温室环境下，农作物种植相对规范，根据人工势场算法和蚁群算法的特点，将两者有机结合，使之适合温室环境下的机器人路径规划。根据蚂蚁当前所在节点与目标节点间是否存在障碍物分为确定性方向选择和概率性方向选择2种方式来选择下一节点，这种节点选择方式既解决了蚁群算法搜索效率低的问题，又克服了人工势场算法容易陷入局部极小点的缺点。

当蚂蚁当前所在节点与目标节点之间不存在障碍物时，蚂蚁选择与势场合力方向夹角最小的自由栅格作为下一个所要选择的节点，如图2所示，分别计算蚂蚁所在栅格位置所受合力Ftot与相邻可选择栅格的角度差，选择角度差最小的一个栅格min|θi-θ|（θi依次取0、45、…、315°）作为蚂蚁下一步要选择的节点。对于蚂蚁根据势场合力方向进行节点选择所走的路径，同样加入蚁群算法禁忌表，已走路径上信息素的更新策略同样按照蚁群算法计算。

在蚂蚁当前所在节点与目标节点存在障碍物时，蚂蚁不能再按照势场合力方向选择下一个将要到达的节点，而是通过运用蚁群算法的概率性方向转移选择下一个将要到达的节点，如图3所示，在当前情况下，蚂蚁所在节点与当前目标点之间存在障碍物，蚂蚁将通过概率性方向转移选择下一个节点，当前可供蚂蚁选择的节点有3个，分别为图3中的1、2、3节点，只有从当前节点直接向节点3转移才是最佳路径。

由于是温室环境下的路径规划，机器人需要像农民似的一排排地对农作物进行作业，所以会选取多个可达点作为机器人运动过程中需要经过的点，把规划的机器人路径是否经过所有的可达点，包围了所有农作物生长区域，并且路径长度是否最短作为路径规划是否成功的标准。在本试验中，将2垄农作物之间路径的中点选取为路径规划过程中需要经过的可达点，如图4所示，对这些可达点进行编号，分别为图4中的1、2、3节点，同时建立类似蚁群算法的禁忌表，这些可达点都是蚂蚁在路径规划过程中必须经过的点，将蚂蚁已经经过的可达点加入禁忌表，加入禁忌表的可达点不再起作用。

在利用蚁群算法进行传统点到点的路径规划时，将当前

节点与目标节点距离的倒数作为启发信息，启发信息的大小随着蚂蚁向目标点的移动而增加，而将蚁群算法应用在温室环境下的路径规划时，随着蚂蚁的移动，当前点与目标点的距离会增加，导致启发信息越来越小，因而在本试验算法中直接使用距离信息作为启发信息，从而使启发信息随着蚂蚁的移动越来越大，同时将当前节点的势场力信息加入到启发信息中，构成综合的启发信息，充分利用对已知环境的感知信息来规避障碍。本试验中改造后的综合启发信息为

式中：dig（t）表示当前点与当前可达点之间的距离。

2.2 算法流程

采用势场蚁群算法进行机器人路径规划的算法流程如下：

步骤1：采用0和1组成的矩阵抽象描述温室环境，确定障碍物分布与可行路径，确定机器人初始点与目标点；步骤2：初始化势场蚁群算法的基本参数，如设置蚂蚁数量m、最大迭代次数Nmax、信息启发因子α、期望启发因子β、信息素挥发因子ρ、初始信息素矩阵τ、信息素强度Q、初始化禁忌表Tabu、引力增益系数katt、斥力增益系数krep、斥力作用半径d0；步骤3：将m只蚂蚁置于起始节点；步骤4：判断蚂蚁所在当前节点i与当前目标点之间是否存在障碍物，如果存在障碍物，按公式（1）选择下一个节点j，如果不存在障碍物，按照势场合力方向与可选节点方向夹角的最小值选择下一个节点j；步骤5：将节点j加入禁忌表Tabu；步骤6：重复步骤4、步骤5，直至蚂蚁到达所有目标点，并保存所有蚂蚁所走路径及其长度，选择最优路径；步骤7：根据公式（10）更新各路径信息素；步骤8：判断是否达到最大迭代次数，若达到，则算法终止并输出最优路径，否则，重复步骤3至步骤7。

3 仿真试验

3.1 关键参数设置

为了验证本试验所提算法的有效性，进行了相应仿真试验，仿真试验环境为Matlab R2014a。在本试验中用25×25的栅格地图模拟真实的温室环境，栅格大小为单位长度为1的正方形，机器人起始点设置在地图的左上角，将2垄农作物之间路径的中点选取为可达点。在设置势场蚁群算法的基本参数时，由于目前尚没有科学的求取适合参数的方法，本试验所设置的参数完全是在仿真环境下试验所得结果，设置的参数为信息素启发因子α=0.7、期望启发因子β=0.3、信息素挥发系数ρ=0.2、信息素强度Q=10、引力增益系数katt=2、斥力增益系数krep=1、斥力作用半径d0=2。

3.2 仿真试验结果

考虑到温室内的实际种植环境，温室内可能会分布一些其他设施，比如温室内的承重柱，各种监测温室内温度、湿度的設施，农作物种植时要避开这些设施，利用栅格地图描述的实际种植效果和势场蚁群算法规划的路径结果如图5所示。改进后的势场蚁群算法的最大迭代次数Nmax设置为50，每次释放蚂蚁数目m=100，规划结果最小路径长度为Lmin=233941 1，并且机器人所走路径包围了农作物种植区域，达到了本试验路径规划的目的。

路径规划过程中会产生大量的迷失蚂蚁，迷失的蚂蚁会在数据筛选过程中剔除，并且迷失的蚂蚁所走路径不能进行信息素更新。由图6可知，在50次的迭代过程中，在第39次产生最短路径，经过2次波动后，最终收敛于最短路径。

在目前的温室种植条件下，农民为了避免种植单种农作物带来的经济风险，根据农作物生长周期安排合理种植等问题，可能会在同一温室内的不同区域同时种植多种农作物。这些农作物由于种类不同，机器人工作的区域就不是整个温室，而是其中的某一个区域或多个区域，如图7所示，温室内同时种植了4种作物，只有其中2块区域的作物需要机器人工作，由于此时的路径规划相对复杂，势场蚁群算法的基本参数不变，机器人起始位置仍然在地图的左上角，每次释放蚂蚁数量增加到300只，当机器人的路径包围了所有需要工作的区域后停止工作，最终的规划结果为最小路径长度为 Lmin=152.355 3，达到了规划目的，机器人所走路径包围了需要工作的农作物覆盖区域，并且路径长度最短。由图8可知，在50次的迭代过程中，在第40次产生最短路径，经过1次波动后，最终收敛于最短路径。endprint

4 结论

本试验针对在温室环境下机器人的特殊路径规划问题，采用人工势场算法和蚁群算法融合的方法，提出蚂蚁根据当前所在位置采用确定性方向转移或者概率性方向转移选择下一个节点的策略。确定性方形转移保证了蚂蚁能快速地向可达点或者目标点的方向运动，概率性方向转移保证了该算法解的多样性。同时，将蚁群算法中的不适应温室环境路径规划的约束条件优化为适应温室路径规划的条件。在Matlab的仿真环境下，对本试验所提算法进行了验证，结果表明，本试验算法对温室环境下路径规划的效果较好，同时具有动态的收敛过程。

参考文献：

[1]高国琴，李 明. 基于K-means算法的温室移动机器人导航路径识别[J]. 农业工程学报，2014，30（7）：25-33.

[2]陈济勤. 农业机械运用管理学[M]. 北京：中国农业出版社，1999.

[3]Stoll A. Automatic operation planning for GPS-guided machiner[C]//Proceedings of 4th European Conference on Precision Agriculture. 2003：657-664.

[4]Dorigo M，Maniezzo V，Colorni A. Ant system：optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems，Man，and Cybernetics，1996，26（1）：29-41.

[5]叶兆莉，袁明新，程 帅，等. 移动机器人的一种烟花爆炸式新免疫规划算法[J]. 计算机仿真，2013，30（3）：323-326，375.

[6]Manikas T W，Ashenayi K，Wainwright R L. Genetic algorithms for autonomous robot navigation[J]. IEEE Instrumentation and Measurement Magazine，2007，10（6）：26-31.

[7]Alvarez A，Caiti A，Onken R. Evolutionary path planning for autonomous underwater vehicles in a variable ocean[J]. IEEE Journal of Oceanic Engineering，2004，29（2）：418-429.

[8]Cobano J A，Conde R，Alejo D，et al. Path planning based on genetic algorithms and the Monte-Carlo method to avoid aerial vehicle collisions under uncertainties[C]//International Conference on Robotics and Automation. 2011：4429-4434.

[9]周明秀，程 科，汪正霞. 動态路径规划中的改进蚁群算法[J]. 计算机科学，2013，40（1）：314-316.

[10]段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社，2005.

[11]Khatib O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research，1986，5（1）：90-98.张启宇，刘 峰，陈英义，等. 海参病害防治诊断专家系统的研究[J]. 江苏农业科学，2017，45（18）：226-229.endprint