2008-01-30

火星上的D-Star算法（定义）

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

听闻D*算法是美国火星探测器使用的寻路算法，听起来挺炫，挺洋气的，标题也因此而得名。同时也忍不住在网上搜了搜，找到以下参考资料以及里面提到的两篇论文：

http://www.embhelp.com/drew/algorithm/shortpath.htm

Optimal and Efficient Path Planning for Partially-Known Environments

The Focussed D* Algorithm for Real-Time Replanning

不过感觉Drew讲得不够详细，不够过瘾；因此把两篇论文啃了一遍，将学习到的知识与大家一起分享和讨论。为了方便大家对照阅读，我会尽可能的按照论文的顺序和其中术语来阐述该算法。

在讲具体算法逻辑之前，本节还是先讲讲其中用到的一些概念和定义，这样之后的内容比较好理解。下面就开始介绍这些概念：

  • state：将空间（地图）分隔成若干个节点，每个节点记着一个state，它有三个状态NEW，OPEN和CLOSED，等会讲tag时再对这几个状态做说明
  • directional arc：连接两个state之间的directional arc，也就是通过这个directional arc，可以从一个state到达另一个state
  • backpointer：除去目标state外的任意state X都有一个backpointer，使之能到达另一个state Y，既b(X) = Y；D*算法也正是使用这一系列的backpointers来描述到达目的点的路径
  • arc cost：state Y通过directional arc到达state X的所需的成本，记着c(X,Y)；这个概念类似于权值。如果c(X,Y)无法定义，则说明state Y没有指向X的 arc；当c(X,Y)和c(Y,X)均能定义，则说明X和Y在空间上是相邻的
  • OPEN list：D*算法里也有一个OPEN列表来记录states（这个与A*类似）；它用于在arc cost函数变化时传递信息和计算state的路径价值
  • tag：每个state都有一个标记（前面讲state时提到的状态），当state为NEW时，表明该state从未在OPEN列表中；如果state为OPEN，该state正在OPEN列表中；而当state为CLOSED时，则说明该state不会在OPEN列表中存在
  • path cost：D*通过h(G, X)函数来估计任意点X到目标点G的arc cost总和，这个Heuristics函数与A*算法里的h函数功能相似
  • optimal cost：在适当的条件下，该隐式函数能估计出从任意点X到目标点G的最佳路径
  • key function：当X在OPEN列表中，并且所有点都未变动并通过h(G, X)进行的估计的前提下，k(G, X)等于h(G, X)的最小值，根据该函数值的不同，可以将X state分为两类：当k(G, X)<h(G, X)时，称为RAISE state，而当k(G, X)=h(G, X)时，为LOWER state
  • kmin：保存OPEN列表中，k(G, X)最小的state值
  • kold：保存最近一次被移出的state，如果state从未被移出，则kold未定义
  • sequence：如果一组有序的states，记着{X1, XN}，当它满足b(Xi+1) = Xi (1≤i≤N)时，则认为这组states为一个sequence
  • monotonicity：如果一个sequence满足(t(Xi)=CLOSED and h(G, Xi) < h(G, Xi+1)) or (t(Xi)=OPEN and k(G, Xi) < h(G, Xi+1))，则认为该sequence具备单调性
  • notation：f(X)≡f (G, X), {X}≡{G, X}, f(°)表示该函数功能不依赖于它的范围，即对所有state都适用

D*里主要的概念和定义也就是这些了，了解了这些才能更好的理解下一节讲的算法描述，如果觉得以上定义存在偏差，请与我联系，很高兴与大家一起讨论。

评论
发表评论

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

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