2008-02-01

火星上的D-Star算法（描述）

关键字: d*, d-star, algorithm

前一节讲到了D*算法的定义，把D*算法的基本概念掌握了，本节内容是学习D*的算法思想，该算法的核心函数是PROCESS-STATE和MODIFY-COST，其中PROCESS-STATE函数用于计算到达目标state的最佳路径；而MODIFY-COST用于当state改变时，重新计算任意两个state之间的arc cost，以及OPEN列表中受影响的state值。本文也将围绕这两个核心函数进行介绍。

首先，我们了解一下算法初始化操作，该操作分为以下几个步骤完成：

  • 将所有state的tag设置为NEW，即tag(°)=NEW
  • 将所有state的h(G)设置为0
  • 将目标state加入OPEN列表中

完成初始化后，就是重复的PROCESS-STATE函数，该函数的终结点（函数出口）和结果有如下几种：

  • 出发点X从OPEN列表中移出时，即t(X)=CLOSED
  • 如果在某个state返回-1，则说明该state在sequence{X}里已经被计算或该state不可计算

接下来，可以根据上步计算出来的sequence{X}节点间的backpoints，由起始state向目的state进发，不过由于上面的PROCESS-STATE的结果有两种可能，因此按照该方法得出的sequence(X)执行，同样也有两种可能，结果依次如下：

  • 由于之前的PROCESS-STATE是正常状态，因此这里可以正常的到达目标state
  • 第二种情况则会通过c(°)函数发现错误（例如探测到障碍物）

至此，PROCESS-STATE函数的功能和预期结果就讲到这里；下面将会接触另一个核心函数MODIFY-COST，当c(°)函数执行或OPEN列表里的节点受变化而影响时，它才会被调用执行，该函数功能比较简单，就不多提了。

下面我们来看看论文里提到的一个例子，假设到达当前state Y时，通过c(°)发现了错误，则循环调用PROCESS-STATE直到kmin≥h(Y)，这时，会新的一个sequence{Y}被构造完成，则可以通过该sequence由点Y移至目标state。

通过上面的文字，对D*算法的两个核心函数都做了简单的描述，这两个函数的伪码在论文里有，比较好理解，这里也就不贴出来了，也不做过多的说明了。如果觉得比较难懂，可以结合94年论文里的图示来辅助理解。
评论
发表评论

您还没有登录，请登录后发表评论

numenzq
搜索本博客
存档
最新评论