全覆盖路径规划——ccpp

在路径规划方法中，有一种是点到点的路径规划，这一类例如dijstra，或者A*这类算法，关注的是点到点的最短路径，偏向一种最优的选择。还有一种是全覆盖是路径规划，这一类路径规划关注的是遍历整个地图，例如扫地机器人之类的，他们的主要目的就是遍历，针对这一需求，全覆盖路径规划产生了。

在目前全覆盖路径规划中常会关注的一些方向：

1.全覆盖工作区域内的障碍物等会影响阻碍农机的工作路径,进而影响现场工作效率

2.全覆盖作业中，存在工作区域的面积遗漏，工作路径重复的问题，进而影响工作质量，造成资源浪费,机器人的路径规划可以避免路径重复，缩短移动距离，提高工作效率

3.面对复杂任务时，单机器人工作效率较低，许多任务无法完成，为了处理复杂问题，提高工作效率，多个机器人合作是一种有效的方式，多机器人合作作业的核心问题是解决机器人之间的任务分配问题.

所以针对这些问题，目前研究方向主要包括环境模型构建、机器人路径规划、多机器人协作任务分配 ３方面。

准确、可靠的环境地图有利于后续路径规划，在已知环境地图的情况下，可以规避静态障碍物，提高作业可靠性；机器人路径规划可有效减少地头转弯次数，减少遗漏面积，提高作业效率；优化的任务分配方案有利于处理复杂的全覆盖作业问题，能够更快、更有效地执行任务，减少作业时间，提高工作效率。

1.环境建模方法

目前在全覆盖路径规划研究领域中，环境建模方法主要包括拓扑图法，栅格法、几何图法和单元分解法等

主要介绍一下单元分解法和栅格地图法（这两种方法是我目前主要关注的）。

单元分解法：

单元分解法（区域分解法）是根据不同的障碍物形状，对整个空间区域进行分割，把整个待覆盖区域分割成若干形状较为简单的无障碍物、无重叠部分的子区域。常用单元分解法有梯形分解法 、布氏（Ｂｏｕｓｔｒｏｐｈｅｄｏｎ）单元分解法 、莫尔斯（ Ｍｏｒｓｅ）分解方法等。

对这类问题，常见的方法是：

第一步：对整个地图进行单元分解，得到一片片单元地图

第二步：对每个单元地图内部做覆盖路径规划

第三步：将所有单元组合起来，要考虑每个单元的起点和终点，组合优化问题

栅格法：

栅格地图法是一种二值信息表示环境的方法，将机器人工作空间的环境信息利用相同尺寸的栅格
进行分割，以栅格单元为单位表达该区域环境信息，然后在环境地图上使用路径规划算法进行路径规划，目前多种路径规划算法均采用栅格地图的建模方式。

对于栅格法，所得的栅格地图都会有相应的值，从而可以区分地图中的空闲区域和障碍物区域，利用这种信息可以设计路径规划算法。

2路径规划算法：

全覆盖路径规划中的关键问题在于如何最大程度遍历工作区域内除障碍物以外的部分，并有效规
避所有障碍物。

简单路径规划算法有：往复式覆盖法和螺旋式覆盖法

往复式覆盖法：

这类方法例如牛耕法，就是按照一定的规则遍历这个区域，这类算法简单，但是遗漏率高一些 

 往复式覆盖易实现且具有作业覆盖率高的优势，但转弯次数多且需要进行 １８０°转弯，转弯难度大，造成转弯区域面积大的问题，对于体积较大的机器人实现起来较困难。

螺旋式覆盖法：

这种方法就像名字一样是螺旋式的，从外到内或者由内到外，遍历。

螺旋式又分为内螺旋与外螺旋，内螺旋式覆盖方式如图 ２ｂ所示，是指机器人从作业区域某一边开始作业，直到区域边界转向 ９０°到另一边界继续。

优化的路径规划算法

基于生物启发神经元的方法

生物激励神经网络（BINN）算法

针对机器人覆盖过程中需要避障和逃离死区的问题， ＲＡＳＨＩＤ等将需要全覆盖的二维栅格地图单元与生物启发神经网络的神经元一一对应起来，利用神经元的活性值和机器人的上一位置信息进行实时路径规划，该算法不存在神经网络学习过程，算法实时性好 。

这些启发式方法或者优化方法都可以对路径的选择起到很大帮助。

混合式路径规划方法：

混合式路径规划方法是简单路径规划方法和复杂路径规划方法的结合，采用简单路径规划方法或改进算法进行子区域遍历，后结合优化算法（如蚁群算法、Ａ∗算法、深度优先搜索等）进行子区域的连接优化，以实现全覆盖路径规划。

常见的优化方法还有theta*方法，这个方法可以弥补A*算法那种过于固化的选择方向。选择的方向更多。

3多机器人任务分配方法

多机器人任务分配是指为多机器人设定一个评价指标，将一系列作业任务分配给特定机器人，在任务能够被全部完成的同时使机器人的收益最高 。在全覆盖作业中每个机器人的任务是物理环境中所划分出来的一个独立的作业区域，所有机器人完成分配的任务，也就实现了工作区域的全覆盖。

3.1基于数学规划的任务分配方法

3.2基于启发式搜索的任务分配方法

3.3基于群体智能的任务分配方法

3.4基于市场机制的任务分配方法

论文：

农业机器人全覆盖作业规划研究进展 王  宁   韩雨晓   王雅萱  王天海  张  漫  李  寒