2

对于一个机器人项目，我一直在使用我想使用Koenig，2002 年论文中的D Lite（优化版） * 来为不断变化的占用网格/成本图进行动态路径规划。如本文所述，D* Lite 搜索算法的思想是，它基本上通过从目标开始反向运行 A* 搜索并尝试回到起点来工作。然后求解器给出当前的解决方案并等待它所呈现的权重或障碍的某种变化。与重复的 A* 搜索相反，D* Lite 算法避免从头开始重新规划并逐步修复路径，使其修改保持在机器人姿态附近。

我的问题

我已经在 python 中实现了该算法，并在 pygame 中进行了模拟以测试性能。但我有一个与伪代码有关的问题。我已经实现了优化版和非优化版的算法，现在已经执行了 3 次了，我仍然得到一个错误，即当算法遇到一些配置的障碍物（十字形或大的垂直障碍物）时，算法会突然卡在一个while 循环内部的无限循环（Procedure Main，第 32 行伪代码），并在顶点 s_start 的两个选项之间来回切换（Procedure Main，第 34 行）。我现在已经将我的 python 实现与伪代码进行了多次比较，但我找不到任何可能导致此错误的伪代码偏差。

我的临时“修复”

现在，为了避免算法陷入无限循环，我在 Procedure Main() 的第 48 行将computeShortestPath()缩进了左侧一个，这样我就超出了Procedure Main() 第 37 行的if范围.

当我这样做时，算法几乎总是能够在发现路径中的新障碍时计算出新的最短路径。

我的问题

  1. 首先，任何人都知道为什么算法有时会陷入无限的while循环以及如何解决它？

  2. 我想我的临时“修复”将再次认为该算法的计算成本更高，因此 D* Lite 算法的许多目的现在已经不复存在。我的缩进修复与原始算法的计算复杂度是多少？

  3. 现在有了我的临时修复，与动态 A* 相比，代码实际上在计算方面是否有任何不同，在动态 A* 中，每次必须重新规划新路径时都重新计算所有内容？

  4. 有时，当遇到大量复杂的迷宫时，需要对新顶点进行大量探索，我的“临时固定”代码有时会变得有点慢。但是，即使在原始代码中也不会在某种程度上发生这种情况吗？

我的实现

如果你想自己运行代码并体验算法，你可以在这里运行 python main.py来测试我的实现。

这个特定的实现包括我的“临时修复”。但是，如果您想在没有的情况下体验它，可以转到 d_star_lite.py 中的第 156 行并将 compute_shortest_path() 向右缩进一个，以便它进入第 132 行的“if”内。

伪代码

这是 D* Lite（优化版）算法的原始伪代码。

procedure CalculateKey(s)
{01”} return [min(g(s), rhs(s)) + h(s_start, 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(s_goal) = 0;
{06”} U.Insert(s_goal, [h(s_start, s_goal); 0]);

procedure UpdateVertex(u)
{07”} if (g(u) != rhs(u) AND u ∈ U) U.Update(u,CalculateKey(u));
{08”} else if (g(u) != rhs(u) AND u /∈ U) U.Insert(u,CalculateKey(u));
{09”} else if (g(u) = rhs(u) AND u ∈ U) U.Remove(u);

procedure ComputeShortestPath()
{10”} while (U.TopKey() < CalculateKey(s_start) OR rhs(s_start) > g(s_start))
{11”} u = U.Top();
{12”} k_old = U.TopKey();
{13”} k_new = CalculateKey(u));
{14”} if(k_old < k_new)
{15”}   U.Update(u, k_new);
{16”} else if (g(u) > rhs(u))
{17”}   g(u) = rhs(u);
{18”}   U.Remove(u);
{19”}   for all s ∈ Pred(u)
{20”}   if (s != s_goal) rhs(s) = min(rhs(s), c(s, u) + g(u));
{21”}   UpdateVertex(s);
{22”} else
{23”}   g_old = g(u);
{24”}   g(u) = ∞;
{25”}   for all s ∈ Pred(u) ∪ {u}
{26”}   if (rhs(s) = c(s, u) + g_old)
{27”}     if (s != s_goal) rhs(s) = min s'∈Succ(s)(c(s, s') + g(s'));
{28”}   UpdateVertex(s);

procedure Main()
{29”} s_last = s_start;
{30”} Initialize();
{31”} ComputeShortestPath();
{32”} while (s_start != s_goal)
{33”} /* if (g(s_start) = ∞) then there is no known path */
{34”}   s_start = argmin s'∈Succ(s_start)(c(s_start, s') + g(s'));   <--- ** jumps between two solutions of s_start**
{35”}   Move to s_start;
{36”}   Scan graph for changed edge costs;
{37”}   if any edge costs changed         <--- ** this if ****
{38”}     km = km + h(s_last, s_start);
{39”}     s_last = s_start;
{40”}     for all directed edges (u, v) with changed edge costs
{41”}       c_old = c(u, v);
{42”}       Update the edge cost c(u, v);
{43”}       if (c_old > c(u, v))
{44”}         if (u != s_goal) rhs(u) = min(rhs(u), c(u, v) + g(v));
{45”}       else if (rhs(u) = c_old + g(v))
{46”}         if (u != s_goal) rhs(u) = min s'∈Succ(u)(c(u, s') + g(s'));
{47”}       UpdateVertex(u);
{48”}     ComputeShortestPath()  <--- ** this calculation **
4

0 回答 0