planning alg翻译-by jiayao 2016.11.23

7.6 覆盖算法

翻译

planning alg翻译-by majiayao 2016.11.23

7.6 覆盖算法

试想一个自动运动的割草机，需要在一个有很多障碍物的地方工作，例如房屋、树木、车库，和复杂的边界。
什么样的zig-zag对于割草机是最好的？多余覆盖的路程能最小化么？割草机停止和转弯的次数能最小么。
这就是一个coverage planning覆盖规划的例子。
这样的应用的例子除了割草，还有自动工作，粉刷，吸尘器，采矿等。
survey[217]综述
[216] H. Choset. Coverage of known spaces: The boustrophedon cellular decomposition.
Autonomous Robots, 9:247–253, 2000.
[217] H. Choset. Coverage for robotics – A survey of recent results. Annals of Mathematics and Artificial Intelligence, 31:113–126, 2001.

即使在二维下，寻找覆盖的最优路径是NP难问题。问题简化后可以看做是Traveling Salesman Problem
旅行商问题。[36, 709]

因此，我们即使在R2空间内也容忍近似，甚至启发式的算法去解决覆盖问题。

Boustrophedon decomposition 牛耕分解法

一种方法是把Cfree分解成cells，然后像牛耕地一样运动。

[222].
它假设机器人是W=R2中的一个点，但是其有工具厚度E挂在机器人的两边，覆盖cfree以E/2,这种方法常用在打印机减少打印转弯。
如果COBS是多边形，像6.2.2讨论的垂直分解，那个算法里有很多情况，在牛耕运动中只遇到第一种情况。
这使得分解出的cell数目少，即使是非凸的，也能很好的切成垂直的片，很适合于牛耕。
原始的垂直方法也可以使用，但是多余的cell边缘会导致机器人不必要的重新定位。
一个相似的方法是最优化机器人的转角[468]

Spanning tree covering 生成树覆盖。

这个有趣的方法是Gabriely and Rimon提出的，在CFREE中放瓷砖，通过connectivity graph连接图计算结果[373]
假设CFREE是多边形。

第一步是用真方形来贴满CFREE。每个方形，宽度是E
第二步，Next, 建立地图G 在每个方形中心放置顶点，然后连接每个相邻的方形成一条边。
第三步：计算G的生成树. 是一个便利每个顶点和且无环路的子图，计算复杂度O(n) G 有n条 边
第四步：有很多可能的生成树，可以有一个标准来优化结果。
当生成树建立了，机器人，从生成树的一个点开始走，沿着它的周边走。
路径可以是这样的：

双倍贴砖的精度，会改写路图。一部分roadmap和生成树一直，但是也包含回环的路径。这个路径会便利新方块的中心。路径结果在上图。通常，方法会有一个最优路径。
对于未遍历地方的近似在[372]，没有先验地图的在[373]，包含推理的在十一章讲。