英语原文共 8 页

部分已知环境的最优高效路径规划

安东尼斯坦兹

机器人研究所; 卡内基·梅隆大学; 宾夕法尼亚州匹兹堡15213

摘要

在研究文献中，规划移动机器人轨迹的任务受到了相当多的关注。大多数工作假设机器人在移动之前有一个完整的并且准确的环境模型，极少关注环境并未全部已知的问题。当探索机器人或其他机器人必须在没有平面图或地形图移动到目标位置时，这种情况就出现了。现有方法基于已知方案规划初始路径，然后当机器人通过传感器发现障碍物时，在本地修改计划或者重新规划整个路径，分别牺牲最优性或计算效率。本文介绍了一种新算法D *，能够在未知的，部分已知的，以及易变的环境中以高效，优化，完整的方式规划路径。

1.0介绍

研究文献广泛涉及一个或多个机器人穿过一系列障碍到达目标的动态规划问题。大部分的研究假设机器人开始移动前环境已经完全已知（参考Latombe [4]的一项调查）。该文献中的最佳算法探究一种状态空间（例如，可见性图，网格单元），利用距离变换[2]或试探法[8]去寻找从机器人的起始状态到目标状态的最低成本的路径。成本可以被定义为行进的距离，消耗的能量，暴露在危险中的时间等。

不幸的是，在他开始遍历前，机器人可能只有部分或者没有关于环境的信息，但是他配备了一个在移动中能够测量环境的传感器。这种场景中的一种路径规划方法是利用已知信息生成全局路径，然后尝试“本地”绕过传感器检测到的路线上的障碍物[1]。如果路线完全被阻挡，则计划新的全球路径。Lumelsky [7]最初假定环境没有障碍，机器人直接朝着目标前进。如果一个障碍阻挡了路径，机器人围绕障碍周边移动直到障碍上距离目标最近的一点被发现，那么机器人继续直接朝着目标前进。Pirzadeh[9]采用了一种策略，让机器人徘徊环境直到它发现目标。机器人以最低的成本反复移动到相邻的位置，并在每次访问一个位置时增加该位置的成本，以便下次到达相同位置时能够计算成本。当机器人在环境中移动时，Korf [3]使用初始地图信息去估算每个状态下到达目标的成本并通过回溯成本有效地更新它。

虽然这些方法是完整的，但是他们并不是最理想的，因为他们在获得传感器收集到的信息后并没有得到最低成本路径，并且假设所有已知的先验信息是正确的。通过从已知的地图信息计算最佳路径可以得到最佳行为，沿着路径移动机器人，直到它到达目标或其传感器检测到地图和环境之间的差异，更新地图，然后重新规划一条从机器人现在位置到到目标的最优路径。尽管这种强力的，重新规划路径的方法是最佳的，但是他可能效率极低，特别是在目标很远并且存在很少地图信息的广阔环境中。Zelinsky [15]通过使用四叉树[13]来表示自由和障碍空间来增加效率，从而减少了在规划空间中搜索的状态数。然而，对于自然地形，地图可以编码机器人在连续区间上的每个位置的的遍历可行性，从而使四叉树不合适或不理想。

本文提出了一种新的算法，用于为使用传感器和环境地图操作的机器人生成最佳路径。地图可以是完整的，空的，或包含有关环境的部分信息。对于未知的环境区域，地图可能包含近似信息，占用的随机模型，甚至是启发式估计。该算法与野蛮的重新规划算法有相同的功能，但效率更高。

该算法是根据有向图中的最优寻径问题来表示的，其中弧被标记为在一个连续范围内的成本值。机器人的传感器能够测量机器人附近的弧成本，已知的和估计的弧成本组成地图。因此该算法可以用于各种规划表示，包括可见性图[5]和网格单元结构。本文描述了这种算法算法，说明了它的操作，提出了其健全性，最优性和完整性的非正式证明，然后对该算法与最优重规划算法进行了实证比较。

2.0 D*算法

之所以选择该算法的名称D*，是因为它类似于A*[8]，只是在解决问题过程中，弧成本参数会发生改变的情况下，该算法是动态的。假设机器人的运动与算法适当耦合，D*算法生成最优路径。本节从算法中使用的定义和符号开始，介绍D*算法，并以其操作的说明结束。

2.1 定义

路径规划者的目标是让机器人从世界上的某个地点移动到目标地点，例如

它避开了所有的障碍，并且最大限度地降低正成本度量（例如，遍历的长度）。问题空间可以由显示机器人位置，由定向弧连接的一组状态来表示，每个弧都有一个相应的成本。机器人从特定的状态开始跨越弧线（产生遍历的成本）移动到其他状态直到达到目标状态，用G表示。除G之外的每个状态X都具有到下一个状态Y的后向指针，用b（X）= Y表示。D*算法使用反向指针来表示通往目标的路径。从状态Y到状态X遍历弧的成本是由弧成本函数c（X，Y）给出的正数。如果Y没有到X的弧，那么c（X，Y）是未定义的。如果定义了c（X，Y）或c（Y，X），则空间中的两个状态x和y是相邻的。

像A*算法一样，D*算法维护一个OPEN状态列表。OPEN列表用于将有关更改的信息传递到弧成本函数，并计算空间中状态的路径成本。每个状态X都有一个关联的标记t（X），这样如果X从未在OPEN列表中t（X）=NEW，如果X当前在OPEN列表中t（X）=OPEN，如果X不再出现在OPEN列表中t（X）=CLOSED。对于每个状态，D *算法保持由路径成本函数h（G，X）给出的从X到G的弧成本之和的估计值。在适当的条件下，该估计值等价于由隐函数o（G，X）给出的从状态X到G的最优（最小）代价。对于OPEN列表中的每个状态x（即t（x）=OPEN），由于X被放置在OPEN列表中，关键函数k（G，X）被定义为等于修改前的h（G，X）的最小值，以及h（g，x）假设的所有值。关键函数将OPEN列表中的状态X分为以下两种类型之一：如果k（G，X）lt;h（G，X）则为RAISE状态，如果k（G，X）= h（G，X）则为LOWER状态。D *算法使用OPEN列表上的RAISE状态来传播关于路径成本增加的信息（例如，由于增加了弧成本）和LOWER状态以传播关于路径成本降低的信息（例如，由于降低了弧成本或者到目标的新路径）。传播是通过重复地从OPEN列表中删除状态来进行的。每次从列表中删除状态时，它都会扩展为将成本更改传递给其邻居。这些邻居依次被放在OPEN列表中以继续该过程。

OPEN列表中的状态按其关键函数值排序。参数kmin被定义为令t(X) =OPEN的所有X的最小k(X)值。参数kmin表示D *算法中的重要阈值：路径成本小于或等于kmin的是最优的，而大于kmin的那些可能不是最佳的。参数kold被定义为等价于最近一次从OPEN列表中删除状态之前的kmin。如果未删除任何状态，则kold未定义。

如果对于所有满足1le;i lt; N的i，b(Xi 1) = Xi，并且对于所有满足1 le;i lt; j le; N的（i，j），Xi ne; Xj，则将{X1，XN}表示的状态的排序定义为序列。因此，序列定义了从XN到X1的后向指针的路径。

对于所有满足1le;i lt; N的i，若t（Xi） ＝CLOSED且h（G，Xi）lt;h（G，Xi 1））或者t（Xi）＝OPEN且k（G，Xi）＜h（G，Xi 1）），则序列{X1，XN}被定义为单调的。D *算法构造并保持一个单调序列{G，X}，表示对于在或不在OPEN列表上的每个状态X，减少当前或下限路径成本。给定状态序列{X1，XN }，如果1le;ilt;jle;N则状态Xi是状态Xj的祖先，如果1le;jlt;ile;N则状态Xi是Xj的子孙。

对于涉及目标状态的所有双态函数，使用以下简写符号：f（X）equiv;f（G，X）。同样，对于序列，使用记法{X}equiv;{G，X}。符号 f（°）用于表示独立于其域的函数。

2.2 算法描述

D *算法主要由两个函数组成：PROCESS-STATE和MODIFY-COST。PROCESS-STATE用于计算到目标的最优路径成本，MODIFY-COST用于更改弧成本函数c（°）并在OPEN列表中输入受影响的状态。在初始时，所有state的t（Tag）被设置为 New，h(G)被设置为0,G被放置于OPEN列表中。然后Process-State函数被不断执行，直到机器人所处state X由OPEN列表中出队（即，t（X）= CLOSED）或返回值-1，此时序列{X}已分别计算或不存在。然后机器人继续跟随序列{X}中的后向指针，直到它到达目标或发现弧成本函数c（°）中的误差（例如，由于检测到的障碍物）。当移动过程中发现新探测到的障碍时MODIFY-COST函数立刻被调用，来更正C（°）中的路径开销并将受影响的状态重新置于OPEN列表中。令Y表示机器人发现障碍时所在的状态。通过不断调用PROCESS-STATE函数直到k_minge;H（Y），表示路径开销的更改已经传播到了Y，使得h（Y）= o（Y）。此时，一个可能的新序列{Y}已经构建，并且机器人继续沿着序列中的后退指针朝向目标前进。

PROCESS-STATE和MODIFY-COST算法如下所示。嵌入式程序是MIN-STATE，它返回OPEN列表中k（°）值最小的状态（如果列表为空，则为NULL）；GET- KMIN，返回列表的最小K值（如果列表为空，则返回-1）；DELETE（X），它从OPEN列表中删除状态X并设置t（X）= CLOSED；INSERT（X，hnew），计算

k（X）= hnew。如果t(X) = NEW，则k(X) = min(k(x),hnew)。如果t(X)=OPEN，则k(X) = min(h(X),hnew)。如果t(X) = CLOSED，设置h (X)= hnew和t（X）= OPEN，并按k（°）排序放置或重新定位OPEN列表中的状态X。

在PROCESS-STATE函数L1-L3中，拥有最低K值的X由OPEN列表中移出。如果X为Lower（即k(X) = h(X)），那么将原来的最小K值赋给h(X)后它的路径代价为最优的。在L8-L13，X的所有邻接状态Y都被检测是否其路径代价可以更低。状态为New的邻接状态被赋予初始路径开销值，并且开销的变动被传播给每一个反向指针指向X的邻接状态 Y（不管这个新的开销比原开销大或者小）。由于这些状态是X的后代，因此对X的路径成本的任何改变也会影响它们的路径成本。 Y的反向指针被重定向（如果需要），以便构造单调序列{Y}。所有路径开销有所变动的邻接状态都被置于OPEN列表中进行处理，从而将变动传播给邻接的状态。

如果X为RAISE，它的路径开销可能不是最优的，在X将成本变化传播到其邻接节点之前，在L4-L7中，通过其邻接状态中已经处于最优开销（即h（Y）le;k_old）的节点来优化X的路径开销。在L15-L18中，开销变化以与LOWER状态相同的方式传播到NEW状态和直接后代。如果能够降低不是直接后代的状态的路径成本（行L20和L21），则将X放回到OPEN列表以供将来扩展。需要执行下一节中显示的操作来避免反向指针中出现闭环。在L23-25中，如果X可以通过一个状态为CLOSED的并不是最理想的邻接状态Y来减小路径开销，那么将Y重新置于OPEN列表中。因此，更新被“推迟”直到邻接状态具有最佳路径成本。

函数：PROCESS-STATE（）

L1 X = MIN – STATE ( )

L2 if X = NULL then return -1

L3 kold = GET – KMIN( );DELETE(X)

L4 if koldlt;h(X) then

L5 for each neighbor Y of X:

L6 if h(X) le;kold and h(X)gt;h(Y) c(Y,X) then

L7 b(X) = Y; h(X) = h(Y) c(Y,X)

L8 if kold = h(X) then

L9 for each neighbor Y of X:

L10 if t(Y) = NEW or

L11 (b(Y) = X and h(Y) ne; h(X) c(X,Y)) or

L12 (b(Y) ne; X and h(Y) gt; h(X) c(X,Y)) then

L13 b(Y) = X;INSERT(Y,h(X) c(X,Y))

L14 else

L15 for each neighbor Y of X:

L16 if t(Y) = NEW or

L17 (b(Y) = X and h(Y) ne; h(X) c(X,Y)) or

L18 b(Y) = X;INSERT(Y,h(X) c(X,Y))

L19 else

L20 if b(Y) ne;X and h(Y) gt;h(X) c(X,Y) then

L21 INSERT(X,h(X))

L22 else

L23 if b(Y) ne; X and h(X) gt; h(Y) c(Y,X) and

L24 t(Y) = CLOSED and h(Y) gt; kold then

L25 INSERT(Y,h(

资料编号：[5010]