基于蚁群算法的多采摘机器人路径规划与导航系统

张 璐，王 慧

(河南工业职业技术学院，河南 南阳 473000)

0 引言

近年来，人工智能已成为新一轮工业革命的基石，不仅广泛应用于工业控制领域，在农业生产中的应用越来越普及。在农忙时节，农场往往会出现劳动力大量匮乏的现象，因此机器人在农业上的应用需求越来越明显。研发出一种能进行远程控制的采摘机器人，代替传统人力的作业操作，对提高农业生产水平及种植效率具有重要意义，也是现代化农业的发展趋势。为此，根据采摘机器人作业环境，采用蚁群算法，结合先全局后局部的路径规划方法，设计了一种多采摘机器人路径规划和导航系统。

1 蚁群算法简述

蚁群算法是意大利学者Dorigo在20世纪90年代模拟和总结蚂蚁寻找食物的一系列行为过程，得出的一种解决复杂组合优化问题的方法。该方法从蚂蚁、蜜蜂这些昆虫寻找食物的行为入手，其实对于一个个体而言，它们的行为非常容易分析，但当它们组合成一个庞大的群体后，群体行为分析难度就大大增加了。其原因是因为蚂蚁个体间是由一种分泌物作为信息素进行交流通信，蚂蚁在行走的路线上会留下这些物质，而所有的蚂蚁都能够感知这些物质的浓度，并根据该物质浓度的强弱选择自己的运动方向。因此，蚁群的集体行为会形成一种特定的信息正反馈场景，即某路线上经过的蚂蚁数量越大，则后面选择该路线的蚂蚁就会越多。蚂蚁间根据感知这种信息素物质的强弱实现搜索食物的整个过程，这也就是蚁群算法的缘由。蚁群寻找食物过程示意图如图1所示。

图1 蚁群寻找食物过程示意图Fig.1 The schematic diagram of ant colony searching for food process

图1中，假设A为蚁群群居的位置，E为有食物的地方，MN为AE之间的一个阻挡物。由于从A到E之间存在障碍物MN，那么蚁群在搬运食物的过程中只能是从BCD或者BFD两条路径。其中，两条路径的长度分别为10和20。假设在1min内有200只蚂蚁从A运动到E，蚂蚁经过后信息素总数增加为20，为了让计算比较简单，设定信息素从产生到消失的时间为10min。在最开始时，没有信息素物质的存在，蚂蚁选择两条路线的概率相同；但因为BCD路径短，蚂蚁选择BCD需要的时间较少，因此在相同时间内，走过BCD的蚂蚁会多一些；这样BCD路径上的信息素物质比BFD要多，也会吸引后面的蚂蚁从BCD走，从而实现从A到E的最优路径。

蚁群算法最初是应用于解决TSP问题，其原理为：在最初时刻，所有蚂蚁都在同一起点，每条可供选择前进路径的信息素物质都为零，设定行程最短的路径距离为smin，距离最长的为smax，经过的蚂蚁数量为M。其中，经过smin和smax的蚂蚁数量分别为M1和M2，则

M=M1+M2

(1)

那么，当M只蚂蚁经过smin和smax后，接下来的蚂蚁从smin经过的概率为

(2)

其中，Psmin(M+1)为低M+1次蚂蚁从smin经过的概率；a和h为参数。

2 多采摘机器人路径规划

在多采摘机器人作业过程中，障碍物较多，机器人间相互影响，成为彼此的障碍物，因此多机器人路径规划难度较大。在实际研究中，多个采摘机器人在同一种植区作业，需要规划多条最优路径，但在具体的作业过程中，由于障碍物的存在，最优路径会发生变化，也会影响其他机器人的移动路径。基于上述问题，为了保证多采摘机器人实现无碰撞作业，该系统需要实时规划路线，防止机器人间、机器人与障碍物间的碰撞。

2.1 多采摘机器人路径规划整体设计

由于产业种植园区环境不确定性因素较大，如种植人员园区工作以及其他机械的随机移动，且传感器探测具有一定的局限性，机器人在最初规划时往往很难获取全部的信息，采用简单的规划往往难以获得理想的最优路径。因此，可在获得一定园区环境信息的基础上，进行作业前的全局规划，并将其作为理想的最优路线。在采摘机器人群的实际运动作业中，根据后续探测的环境信息，规划出局部的最优路径，进行简单的微调，使机器人避开所有碰撞物，并最快地到达目的地。基于以上问题，该系统采用全局和局部的规划方法，实现多采摘机器人的路径规划。多采摘机器人路径规划框架如图2所示。

1)全局路径规划。本章研究的是多采摘机器人在实际园区作业过程中的路径规划算法，对于其全局路径规划，首先要做到的是按照具体作业要求，根据已知环境信息，给每个机器人分配任务，并确定每个机器人作业的起始点和终点，然后结合多机器人间的合作机制，在两点之间规划一条无碰撞的优化路线。在整个算法中，最重要的是提高路线规划速度和实现路径规划的最优性。由于蚂蚁算法路径规划效率比较高，且其对于障碍物变化的适应性较强，因此本文将采用蚁群算法对多采摘机器人进行全局路径规划。

2)局部路径规划。有了全局路径规划之后，采摘机器人群就可以开始各自的作业任务。开始阶段，采摘机器人将按照各自的规划路径进行作业，并实时采集周边环境信息，根据采集到的动态信息，进行分析处理，根据碰撞检测、决策算法和行为检测等进行局部的路径修改，从而使自身具有更强的环境适应能力。

本系统采用的局部规划算法是利用机器人的车载传感器对周边环境信息进行实时检测，并与全局规划时的信息进行对比分析，根据碰撞检测子系统对是否存在碰撞风险进行评估。若存在撞机危险，则对局部路径进行一定的调整，在调整过程中，始终以作业终点为最终目标，避免出现局部的极值点而忽略机器人整体规划。另外，在局部规划过程中，行为检测子系统需要实时对采摘机器人规划的路径进行判断，确定其是否符合全局规划的目标，若符合，则执行。在机器人成功避开障碍物后，则可以按照全局规划的路线继续进行作业操作，在执行期望路径的过程中，向最近的子路径节点移动。如此反复，不管局部规划路径怎么实施，采摘机器人最终的目标终点不会发生改变，直到其成功到达终点。

图2 路径规划框架图Fig.2 The path planning framework

2.2 路径规划的适应度函数

在进行路径规划中，除保证各机器人前进路径最优外，还需要各机器人间协调，以避免出现两采摘机器人发生碰撞。路径规划的适应度函数是影响蚁群算法能否高效的计算出最优解的主要原因，多采摘机器人路径规划要求包含避障和距离最短。因此，适应度函数重点要考虑路径长度、路径平滑度及可行性，计算方法如下：

路径长度为

(3)

其中，d(p)为路径长度；i为路径子节点编号；n为障碍物数量。

d(p)的倒数是决定路径规划是都最短的适应度函数fit1，其表达式为

(4)

路径平滑度为

(5)

其中，h(p)为路径平滑度。在路径规划过程中，在选择目标函数时，要结合采摘机器人移动性能、光滑适应性作为主要参数，尽可能使生成的路径变化均匀，取h(p)的倒数为路径平滑度的适应度函数fit2为

(6)

躲障是采摘机器人工作的首要条件，是其正常作业的保证，因此可行性是指采摘机器人群是否能够安全地避开障碍物并得到终点。以下是采摘机器人在最优路径行驶中会出现的几种情况：

1)在优化路径中没有出现障碍物，则可以按照蚁群算法确定其适应度函数fit3为

(7)

由式(7)可以看出：当规划的路径中没有出现障碍物时，fit3值为1，否则为0。

2)假设一采摘机器人从路径子节点i移动到路径子节点i+1，则其与障碍物不想交的适应度函数fit4为

(8)

综上所述，采摘机器人最终可行性为

Fi1t=fit3·fit4

(9)

3 多采摘机器人导航系统

3.1 导航系统整体方案

多采摘机器人导航系统是指在执行任务期间，对各采摘机器人的作业路线进行导航，即根据空间位置的做出全局规划，结合在前进过程中感知到的部分环境信息，实时对路线进行恰当的修改，引导各机器人安全前进到指定位置。该方案主要包括环境建模、自主定位和路径规划3部分。由于路径规划已在前一章详细的阐述，这里不再重复。

1)环境建模。环境建模是指采用数学模型的方法，对采摘作业区域进行详细描述，并将其抽象成计算机系统能够直接识别的数据信息。本文所采取的导航系统数据信息存在于后台服务器中，并由该信息抽象出拓扑图，对路线信息进行简单的描述。另外，也方便各采摘机器人识别道路之间的联系，准确实现全局、局部路径规划和实时导航。

2)采摘机器人定位。采摘机器人定位是指根据周边环境信息和GPS确定其在作业区域相对于全局坐标的具体位置，其流程图如图3所示。

图3 采摘机器人定位流程图Fig.3 The positioning flow chart of picking robot

3.2 环境建模的具体实现

环境建模的空间信息对实现多采摘机器人的导航具有决定性的意义，本文所采用的方法是将地图信息存在后台服务器，通过后台服务器的数据库进行拓扑图的绘制，并采用循环链表的方式将数据信息进行保存。因此，后台服务器中的数据库存放有地图的全部信息，可用于多采摘机器人的实时定位与导航，而拓扑图则可以用于结合蚂蚁算法实现路径的最优规划。

1)地图信息数据库。先将地图信息分为站和道路两种，其中站面积比较大，占地较多，可以用来让机器人进行短暂的停留；而道路则是机器人前进的路线，用来连接各个站。其次，在策略算法进行规划的过程中，可以将站和道路看成一段段或者一块块的矩阵，将其连接起来就可以用来表示地图。地图信息如图4所示。

图4 搭建导航地图信息图Fig.4 The establishment of navigation cartographic information

2)建立拓扑图。建立拓扑图需要以服务器中的数据信息为依据，其主要是用来描述各站点与道路之间的连接状态，在内存中以循环链表的方式进行储存。导航地图拓扑图如图5所示。

图5 导航地图的拓扑图Fig.5 The topological graph of navigation map

循环链表是数据结构中一种常用的保存数据信息的方法，可以灵活地表示数据间的前后关系，找到其中一个信息，便可以知道其前后内存里面的信息。在导航过程中，需要经常访问节点间的连接信息，因此采用该方法可以大大提高数据读取信息。

4 实验结果与分析

为了验证多采摘机器人路径规划与导航系统的准确性可靠性，本文利用MatLab仿真软件对其进行了仿真实验。其中，蚁群迭代步长设置为0.02，迭代次数为100次，运行环境为200m×200m的区域，本实验中采摘机器人数量为3个。实验目的：在采摘作业区域，该系统经过改变执行和迭代次数，判断多采摘机器人群是否能够成功避开障碍物，并且安全达到目的地。仿真结果如图6所示。

图6 仿真结果图Fig.6 The simulation result diagram

由图6可以看出：实验中各采摘机器人均安全从起点到达终点，当一条线路只能允许一台机器人通过时，其他机器人能够避让到站点休息，然后再进行前进操作，成功解决了路径冲突的问题。从路径长度和光滑度可以看出，该系统优化效果明显，具有很强的避障、路径规划和导航能力，且可行性高。

5 结论

1)针对多采摘机器人联合作业容易出现路径冲突和碰撞的问题，采用蚁群算法，设计了多采摘机器人路径规划和导航系统。

2)针对产业种植园区环境不确定性因素较大及机器人在最初规划的时候往往很难获取全部的信息的问题，提出了先全局后局部的路径规划方法，实现了多采摘机器人移动路径的实时动态规划。

3)提出了多采摘机器人环境下，各机器人利用环境建模和自主定位进行自主导航的方法，通过建立地图信息数据库和拓扑图，实现了对多采摘机器人的安全引导。最后，运用MatLab软件仿真对路径规划和导航成功进行了验证。