移动机器人的路径规划实例分析

1、覆盖路径空间：关于移动机器人路径规划的实例分析摘要本文介绍了移动机器人在动态环境下路径规划的一个实例的理论分析。不像其他基于案例的路径规划方法，我们用栅格地图表示允许机器人在非结构环境下运行的环境。移动机器人的目标是选择跟踪低危险度的路径。本次实验以真正的机器人表现了我们想法的有效性。在本文，我们替换了种子实例库中移动机器人的搜索式路径规划算法并证实了实例库中基数的上下极限。证据表明用一些解决路径搜索问题的方案来发展实例库是实际可行的，结果是不可能存在与实例库中的路径区别较大的方案。这保证了在理论上机器人将会搜索从起点到终点的所有路径。实例库中基数集上限表明，在长远看来，实例库将不断扩大，不可

2、能保存所有解决方案。为了保持最有效的解决方案，实例库在运行中必须加以改进，或必须考虑一些其他方法的路径差异。2003 Elsevier Science B.V. 保留所有权关键词：基于实例的推理；路径规划；覆盖度量空间1简介本文介绍的工作是移动机器人研究方面的理论延伸，我们调查了包括移动机器人在解空间内生成一个种子实例库的问题。在我们先前的工作中，基于案例推理（CBR）的方式，我们已经在实际的机器人上实现了移动机器人路径规划和测试。在这项工作中，我们证明了理论上限和下限对于实例基数的可行性和我们的方法的局限性。本文的其余部分组织如下：在第1节我们着眼于机器人的导航领域介绍并解释这个问题的重要性

3、。第2节介绍了系统以前的实验做法和对实验结果的评语。在第3节，我们给出了基本的定义并且陈述了主要空间的机器人路径，上述内容也覆盖了第4节的问题。第5、6节（精确）证明理论下限和上限，分别对覆盖问题加以说明。第7节在当前的介绍上将旧启发式算法与新的进行比较。第8节得出了一些结论，并讨论了今后的工作。 1.1行动方式我们的工作是基于一个事实，大部分的移动机器人的应用意味着在环境变化时重复遍历于预定义的起点和目标点之间。例如，一个移动机器人可用于在商店和生产线之间传送细节并分部装配。这项任务暗示了在商店和最小单元生产组之间的的重复遍历。这项任务也暗示着以一个预定义的顺序在一个封闭的区域上访问某些关卡

4、。操作这些移动机器人的真实环境本质上是动态的，从移动机器人的导航视图中看，这意味着意外障碍也会出现和消失。这些障碍的性质和密度通常是未知的或很难模拟。与此同时在动态环境中的移动机器人必须尽可能快速安全地完成分配。这意味着在目标点之间选择路径是最畅通的，并且在这些路径中的机器人在障碍之间并不会花费很多时间。迄今为止，很少有研究报告报道路径选择方面的问题。不像这些方法，我们并未假定环境结构是已知的，因此，我们的方法也适用于环境是未知的并且环境会改变的案件。2.系统描述移动机器人路径选择的方法包括整个世界模型以及存储路径运行的经验以备后用的记忆模式。内存是一个实例库用于存储以前运行过的路径。世界模型

5、是指一个允许路径规划的地图，由于在动态环境中，机器人不能模拟其周围环境的所有方面，所以地图总是或多或少不精确。图1抓住了这种方法的底线,。该全局规划师接收来自用户的任务，这些任务是需要从机器人的现状位置移动到一个特定的点。全局规划师有一个环境地图，这个地图仅仅呈现出目标点的环境和位置的几何方面。在环境中，动态障碍的存在和位置是未知的。给定了新的任务，全局规划师要么可以基于地图的路径规划找到一个新的解决方案，要么重新使用一个从早期的实例库中发现的路径。由全局规划师规划的路径被提交到低一级的规划和执行单位，该单位负责任务分解（如有必要），重新规划，定位，传感器的数据处理和执行器的控制。全局规划师的

6、目标是根据一些标准选择最好的运行路径（如时间，距离，安全性）。CBR允许该机器人记住和学习其过去的经验。该机器人将适应动态环境的变化，学会更好的使用路径。 图1 路径规划概览2.1基于实例的推理改变先前对类似问题的成功解决方案，基于案例推理（CBR）解决了新的问题。过去的经验，通过应用数据库技术管理，都存储在一个实例库。为了便于案例检索，在实例库案件中应加索引。当一个新的问题出现时，从特性中提取索引，用于查找匹配的实例库案件。如果不止一个匹配案例被发现，那么候选案件是非常有价值的，用以找到最合适的一个。除非检索到的情况是一场势均力敌的比赛，该解决方案可能必须在使用前加以修改以便解决问题。如果修

7、改后的情况下发现是成功的，它会产生一种新的情形，即存储在实例库中。因此在CBR中，学习是通过新案例的积累来完成的。在本文描述的方法中，问题是从一个给定的出发点到一个给定的目标点之间找到最佳路径。该解决方案的结果是反映路径的成本，反映了运行此路径是多么容易。如果机器人反复遍历一条路径，每次遍历后路径的成本都将更新。这笔费用将反映这条道路的平均特点。通过选择具有最小代价的路径，机器人可以降低碰撞风险，以及减少运行距离。路径规划的CBR方式在文献4-7 描述。这些方法用于规划静态环境。PRODIGY/ANALOGY将CBR应用于美国匹兹堡8市动态路径规划。这些方法使用一个基于图形的地图来进行路径规划

8、，该地图的缺点是它假设环境的刚性结构为不同的捕获地方（节点）和连接路径（边）。如果结构环境发生改变，整个图形要改组，以更新地图。在许多情况下，它是可行的，推定环境结构是稳定的。例如，在PRODIGY/ANALOGY的情况下，很明显该匹兹堡结构（即街道和口岸）不随时间明显变化。另一方面，也有许多移动机器人的应用领域，那里的环境可以根据机器人的任务（例如建筑或救助网站）巧妙地改变。为了能够使用高动态机器人环境，我们使用一个基于网格的地图，而不是一个拓扑性地图。基于网格的地图针对单一路径规划问题也提供更多的解决方法，并提供更详细的路径规划。由于可以有多个路径之间的替代给定的目标点，所以实例库中的每个

9、问题可以有多个解决方案。要从实例库中查找类似问题，我们用最近邻检索，即机器人将查找该案例开始和目标点尽可能接近当前的问题。但是，为了分析我们的实例库，我们假设它仅有一个问题组成，该问题有许多解决方法。这个问题将有尽可能多的解决方案，即在斜对面的角落之间通过的问题。将我们的问题正规化，所有其他路径规划问题都是这一最普遍问题的子问题。我们的目标是根据一些相似的问题的解决措施，将现有问题的所有不同解决方案来生成实例库。2.2路径规划在移动机器人学的背景中，路径规划方法是指寻找从开始到目标的无碰撞路径。该路径规划的方法取决于机器人世界模型。（文献9为智能机器人技术的概述和路径规划技术）在这项工作中，我

10、们选用一种常见的移动机器人世界模型栅格地图。栅格地图用一个个小的单元格来描述世界。那些已知的，包括静态障碍物的单元格可被标记为已占领。在我们先前的工作中，我们已经研制了一个搜索式算法的修改版，由于地图上随机扰动的生成，它对一个简单的路径规划问题会产生许多可选择的解决方案。图2表示一个网格地图。地图上的黑色区域代表静态障碍，搜索式算法生成了从起点到目标点的路径。有两个问题与路径生成方式相关：首先，在理论上，他不可能保证找到从给定起点到给定目标点的所有可能路径。第二，即使在一个相对小网格，在指定的目标点之间不同的路径数量是十分巨大的；与此同时，区别较大的路径数目较少。为了克服这一问题，我们定义了一

11、个相似度（详见第3部分）。有了相似度，我们可将区别较小的路径视为相同。机器人运行的路径贮存在实例库中，在此，我们利用相似度的特点，只贮存彼此间区别较大的路径。这样大大减少了实例库的规模。 图2 栅格地图在我们的实验中，我们建立一个空的实例库，若一个必要的解决方案没在实例库中或它的特性不是很好，则会产生基于地图的路径规划的新的解决方案。我们可以在环境或用真正的机器人来深入检验我们的算法。测试表明，机器人能快速适应环境的变化并 学会使用风险较小的路径。所有的测试表明，即使环境很大，实例库规模实际上是很小的。然而，测试也指出了我们算法的缺点。我们的路径规划算法可更改地图来生成新的随机解决方案。在测试

12、中，很明显可以观察到，由算法生成的许多路径是十分相似的。机器人花费很多时间来等待寻找不同的解决方案。有时机器人也会困在局部区域一些本来十分容易运行的路径是永远也不会生成的。2.3实例库的生成为了克服我们目前装备的缺点，我们实施了针对当前问题所有解决方案来生成实例库，从理论上讲，从一个给定起点到给定终点的可能路径数是十分庞大的。这些路径中许多仅有小部分差别，从轨迹跟踪角度讲，大部分路径是不可行的（如不可行的弯曲或过长），因此，我们必须限制其在实例中使用的路径设置。为确保我们的限制，我们必须解释一些机器人轨迹跟踪的细节。在现实生活中，机器人永远无法精确按照已设计好的路径进行跟踪。由于位置误差，传感

13、器噪音以及机械间不精确连接，机器人常常会偏离它的轨迹。在动态环境中，机器人也必须在意想不到的障碍周围行进。后者很大程度上会使得机器人偏离原来轨迹。因此，我们的相似度是基于路径的偏差，我们认为那些偏离彼此较大的路是不同的。相反，我们认为那些通过环境地图大致相同区域的路径是相似的。我们的相似度是第3节中定义。移动机器人使用避障轨迹和运行时间重规划来解决动态障碍。在我们的真正的机器人实验中，我们观察到规划路径与最终跟踪路径差别很大，因为围绕着障碍进而重新规划和定位误差有时会使得机器人沿着另一个方向行进而不是最先的规划方向。因此，我们发现最实际的道路通行方式就是规划路径与实际跟踪路径之间相似路径。能使

14、的机器人跟踪的越好，那么这个路径就越好。我们可以用来评估估计的第二种方式是路径跟踪时间。这种方法也十分实用，因为移动机器人通常能预期尽可能快的完成任务。因此生成实例路径既短又直看起来是可行的。这些路径是最可能满足我们良好通行标准的。短路径是最有可能导致机器人更快到达目标。过于弯曲的路径在技术上也很难跟踪（而且机器人到达目标花费的时间更长）。因此我们限制我们对路径的设置为能直接更快到达的移动。它将排除所有不必要的又长又复杂的路径（实际指所有有回环的路径）。这种约束的缺点在于该机器人在迷宫一样的环境中不能有效运作。然而，多数实际环境并不是迷宫一样的。另一个缺点是指迂回式弯曲路径，这个缺点不是那么严

15、重，因为我们只认可短而直的路径。这是典型的基于网格的方法和路径规划，通常移动机器人运用路径松弛技巧在运行时平滑通过路径。本片文章其余部分我们主要讨论实例管理的问题。第一个问题是是否能够用相对较少的不同实例来生成实例库以便涵盖整个解空间。这个问题的答案是肯定的。第二个问题是系统是否可以在无人管理实例库的情况下正常运行。例如，仅在实例库中路径不太相似的条件下，机器人可随机生成可能的路径。这个问题的答案是否定的。不同解决方案的最大数量将增加很多，实例库过大，机器人管理实例库的能力减缓。因此，必须舍弃那些不太有用的解决方案。在下一章，我们将我们会描述问题，定义一个相似度并证明实例库中基数的下限和上限。

16、3.基本定义设a,b，表示集合。我们认为机器人在一个的长方形网格中做正确和短距移动。机器人从原点0,0出发（以网格的左下角为原点）到达终点m,n。定义1：在的网格中，一条路径由一系列的网格点构成。比如，（1）对于每一个，在网格中满足条件的所有路径集合记为。接下来，我们定义一个路径间的相似度的概念。直观地讲，我们认为机器人选择的路径分离幅度不是很大，我们就认为这两条路径相似。为了描述这个想法，首先我们需要定义一个大致距离度量。每一种定义都有几种可能性，在本文中我们选择其中之一。定义2：我们定义点和路径间的网格距离为，定义为点C1和点C2间的距离。即c1=(x1,y1),c2=(x2,y2).将P

17、1和P2间的网格距离定义为。的最大以及最小距离被称为Hausdorff距离。（见文献10）.对于任何内部指标d来说，Hausdorff距离并非是实际距离。因为他很可能不是对称的；只有当d指的是欧式距离时，这样的情况才可能会发生。为了解决这一问题，可以采取一些措施，最常见的一种方法就是用见文献10或来代替向性距离。见文献11然而，在本文中，由于我们非常特殊的选择相应的设置和内部指标，向性豪斯多夫距离十分接近实际距离。引理1：是一个度量空间。证据：首先，我们注意到始终是一个非负整数。度量空间的恒等式和三角不等式的公理是很容易证明的（实际上，它们支持每一个向性Hausdorff距离）。为了证明对称性

18、，我们首先证明以下每两条路径P1，P2是对称的。：。 （1）取一点，首先设若，则得且我们可令c2=c1来满足方程（1）.若，则假设w.l.o.g是P2的运行路径在点c1上方。在度量空间中取封闭圆形B，以c1点为圆心，为半径，d的含义正是指定义2中的距离。（标注：这个圆实际看起来是指以c1为圆心，以为边缘长度所构成的面积。）从定义2中可以看出，圆B内部中不包含路径P2上任一点，但圆B边缘可能包含P2上的点。尤其是，B的左上角上的点必须始终属于P2的，现将此点作为c2点，则P1上任何点都不可能比c1点离c2点更近，则，方程（1）得证。现设作为令成立的点。通过方程（1）我们可选取一点使得，则.同理可

19、证，故得。根据引理1，定义3仅仅是度量空间中封闭圆形标准定义的应用。定义3：在度量空间中，设一个以p点为圆心，以为半径的圆。令，则我们得到以下标准结果。引理2. 证明.每一路径包含m+n步，其中m步向右移动。4.问题表述在度量空间中，我们主要着眼于覆盖问题。问题。对于一个给定整数和尺寸为m,n的网格，寻找基数子集一个上限和下限的估计使之满足下列性质： （2） (3) 下限估计与有效覆盖问题相关，在这一背景下，为了获取偏差不超过极限的所有可能路径，我们问在实例库中要求预先计划的路径的最少数目是多少。与此相反，上限估计是处理最糟糕情况的。在这种情况下，我们考虑一个随机路径的产生过程并思考如果我们每

20、次只包含那些与先前记录的所有路径偏离最多不超过得新路径，那那我们可设置的最大路径是多少 。5.下限定理1：对任意且任意子集满足性质（2）和（3），则不等式（4）成立。 （4）甚至，存在一个集合S满足（2）和（3）的性质以及不等式（4）。证明：首先我们考虑一种特殊情况，定义，和子集满足下列条件：。我们注意到时不等式成立。因此，集合T中任两个元素都不可能被包含在半径为的同一个圆内。所以，当覆盖以集合S（满足条件（2）中元素为圆心，为半径的圆构成的空间时，至少有与集合T中元素数量相同的圆。但T的路径实际上是网格尺寸为的网格上的路径（网格面积），因此，在此情况下，定理中的不等式成立。为了证明在这种情况

21、下的不等式，我们简单认为考虑一个尺寸为的次网格是可能的，并且以与定义集合T的情况相似的方式定义一组（局部的）路径。上述提供的论证也可以很容易适用于这种情况。以等式成立为条件的集合S的存在也可先在的情况下证明。我们可以证明S=T，T是上面定义的集合。它有正确的基数，条件（3）成立是显而易见的。它还需证明条件（2）也成立。为了证明这一结论，我们必须表明，集合中每一条可能路径都属于圆中某些路径，其中。令可能是网格中任意路径。我们将网格划分为的区域并建立一条新路径以便于：（1）它沿大区域边缘行进（则）；（2）对于P路径上的每一点c1，则在路径上存在一点c2使得（则）。我们将沿大区域跟踪路径P并表示出路

22、径P0在每种情况下必须大区域的边缘和顶点：我们在大区域按照路径P起始点的位置分情况，有四种可能的区域作为起点和终点，每一区域包含长度为的两部分，它们位于大区域的四个角落。共有8种可能情况，路径相关部分所有可能情况见图3. 图3 路径的建立在的情况下推广这种存在性证明是很简单的。正如上面所做，我们选择一个规模为的次网格，但我们必须更谨慎。也就是说，次网格必须定位以便次网格的边缘间没有距离而且为了包含网格中所有路径，整个网格的相关边缘不能大于。由于m和n除以的最大余数是，这样的定位可以很容易做到。它仍填补了网格中由集合T给定的路径，网格中的子路径加入了整个网格的左上角和左下角。右上角和右下角也是类

23、似的。6.上限定理2：对任意且任意子集满足性质（2）和（3），则不等式 成立。若是奇数，选上面式子；若为偶数，选下面的式子。而且，存在一个集合S满足性质（2）（3）和等式。证明：这个定理的证明与定理1的证明十分相似。首先我们考虑当为偶数且时的情况。我们定义集合T如下：。假设我们还有一集合S符合性质（2）和（3）。类似与定理1的证明，可以表示对每一条的路径，存在一条的路径满足。若对两条不同路径，相应的路径相同，则有，与性质（3）矛盾。因此，集合S不可能比集合T含有更多的元素。正如定理1，我们有，在这种情况下，定理中的不等式成立。为了在的条件下也推广结果，我们再次考虑一个规模为的次网格位于的网格中

24、心。我们也注意到令S=T提供了符合要求的集合来实现该定理的不等式。当为奇数时的证明是完全类似的。唯一不同的地方是在这种情况下，我们不能要求任何路径P在集合T中存在一条距离远大于路径，但我们必须用来代替。7.算法比较 与以前的探索式算法相比，为了说明现有算法的优越性，我们用我们以前实际实验之一的参数。对于一个单元格的栅格，以及相似的极限值，种子实例库的尺寸为个实例。 与此同时，如果使用探索式路径生成算法，虽然实验所涉及的解空间包括500多个运行，新生成的路径不可能覆盖解空间。另一套我们以前的实验，在仿真环境下，20，000个运行给出一个相似的结果。此外，搜索式算法常常产生随机路径，与实例库中已经

25、存在的旧路径十分相似。新路径中大约四分之一的路径是创新性的，即与实例库中的所有路径不同。新算法有双重优点：（1）它产生的种子实例库可以保证覆盖机器人的路径空间，而以前的搜索式算法不能给出这样的保证。（2）它可以加快学习速度因为所有的路径都储存在种子实例库中。不像搜索式算法，因为机器人无法花时间在寻找新的创新性解决方案。然而，如果减小，种子实例库的规模会迅速增加。当=2时。实例库将包含超过一百万的实例。实际上，一个机器人永远不会尝试所有可能的解决方案。当它找到了一个足够好的解决方案，他会减少探索。当现有路径的花费增加时，它才会又开始探索新的可能性。种子实例库在理论上保证了概无可能的解决办法仍未被

26、发现。证明上限的想法是为了检验我们是否能给出实例库中可能案例的最少数量。这将给实例库设计者一个信心，实例库不会扩展大于一个必然的可行数量。不幸的是，实例库的上限太大。在上面所给例子中，（m=51，n=67，=5），实例库包括个实例。因此，保持实例库的规模受到控制是十分有必要的维修策略。在我们以前的工作中，我们使用过基于解决方案质量的遗忘策略。例如，当学习程序成功驱动机器人时只记忆最好的解决方案，当学习程序驱动失败，机器人会记忆最糟糕的解决方案。然后，实例库只用来验证一个新的解决方案是否好到值得从头开始生成。我们的实验还没有表现出遗忘算法的优越性。这更能看出实例库的管理技巧很大程度上取决于环境的

27、特点和手头上的问题。8.结论及未来工作我们的工作是基于一个事实，即以前的搜索式算法不可能生成当前路径搜索问题的所有可能的不同解决方案。因此，我们研究这种可能性是为了创造一个覆盖机器人所有解决方案的种子案例库。在本文中，我们已经证明了解空间的下限和上限。下限的证明表明了生成一个包含对任意一条可能路径密切相符的解集的实例库是可行的。这保证了在理论上没有路径仍未被发现。与此同时，上限的证明表明将所有不同的可能解决方案保存到实例库是不可行的。为了限制实例库，它在运行时必须加以修正。实例库激增的可能解决方案之一是基于以下观察。从栅格距离的角度讲，尽管实例库包含了距离彼此较远的路径，但仍有许多路径明显重叠

28、。如果我们只是尽量覆盖路径的网格碎片而不是通过所有路径本身，那么这会使得实例库变得更小。如何更好处理这个问题是未来研究课题。同样重要的是要强调上述例子代表的只是对一个问题的解决方案数量。这个问题是最普遍的斜对角间遍历问题。其他问题是这个问题的子问题，并将需要少量解决方案覆盖其解空间。在实际应用中移动机器人通常都有少部分目标点（除非它是一个映射或探索性问题）。在今后的研究中，我们还打算分析解决方案数量与案例库规模之间的依赖关系。我们还打算研究一些不同的相似性方式来更大的减小解空间的规模。一种可能性是将将其定义为由路径所包围的区域。参考文献1 M. Kruusaa Repeated Path Pl

29、anning for Mobile Robots in Dynamic Environments, PhD Thesis, Chalmes University of Technology, Gothenburg, Sweden, 2002.2 H. Hu, M. Brady, Dynamic global path planning with uncertainty for mobile robots in manufacturing, IEEE Trans. Robot. Automat. 13 (5) (1997) 760 767.3 K.Z. Haig, M.M. Veloso, Planning, execution and learning in a robotic agent, AIPS-98 June (1998) 120 127.4 C. Vasudevan, K. Ganesan, Case-based path planning for autonomous underwater vehicles, Proc. 1994 IEEE Int. Symp. Intell. Control ，August (1994) 160 165.5 A.K. Goel, K.S. Ali, M.W. Donnellan, A. Go