一种基于牛耕式运动的全覆盖路径规划方法与流程

阅读：评论：0

1.本发明属于单机器人全覆盖路径规划领域，尤其涉及一种基于牛耕式运动的全覆盖路径规划方法。

背景技术：

2.全覆盖路径规划可应用于单机器人的清洁、除锈、探伤、扫雷等任务场景，其目的是为机器人在计算机/处理器的控制下，有序、完全地遍历目标区域提供支撑。
3.现有的全覆盖路径规划专利，例如，一种基于多边形分解的全覆盖路径规划算法（cn202111669496.8）、基于单元分解的全覆盖路径规划方法及相关设备（cn202111579455.x）等，在进行路径规划时，是通过单元分解的方式，依据障碍物的形状和位置分布，将目标区域划分为多个易遍历的子区域，且子区域间转化为旅行商问题求解来进行的。虽然它们能够获得一条遍历任务区域的路径，但当目标区域具有边缘不规则，或是区域内障碍物数量较多、分布随机等特点时，这些方法所得规划路径较长（即路径重复率较高），原因在于，此种情况下机器人易陷入死区（即机器人周围均为障碍物或是已遍历区域），且由于环境复杂，子区域数目较多，机器人在逃离死区以及子区域间移动的过程中将再次经过部分已遍历的区域，导致最终路径重复率较高。
4.因此，需要研究一种应用于上述较复杂平面区域的全覆盖路径规划方法，并确保所得路径具有较小的路径重复率。

技术实现要素：

5.本发明目的在于提供一种基于牛耕式运动的全覆盖路径规划方法，以解决现有算法在较复杂平面区域获取的全覆盖路径存在路径重复率较高或是区域覆盖率较低的技术问题。
6.为解决上述技术问题，本发明的一种基于牛耕式运动的全覆盖路径规划方法的具体技术方案如下：一种基于牛耕式运动的全覆盖路径规划方法，包括如下步骤：步骤1：用栅格划分地图，用不同阴影表示障碍物和机器人待覆盖区域，机器人从初始位置开始，进行牛耕式运动；步骤2：重复步骤1，直到机器人当前位置的上下左右4个相邻栅格均非未覆盖，即陷入死区，此时跳转至步骤3；步骤3：对当前未遍历的栅格进行划分，生成若干个栅格集合；步骤4：判断各栅格集合是否满足路径插入条件；步骤5：对步骤4中满足要求的各栅格集合依次进行路径插入操作；步骤6：重复步骤4-5，直到不存在满足路径插入条件的栅格集合；步骤7：判断当前是否已完成所有栅格的覆盖任务，若是，则跳转至步骤9；若否，则跳转至步骤8；
步骤8：以a*算法计算所有仍未覆盖的栅格到机器人当前所在栅格的移动距离，选取其中最短距离，并将机器人移动至对应未覆盖栅格，同时在c
nav
中已有路径末端记录该栅格，之后跳转至步骤1；步骤9：根据最终得到的有序导航点集合c
nav
，以a*算法补全集合中前后相邻排列的两个栅格之间的实际移动路径；步骤10：合并各移动路径，得到最终机器人实际运动路径。
7.进一步地，所述步骤1包括如下具体步骤：栅格地图的坐标原点位于左上角，向下方向为x轴，向右方向为y轴，以坐标（m,n）表示第m行、第n列栅格，机器人从初始位置开始，进行牛耕式运动，并优先y轴方向，若机器人当前位置的左右两个相邻栅格均未覆盖，则随机选择一个栅格移动；若左右两个相邻栅格只有一个未覆盖，则移动到该未覆盖栅格；若左右两个相邻栅格均非未覆盖，则判断上下两个相邻栅格的覆盖情况并确定下一个移动目标，与左右类似，同时，在机器人的移动过程中，依次记录其新覆盖的栅格及其坐标，得到机器人先后经历的有序导航点集合c
nav
。
8.进一步地，所述步骤3包括如下具体步骤：对栅格地图，沿x轴方向，依次以一直线横穿整个地图，并将每一行直线所串联的未被障碍物阻断的未覆盖栅格归于同一集合。
9.进一步地，所述步骤4包括如下具体步骤：对某一集合cm而言，选取该集合中所有栅格的上方或下方相邻栅格，临时组成一新集合c0，若c0同时满足：（1）集合中不存在未覆盖的栅格；（2）集合中所有已覆盖的栅格未被障碍物阻断；则cm满足要求。
10.进一步地，所述步骤5包括如下具体步骤：步骤5.1：寻与当前集合cm对应的步骤4中临时组成的新集合c0中，y轴数值最小和最大的已遍历栅格；步骤5.2：寻这两个栅格在c
nav
中的排序序号，设y轴数值最小值的序号为p
ymin
，最大值的序号为p
ymax
，并取p
min
=min（p
ymin
，p
ymax
），p
max
=max（p
ymin
，p
ymax
）；步骤5.3：对c
nav
中序号在p
min
和p
max
之间的所有栅格，依次判断前后相邻排列的两个栅格，设序号以及坐标分别为pn、p
n+1
，（xn，yn）、（x
n+1
，y
n+1
），是否满足：（a）xn= x
n+1
= x0；其中，x0为集合c0中栅格的x轴坐标值；（b）|ynꢀ‑ꢀyn+1
|=1；若不满足要求，则继续判断下一组，即取n=n+1；若满足要求，则将栅格地图中，与（xn，yn）相邻的栅格（xm，yn）、与（x
n+1
，y
n+1
）相邻的栅格（xm，y
n+1
）依次插入在c
nav
中序号pn与p
n+1
之间（xm为cm中栅格的x轴数值），并继续取n=n+1重复进行；步骤5.4：判断集合cm中是否仍存在未插入的栅格，若否，则跳过此步骤；若是，则此时分三种情况讨论；（a）步骤5.3中未插入任何栅格到c
nav
中，此时判断栅格地图上机器人在集合c0中的移动方向，若为y轴正向，则将cm中所有栅格按照x轴数值从小到大的顺序，依次插入到c
nav
中序号p
max
前一位；若为y轴负向，则将cm中所有栅格按照x轴数值从大到小的顺序，依次
插入到c
nav
中序号p
min
前一位；（b）未插入栅格位于栅格地图上已插入栅格的中间位置，此时寻集合c0中与该栅格在地图上相邻的栅格在c
nav
中的排序，并将其插入到该序号的前两位处；（c）非（b）中未插入的栅格，此时若机器人移动方向为y轴正向，则当地图上某一未插入栅格的右侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的前一位，当其左侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的后一位；若机器人移动方向为y轴负向，则当其右侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的后一位，当其左侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的前一位，直到所有栅格插入完毕；步骤5.5：寻步骤5.4的情况（b）中栅格，以及情况（c）中地图上一侧为障碍物、另一侧相邻栅格为步骤5.3中插入的栅格在c
nav
中的排序序号，设为ps，坐标值为（xs，ys），设与其在栅格地图同一行以及c
nav
排序中均相邻的栅格在c
nav
的排序为pr，坐标值为（xr，yr）；取p
t
=min（pr，ps），设序号为（p
t-2i+1）和（p
t-2i）的栅格坐标分别为（x
t-2i+1
,y
t-2i+1
）、x
t-2i
,y
t-2i
），其中i为正整数，若满足：（a）x
t-2i+1
=x
t-2i
；（b）（y
t-2i+1
=ys&&y
t-2i
=yr)||（y
t-2i
=ys&&y
t-2i+1
=yr）；则将（p
t-2i+1）和（p
t-2i）所代表的栅格在c
nav
中的排列位置互换；再取pu=max（pr，ps），设序号为（pu+2i-1）和（pu+2i）的栅格坐标分别为（x
u+2i-1
,y
u+2i-1
）、x
u+2i
,y
u+2i
），其中i为正整数，与p
t
类似，若满足：（c）x
u+2i-1
=x
u+2i
；（d）（y
u+2i-1
=ys&&y
u+2i
=yr)||（y
u+2i
=ys&&y
u+2i-1
=yr）；则将（pu+2i-1）和（pu+2i）所代表的栅格在c
nav
中的排列位置互换。
11.本发明的一种基于牛耕式运动的全覆盖路径规划方法具有以下优点：本发明能够在具有较复杂的区域边界、障碍物的二维已知环境下获取一条长度较短（路径重复率较低）的单机器人全覆盖路径。
附图说明
12.图1是本发明的基于牛耕式运动的全覆盖路径规划方法整体流程图；图2是栅格地图；图3是记录机器人先后覆盖经过的栅格的导航点集合示意图；图4是机器人初次陷入死区时的移动情况示意图；图5是划分并更新生成未覆盖栅格集合的方法示意图；图6是选取下方相邻栅格时满足路径插入要求的四种情况示意图；图7是路径初步插入操作的示意图；图8是路径初步插入操作时未能插入栅格的两种情况示意图；图9是未插入栅格位于栅格地图中已插入栅格之间的情况示意图；图10是插入栅格后的路径调整效果示意图；图11是图4路径完成插入操作后的情况示意图；图12是最终移动路径示意图。
具体实施方式
13.为了更好地了解本发明的目的、结构及功能，下面结合附图，对本发明一种基于牛耕式运动的全覆盖路径规划方法做进一步详细的描述。
14.如图1所示，本发明的一种基于牛耕式运动的全覆盖路径规划方法，在二维栅格地图上，机器人从初始位置开始，进行牛耕式运动。当机器人陷入死区时，对剩余未遍历栅格进行划分，生成若干个栅格集合。对这些栅格集合进行条件判断，若满足要求，则将其插入到已生成的路径中。当路径插入操作结束后，判断是否已完成目标区域的遍历，若是，则生成最终实际运动路径，否则以a*算法前往最近未遍历栅格，以逃离死区。
15.下面以附图2所示栅格地图为例，阐述本方法的具体实施过程。其中附图2中黑栅格为障碍物，白栅格为待覆盖的栅格，黑圆代表机器人，其目前所在栅格为机器人初始位置，地图边缘之外视为障碍物区域。栅格地图的坐标原点位于左上角，向下方向为x轴，向右方向为y轴，以坐标（m,n）表示第m行、第n列栅格。
16.1、机器人从当前位置开始，进行牛耕式运动，并优先y轴方向，具体如下：若机器人当前位置的左右两个相邻栅格均未覆盖，则随机选择一个栅格移动；若左右两个相邻栅格只有一个未覆盖，则移动到该未覆盖栅格；若左右两个相邻栅格均非未覆盖，则判断上下两个相邻栅格的覆盖情况并确定下一个移动目标，与左右类似。同时，在机器人的移动过程中，依次记录其新覆盖的栅格及其坐标，得到机器人先后经历的有序导航点集合c
nav
。附图3是导航点集合c
nav
的示意图，表示机器人先后覆盖经过了栅格a、b、c、d、e
……
（坐标值未标出）。
17.2、重复步骤1，直到机器人当前位置的上下左右4个相邻栅格均非未覆盖（即陷入死区），此时跳转至步骤3。附图4是机器人在附图2栅格地图上初次陷入死区时的移动情况。
18.3、对当前未遍历的栅格进行划分，生成若干个栅格集合，具体如下：对栅格地图，沿x轴方向，依次以一直线横穿整个地图，并将每一行直线所串联的未被障碍物阻断的未覆盖栅格归于同一集合。附图5为生成栅格集合的示意图，其中x=1的直线只贯穿了1组3个未覆盖栅格，则将这3个栅格归于集合1；x=6的直线贯穿了3组多个未覆盖栅格，则将其生成3个集合。
19.4、判断各栅格集合是否满足路径插入条件，具体如下：对某一集合cm而言，选取该集合中所有栅格的上方（或下方）相邻栅格，临时组成一新集合c0。若c0同时满足：（1）集合中不存在未覆盖的栅格；（2）集合中所有已覆盖的栅格未被障碍物阻断。
20.则cm满足要求。附图6为选取下方相邻栅格时，满足要求的四种情况示意图（选取上方相邻栅格与此类似），其中左向阴影栅格代表cm，白栅格代表c0中的已覆盖栅格，黑为c0中的障碍物（下同）。
21.5、对步骤4中满足要求的各栅格集合依次进行路径插入操作，具体如下：（1）寻与当前集合cm对应的步骤4中临时组成的新集合c0中，y轴数值最小和最大的已遍历栅格；（2）寻这两个栅格在c
nav
中的排序序号。设y轴数值最小值的序号为p
ymin
，最大值的序号为p
ymax
，并取p
min
=min（p
ymin
，p
ymax
），p
max
=max（p
ymin
，p
ymax
）；（3）对c
nav
中序号在p
min
和p
max
之间的所有栅格，依次判断前后相邻排列的两个栅格
（设序号以及坐标分别为pn、p
n+1
，（xn，yn）、（x
n+1
，y
n+1
））是否满足：（a）xn=x
n+1
=x0；（x0为集合c0中栅格的x轴坐标值）（b）|y
n-y
n+1
|=1。
22.若不满足要求，则继续判断下一组（即取n=n+1）；若满足要求，则将栅格地图中，与（xn，yn）相邻的栅格（xm，yn）、与（x
n+1
，y
n+1
）相邻的栅格（xm，y
n+1
）依次插入在c
nav
中序号pn与p
n+1
之间（xm为cm中栅格的x轴数值），并继续取n=n+1重复进行。附图7为该过程及其实现的效果的示意图，其中右向阴影两个栅格即为此时已插入的（xm，yn）和（xm，y
n+1
），黑带箭头线段为根据c
nav
确定的机器人移动路径（下同）。
23.（4）判断集合cm中是否仍存在未插入的栅格，若否，则跳过此步骤；若是，则此时分三种情况讨论：（a）步骤（3）中未插入任何栅格到c
nav
中，附图8是此时的两种情况示意图，其中竖向实线阴影栅格为c
nav
中排列序号在p
min
和p
max
之间，且不属于c0的栅格，竖向虚线阴影为c
nav
中其它栅格，（下同）。此时判断栅格地图上机器人在集合c0中的移动方向，若为y轴正向，则将cm中所有栅格按照x轴数值从小到大的顺序，依次插入到c
nav
中序号p
max
前一位；若为y轴负向，则将cm中所有栅格按照x轴数值从大到小的顺序，依次插入到c
nav
中序号p
min
前一位；（b）未插入栅格位于栅格地图上已插入栅格的中间位置，附图9是此种情况示意图。此时寻集合c0中与该栅格在地图上相邻的栅格在c
nav
中的排序，并将其插入到该序号的前两位处；（c）非（b）中未插入的栅格，此时若机器人移动方向为y轴正向，则当地图上某一未插入栅格的右侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的前一位，当其左侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的后一位；若机器人移动方向为y轴负向，则当其右侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的后一位，当其左侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的前一位，直到所有栅格插入完毕。
24.（5）寻步骤（4）（b）中栅格，以及（c）中地图上一侧为障碍物、另一侧相邻栅格为步骤（3）中插入的栅格在c
nav
中的排序序号，设为ps，坐标值为（xs，ys）。设与其在栅格地图同一行以及c
nav
排序中均相邻的栅格在c
nav
的排序为pr，坐标值为（xr，yr）。
25.取p
t
=min（pr，ps），设序号为（p
t-2i+1）和（p
t-2i）的栅格坐标分别为（x
t-2i+1
,y
t-2i+1
）、x
t-2i
,y
t-2i
），其中i为正整数。若满足：（a）x
t-2i+1
=x
t-2i
（b）（y
t-2i+1
=ys&&y
t-2i
=yr)||（y
t-2i
=ys&&y
t-2i+1
=yr）则将（p
t-2i+1）和（p
t-2i）所代表的栅格在c
nav
中的排列位置互换。
26.再取pu=max（pr，ps），设序号为（pu+2i-1）和（pu+2i）的栅格坐标分别为（x
u+2i-1
,y
u+2i-1
）、x
u+2i
,y
u+2i
），其中i为正整数，与p
t
类似，若满足：（c）x
u+2i-1
=x
u+2i
（d）（y
u+2i-1
=ys&&y
u+2i
=yr)||（y
u+2i
=ys&&y
u+2i-1
=yr）则将（pu+2i-1）和（pu+2i）所代表的栅格在c
nav
中的排列位置互换。
27.附图10为本步骤所带来的路径变化，其中左向稀疏阴影代表待进行插入处理的栅
格。
28.6、重复步骤4-5，直到不存在满足路径插入条件的栅格集合。附图11是附图4机器人重复步骤4-5后的路径变化情况。
29.7、判断当前是否已完成所有栅格的覆盖任务，若是，则跳转至步骤9；若否，则跳转至步骤8。
30.8、以a*算法计算所有仍未覆盖的栅格到机器人当前所在栅格的移动距离。选取其中最短距离，并将机器人移动至对应未覆盖栅格，同时在c
nav
中已有路径末端记录该栅格。之后跳转至步骤1。
31.9、根据最终得到的有序导航点集合c
nav
，以a*算法补全集合中前后相邻排列的两个栅格之间的实际移动路径。
32.10、合并各移动路径，得到最终机器人实际运动路径，如附图12所示。
33.可以理解，本发明是通过一些实施例进行描述的，本领域技术人员知悉的，在不脱离本发明的精神和范围的情况下，可以对这些特征和实施例进行各种改变或等效替换。另外，在本发明的教导下，可以对这些特征和实施例进行修改以适应具体的情况及材料而不会脱离本发明的精神和范围。因此，本发明不受此处所公开的具体实施例的限制，所有落入本技术的权利要求范围内的实施例都属于本发明所保护的范围内。

技术特征：

1.一种基于牛耕式运动的全覆盖路径规划方法，其特征在于，包括如下步骤：步骤1：用栅格划分地图，用不同阴影表示障碍物和机器人待覆盖区域，机器人从初始位置开始，进行牛耕式运动；步骤2：重复步骤1，直到机器人当前位置的上下左右4个相邻栅格均非未覆盖，即陷入死区，此时跳转至步骤3；步骤3：对当前未遍历的栅格进行划分，生成若干个栅格集合；步骤4：判断各栅格集合是否满足路径插入条件；步骤5：对步骤4中满足要求的各栅格集合依次进行路径插入操作；步骤6：重复步骤4-5，直到不存在满足路径插入条件的栅格集合；步骤7：判断当前是否已完成所有栅格的覆盖任务，若是，则跳转至步骤9；若否，则跳转至步骤8；步骤8：以a*算法计算所有仍未覆盖的栅格到机器人当前所在栅格的移动距离，选取其中最短距离，并将机器人移动至对应未覆盖栅格，同时在c
nav
中已有路径末端记录该栅格，之后跳转至步骤1；步骤9：根据最终得到的有序导航点集合c
nav
，以a*算法补全集合中前后相邻排列的两个栅格之间的实际移动路径；步骤10：合并各移动路径，得到最终机器人实际运动路径。2.根据权利要求1所述的基于牛耕式运动的全覆盖路径规划方法，其特征在于，所述步骤1包括如下具体步骤：栅格地图的坐标原点位于左上角，向下方向为x轴，向右方向为y轴，以坐标（m,n）表示第m行、第n列栅格，机器人从初始位置开始，进行牛耕式运动，并优先y轴方向，若机器人当前位置的左右两个相邻栅格均未覆盖，则随机选择一个栅格移动；若左右两个相邻栅格只有一个未覆盖，则移动到该未覆盖栅格；若左右两个相邻栅格均非未覆盖，则判断上下两个相邻栅格的覆盖情况并确定下一个移动目标，与左右类似，同时，在机器人的移动过程中，依次记录其新覆盖的栅格及其坐标，得到机器人先后经历的有序导航点集合c
nav
。3.根据权利要求1所述的基于牛耕式运动的全覆盖路径规划方法，其特征在于，所述步骤3包括如下具体步骤：对栅格地图，沿x轴方向，依次以一直线横穿整个地图，并将每一行直线所串联的未被障碍物阻断的未覆盖栅格归于同一集合。4.根据权利要求1所述的基于牛耕式运动的全覆盖路径规划方法，其特征在于，所述步骤4包括如下具体步骤：对某一集合c
m
而言，选取该集合中所有栅格的上方或下方相邻栅格，临时组成一新集合c0，若c0同时满足：（1）集合中不存在未覆盖的栅格；（2）集合中所有已覆盖的栅格未被障碍物阻断；则c
m
满足要求。5.根据权利要求4所述的基于牛耕式运动的全覆盖路径规划方法，其特征在于，所述步骤5包括如下具体步骤：步骤5.1：寻与当前集合c
m
对应的步骤4中临时组成的新集合c0中，y轴数值最小和最
大的已遍历栅格；步骤5.2：寻这两个栅格在c
nav
中的排序序号，设y轴数值最小值的序号为p
ymin
，最大值的序号为p
ymax
，并取p
min
=min（p
ymin
，p
ymax
），p
max
=max（p
ymin
，p
ymax
）；步骤5.3：对c
nav
中序号在p
min
和p
max
之间的所有栅格，依次判断前后相邻排列的两个栅格，设序号以及坐标分别为p
n
、p
n+1
，（x
n
，y
n
）、（x
n+1
，y
n+1
），是否满足：（a）x
n
=x
n+1
=x0；其中，x0为集合c0中栅格的x轴坐标值；（b）|y
n-y
n+1
|=1；若不满足要求，则继续判断下一组，即取n=n+1；若满足要求，则将栅格地图中，与（x
n
，y
n
）相邻的栅格（x
m
，y
n
）、与（x
n+1
，y
n+1
）相邻的栅格（x
m
，y
n+1
）依次插入在c
nav
中序号p
n
与p
n+1
之间（x
m
为c
m
中栅格的x轴数值），并继续取n=n+1重复进行；步骤5.4：判断集合c
m
中是否仍存在未插入的栅格，若否，则跳过此步骤；若是，则此时分三种情况讨论；（a）步骤5.3中未插入任何栅格到c
nav
中，此时判断栅格地图上机器人在集合c0中的移动方向，若为y轴正向，则将c
m
中所有栅格按照x轴数值从小到大的顺序，依次插入到c
nav
中序号p
max
前一位；若为y轴负向，则将cm中所有栅格按照x轴数值从大到小的顺序，依次插入到c
nav
中序号p
min
前一位；（b）未插入栅格位于栅格地图上已插入栅格的中间位置，此时寻集合c0中与该栅格在地图上相邻的栅格在c
nav
中的排序，并将其插入到该序号的前两位处；（c）非（b）中未插入的栅格，此时若机器人移动方向为y轴正向，则当地图上某一未插入栅格的右侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的前一位，当其左侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的后一位；若机器人移动方向为y轴负向，则当其右侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的后一位，当其左侧相邻栅格为已插入时，将其插入在c
nav
中该已插入栅格的前一位，直到所有栅格插入完毕；步骤5.5：寻步骤5.4的情况（b）中栅格，以及情况（c）中地图上一侧为障碍物、另一侧相邻栅格为步骤5.3中插入的栅格在c
nav
中的排序序号，设为p
s
，坐标值为（x
s
，y
s
），设与其在栅格地图同一行以及c
nav
排序中均相邻的栅格在c
nav
的排序为pr，坐标值为（x
r
，y
r
）；取p
t
=min（p
r
，p
s
），设序号为（p
t-2i+1）和（p
t-2i）的栅格坐标分别为（x
t-2i+1
,y
t-2i+1
）、x
t-2i
,y
t-2i
），其中i为正整数，若满足：（a）x
t-2i+1
=x
t-2i
；（b）（y
t-2i+1
=y
s
&&y
t-2i
=y
r
)||（y
t-2i
=y
s
&&y
t-2i+1
=y
r
）；则将（p
t-2i+1）和（p
t-2i）所代表的栅格在c
nav
中的排列位置互换；再取p
u
=max（p
r
，p
s
），设序号为（p
u
+2i-1）和（p
u
+2i）的栅格坐标分别为（x
u+2i-1
,y
u+2i-1
）、x
u+2i
,y
u+2i
），其中i为正整数，与p
t
类似，若满足：（c）x
u+2i-1
=x
u+2i
；（d）（y
u+2i-1
=y
s
&&y
u+2i
=y
r
)||（y
u+2i
=y
s
&&y
u+2i-1
=y
r
）；则将（p
u
+2i-1）和（p
u
+2i）所代表的栅格在c
nav
中的排列位置互换。

技术总结

本发明属于单机器人全覆盖路径规划领域，公开了一种基于牛耕式运动的全覆盖路径规划方法，以路径长度最短（路径重复率较低）为目标的、基于牛耕式运动的单机器人全覆盖路径规划方法，可应用于机器人扫地、除锈、扫雷、探伤等环境已知的二维平面场景。本方法在栅格地图上进行，通过机器人的牛耕式运动，并在陷入死区时更新未遍历栅格集合，之后对已生成路径进行路径插入操作，以及A*算法逃离死区的方式，获取一条路径重复率较低的规划路径。本发明能够在具有较复杂的区域边界、障碍物的二维已知环境下获取一条长度较短（路径重复率较低）的单机器人全覆盖路径。机器人全覆盖路径。机器人全覆盖路径。