基于并行蚁群算法的设施温室机器人多点路径规划的研究

王红君 付勇 岳有军

摘要：在设施温室中，为了实现机器人在面对多个工作点时，能够找到一个最优顺序使得完成全部工作所走过的路程最短，受蚁群算法解决旅行商问题（TSP）的启发，提出一种并行的蚁群算法来解决设施温室农业机器人多点路径规划问题。首先，该算法借助于蚂蚁数量自调整的蚁群算法计算出所有点与点之间的最短安全距离，形成一个特殊的距离矩阵;然后借助于蚁群算法根据特殊的距离矩阵来寻找最优顺序;再按照最优顺序依次实现路径规划。仿真结果表明，该方法克服了目前蚁群算法在解决TSP上存在的近似计算及未考虑安全性问题，提高了计算精度，可以快速找到最优顺序进行路径规划，使机器人得到最短、最安全的路径。

关键词：温室机器人;多工作点;安全性;高精度;自调整

中图分类号： TP242  文献标志码： A  文章编号：1002-1302（2019）17-0237-05

路径规划是机器人领域研究的热点之一。在温室中，通过路径规划，机器人可以实现自主避开障碍物，找到一条安全、最短的路径到达指定位置进行工作。由于在设施温室中机器人的工作地点往往是随机分布的，为了能让机器人以最短的距离遍历全部工作地点，并完成全部工作，要求机器人可以实现多点路径规划[1]。由于多点路径规划就是遍历全部指定地点且仅经过1次，最后到达终点，且总路程最短[2]，因此可以将多点路径规划归结为旅行商问题（TSP）[3]。

TSP问题是一个著名的组合优化问题，同时也是颇具研发挑战难度的一类工程项目任务[4]。可以简单描述为有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访1次，而且最后要回到原来出发的城市[5]。路径选择目标的要求是在走完所有城市到达终点后所走的总路程是最短的。

经过不断探索，目前已提出如蚁群算法、遗传算法、粒子群算法等解决TSP问题的智能算法。邓慧允等通过对比发现，在解决TSP问题上，无论城市个数多少、城市之间的距离远近，蚁群算法都要优于遗传算法[6]。蒲兴成等将蚁群算法与粒子群算法相结合，不仅实现了点与点之间的距离最短，还将点与点之间的安全性考虑在内，较好地实现了移动机器人多目标点的路径规划，但该方法所得到的路径，并没有达到最短[7];杨岱川等提出将蚁群算法和改进PRM算法相结合，可以快速有效地实现多点路径规划，但该方法在路径规划时存在随机性[8];余晖等提出将快速行进（fast marching）算法与遗传算法相结合来进行路径规划，并将该方法应用到水下多点水质监测[9]。

在设施温室大棚中，多目标点路径规划比TSP问题复杂得多。既要找到使总路程最短的路径，还要保证点与点之间路径的安全性。虽然城市之间存在大量的障碍，且道路不可能是笔直的，因此蚁群算法在解决TSP问题时通过近似计算来计算2个城市之间的距离，由于距离较远、范围较大、要求精度不高，所以是合理的。但由于农业机器人多点路径规划的工作环境是在设施温室中，范围较小，且环境复杂存在着障碍物，要求精度较高，如果采用相同的方式进行计算寻优，会导致在设施温室中，农业机器人多点路径规划所得到的最终结果不精准、不安全。

本研究提出一种并行蚁群算法来解决设施温室大棚中的农业机器人多点路径规划问题，该算法使用改进的蚂蚁数量自调整的蚁群算法来计算多个点与点之间的最短安全距离，然后进行寻优，找到使得总体路径最短的顺序，最后进行点与点之间的路径规划。

1 基本算法原理

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

本研究探讨的是设施温室中的农业机器人多点路径规划问题，可以在二维空间进行分析[10]。目前环境建模的方法有很多种：单元分解法、模板模型法、拓扑法、可视图法、几何法。栅格法在实现上较为简单，通过矩阵就可以实现。因此本研究采用栅格法对设施温室大棚环境进行创建。

如图1所示，采用直角坐标法，黑色区域代表农作物种植和设备所在区域（危险区域），白色区域代表空地（安全区域）。危险区域的栅格中心坐标表示为障碍物的中心点，安全区域（白色部分）的栅格中心点作为农业机器人可行走的路径点。

1.2 蚁群算法

蚁群算法具有较强的鲁棒性、优良的分布式计算，易于与其他算法相结合[11-12]。蚁群算法解决TSP问题的基本原理，是在最初的时候将蚂蚁放到各个城市上，根据城市之间的距离来确定蚂蚁从某一城市到另一城市之间的概率，距离越小，被选中的概率越大，蚂蚁在走过的路径上释放信息素，信息素浓度随时间降低，后代蚂蚁根据前一代蚂蚁所留下的信息素的浓度的大小，确定行走的路径，并在所确定的路径上释放信息素;经过历代蚂蚁的寻找，最终找到信息素浓度最高的就是最优路径[13]。

2 改进的蚁群算法

2.1 并行蚁群算法

由于在设施温室大棚中的农业机器人多目标点路径规划可以归结为TSP问题，但是多目标点路径规划问题要比TSP问题复杂得多，不仅对精度要求较高，还要考虑到安全性的问题[14-15]。在存在障碍物的设施温室中，计算2点之间的距离不能忽略安全因素，须保证机器人能够在2点之间安全行走。保证机器人实际行走路程与计算的距离相等，不存在近似计算，从而提高精确度。

目前蚁群算法虽然能很好地解决TSP问题，但在设施温室大棚中不能精准、安全地实现多点路径规划。为此，本研究提出采用改进的并行蚁群算法来解决设施温室大棚农业机器人多点路径规划的问题。

2.2 点与点之间的距离计算

在存在障碍物的栅格图中要计算2点之间的最短安全距离，僅利用欧拉公式（2）计算不能达到目的。

2.5 算法流程

本研究算法流程见图2。

3 仿真试验及分析

为了检测该算法的有效性及优越性，本研究借助于Matlab软件对其进行了仿真试验。在带有障碍物的栅格中随机选取了14个点分别作为起点、终点以及必经点，规定机器人从起点出发到达终点，中途只能经过1次必经点。设置搜索最优顺序的蚁群算法的相关参数：每一代的蚂蚁数目m=50，蚁群迭代次数K=200，信息素α=1，启发式因子β=4，信息素蒸发系数ρ=0.2，信息素增加Q=100[16-17]。所有点的坐标a1（0.5，19.5）、a2（2.5，16.5）、a3（9.5，16.5）、a4（4.5，14.5）、a5（6.5，14.5）、a6（11.5，14.5）、a7（3.5，10.5）、a8（8.5，11.5）、a9（10.5，7.5）、a10（8.5，7.5）、a11（14.5，6-5）、a12（16.5，4.5）、a13（12.5，2.5）、a14（19.5，0.5）。

图3是在设有障碍物的栅格中标有多个工作点的坐标点。其中1表示农业机器人的起点，14表示终点，2～13表示的是必经过点。

通过对未考虑ω和考虑ω且对不同的ω得到不同蚂蚁数量所产生路径规划结果进行分析比较得到表1、表2：在中短距离时，ω=2时花费时间较短，而在长距离时，未考虑ω的情况花费时间较短，但是当2点相距较远时，未考虑ω所得到的结果在迭代稳定后又会出现跳变的不稳定现象。因此要考虑复杂度系数ω。

由表1、表2也可以看出，当2点距离较近时，复杂度系数ω的取值对趋于稳定的时间影响较小;但是距离较远时，复杂度系数ω的取值对区域稳定的时间影响较大。所以当2点之间的距离较近时，确定蚂蚁数量可以不考虑ω，当距离较远时，就必须考虑ω。因此从全局的角度考虑，为了进一步确定ω的范围，以远距离为试验对象，对ω从1.3～2.0进行试验，结果见图4。通过多次试验发现，在ω小于等于1.4时易出现迭代稳定后的跳变不稳定现象，为了能够保证蚁群算法的稳定性，ω取值要大于1.4;从图4曲线可知：当ω为1.6时所用时间最短，且随着复杂度系数ω的增加（蚂蚁数量的增加），所耗时间越多。

取ω=1.6进行全局的仿真试验，结果见表3，根据起点和終点的欧氏距离以及复杂度系数得到蚂蚁的数量，从全局结果来看该方法得到的蚂蚁数量较好，可以快速地找到最优路径。

多点路径规划得到的结果见图5，用蚁群算法进行多点规划得到最优顺序为：1、2、4、7、5、3、6、8、9、10、13、11、12、14。

在多点路径规划的过程中，随着历代蚂蚁的寻优，由图6可知，在对14个点进行路径规划的过程中，蚂蚁在10代左右就可以找到最优顺序实现总路程最短，总路程为55.355 0 cm。

4 结论

在农业设施温室大棚中，为了能够让机器人在面对多个工作点时，快速找到1条遍历所有点完成相应的工作最终到达终点的最短安全路径，本研究在蚁群算法解决TSP问题的基础上，提出了一种精度高、安全性好的蚂蚁数量自调整的并行蚁群算法进行路径规划。从仿真结果来看，该算法有以下优点：（1）构建了一个新的数学模型来求解蚂蚁数量，并找到了复杂度系数ω的合理取值范围。（2）在计算不同点之间的距离时，可以根据距离自行调整蚂蚁的数量在合理范围之内。（3）可以精确地计算出点与点之间的安全最短距离。（4）可以规划出遍历所有点的最优顺序，使得总的路程最短、最安全。（5）从收敛曲线来看，该算法在寻优的过程中可以快速找到最优路径并趋于稳定。

参考文献：

[1]梁宏伟，陶学恒，张世文. 移动机器人的遗传多点路径规划[J]. 科技信息（学术研究），2008（21）：584-585，587.

[2]郑继明，杨 坤，刘慧鹏，等. 基于0-1线性规划的多点路由规划模型研究[J]. 通信技术，2017，50（7）：1443-1446.

[3]Dantzig G，Fulkerson R，Johnson S. Solution of a large-scale traveling-salesman problem[J]. Journal of the operations research society of America，1954，2（4）：393-410.

[4]Caballero R，Hernandez-Diaz A G，Laguna M，et al. Cross entropy for multiobjective optimization problems with linear relaxation[J]. European Journal of Operation Research，2015，243（2）：362-368.

[5]Lin W，Delgado-Frias J G，Gause D C，et al. Hybrid newton-raphson genetic algorithm for the traveling salesman problem[J]. Journal of Cybernetics，1995，26（4）：387-412.

[6]邓慧允，张清泉. 蚁群算法与遗传算法在TSP中的对比研究[J]. 山西师范大学学报（自然科学版），2017，31（3）：34-37.

[7]蒲兴成，李俊杰，吴慧超，等. 基于改进粒子群算法的移动机器人多目标点路径规划[J]. 智能系统学报，2017，6（3）：301-309.

[8]杨岱川，文成林. 基于蚁群和改进PRM算法的多目标点路径规划[J]. 杭州电子科技大学学报（自然科学版），2017，37（3）：63-67.

[9]于 晖，王永骥. 基于fast marching方法的多目标点路径规划的研究[J]. 计算技术与自动化，2015，34（3）：11-15.

[10]史恩秀，陈敏敏，李 俊，等. 基于蚁群算法的移动机器人全局路径规划方法研究[J]. 农业机械学报，2014，45（6）：53-57.

[11]Vogt L，Poojari C A，Beasley J E. A tabu search algorithm for the single vehicle routing allocation problem[J]. Journal of the Operational Research Society，2007，58（4）：467-480.

[12]朱铁欣，董桂菊，颜丙学，等. 基于改进蚁群算法的农业机器人路径规划研究[J]. 农机化研究，2016（9）：48-52.

[13]喻 环. 改进蚁群算法在机器人路径规划上的应用研究[D]. 合肥：安徽大学，2017.

[14]朱 霞，陈仁文，徐栋霞，等. 基于改进粒子群的焊点检测路径规划方法[J]. 仪器仪表学报，2014，35（11）：2484-2493.

[15]萧蕴诗，李炳宇，吴启迪. 求解TSP问题的模式学习并行蚁群算法[J]. 控制与决策，2004（8）：885-888.

[16]张 可. 蚁群算法的参数调整研究[D]. 合肥：合肥工业大学，2012.

[17]杨亚南. 蚁群算法参数优化及其应用[D]. 南京：南京理工大学，2008.