基于改进A*算法和DFS算法的割草机器人遍历路径规划*

王新彦，盛冠杰，张凯，易政洋

(江苏科技大学机械工程学院，江苏镇江，212100)

近年来，随着移动机器人技术的迅速发展，智能化设备已被广泛应用于社会的各个领域，给人们的生产生活带来了极大的便利[1-3]。割草机器人作为农业机器人的一种，不仅用于市政绿地、机场、高尔夫球场等场地的草坪修剪工作，还用于耕地和林地的除草工作，因此受到广泛关注，而遍历路径规划在割草机器人应用过程中起着至关重要的作用[4-6]。

全覆盖遍历路径规划是一种在二维环境中特殊的路径规划，指在满足某种性能指标最优的前提下，在设定区域内寻找一条从起点到终点且经过所有可达点的连续路径[7-9]。该技术发展至今已涌现出了大量研究成果，Balch采用随机遍历算法进行目标区域遍历，使机器人沿直线移动，当遇到障碍物时随机转动一个角度继续前进，该方法原理简单、易于实现，但要达到高覆盖率需要很多时间，工作效率低。张赤斌等[10]将蚁群算法应用到遍历路径规划中，通过牛耕式分解法将目标区域分解成若干个不含障碍物的子区域，采用蚁群算法搜索出子区域的遍历顺序，该方法覆盖率高，但算法运算量大且跨区域转移路径长。李楷等[11]提出了一种局部区域覆盖和回溯机制相结合的遍历方法，利用回溯机制对局部覆盖过程中存在的遗漏区域进行回溯遍历，以此提高遍历覆盖率，但存在遍历重复率较高的问题。Le等[12]提出了一种基于螺旋生成树的遍历方法，该方法遍历重复率低，但其规划的遍历路径转向次数多且易陷入死区。马全坤等[13]提出了一种基于记忆模拟退火和A*算法的遍历方法，采用记忆模拟退火算法确定各子区域的遍历顺序，通过A*算法规划跨区域转移路径，该方法性能较优，但跨区域转移路径较长。

上述研究成果对遍历路径规划技术的发展起到了积极的推动作用，但仍存在遍历重复率高、遗漏区域多、普适性弱的问题。为此，本文提出一种改进A*算法与DFS算法相结合的遍历算法，通过DFS算法确定目标区域划分后的子区域遍历顺序，然后使用改进A*算法进行跨区域转移路径规划，从而实现割草机器人的遍历路径规划。

1.1 建立栅格地图

本文采用栅格法[14]进行环境建模，将割草机器人的工作环境全局信息分解成一系列具有二值信息的等大小正方形网格单元，单元格边长为割草机器人割幅。接着每个栅格被赋予环境信息值：若某个栅格内不含障碍物，则称该栅格为自由栅格并赋值为0，反之被称为障碍栅格并赋值为1。本文结合市政绿地的现实情况，对环境做如下假定：(1)假定市政绿地环境全局信息已知；
(2)假定灌木植物为圆形障碍物；
(3)假定石块、垃圾桶等为多边形障碍物；
(4)假定积水区、小土丘等为形状不规则障碍物。

建立的栅格地图如图1所示，把环境信息赋予对应的栅格，相当于将环境地图离散化，每个单元格映射出环境信息的一部分。

图1 栅格地图

1.2 障碍物膨胀处理

在栅格地图中存在一些障碍物的边缘不完全与栅格单元边界重合，如图1所示，此时需要进行图像处理，通过二值形态学中的膨胀运算对这些障碍物的边缘区域进行膨胀处理，使其边缘在栅格化的地图中与栅格单元边界重合，以防止割草机器人陷入死角以及智能算法陷入局部最优[15]，以便后续遍历算法在此基础上进行路径规划。

(1)

根据上述膨胀数学模型，边缘不完全与栅格单元边界重合的障碍物目标经过膨胀处理后得到的新障碍物栅格M，如图2所示。

图2 膨胀处理后的障碍物

1.3 目标区域划分

栅格地图建立后，由于障碍物分布毫无规律，割草机器人工作时易出现漏割、重复遍历、效率低等情况。为提高工作效率，采用牛耕式分解法将目标区域划分成多个不含障碍物的子区域，使割草机器人通过遍历单个子区域并进行子区域之间路径转移，来达到全覆盖遍历路径规划。

牛耕式分解法[16]是从梯形单元分解法[17]上改进而来，该方法假设一条垂直的切割线从左往右扫描整个有界区域，每当遇到障碍物上的临界点或边时便进行分割，目标区域中的非障碍物部分进而被分割成多个子区域。

相比梯形单元分解法，该方法使目标区域划分过程中产生的子区域数量更少，可有效降低遍历重复率。子区域划分后，按照从上到下、从左到右的原则对各子区域进行数字标号，如图3所示，以便后续子区域遍历顺序的规划。

图3 目标区域划分

目标区域完成划分后，割草机器人要实现对目标区域的全覆盖遍历可通过以下两个步骤：(1)根据子区域之间连通关系确定子区域的遍历顺序，保证每个子区域在遍历路径规划中有且仅被访问一次；
(2)按照给定的遍历顺序依次访问每个子区域，完成子区域间路径转移。

2.1 子区域遍历顺序规划

子区域的遍历顺序规划采用DFS算法[18]，该算法是图算法中一种著名的搜索算法，经常被用来遍历连通图中每个节点，找到一条详尽可靠的覆盖路径，算法步骤如表1所示。

将目标区域划分得到的每个子区域看作连通图中节点，按照子区域间相邻关系建立连通图，如图4(a)所示。根据目标区域划分中切割线移动方向，将①设置为遍历起始区域，图4(b)是使用DFS算法规划的子区域遍历顺序图。

表1 DFS算法步骤Tab. 1 DFS algorithm steps

(a) 连通图

(b) 遍历顺序图

2.2 子区域间路径转移

为了使割草机器人有序地完成对每个子区域的遍历，就需要解决子区域之间路径转移的问题。针对该问题，本文采用改进A*算法规划从上一个子区域遍历终点到下一个子区域遍历起点的最短路径。

2.2.1 A*算法的评价函数

A*算法是人工智能中一种典型的启发式搜索算法，被广泛应用于静态路网中两点间最优路径的求解。其评价函数如式(2)所示。

f(n)=g(n)+h(n)

(2)

式中：f(n)——从起始节点到目标节点的评价函数；

g(n)——起始节点到当前节点n的实际代价函数；

h(n)——当前节点n到目标节点的启发代价函数。

在二维地图中，代价函数的值通常指两个节点之间的欧几里得距离，即

(3)

(4)

式中：
(xs,ys)——起始点位置；

(xn,yn)——当前点位置；

(xt,yt)——目标点位置。

2.2.2 改进A*算法

A*算法规划所得到的是一系列相邻的路径节点，将各相邻节点用直线连接起来即为所得到的路径。由于A*算法规划的路径存在冗余的路径节点且转向次数多[19]，导致路径平滑性较差且路径长度不是最短，同时路径穿过障碍物边界点时易发生碰撞。针对上述问题，本文通过路径平滑性优化和添加防碰撞安全间距对A*算法进行改进，改进A*算法的流程图如图5所示。

图5 改进A*算法流程图

防碰撞预处理是通过计算障碍物边界点到路径的垂直距离l，与设置的安全间距η进行对比，判断路径是否安全。防碰撞安全间距η的大小与栅格单元边长γ有关，满足η∈(0,0.5γ),η的值可根据实际情况进行调节。如图6所示，路径节点A、B坐标分别为(xa,ya)、(xb,yb)，障碍物边界点H坐标为(xe,ye)，直线BC垂直于H点所在的横轴，垂足为C点，连接CH，直线AB与直线CH相交于F点，H点到直线AB的垂直距离DH即为l的长度，线段FH长度为t，θ为直线AB与直线BC所夹锐角。由于A、B、H三点坐标已知，可求解障碍物边界点H到路径AB的垂直距离l。

直线AB与直线BC所夹锐角

(5)

线段FH长度

(6)

障碍物边界点H到路径AB的垂直距离

l=t·cosθ

(7)

图6 防碰撞路径图

A*算法的改进是在获取A*算法规划的路径节点后进行，如图7所示，Ni(i=1～13)是A*算法规划的路径节点，i为路径节点的标号。改进算法的步骤如下。

步骤1：从起点G往终点E方向，取初始路径的第一个节点Ni(i=1)。

步骤2：若节点Ni+1是终点E，转至步骤6；
若节点Ni+1既不是终点E，也不是起点G，转至步骤3；
若节点Ni+1是起点G，转至步骤7。

步骤3：判断直线NiNi+1与直线Ni+1Ni+2斜率是否相等。若斜率相等，节点Ni、Ni+1、Ni+2共线，删除节点Ni+1并使Ni后面节点的标号均减1，返回步骤2；
若斜率不相等，节点Ni、Ni+1、Ni+2不共线，转至步骤4。

步骤4：判断节点Ni和Ni+2之间是否存在障碍物。若有障碍物，路径节点不变，转至步骤5；
若无障碍物，由式(5)～式(7)计算障碍物边界点到路径NiNi+2的垂直距离l并判断与安全间距η的大小：如果l≤η，路径节点不变，转至步骤5；
如果l>η，删除节点Ni+1并使Ni后面节点的标号均减1，返回步骤2。

步骤5：令i=i+1，更新i的值并返回步骤2。

步骤6：从终点E往起点G方向，取初始路径的第一个节点Ni(i=1)，返回步骤2。

步骤7：输出优化路径Path，算法结束。如图7所示，优化后路径为：G→N6→M1→E。从起点G往终点E正向取点，处理后路径为：G→N6→N11→E；
从终点E往起点G反向取点，处理后路径为：E→N7→N4→N3→G。

图7 路径平滑性处理

通过使用牛耕式分解法将目标区域划分成多个不含障碍物的子区域；
其次，使用DFS算法确定子区域的遍历顺序；
然后，采用改进A*算法搜索出最短、无碰撞的跨区域转移路径并对子区域内部进行往复前进式遍历，最终实现对整个栅格地图的遍历路径规划。

为了直观、清晰地显示仿真结果，栅格地图由23×23 个栅格组成，其中黑色区域为障碍物占据的栅格，其他白色区域是自由栅格。图8为遍历路径规划仿真结果图，由图可知，不论在上文建立的普通环境模型中，还是在特殊的复杂环境模型中，本文提出的遍历路径规划算法的覆盖率都达到100%且遍历重复率为0。

图9为A*算法改进前后规划的跨区域转移路径对比图，其中每个子区域的遍历起点用“●”表示，每个子区域的遍历终点用“★”表示。遍历整个栅格地图需进行九次跨区域路径转移，这里主要对比其中三条转移路径：⑩—⑨区域、⑨—⑥区域、⑥—③区域，对应路径在图9中用加粗黑线表示。

结合图9、表2和表3可以看出，改进后的A*算法所规划的路径删除了冗余的路径节点，使路径长度缩短了3.26%，转向次数减少了62.5%，提高了路径的平滑性，同时，由于添加了防碰撞安全间距，改进后的A*算法所规划的路径不会出现穿过障碍物边界点的情况，路径安全性得到提高。

(a) 普通环境

(b) 复杂环境

(a) A*算法

(b) 改进A*算法

表2 路径转移距离对比Tab. 2 Comparison of path transfer distance

表3 路径转移转向次数对比Tab. 3 Comparison of the number of times of path transfer

针对割草机器人大面积作业时遍历路径规划覆盖率低、重复率高、普适性弱的问题，本文提出了一种改进A*算法与DFS算法相结合的遍历算法。

1) 针对目标区域划分后的子区域间路径转移，采用改进A*算法规划转移路径。通过路径平滑性优化与添加防碰撞安全间距对A*算法进行改进，使之规划的路径更平滑、更安全，路径长度更短。MATLAB仿真试验表明，采用改进A*算法所规划的跨区域转移路径长度和转向次数比A*算法分别减少了3.26%和62.5%，路径不会穿过障碍物边界点。

2) 针对割草机器人遍历路径规划，提出了一种改进A*算法与DFS算法相结合的遍历算法。通过DFS算法确定目标区域划分后的子区域遍历顺序，然后使用改进A*算法进行跨区域转移路径规划。通过仿真试验表明，遍历路径规划覆盖率达到100%，遍历重复率为0，本文遍历算法具备有效性和可行性。由于本文算法只适用于静态环境，下一步将在此工作基础上进一步展开动态环境中遍历路径规划的探讨与研究。

猜你喜欢边界点栅格障碍物基于邻域栅格筛选的点云边缘点提取方法*科技创新与应用(2021年31期)2021-11-09高低翻越动漫界·幼教365(中班)(2020年3期)2020-04-20SelTrac®CBTC系统中非通信障碍物的设计和处理铁道通信信号(2020年9期)2020-02-06基于降维数据边界点曲率的变电站设备识别郑州大学学报（工学版）(2017年2期)2017-05-18不同剖面形状的栅格壁对栅格翼气动特性的影响弹箭与制导学报(2015年1期)2015-03-11面向手绘草图检索的边界点选择算法微型电脑应用(2014年4期)2014-08-08基于CVT排布的非周期栅格密度加权阵设计雷达学报(2014年4期)2014-04-23一种去除挂网图像锯齿的方法及装置电脑与电信(2014年6期)2014-03-22土钉墙在近障碍物的地下车行通道工程中的应用城市道桥与防洪(2014年5期)2014-02-27栅格中间层数据在数字地形分析中的应用测绘科学与工程(2013年6期)2013-03-11

推荐访问:割草 算法 遍历