点击上方“小白学视觉”，选择加"星标"或“置顶”

重磅干货，第一时间送达

1. 简介

覆盖规划是机器人学中一个问题，其应用场景包括自动农场，扫地机，扫描监视无人机等。其对应的问题被定义为：使机器人从某一起点开始，规划一条不与障碍物发生碰撞且尽可能短的路径，实现对划定区域的全覆盖。

覆盖规划算法

2. 问题分解

解决覆盖路径规划问题的方法有很多，其中一种思路是，也是最常见的一种解决思路是区域分解法：

1.首先将一个复杂的空间分解为一系列简单几何图形的子区域，并对使用单一覆盖规则对子区域进行覆盖。

2.然后规划一条路线，连接所有的子区域，以确保路径覆盖所有的区域。

区域分解

这样，我们就将一个问题分解成了两个子问题。

3. 区域分解 (Cell Decomposition)

对于问题1来说，一种常见的思路是先找到区域内障碍物的顶点 (Vertex)，沿着顶点画线直到与区域边界相交（或平行于 x, y 轴，或平行于障碍物的边）。这样复杂的几何区域便可以被分解为一个个凸多边形区域 (Convex Region)。

之后再使用平行线清扫的覆盖规则，对分解好的子空间进行规划。这样的方法叫做梯形分解 (trapezoidal cell decomposition, TCD)。

另外一种区域分解方式与TCD类似，叫弓形分解

(boustrophedon cell decompositon BCD)，Boustrophedon的意思是牛耕地的方式。该方式与 TCD 的区别在于对画线顶点的选择。

TCD会对所有的顶点画延长线，但BCD只会选择那些两端都可以延长顶点画线。因此BCD先对于TCD来说减少了很多冗余的区域分解。因此BCD的分解方式也更加的流行一些。

有了区域分解，接下来就是选择对子区域进行弓形覆盖时的方向，以及开始点了。

由于被分解后的图形都是非常简单几何形状，因此在方向的选择上就只有几何形状每条边的方向。开始点也只有每个子区域的顶点。

对于单个子区域来说，转弯数量最少的覆盖方向即为最优方案，但是对于全局来说，还需要考虑各个子区域之间的连线距离。从这个角度来说，区域分解方案的好坏可以使用下面的公式来衡量：

其中，m 是被分解出来的子区域的总数，ymax,i 是第 i 个被分解的区域的 y 坐标最大值顶点，ymin,i 是第 i 个被分解的区域的 y 坐标最小值顶点。w 为该分解的最小方向总和。

4. 旅行商问题

第二个子问题可以被归为旅行商问题。即在路径重复的情况下覆盖所有的目标点。

在本问题中则为找到一条可以连接所有子区域的最短路径。该问题的一种解决方案是使用遗传算法，或者是使用启发式算法，如以下链接，所提供的解决方案：

https://arxiv.org/pdf/1907.09224.pdf

TSP

5. 代码

一个使用 ROS 的开源代码：

https://github.com/ethz-asl/polygon_coverage_planning

一个基于 OpenCV 的 C++ 方案: 

https://github.com/RicheyHuang/CoveragePlanner

下载1：OpenCV-Contrib扩展模块中文版教程

在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。


下载2：Python视觉实战项目52讲
在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。


下载3：OpenCV实战项目20讲
在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。


交流群

欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~