英语原文共 19 页，剩余内容已隐藏，支付完成后下载完整资料
机器人覆盖路径规划综述
Enric Galceran,Marc Carreras
摘要——覆盖路径规划（CPP）是关于决定通过一个区域或避碰时关心区域中所有点的路径的任务。这个任务对于机器人应用来说是不可或缺的，例如真空清洁机器人，着色机器人，自主水下航行器进行图像拼接，扫雷机器人，锄草机器人，自动收割机，窗户清洁器和复杂结构检查指导等，这里只举一部分例子。对于CPP问题已经有很多的研究，然而在CPP这个领域过去十年没有最新的综述去反映其近期进展。在本篇文章，我们对最成功的几种CPP问题解决方案作一个综述，着重于过去十年内取得的成就。此外，我们还讨论报告中所描述的CPP方法的应用领域。这个工作旨在为初涉CPP问题的研究者们提供起点，同样地，也对这项领域最近的突破作一个全面的综述，提供通向优秀成功工作的桥梁。
关键词——CPP，机器人，覆盖路径规划。
1.介绍
覆盖路径规划（CPP）是关于决定通过一个区域或避碰时关心区域所有点的路径的任务。个任务对于机器人应用来说是不可或缺的，例如真空清洁机器人[1]，着色机器人[2]，自主水下航行器进行图像镶嵌[3]，扫雷机器人[4-6]，锄草机器人[7,8]，自动收割机[9,10]，窗户清洁器[11]和复杂结构检查指导[12]等，这里只举一部分例子。
根据所查文献，对于CPP的早期工作定义了在执行遍历工作时需要满足的要求[7]。即使之前所提的文章中的应用目标是移动式机器人在2维平面环境中移动，但在其他覆盖环境中标准同样适用，其要求如下所述：
- 机器人必须通过目标区域中所有点并完全覆盖。
- 机器人必须覆盖区域的同时路径不重叠。
- 按时序连续操作并没有任何重复路径。
- 机器人必须避开障碍物。
- 应该尽量用简单的移动轨迹（直线或曲线便于控制）。
- 基于可用性前提下有多种可选轨迹。
然而，在复杂环境中不是总是能够满足这些所有标准。因此，有时一个优先规划是必须的。
CPP问题就像是覆盖商问题，是著名的旅行商问题的变种，代理商要访问每个城市中的每一户而不是访问每个城市[13]。然而，在CPP问题中，相比访问每一户人家，代理商要通过目标区域的每一个点。因为旅行商问题是非确定性多项式（NP问题）[14]，当问题维度增大时解决问题所需要的计算时间就大大提升。实际上，在一个给定的被草覆盖的区域中寻找一个将所有草都割除的路径，被人们称为“锄草问题”，并被证明是一种NP问题。要注意的是，锄草问题并不涉及障碍。实际上，即便是像被称为“钢琴搬运问题”的这种从起始位置到目标位置找一条无碰撞路径的基础的路径规划问题，都被证明为是PSPACE问题，即意味着也是NP问题[15,16]。另外两个和CPP相似的问题分别是美术馆画廊问题和巡视员路径问题。美术馆画廊问题是在一个多边形画廊中以最少的守卫并使得画廊的每一处都至少被一个守卫看到[17]。巡视员问题需要一个从给定点到返回的最短路径并能使得巡视员在路径上至少有一点沿着路径能够看到给定区域的所有点[18]。像覆盖简单多边形内部的简单巡视员问题的案例可以通过多项式时间达到[19]。但是，总的来说，这两个问题都是NP问题[17,18]。一些我们在8.6节中讨论的覆盖演算法将CPP问题近似处理为美术馆画廊问题和巡视员路径问题。
覆盖演算方法可以归为试探式或完全取决于是否能够自由空间全覆盖。单独地，也可以分为离线和在线两种。这种分类法最初由Choset提出[20]。离线演算法只能用于静态形式，环境必须假定为已知。然而，预先知道环境的所有情况在很多场合下是不现实的。另一方面，在线演算法不需要假定环境的所有情况都已知并且利用实时测量传感器扫描目标区域。因此，这些后来的演算法也被称为基于传感器的覆盖演算法。
在已知的环境下，一个有效去解决问题的方法是使之随机化。一些清洁机器人就采用这种方法：如果地板被随机扫过足够长的时间，那么它一定被完全清洁。完全或部分基于这种决策的商业化地板清洁机器人，例如由Karcher发明的RC3000和iRobot公司[21]的Electrolux和Roomba研发的三叶虫（Trilobite）。这种方法有几个优点，最主要的一点是它既不需要安装复杂的传感设备，也不需要昂贵的计算资源。然而，对于遍历一个很大的区域，尤其是像水下或航空机器人操作这种本质上是三维空间的情况，很难想象这种随机演算法是适用的，同时操作这些航行器（能源和时间上）的费用也是难以承担的。
在文献中能找到大量关于CPP的研究报告。Choset[20]提到过关于覆盖路径规划的综述。然而，在CPP这个领域过去十年没有最新的综述去反映其近期进展。本篇文章，我们对最成功的几种CPP问题解决方案作一个综述，着重于过去十年内取得的成就。此外，我们还讨论报告中所描述的CPP方法的应用领域。这个工作旨在为初涉CPP问题的研究者们提供起点，同样地，也对这项领域最近的突破作一个全面的综述，提供通向优秀成功工作的桥梁。
因为大多数CPP演算法将目标区域分割成若干子区域以实现覆盖，[20]归类CPP演算法就要根据采用的分割区域的方法。因此，CPP演算法的分类包括探索式和随机法（典型不重复描述环境并因此不用分割区域），以及近似、半近似和完全模块分解法。然而，我们认为不同的方可以定性的分为这些种类。因此，这篇文章的几节不和Choset的分类法一一对应，而是反映一个普通基础用于讨论的方法中的思想。尽管如此，Choset的分类法被普遍应用于文献中。因此，我们为方法综述提供符合Choset的分类法。
图1.典型的z型路径。阴影区域指当机器人完成跟随z型路径时已经被覆盖（较暗的部分）的区域和将要被覆盖的区域（较浅的部分）。
考虑到这些因素，文章接下来的安排如下：第二节回顾经典的模块分解演算法，这个演算法为模块分解方法奠定了基础。第三节讨论模块分解的基础：莫尔斯函数的临界点，能够解决更多种类的障碍问题。第四节提到了基于探测自然地标的覆盖法。第五节讨论一种装备只在直线环境中操作的接触式传感器的机器人覆盖演算法。基于空间栅格化的方法在第六节中回顾。第七节中简要回顾解决环境覆盖问题的工作，将环境图表化，例如街道或道路网。第八节中几种对于三维环境的覆盖方法会被提到。第九节回顾几种实现选择性覆盖的方法，同时第十节着重于在实现覆盖时减少定位误差的方法。第十一节回顾几种多机器人协同覆盖路径规划法。最后，第十二节给出包括摘要表和未来研究方向的总结。
2.经典的完全模块分解法
完全的模块分解法将自由空间（空间中没有障碍）分解为简单的、不相互重叠的区域，称为单元模块。这些单元模块完全地填充这个自由空间。这些子区域中不存在障碍，机器人采用简单的移动方式就能很容易的遍历。例如，每个单元都能被z型路径遍历，就像图1中所示的“割草坪”模式。这种z型路径移动方式也被称为撒种移动，在文献[22-24]中有被很好的记录。
两个胞单元如果共用边界，我们称之为邻接。一个邻接图能够被用来去表示模块分解，图中的一个节点表示一个单元模块，一条变表示两个单元模块相互邻接的关系。完全的模块分解可以通过用一条线扫过这个空间产生（例如从左向右）。当一些事物遭遇扫过的线，就形成了模块单元的边界。比如：随时间变化的线扫过并与障碍的边界交叉就可以作为一个事件。
通常情况下，一个基于完全模块分解的规划者会采取两个步骤产生覆盖路径。首先，将一个自由空间分解为若干个单元模块并且将分解结果以邻接图形式存储。接下来，计算走过邻接图的详尽步骤（也就是连续并完全地经过图中每个结点）。获得的详尽步骤是连续的结点（也就是模块单元）而不是确切的覆盖路径是值得的。因此，一个遍历所有单元明确的路径要被导出。
接下来，我们讨论为更新的方法奠定基础的两种广泛应用的离线模块分解法（2.1和2.2节）。
2.1.梯形分解
完全模块分解技术中的一种能产生完全覆盖路径的方法是只用于处理多边形平面空间的梯形分解法[25,26]。这种方法被归类为离线式。梯形分解法中，每个单元模块都是梯形，如图2所示。因此，简单的往复运动形式就能覆盖每个单元模块。通过邻接图联系分解找到详尽步骤保证能够完全覆盖（如图2在分解上进行覆盖）。最终一条精确的能覆盖每个模块的z型路径就产生了。
图2.题型分解的工作空间实例及其相符的邻接图
详尽的步骤决定完全覆盖每个单元模块的顺序。最终一条能覆盖每个模块的确切路径就产生了，典型的是采用往复运动形式执行“割草坪”指令。
对于实际应用，就农业领域和农业机械来说，[27]推荐基于梯形分解的离线式演算法进行覆盖路径规划。它们的演算法适合后融合单元模块的梯形分解。产生的单元模块类似于由交错分解产生的单元，在2.2节中会有介绍。为了优化路径，他们采用基于路径消耗的函数去评估最大的单元模块通过用一条倾角30°以内的斜线扫过目标区域，产生六个不同的梯形模块。然后，选择三个最有利的方向并重复这个过程，并额外在被选择的方向两端各增加15°。这个过程连续交替进行直到每一步的增值都达到临界值，为了应用需要达到5次之后（精确到1°），要求分解成36个子区域。然后，最低消耗的分解中最大的单元模块从目标区域移除，并对剩余区域反复这个程序直到所有区域被路径覆盖。这个设计有效地生成了优化的覆盖路径，用于凸域和边界由长、直的线段构成的区域的高质量路径。
2.2.往复交替分解
梯形分解的一个缺陷是，这个方法生成很多个单元模块，直观上可以融合成一个大的模块。但显然地这很不便，产生的模块越多，如图3所示最终的路径就会越长。之所以发生这种情况是因为梯形分解只产生凸单元。然而，非凸单元也能通过简单的移动方式完成覆盖路径。为了克服这个限制，Choset和Pignon 交错单元模块分解法[23,28]。“boustrophedon”这个词来源于古希腊，字面意义是“牛走的道路”，意味着这个模式就像牛来回拉犁一样。往复交替分解和之前介绍的梯形分解类似，但这个方法只考虑能够在顶点的上部和下部延伸的纵向部分。这个顶点被称为临界点。
(a)
(b)
图3.更少模块的分解使得产生的路径更短。3(a)中指出相比3(b)中往复交替分解，梯 形分解中怎样被需要额外的带的。
遵循这种方案，往复交替分解有效地减少了梯形分解产生的单元模块的数量。因此，也就得到了更短的路径。需要注意的是，梯形分解这种方法假设多边形障碍和区域范围是已经给出的，所以被归类为离线式方案。
3.基于莫尔斯函数的单元模块分解法
之后[24]的交错分解法产生于被提出的一种基于莫尔斯函数[29]临界点的全新分解法。实际上，他们证明了交错分解是莫尔斯分解的一种特殊情况。相对于最初的往复交替分解，基于莫尔斯函数的分解胜在也能够用于非多边形障碍的场合。通过选择不同的莫尔斯函数，可以获得不同形状的单元模块，例如，圆形或者锥形模块。理论上来说，莫尔斯分解能够适用于任何n维度空间。此外，他们还提出了通过感应范围信息并基于移动样板演算以确保在目标区域内与所有临界点相遇来探测临界点的方法，来进行对平面空间的覆盖工作。因此，这种方法允许完全的在线覆盖。
莫尔斯分解基于由Canny[32,33]提出的用于始发点-终点路径规划的界标法。莫尔斯函数的临界点约束被用于决定模块分解的障碍边界。回想一下，给定一个实值函数，它在的微分是。一个临界点指函数在中这个点不可微分，或者它的所有偏导数都是0，也就是，并且它的Hessian矩阵（）是一个非奇异矩阵。例如，在单变量函数的情况下，一个临界点与局部极大值或局部极小值或拐点相联系。一个莫尔斯函数的临界点是非简并的。实际上来说，这意味着临界点之间彼此相互独立。
为了确定模块分解，让一个薄片扫过目标区域。形式上，就莫尔斯函数的前像来说这个薄片是个多样定义的余维数，，是机器人的工作空间，也就是待覆盖的空间。比如，在一个平面（），选择可以使薄片有效地形成直线。薄片连续性的变化发生在莫尔斯函数的临界点制约障碍的边界。简单来讲，在临界点的扫线与障碍相遇时，障碍的表面一般是垂直于扫线的，如图4所示。莫尔斯理论证明在临界点之间薄片的连续性保持不变。因此，在临界点之间不存在障碍时，它们之间的区域可以采用简单运动方式很容易的覆盖，并且临界点可以被用来决定单元模块边界。
法平面
临界点
扫线
扫向
图4.莫尔斯分解中单元模块边界位于临界点，即障碍的法平面垂直于扫线的位置，并平行于扫向
选择不同的莫尔斯函数产生不同的模块薄片形状并因此模块分解的模式也不同。为简单理解，我们把基于莫尔斯函数的交错分解描述为发生在平面环境。之后，我们会给出用不同的莫尔斯函数所得到不同的分解模式的例子。
在往复交替分解中，一条垂线，在莫尔斯函数中定义为，从左向右扫过工作区域，也就是沿着横坐标轴。因此，垂直的薄片就由莫尔斯函数的前像确定，。薄片被参数化为，在目标区域中固定其位置。增大薄片的参数的值，，让薄片从左到右扫过目标区域。
当扫过区域是薄片与障碍交叉（或停止交叉），这会使得它会在第一次遇到障碍时将其划分为更小的薄片，也就是，薄片在自由空间的连续性增大了。同时，在薄片扫过障碍时，更小的薄片又立刻汇聚成更大的薄片（薄片在自由空间的连续性减小）。发生薄片连续性变化的点就是临界点。（回想临界点总是位于障碍的边界上）因此，
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[140353]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
