D*-Lite算法

Question

我正在尝试实现D*-Lite路径规划算法，参考Koenig和Likhachev在2002年发表的文章2002 article，并将其应用于Boost::Graph。我认为我已经基本掌握了其背后的基本思想和理论，但我不理解何时更新Pred和Succ集合。

我猜这发生在Main中的Move to sstart步骤中，但那么第一次调用ComputeShortestPath就毫无意义了吗？而且Succ集合是否只能与Pred集合同时插入？然后Pred和Succ可以作为双向链表实现吗？

我已经在下面插入了该算法的伪代码。Pred和Succ集合分别是前驱和后继。g，h，rhs和c是不同的成本和权重。 U是要访问的顶点的优先队列。

procedure CalculateKey(s)
{01’} return [min(g(s), rhs(s)) + h(sstart, s) + km; min(g(s), rhs(s))];

procedure Initialize()
{02’} U = ∅;
{03’} km = 0;
{04’} for all s ∈ S rhs(s) = g(s) = ∞;
{05’} rhs(sgoal) = 0;
{06’} U.Insert(sgoal, CalculateKey(sgoal));

procedure UpdateVertex(u)
{07’} if (u ≠ sgoal) rhs(u) = min s'∈Succ(u)(c(u, s') + g(s'));
{08’} if (u ∈ U) U.Remove(u);
{09’} if (g(u) ≠ rhs(u)) U.Insert(u, CalculateKey(u));

procedure ComputeShortestPath()
{10’} while (U.TopKey() < CalculateKey(sstart) OR rhs(sstart) ≠ g(sstart))
{11’}   kold = U.TopKey();
{12’}   u = U.Pop();
{13’}   if (kold ˙<CalculateKey(u))
{14’}     U.Insert(u, CalculateKey(u));
{15’}   else if (g(u) > rhs(u))
{16’}     g(u) = rhs(u);
{17’}     for all s ∈ Pred(u) UpdateVertex(s);
{18’}   else
{19’}     g(u) = ∞;
{20’}     for all s ∈ Pred(u) ∪ {u} UpdateVertex(s);

procedure Main()
{21’} slast = sstart;
{22’} Initialize();
{23’} ComputeShortestPath();
{24’} while (sstart ≠ sgoal)
{25’}   /* if (g(sstart) = ∞) then there is no known path */
{26’}   sstart = argmin s'∈Succ(sstart)(c(sstart, s') + g(s'));
{27’}   Move to sstart;
{28’}   Scan graph for changed edge costs;
{29’}   if any edge costs changed
{30’}     km = km + h(slast, sstart);
{31’}     slast = sstart;
{32’}     for all directed edges (u, v) with changed edge costs
{33’}       Update the edge cost c(u, v);
{34’}       UpdateVertex(u);
{35’}     ComputeShortestPath();

- carlpett

Answer 1

原来我并没有很好地掌握基本思想和理论......我误解了“后继者”和“前任者”的含义，因为我假设它是“按路径顺序”，所以在路径v0->v1->v2中，v0将成为v1的前任者，而v2将成为后继者。

然而，实际上指的只是邻居节点。前任集是所有具有对给定节点的“入边”的节点集，而后继则有“出边”。

- carlpett

Answer 2

阅读LPA*论文，您将了解它们是什么。 基本上，在LPA*中，搜索从起始位置开始。因此，后继节点将是u.Pop节点周围的节点。这意味着它们是从当前节点到达的节点。而Pred，则是一个母节点。这意味着后继节点的前驱是u.Pop。

在DLite中，一切都相反。搜索从目标位置开始。 所以，对您来说有点混乱。 DLite的后继节点是LPA*中的Pred。因此，后继节点=U.pop。 DLite的前驱是LPA*中的后继节点。因此，Pred是您从后继节点到达的节点。

希望您能理解我的糟糕英语。

- Truc Nguyen