D*-Lite算法

Question

我正在尝试实现D*-Lite寻路算法,如Koenig和Likhachev在2002年的文章中描述的Boost :: Graph.我认为我已经掌握了它背后的基本思想和理论,但是在理解Pred和Succ更新集合时我遇到了问题.

我猜它是在这Move to sstart一步中发生的Main,但是第一次调用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();

Answer 1

事实证明我对基本思想和理论没有很好的掌握......我误解了"继承者"和"前任"的含义,因为我认为它的意思是"按路径顺序",所以在路径中v0->v1->v2,v0将是前任v1和v2继任者.

然而,这意味着只是邻居.前一个集合是所有顶点的集合,其具有到给定顶点的"边缘",并且后继者具有"外边缘".