D* Lite:您可以根据实际机器人位置更改启动节点吗?

Question

我正在阅读这篇关于 D* Lite 的 Koening 和 Likhachev 论文，每次迭代它都会通过遍历到图上的连接节点来更新起始节点。我想知道在现实世界机器人中的使用，机器人可能会超过连接节点并最终到达图形中的不同点。如果您在根据机器人的实际位置自己设置起始节点时保持算法的其余部分不变，D* Lite 是否仍然有效？特别是这两行伪代码可以从论文中摘取

{26’}  s_start = argmin s'∈Succ(s_start)(c(s_start, s') + g(s'));
{27’}  Move to s_start;

成为

       s_start = actual robot location on graph

以下是论文中的完整伪代码：

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

是的，你可以这样做。每次将机器人从一个顶点/网格单元移动到另一个顶点/网格单元时，您都会调用程序 Main(((仅在第一次运行过程 Main 时调用初始化(。设置 sstart = 机器人位置，然后 slast = sstart。现在，该算法将计算从机器人当前位置到目标顶点的最短路径。每次机器人处于接受新网格单元的圈内时，您都必须调用过程 Main((。我自己已经实现了这样的代码。这是我与算法实现相关的堆栈溢出问题。