中写了D*规划算法主要流程，但是过于抽象，本文从具体的例子一步步分析D*算法，文中用到的表达符号在前文中都有描述，如果不明白可以参阅前文。

D*规划算法调用流程

整体的D*规划算法调用流程大致如下:

核心的流程

1) k(X): Open表中State的优先级；

2) LOWER state

– k(X) = h(X)
– Propagate information about path cost reductions (e.g. due to a reduced arc cost or new path to the goal) to its neighbors
– For each neighbor Y of X
if t(Y) = NEW or h(Y) > h(X) + c(X,Y) then
• Set h(Y) := h(X) + c(X,Y)
• Set b(Y) = X
• Insert Y into an OPEN list with k(Y) = h(Y) so that it can propagate cost changes to its neighbors

3) RAISE state

– k(X) < h(X)
– Propagate information about path cost increases (e.g. due to an increased arc cost) to its neighbors
– For each neighbor Y of a RAISE state X,
 • If t(Y) = NEW or (b(Y) = X and h(Y) ≠ h(X) + c(X,Y)) then insert Y into the OPEN list with k(Y) = h(X)+c(X,Y)
 • Else if (b(Y) ≠ X and h(Y) > h(X) + c(X,Y)) then insert X into the OPEN list with k(X) = h(X)
 • Else if (b(Y) ≠ X and h(X) > h(Y) + c(X,Y)) then insert Y into the OPEN list with k(Y) = h(Y)

D*规划算法示例

步骤一：机器人能够向8个方向移动。

步骤二: 地图如下图所示，所有的State初始化为NEW，k和h的大小用栅格地图的距离度量。

步骤三：将目标节点(7,6)加入到Open表中，h(goal)=0，k(goal)=0。

步骤四：将目标节点(7,6)从Open表中取出，遍历其Neighbor节点 (6,6), (6,5), (7,5)，并把它们加入到Open表。

对应的代码如下:

步骤五：扩展节点(6,6)，将(5,6)和(5,5)放到Open表中。

步骤六：扩展(7,5)，把(6,4)和(7,4)加入到Open表中。

步骤七： 扩展(4,6)，把(3,5)和(3,6)加入到Open表。

步骤八：扩展到起点s时，搜索结束。此时Open表中仍然有元素，并且地图中仍然存在未遍历的节点。

步骤九：路径追溯，获取目标路径。