自动翻晒谷物机器人的全覆盖路径规划研究

王温鑫

（仰恩大学 工程技术学院，福建泉州，362000）

0 引言

谷物干燥是谷物收获后需要处理的重要步骤，不仅保证了谷物的品质而且能够提高谷物的出谷率。因气候原因，谷物可能由于没有晒干达不到安全水分的要求，导致其产量受到损失，因此对谷物进行翻晒使其充分干燥，将损失降低到最低点是谷物生产、丰收的重要保障。目前谷物翻晒主要有两种方式：一是人工翻晒，该方案不仅劳动强度大且易受天气的影响；二是使用大型机械设备进行烘干，该方法成本高且产生的废气会对空气造成一定的污染。因此为了减少翻晒劳动力和降低干燥成本，研发一款小型自动翻晒谷物机器人是非常有价值的。随着精准农业的大力推广，全覆盖路径规划是翻晒谷物机器人对谷物进行全面均匀翻晒的研究重点。在国外，Khan A 等人利用在线牛耕分解法对未知工作空间进行区域划分，并利用所提出的双向邻近搜索算法，使用回溯技术完成区域全覆盖[1]；Hong 等人利用启发式模板规则并结合贪心准则的回溯机制实现区域全覆盖[2]；Ma 等人提出一种高精度定位、低分辨率栅格建模方法，并利用生物激励网络实现移动机器人的全覆盖路径规划[3]。在国内，聂杨利用无标识工作区域的边界建立和识别方法，引导机器人完成草坪边界信息的采集，然后将A*算法与往复式算法相结合实现割草机器人的全区域覆盖路径规划[4]；李楷提出一种起始点方向优先的局部区域覆盖算法，然后结合改进的theta*算法进行子区域间的衔接，实现全覆盖路径规划[5]；周琳娜等人提出利用牛耕分解法对环境地图进行划分，然后将生物激励神经网络算法与深度优先算法相结合完成作业区域全覆盖[6]。

为了使谷物机器人对谷物实现全面的均匀翻晒，提高谷物翻晒效率。本文提出一种基于改进A*算法的全覆盖路径规划方法。首先，设计了面向谷物翻晒机器人的环境建模方法和区域划分策略。接着根据谷物机器人的作业能量消耗与实际需求，利用沿长边行走的弓子型往返式路径规划方法，实现子区域全覆盖。其次，通过贪婪算法与距离公式相结合的方式，对下一个子区域的起点进行选择。然后，利用优化后的A*算法和Bezier 曲线（B-A*）实现区域衔接，通过仿真分析可知，B-A*算法可减少节点搜索时间，规划出的路径更加平滑、安全。最后，利用上述全覆盖路径规划策略进行仿真实验，实验结果表明该方案可实现全覆盖，说明了该方案的有效性和可行性。

1 翻晒谷物机器人全覆盖路径规划性能指标

翻晒谷物机器人全覆盖路径规划并不是点到点的路径规划，而是通过点到线，再从线到面，最终将规定区域内所有的空白区域全部覆盖完毕。本文对翻晒谷物机器人的全覆盖路径性能指标主要有以下几方面：

（1）机器人能够避开行走过程中的所有障碍物，并遍历完工作区域内的其他所有地方。

（2）为了利于实际机器人的行驶，应尽量使用直线、曲线这样的运动轨迹。

（3）翻晒谷物机器人应当尽量减少整个遍历过程中的能量消耗。

全覆盖路径规划的含义可由以上几个方面的指标所体现，覆盖率越高，机器人转弯次数越少、能量消耗越低越能体现算法的优越性。全覆盖路径规划算法还有一个重要指标为重复率，由于本文是针对翻晒谷物机器人对谷物进行翻晒作业，可在机器人行驶过程中对谷物进行重复翻晒，因此本文不考虑重复率这一指标。

2 翻晒谷物机器人全覆盖路径规划

2.1 环境建模

本文利用栅格法[7～8]创建作业环境模型，单位栅格长度为机器人的尺寸大小。在栅格法中，每个栅格都会通过一个值来衡量该栅格的可行率，一般来说，使用0 来代表可行栅格，即机器人可通过该栅格区域；使用1 来代表障碍栅格，即机器人不可移动的区域。由于本文研究的是全覆盖路径规划算法，所以栅格也需要记录自身是否已经被机器人所覆盖的信息。根据栅格是否已覆盖，又可将栅格划分为已覆盖栅格和未覆盖栅格。根据以上信息的组合后，栅格有以下三种状态：可通行并未覆盖区域、可通行但已覆盖区域、障碍物，具体的数字编码情况如表1 所示。根据栅格法，对环境进行相应的建模，结果如图1 所示。空白栅格代表可通行区域，黑色栅格代表障碍物。

图1 环境地图栅格化

表1 栅格数字编码情况

2.2 区域分割

区域分割是将作业环境根据障碍物分布情况，利用相关算法将工作环境划分为多个子区域，使得各个子区域内不再包含障碍物。传统区域分割法是梯形分解法[9～11]，牛耕分解法[12]在梯形分解法基础上进行相应的改进，该方法通过一条垂直线从左到右按照平移方向扫过具有多边形障碍物的区域，每遇到障碍物顶点可上下延伸的临界点进行分割，最终作业环境被分割成多个不含障碍物的子区域，其示意图如图2 所示。相比梯形分解法，该方法产生更少的子区域，可减少机器人作业时对地图环境的分解时间，提高机器人的工作效率，因此本文采用牛耕分解法作为区域划分方法，进而为后续机器人进行全覆盖路径规划做准备。

图2 牛耕分解法示意图

2.3 子区域内部遍历算法

利用牛耕分解法对环境地图进行分区后，关键步骤是完成对子区域内部的遍历。针对内部区域遍历主要有往返式弓子形和螺旋式路径规划，基于同一区域，文献[13]对两种路径规划方法在路径长度和转弯次数两方面进行实验对比，发现弓子形路径更优。另外针对往返式弓子型路径规划，需要对谷物机器人的行走方向进行确定。在同一区域，机器人分别沿着长边和短边行走，发现直线行驶距离以及转弯次数各不相同，这将导致其在区域内的行走轨迹以及对整个区域覆盖所消耗的能量也会产生一定的差异，文献[14]讨论了机器人在相同区域内，分别沿着不同方向进行弓子形路径规划行走轨迹，发现沿长边行走机器人的转弯次数较少，能量消耗较小，因此本文选用沿长边行走的往返式弓子形遍历规则实现对子区域的全覆盖。

2.4 子区域衔接起点的选择

当完成对谷物翻晒场划分为一系列简单的无障碍子区域，并对当前的子区域完成全覆盖后，需要规划出一条路径对下一个子区域进行衔接，然后结合弓子型路径完成对下一个子区域进行顺序覆盖。在进行区域衔接路径规划时，需要寻找到下一个区域的起点。为了减少内存的消耗以及搜索时间，对于起点的选取，本文在算法程序中：

（1）只记录区域在进行划分过程中，与障碍物、区域边界交点所产生的顶点信息。通过这种方式可减少起点的数量，进而减少完成整体全覆盖路径规划所需要的时间。

（2）下一个区域的起点与上一个区域的终点之间的距离应最小，这样可减少谷物机器人行走的路径长度，降低消耗的能量。

为此针对如何选取下一个区域的起始点，本文利用贪婪算法与曼哈顿距离公式相结合的方式，以曼哈顿距离公式作为贪婪算法的选择策略，每次选取与当前位置最近的区域顶点作为下一个区域的起点，算法描述如下：

其中，tn表示当前区域的终点，n表示下一个区域的起点。则所有可选择的起点可表示为：

式中，nmin为选择出的下一个覆盖区域的起点。

2.5 子区域衔接路径规划

2.5.1 传统A*算法

翻晒谷物机器人的全覆盖路径算法即机器人从起始点出发，通过对翻晒环境进行区域划分、进行子区域全覆盖、对下一个子区域的起点进行选取、建立子区域间的路径衔接最终完成整个工作环境的全覆盖路径规划。本文选择以当前区域的终点为起点，以下一个区域的起点为目标点利用A*算法[15～17]实现区域衔接路径规划。另外A*算法也可作为在整个环境地图中避障算法。

A*算法是利用启发式函数来进行搜索路径，主要通过代价函数进行路径规划，从起点位置向附近的子节点进行扩展，评价函数根据子节点距离代价值最小的节点选为下一父节点，重复此过程直到完成路径规划，生成最终路径。

启发式函数的一般表达式为：

式中，F（n） 表示从起始点经过任意节点n到达目标点的总代价值，g（n） 为从起始点到任意节点n的实际距离评估值，h（n） 为从任意节点n到达目标点的估计值。

根据对传统A*算法进行寻路过程的研究发现，若将该算法直接应用于实际中的翻晒谷物机器人进行全覆盖路径规划，其还存在一定的缺陷，需要对其进行优化，以便更好地完成任务。本文将从以下两个关键问题对传统A*算法进行优化和改进：

①从A*算法的启发函数来看，g（n） 为定值，因此对其进行修改所起到的作用不明显。估计函数h（n） 才是启发函数的灵魂所在，因此估计函数的优劣会决定A*算法能否高效、准确地判断出下一个节点。在传统的A*算法进行节点搜索的过程中，会搜索大量不必要的节点，导致搜索时间变长，增加计算量，使路径规划效率变低。

②平滑度差。传统A*算法的节点搜索方向仅限于栅格之间的相交位置，使得规划出来的路径转折点多，搜索方向易受到谷物机器人转弯半径的影响，不利于实际机器人的行驶，另外实际中多次转弯的代价会影响谷物机器人的运行效率。

2.5.2 改进A*算法

传统的A*算法在节点搜索的过程中会产生大量的不必要节点，从而导致搜索时间长，路径规划效率低。为了使算法在搜索的过程中，能够尽快地朝向目标点前进，本文对估价函数h（n）进行优化和改进，该函数对于A*算法的运行速度有着非常重要的影响，现对估价函数h（n） 和代价函数g（n）之间的关系对A*算法的影响进行讨论：

①当h（n） = 0时，只有g（n）起作用，A*算法将会演变为Dijkstra 算法，该算法是一种盲目式搜索算法，因此会扩展更多无用节点，搜索效率低。

②当h（n） ＜g（n）时，此时可找到一条最短路径，但随着搜索不断地向终点靠近，h（n）不断地减少，此时会使得A*算法搜索扩展的节点变多，搜索时间变长，导致机器人寻径效率变低。

③当h（n） =g（n）时，A*算法将会仅仅寻找最佳路径上的节点，不会扩展别的任何节点，此时运行速度最快。

④当h（n） ＞g（n）时，此种状态会比②时的速度快，搜索节点减小，运行效率变高，但不能保证搜索得到最优路径。

⑤当h（n） ＞＞g（n）时，此时只有h（n） 起作用，该算法演变为BFS 算法，该算法是一种启发式搜索算法，利用启发函数使得扩展节点变少，搜索效率高，但不一定能搜索到最短路径。

因此在设计估价函数时，应保证g（n） 和h（n） 最好能在同一个数量级，避免出现极端情况的出现。

本文选用欧几里得距离公式作为估价函数，A*算法在传统的估计函数的影响下，只会单一地进行往返搜索生成大量的搜索节点，而在实际情况中当前节点到目标节点之间的距离一定会大于实际路径的消耗值，因此需要加快当前节点向目标节点的收敛速度，即增大估价函数h（n） 的权重。该权值的选择应满足当h（n） 较大时，当前节点远离目标点，应增大权重，此时A*算法能尽快地向目标点扩展，搜索速度会较快，当h（n） 较小时，也即扩展节点接近目标点，权重应减小，此时A*算法更倾向于搜索最优路径。因此本文引入以指数形式的权重因子h（n）e对传统A*算法的表达式进行改进，公式修改为：

h（n）估计值应始终大于0，eh（n）的图像如图3 所示，从图中可知，当h（n） 减小时，eh（n）也在不断地减小，当h（n）等于0，也即当前节点到达目标点时，eh（n）为1，整体不发生改变，符合上述改变权值的要求。

图3 h（ n）e 变化图像

2.5.3 贝塞尔曲线优化

A*算法本身存在着许多的不足：在栅格环境下A*算法规划出的路径往往存在许多的转折点，累积转折角度大，在后期应用于实际谷物机器人中时会不利于机器人的行驶，存在过多转弯现象，运行效率低等问题。于是本文在对改进后A*算法规划出的路径进行平滑处理，减少因路径转折点过多而降低机器人工作效率。

Bezier 曲 线[18]由 伯 恩 斯 坦 多 项 式（Bernstein polynomial）演化而来，其受曲线上控制点数目的影响。伯恩斯坦多项式的第n阶项有如下形式：

其中i= 0,1,… ,n，而：

一般伯恩斯坦多项式可以表示为：

其中，βi为伯恩斯坦系数。当伯恩斯坦系数是二维平面中的一系列固定点时，伯恩斯坦多项式就演变成为Bezier 曲线。

将Bezier 曲线与A*算法（B-A*）相结合，A*算法生成路径点的总控制点个数为n+ 1，βi伯恩斯坦系数为A*算法生成的第i个路径点Pi，其中i= 0,1,… ,n。则通过公式 （7）计算可得B0…Bn，即可得到平滑后的曲线路径。

根据Bezier 曲线的性质可知，规划所得曲线路径不会与控制点连接而成的多边形外部障碍物发生碰撞，但会有与内部障碍物发生碰撞的可能，在实际工作中该种情况会使谷物机器人陷入工作死区对自身造成一定的损坏，所以需对Bezier 曲线进行一定的优化。对Bezier 曲线进行优化的思想，是将两个相邻节点中插入一定的点，将插入的点共同作为控制点，以此增加控制点的数量。合适的控制点会使得曲线接近拐点，以此尽量向规划的路径上靠拢，进而增大与障碍物之间的距离，躲避障碍物。增多控制点思想的伪代码如下：

for i=1:1:pointnum-1

%pointnum 所需插入点的个数

D（ai+i,:）=（（B - C）./pointnum*i ）+ C;

%B 和 C 为相邻控制点，D 所分控制点坐标

end

ai=ai+pointnums;

2.6 仿真实验

2.6.1 改进A*算法对比分析

在翻晒谷物时，一般会尽可能地选取宽敞且障碍物较少的场地进行翻晒，为了验证A*算法作为从当前区域到下一个区域衔接路径规划算法的有效性，随机在栅格环境中选定起始点与目标点。改进的A*算法主要是减少扩展节点，缩短节点搜索时间，没有对路径长度进行改进。因此本文以15×15 和30×30 两个不同栅格大小的障碍物地图作为仿真实验环境，通过Matlab 软件分别对Dijkstra 算法、A*算法以及改进的A*算法进行实验对比分析，仿真结果如图4所示。

图4 15×15 环境地图仿真图

图4 中，黑色栅格代表障碍物，白色栅格代表可通行栅格，灰色栅格代表所搜索的节点，五角星代表起点，圆圈代表终点，从起点到终点的线段为规划出的路径。从图中可以看到通过三种方法都能成功地从起始点搜索出一条路径达到目标点，但改进的A*算法相对于Dijstra 算法和标准A*算法搜索节点大大减少，从表2 中也可以看到，改进后的A*算法在寻路时间和遍历节点数的性能指标上都得到了很大的提升。为了进一步验证改进A*算法的有效性，扩大地图环境，以30×30 环境地图再次进行仿真实验，结果如图5 所示，从仿真结果与表3 都能再一次看到经过改进后的A*算法性能更优，达到实验要求。

表3 30×30栅格地图环境

2.6.2 路径平滑对比分析

通过Bezier 曲线对30×30 环境地图下改进A*算法规划出的路径进行平滑处理，得到图6 仿真图，其中Bezier曲线中的控制点即为最优路径中的节点，虚线曲线为通过改进A*算法所规划出的最优路径经过平滑优化后的曲线，从图中可以看到，在对节点进行Bezier 曲线优化时，①和②处能触碰到障碍物，在实际工作中该种情况会使谷物机器人对自身造成一定的损坏，所以需对Bezier 曲线进行一定的优化。

图6 改进A*算法Bezier 曲线优化处理

对上述经过Bezier 曲线平滑后的路径再次通过增加控制点的方式进行优化，在本次实验中将相邻的两个控制点增加3 个点再次进行平滑处理得到如图7 仿真图，图7（a）和图7（b）中的圆圈构成的曲线为图6 中①和②所示经过平滑后的曲线，从图中可以看出，该曲线能一定程度地躲避障碍物，避免了实际谷物机器人在工作过程中触碰到障碍物，减少了对自身的损坏。图7（c）为完整的平滑曲线图，通过对曲线进行优化处理，路径更加顺畅，使得谷物机器人在实际工作中移动得更加流畅，仿真结果表明了本算法对路径平滑的可行性和有效性。

图7 优化Bezier 曲线对改进A*算法平滑处理

2.6.3 全覆盖路径规划仿真实验

前面详细介绍了翻晒谷物机器人基于栅格地图的全覆盖路径规划基本步骤，要想完成一个完整的区域全覆盖，首先需要对工作环境地图进行建模，然后在有障碍物的区域根据障碍物顶点进行区域划分得到多个子区域，其次对子区域设计遍历算法，最终根据区域衔接路径规划完成整个工作区域的全覆盖。下面以30×30 障碍物环境地图进行全覆盖路径规划仿真，以此验证本文设计的全覆盖路径规划的可行性和有效性，仿真结果如下。图8 为通过牛耕分解法对30×30 环境地图下进行区域划分的结果图。通过仿真图可知，该地图被分成①～⑥6 个子区域，验证了牛耕分解法的有效性。

图8 30×30 牛耕分解结果图

接下来对子区域分别进行弓子型区域覆盖，仿真结果如图9 所示。其中五角星表示机器人的起始点，实心圆圈表示当前区域的终点，空心圆圈表示下一个子区域起点。直线表示子区域内进行往返式弓子型路径，曲线表示区域间的衔接路径。从 30×30 全覆盖路径规划仿真图中可以看出，经过本文设计的算法策略均可以实现栅格地图的100%覆盖，验证了本文提出的全覆盖路径规划算法是可行且有效的。

图9 30×30 全覆盖路径规划仿真实验

3 总结

本文提出一种改进A*算法的全覆盖路径规划方案，利用栅格法、牛耕分解法、贪婪算法与曼哈顿距离结合策略、往返式弓子型遍历方法和A*算法分别对机器人工作环境建模、子区域划分、子区域起点选择、子区域内部遍历以及子区域衔接路径规划进行求解，实现整个机器人对场地的全覆盖翻晒。同时对传统A*算法和Bezier 曲线进行改进，在相同仿真环境下，改进后的B-A*算法使得搜索节点时间缩短，路径平滑、安全。通过以上策略对环境地图进行全覆盖仿真分析，实验结果表明本文提出的方法可完成100%的覆盖，表明该方案具有一定的有效性和可适用性。