基于双向迪杰斯特拉算法移栽机补栽路径规划及仿真

冯莉 吕修凯 崔生乐 杨春梅 徐晓燕

摘要：为提高移栽机补栽作业的自动化水平，对移栽机补栽路径规划进行研究。首先，对移栽机补栽进行分析并建立路径规划仿真地图；然后，提出一种双向迪杰斯特拉算法，并进行二次优化实现节点排序，配合A*算法的避障功能实现路径；最后，基于C++编程及OpenCV实现算法功能并进行图像绘制实现算法仿真。仿真结果表明：采用改进后的双向迪杰斯特拉算法规划路径，路径移动距离平均下降14.74%，转向次数平均减少8%，移动时间平均减少13.41%。双向迪杰斯特拉算法，相比迪杰斯特拉算法规划的目标节点顺序更优。因此，改进后的算法能实现移栽机补栽更优的路径规划，提升移栽机补栽效率，为补栽路径规划问题的研究提供重要参考。

关键词：移栽机；补栽；路径规划；避障算法；迪杰斯特拉算法

中图分类号：S223.92

文献标识码：A

文章编号：2095-5553 （2023） 03-0177-06

Abstract： In order to improve the automation level of transplanting machine replanting operation， the path planning of transplanting machine replanting was studied. Firstly， the replanting of transplanting machine was analyzed and the path planning simulation map was established. Then， a bidirectional Dijkstra algorithm was proposed， and the secondary optimization was carried out to realize the node sorting， and the obstacle avoidance function was realized with the A* algorithm. Finally， based on C++ programming and OpenCV， the algorithm function was realized and the algorithm simulation was realized by image rendering. The simulation results show that using the improved twoway Dijkstra algorithm to plan the path， the path moving distance decreases by 14.74% on average， the number of turns decreases by 8% on average， and the moving time decreases by 13.41% on average. Bidirectional Dijkstra algorithm is better than Dijkstra algorithm in planning target node order. Therefore， the improved algorithm can realize better path planning of transplanting machine replanting， improve the efficiency of transplanting machine replanting， and provide an important reference for the research of replanting path planning.

Keywords： transplanter; replanting; path planning; obstacle avoidance algorithm; Dijkstra algorithm

0引言

苗木移栽，是傳统的劳动密集型产业。传统苗木人工移栽存在效率低、移栽精准度差且较为浪费土地及水资源等问题。因而，通过移栽机进行精选机械化移栽作业，对于提升移栽行业的机械化、智能化水平具有重要意义。但是在苗木移栽种植过程中存在缺苗漏种的现象［12］，其主要由于育苗阶段、运输过程中的种种不确定的因素使得钵苗在移栽之前受损导致坏苗；其次由于我国目前全自动移栽机的技术不够成熟，如在复杂工况时机械振动使得取苗失败或基质块破损等情形导致漏种［34］；此外，移栽完成之后由于苗木生存温度、水分等环境因素的影响，存在移栽完成后苗木死亡的情况［5］。在日常作业中为改善这种情况通常需要人工补栽，因此耗费了大量人力，降低了工作效率。

针对这一现象已有学者进行了相关研究，何永玲等［6］针对甘蔗在移栽过程中出现漏播问题，设计了一款补种系统并进行正交试验，补种成功率达到93.97%。伍龙等［7］研究了一种基于PLC的移栽机穴盘苗的取苗喂苗系统，实现了高效移栽。冀荣华等［8］研究了一种基于贪心—蚁群算法的移栽机路径分段优化算法，优化了钵苗自动移栽机的路径，有效提高了移栽效率。魏宁等［9］在对苗木移栽的研究中发现钵苗移栽完成后，存在着由于苗木自身和外界环境因素导致苗木死亡情形。国内外学者对苗木移栽、全自动移栽机及其路径规划的研究较多［1012］。

从国内外学者研究结果来看，移栽机完成移栽作业后，存在着漏栽缺苗或幼苗死亡的问题。为提高土地的利用率，保证移栽苗木的种植密度，从而提升移栽的经济性，所以有必要对移栽后的土地进行补栽。目前针对使用移栽机补栽的路径规划研究及避障问题，大多集中于室内钵苗移栽机补栽问题且多采用遗传算法进行，较少针对室外土地进行移栽机补栽的路径规划及避障问题的研究。

为此，在迪杰斯特拉算法的基础上，提出一种双向迪杰斯特拉算法解决移栽机补栽作业时的路径规划问题，并使用A*算法实现移栽机避障，从而提高移栽机补栽的自动化水平。

1补栽问题分析

采用移栽机作业取代人工苗木移栽是提升移栽行业机械化水平的重要途径。苗木在移栽完成后，由于种种不确定性因素使得漏栽缺苗的情形不可避免，因此补栽成为移栽作业不可或缺的工序之一。补栽过程中，若能够采用先进算法进行路径优化，便可以降低移栽机在作业期间的路径重复程度，对提升移栽机补栽效率具有重要的意义［1315］。本文所述路径规划问题主要针对移栽机补栽过程进行。当移栽机完成移栽后需要补栽且地图情况已知时，此时由计算机系统根据移栽林地情况，按照算法进行路径规划，并将规划后的结果输入移栽机。此后，移栽机根据输入的路径实现补栽过程。

首先，建立移栽机补栽的仿真地图，如图1所示。地图中每一方格（参考图中绿色方格）是实际情形的1 m×1 m大小；其中，绿色方格代表的苗木是成活的；黑色方格代表苗林中的障碍物；白色方格代表苗木间的可行道路；粉色方格代表需要补栽苗木的位置。因此移栽机补栽问题可以简化为：移栽机从地图起点开始，遍歷地图中需要苗木补种的目标节点，实现苗木补种；在移栽机移动过程中，除进行目标节点排序外，还需要规划各个节点之间的具体路径，并实现避开障碍物的功能。

2移栽机补栽路径规划算法

2.1迪杰斯特拉算法及A*算法

迪杰斯特拉算法由荷兰计算机科学家狄克斯特拉设计的一种用来解决最短路径问题的算法，其采用的是贪心策略［16］。

迪杰斯特拉算法原理是：给予地图中的节点权值，并将节点分为S和S-V两个集合。其中，S集合包含的是已经放置到最短路径中的节点，S-V集合中包含的是剩余但未排进最短路径的节点。迪杰斯特拉算法是将S-V集合中的目标节点按照权值递增的顺序逐个加入S集合中，直到S-V中的节点全部加入S集合，从而实现地图目标节点最短路径遍历的目标。

A*算法是启发式算法的一种［17］。该算法的核心是最优启发式函数，其函数为

f*（n）=g*（n）+h*（n）

（1）

其中f*（n）为代价函数，取当前节点周边的某一可移动点，该点到当前节点的距离即为g*（n），h*（n）是该可移动点到目标节点的最短距离。一般情况下，h*（n）值不可知。因此实际应用A*算法时，常用h（n）近似代替h*（n）。其中h（n）为h*（n）的估算值，且一般情况下h（n）≤h*（n），h（n）的估算方法是计算可移动节点到目标节点的直线距离。通过比对当前节点周边可移动节点的代价函数f*（n）的数值，则A*算法可以确定要移动的下一节点，并将此节点作为当前节点，重复上述步骤，直至到达终点。一般情况下，A*算法均倾向于移动到代价函数小的节点上［18］。

2.2双向迪杰斯特拉算法

实现移栽机补栽路径规划的第一步是对需要补栽的节点进行遍历排序。传统算法中，采用迪杰斯特拉算法可以实现这一功能。但是在移栽机遍历顺序排序中，采用迪杰斯特拉算法规划的节点遍历顺序并不最优。其原因在于：在移栽机补栽的仿真中，迪杰斯特拉算法是将节点与起点的距离值作为排序依据进行节点遍历排序的。当排序的节点与起点相近时，排序效果较好，若节点与起点距离较远时，将每个节点到起点的距离作为代价函数值时，该代价函数不包含节点相对于起点的方向信息（例如该节点在地图对角线的上方或下方），且各个节点的代价函数值无法代表各个节点间的距离关系，使得迪杰斯特拉规划出的路径存在较远节点之间来回穿梭的情形，从而增加了路径距离，故迪杰斯特拉算法规划的路径不能最优。因此，本文提出了一种双向迪杰斯特拉算法，实现对迪杰斯特拉算法的改进，从而使得算法排序效果更优。

双向迪杰斯特拉算法是指将各个节点到起点以及终点的距离共同作为排序的代价函数的因素，进行节点排序的一种算法，其代价函数如式（2）所示。

迪杰斯特拉算法及双向迪杰斯特拉算法遍历顺序排序，如图2所示。其中蓝色线条是迪杰斯特拉算法确定的遍历顺序，紫色线条是双向迪杰斯特拉算法确定的遍历顺序。经过测试，K值取1.5时，算法能够达到较好的性能。

综上，双向迪杰斯特拉算法，在移栽机路径规划中，规划遍历顺序的方式类似于A*算法，其原理如下。

1）  先读取地图中全部需要移栽机进行补栽的节点即目标节点坐标。

2）  根据式（2）计算每一个目标节点的目标函数值。

3）  根据第2步计算的目标函数值，进行节点排序，生成初始的目标节点遍历顺序。

4）  对第3步的初步节点进行二次优化，二次优化的原理是：顺序遍历第3步中的每一个节点，每遍历一个节点，即选择该节点前后相邻的两个节点，计算遍历三个节点的路径移动距离，之后交换当前节点前后的两个节点，并计算交换后的路径移动距离，根据两次计算的路径移动距离大小决定是否交换该节点前后两个节点之间的顺序。

双向迪杰斯特拉算法的起点与终点选择，应当遵循在地图同一侧的原则；例如，选择地图左下角及右上角分别作为起点与终点。为保证双向迪杰斯特拉算法排序结果更优，需对双向迪杰斯特拉算法排序进行二次优化。二次优化的原理是：取双向迪杰斯特拉算法第一次排序后，顺序为1的节点，对该节点之后的两个节点按照迪杰斯特拉算法进行二次排序，并相应调整遍历顺序后，再依次对后边节点进行相同的操作，直到二次优化完成。

从图2可以看出，改进后的双向迪杰斯特拉算法确定的遍历顺序更好。其原因在于：（1）代价函数中，节点与地图右上角的距离，提供了偏向于地图左侧的因素，使得排序节点更倾向于历经地图左侧节点后再回到右侧，从而避免了路径较远节点间来回穿梭的开销。（2）迪杰斯特拉算法，对较为靠近起点的节点进行排序的效果较好。因而，公式选择对节点相对起点及终点的距离求平方后再相加，从而增加起点及终点对节点代价函数影响的非线性，即当节点靠近起点时，代价函数受起点影响较多，而当节点靠近终点时，代价函数数值受终点影响较多。（3）如式（1）所示，代价函数中，起点及终点对代价函数数值的影响因子不同，这是由于采取相同的影响因子后，双向迪杰斯特拉算法容易将位于起点及终点同侧靠近中间的节点向后排序，采取不同影响因子后，可以消除此现象。（4）双向迪杰斯特拉算法对遍历顺序进行了二次优化，使得结果更优。

2.3生成細化路径

本文提出的双向迪杰斯特拉算法，实现了移栽机补栽的目标节点排序，但排序结果仍然不是最终路径，本文采用A*算法避障，并生成最终路径。移栽机补栽作业的最终路径应当是，由起点开始，沿着可行区域，逐个移动到目标节点，直到遍历全部目标节点。因而，在确定目标节点遍历顺序后，还需要按照遍历顺序规划各个节点之间的路径，并合理避开已存在成活苗木的节点及其他障碍节点。

最后，移栽机补栽作业路径规划的算法流程图，如图3所示。

3移栽机补栽路径规划仿真

3.1仿真方法及环境搭建

本文采用C++函数封装的方法［19］，实现迪杰斯特拉、双向迪杰斯特拉及A*算法的功能。全部地图数据从TXT文件中读取，以便于修改地图。采用OpenCV4.4，根据TXT文件地图数据进行仿真地图构建，并将仿真结果生成的节点左边转化为路径，绘制到仿真地图中。

3.2仿真结果及对比

移栽机补栽路径规划的仿真对比如图4所示，其中蓝色线条是采用迪杰斯特拉算法进行目标节点遍历顺序排序后，采用A*算法连接各个节点后的路径（下文中简称为迪杰斯特拉算法路径）紫色线条是采用双向迪杰斯特拉算法进行目标节点遍历顺序排序后，采用A*算法连接各个节点后的路径（下文中简称为双向迪杰斯特拉算法路径）。显然，本文提出的双向迪杰斯特拉算法规划的路径更优。

设定移栽机补栽作业时直线移动速度为1 m/s，转向或掉头时间为5 s，在随机更改障碍物及目标节点后，进行15次仿真对比，移动距离、转向次数与消耗时间结果如表1所示。迪杰斯特拉算法规划的路径平均移动距离和平均转向次数分别为669.54 m、47次，双向迪杰斯特拉算法规划的路径平均移动距离和平均转向次数分别为570.86 m、43次，改进算法前后对比路径平均移动距离和平均转向次数分别下降了14.74%、8%。由于改进后双向迪杰斯特拉算法规划的移栽机补栽路径平均移动距离和平均转向次数的明显降低，使得移栽机补栽移动时间平均减少了13.41%。

4结论

1）  针对移栽机补栽作业自动化水平低的问题，进行了移栽机补栽作业路径规划，分析了路径规划的过程，建立路径规划仿真地图。本文提出了一种改进后的迪杰斯特拉算法即双向迪杰斯特拉算法，并进行二次优化实现目标节点排序，配合A*算法的避障功能实现路径规划。

2）  基于C++及OpenCV编程实现了路径规划的仿真，具体方法为：采用C++封装函数实现算法功能，采用OpenCV将规划结果显示到地图中并保存。

3）  对改进前后的迪杰斯特拉算法进行仿真，仿真结果表明移栽机补栽的路径平均移动距离为570.86 m，转向次数为43次，相比于改进前的算法，其路径移动距离平均下降了14.74%，转向次数下降了8%，移动时间减少13.41%，实现了移栽机补栽作业时的路径规划及避障功能，较大程度上提高了移栽机补栽自动化水平。

参考文献

［1］高庆生， 陈永生， 管春松， 等. 露地蔬菜机械化移栽作业现状及水平分析［J］. 中国农机化学报， 2021， 42（11）： 193-197.

Gao Qingsheng， Chen Yongsheng， Guan Chunsong， et al. Status and level analysis of mechanized transplanting production of vegetables in open fields ［J］. Journal of Chinese Agricultural Mechanization， 2021， 42（11）： 193-197.

［2］文永双， 张宇， 田金元， 等. 蔬菜移栽钵苗检测与缺苗补偿系统设计与试验［J］. 农业机械学报， 2020， 51（S1）： 123-129.

Wen Yongshuang， Zhang Yu， Tian Jinyuan， et al. Design and experiment of detection and supply system of vegetable plug seedlings for transplanting ［J］. Transactions of the Chinese Society for Agricultural Machinery， 2020， 51（S1）： 123-129.

［3］Yang Qizhi， Ahmad， Faheem M， et al. Development and assessment of beltdrive seedlings transmission device for fullyautomatic vegetable transplanter ［J］. Computers and Electronics in Agriculture， 2021， 182.

［4］赵海， 刘新鑫， 潘志国， 等.甘薯种植农艺及机械化种植技术研究［J］. 中国农机化学报， 2021， 42（6）： 21-26.

Zhao Hai， Liu Xinxin， Pan Zhiguo， et al. Agronomic characteristics and mechanized planting technology of sweet potato ［J］. Journal of Chinese Agricultural Mechanization， 2021， 42（6）： 21-26.

［5］吴丽君， 游云飞， 陈达， 等. ‘黄樽薄叶金花茶组培苗生根与移栽技术研究［J］. 南京林业大学学报（自然科学版）， 2021， 45（3）： 117-122.

Wu Lijun， You Yunfei， Chen Da， et al. Optimization of the rooting and transplantation techniques of tissuecultured shoots of Camellia chrysanthoides ‘Huangzun ［J］. Journal of Nanjing Forestry University （Natural Sciences Edition）， 2021， 45（3）： 117-122.

［6］何永玲， 吳飞， 李尚平， 等. 甘蔗横向种植机补种系统设计与试验［J］. 农业机械学报， 2020， 51（1）： 94-102， 138.

He Yongling， Wu Fei， Li Shangping et al. Design and test of replenishment system for sugarcane horizontal planter ［J］. Transactions of the Chinese Society for Agricultural Machinery， 2020， 51（1）： 94-102， 138.

［7］伍龙， 刘念聪， 王艳华， 等. 基于PLC的全自动移栽机取苗喂苗控制系统设计［J］. 中国农机化学报， 2021， 42（10）： 87-91.

Wu Long， Liu Niancong， Wang Yanhua， et al. Design of the control system for picking up and feeding seedlings of automatic transplanter based on PLC ［J］. Journal of Chinese Agricultural Mechanization， 2021， 42（10）： 87-91.

［8］冀荣华， 邹国伟， 袁宏涛， 等. 基于贪心—蚁群钵苗自动移栽路径分段优化算法研究［J］. 中国农机化学报， 2019， 40（12）： 165-170.

Ji Ronghua， Zou Guowei， Yuan Hongtao et al. Study on the segmentation optimization algorithm of the automated transplantation path of plug seedlings based on greedyant colony ［J］. Journal of Chinese Agricultural Mechanization， 2019， 40（12）： 165-170.

［9］魏宁， 李国雷， 蔡梦雪， 等. 缓释肥施氮量对4种国外栎苗木质量及移栽成活率的影响［J］. 南京林业大学学报（自然科学版）， 2021， 45（3）： 53-60.

Wei Ning， Li Guolei， Cai Mengxue， et al. Effects of slowrelease fertilization rates on seedling quality and field survival rates of four exotic oaks ［J］. Journal of Nanjing Forestry University （Natural Sciences Edition）， 2021， 45（3）： 53-60.

［10］Wang Yangjun， Liu Kefeng， Zhang Ren， et al. Feasibility of the Northeast Passage： The role of vessel speed， route planning， and icebreaking assistance determined by seaice conditions for the container shipping market during 2020—2030 ［J］. Transportation Research Part E， 2021， 149.

［11］杨保海， 任全会， 李海生. 复杂环境下果园机器人路径规划方法研究［J］. 中国农机化学报， 2021， 42（2）： 134-138.

Yang Baohai， Ren Quanhui， Li Haisheng.Research on path planning method of orchard robot in complex environment ［J］. Journal of Chinese Agricultural Mechanization， 2021， 42（2）： 134-138.

［12］裴晓康， 刘洪杰， 杨欣， 等. 苹果苗木移栽机栽植机构运动分析与试验［J］. 中国农机化学报， 2020， 41（6）： 20-25.

Pei Xiaokang， Liu Hongjie， Yang Xin， et al. Movement analysis and experiment of planting mechanism of apple seedling transplanting machine ［J］. Journal of Chinese Agricultural Mechanization， 2020， 41（6）： 20-25.

［13］Liao Bin， Wan Fangyi， Hua Yi， et al. F-RRT*： An improved path planning algorithm with improved initial solution and convergence rate ［J］. Expert Systems With Applications， 2021， 184.

［14］李晓静， 余东满. 基于自适应蚁群算法的农用智能机器人路径规划［J］. 中国农机化学报， 2019， 40（9）： 189-193.

Li Xiaojing， Yu Dongman. Path planning of agricultural intelligent robot based on algorithm of selfadaptive ant colony ［J］. Journal of Chinese Agricultural Mechanization， 2019， 40（9）： 189-193.

［15］刘洋成， 耿端阳， 兰玉彬， 等. 基于自动导航的农业装备全覆盖路径规划研究进展［J］. 中国农机化学报， 2020， 41（11）： 185-192.

Liu Yangcheng， Geng Duanyang， Lan Yubin， et al. Research progress of agricultural equipment full coverage path planning based on automatic navigation ［J］. Journal of Chinese Agricultural Mechanization， 2020， 41（11）： 185-192.

［16］马张烽， 岳东杰， 蒋弥， 等. 基于迪杰斯特拉算法的哨兵卫星TOPS模式时序影像精配准［J］. 武汉大学学报（信息科学版）， 2020， 45（6）： 904-913.

Ma Zhangfeng， Yue Dongjie， Jiang Mi， et al. Coregistration of image stacks for Sentinel1A TOPS mode based on Dijkstras algorithm ［J］. Geomatics and Information Science of Wuhan University， 2020， 45（6）： 904-913.

［17］李文刚， 汪流江， 方德翔， 等. 联合A*与动态窗口法的路径规划算法［J］. 系统工程与电子技术， 2021， 43（12）： 3694-3702.

Li Wengang， Wang Liujiang， Fang Dexiang， et al. Path planning algorithm combining A* with DWA ［J］. Systems Engineering and Electronics， 2021， 43（12）： 3694-3702.

［18］Roy S， Bhattacharyya A. A Kenmotsu metric as A*conformal Yamabe soliton with torse forming potential vector field ［J］. Acta Mathematica Sinica， 2021， 37（12）： 1896-1908.

［19］丁偉， 张文爱， 冯青春， 等. 畜禽舍防疫消毒机器人控制系统设计［J］. 中国农机化学报， 2019， 40（10）： 175-181.

Ding Wei， Zhang Wenai， Feng Qingchun， et al. Design of robot control system for disinfection of livestock breeding ［J］. Journal of Chinese Agricultural Mechanization， 2019， 40（10）： 175-181.