38

这里有一些关于 D* 的论文的链接，但它们对我来说有点过于数学化了。有没有关于 D*/D* Lite 更适合初学者的信息？

4

7 回答 7

15

维基百科有一篇关于这个主题的文章：http ://en.wikipedia.org/wiki/D*

Sven Koenig 的页面还提供了 C 中的 D* Lite 实现：http: //idm-lab.org/code/dstarlite.tar但是我发现难以理解的数学比 C 源代码更容易阅读；-)

D* Lite（在 C++ 中）的另一种实现可在此处获得：http ://code.google.com/p/dstarlite/

于 2010-07-28T21:12:52.523 回答
13

好吧，如果伪代码对您来说很难（您不必阅读定理和证明 - 如果您知道标准算法，伪代码非常简单）并且您抱怨已发布的 C 和 C++ 代码，那么我想您需要去做其他事情:-)

说真的，不要指望有人可以在几个网页段落中教你一个顶级算法。拿起笔和纸，在纸上写字、画图并跟踪正在发生的事情。您可能需要阅读两遍内容并在谷歌上搜索一两个参考文献才能了解它周围的一些概念，并且根本不需要深入研究定理和证明 - 除非您希望证明作者是错误的 :-) )

没有更多的数学就无法前进-c'est la vie。想象一下，您请某人教您到底什么是矩阵求逆，但您不知道什么是向量。在您首先了解足够的数学上下文之前，没有人可以帮助您。

于 2010-07-29T14:31:42.843 回答
13

话虽如此，为什么不添加更多论文，是的，他们也有数学：-) 但我会尝试获取一些更新的东西。随着时间的推移，人们通常会更好地解释自己的工作，因此重点是 Stentz、Likhachev 和 Koenig

于 2010-07-30T00:23:51.737 回答
8

D* Lite 外行解释

StartD* 从和之间的乌鸦式理想路径开始Goal；它仅在遇到障碍物时处理障碍物（通常通过移动到相邻节点）。也就是说 - D* Lite 在开始沿着理想路径前进之前不知道任何障碍。

任何寻路实现的圣杯是在获得最短路径或至少是一条体面的路径的同时使其快速（以及处理[这里的所有各种特殊条件 - 对于 D* Lite，这是将未知地图作为火星探测器可能会]）。

因此，D* Lite 面临的一大挑战是在遇到障碍时廉价地适应障碍。找到它们很容易——您只需在移动时检查邻居的节点状态。但是我们如何在不遍历每个节点的情况下调整现有地图的成本估算……这可能会非常昂贵？

LPA* 使用了一个巧妙的技巧来调整成本，这是 D* Lite 充分利用的技巧。当前节点问它的邻居：你最了解我，你认为我对自己很现实吗？具体来说，它询问它的g值，即从初始节点到其自身（即当前节点）的已知成本。邻居查看他们自己的g，查看当前节点与他们相关的位置，然后提供他们认为其成本应该是多少的估计值。这些报价的最小值被设置为当前节点的rhs值，然后用于更新其g值；在估计时，邻居会考虑新发现的障碍物（或自由空间），这样当当前更新g使用rhs，它会考虑新的障碍物（或自由空间）。

当然，一旦我们g全面掌握了现实的价值观，就会出现一条新的最短路径。

于 2016-02-05T10:06:11.650 回答
2

D* 与 D* Lite： 首先，D*-Lite 被认为比 D* 简单得多，而且由于它的运行速度至少与 D* 一样快，因此它已经完全淘汰了 D*。因此，没有任何理由使用 D*；改用 D*-Lite。

D* Lite vs A*： D* Lite 算法的工作原理是从目标开始反向运行 A* 搜索并尝试回到起点。然后求解器给出当前的解决方案并等待它所呈现的权重或障碍的某种变化。与重复的 A* 搜索相反，D* Lite 算法避免从头开始重新规划并逐步修复路径，使其修改保持在机器人姿态附近。

如果你想真正理解算法。我建议您首先阅读 A* 的伪代码并实现它。首先尝试了解如何从堆队列中提取和插入，以及算法如何使用另一种启发式而不是常规的 Dijkstra 算法，以及为什么与 Dijkstra 相比，它允许算法探索更少的顶点。

一旦你觉得你掌握了 A* 的工作原理（你也应该实现它），那么我建议你再看看Koenig，2002。我建议您首先开始查看常规的 D*-Lite 伪代码。确保你理解每一行代码。

优先队列的概念

  • 'U' 是您想要堆叠未探索顶点的优先级队列。
  • 'U' 具有 (key, value) 的元素，其中 key 是您的顶点，而 value 是 value = [k1, k2] = calculateKey 的结果，表示键（表示顶点）的优先级应该是什么。现在您的优先级队列使用 a。
  • 'U.Top()' 返回优先级队列 U 中所有顶点中优先级最小的顶点。
  • 'U.TopKey()' 返回先前所有顶点的最小优先级。
  • 'U.Pop' 删除优先级队列 U 中优先级最小的顶点并返回该顶点。
  • 'U.Insert()' 以优先级将顶点插入优先级队列 U。
  • 'U.Update()' 将优先级队列 U 中顶点的优先级更改为。

执行

我已经在 python 中实现了 Optimized D*-Lite 算法（在此处查看此线程）。我建议您将代码和伪代码并排阅读。如果您愿意，那里也有测试模拟的说明。

于 2020-04-29T11:24:06.773 回答
1

我想出了这个
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf和这个
http://www.cs.cmu.edu/~maxim/files/dlitemap_iros02.pdf http:// www.cs.cmu.edu/~maxim/files/dlite_icra02.pdf - 有 2 个版本的 D*

http://www.cs.cmu.edu/~maxim/files/dlite_tro05.pdf - icra02 的完善版

https://www.cs.cmu.edu/~maxim/files/rstar_aaai08.pdf - R* - 随机化以降低计算成本

http://www.cs.cmu.edu/~maxim/files/rstar_proofs34.pdf - 修改后的 R* http://www.cs.unh.edu/~ruml/papers/f-biased-socs-12.pdf - 实时 R* + PLRTA*

我希望这些链接对您有所帮助:)
编辑：发布后我注意到我给您的链接也在您指出的链接中。尽管如此，我还是直接在谷歌上找到了这些。无论如何，我已经查了一下它们，它们似乎并不那么复杂。如果你很了解 A*，你也应该设法理解 D*。
根据经验，我可以告诉你，A* 也可以用于你想要的。

于 2010-07-27T13:44:56.907 回答
0

Maxim Likhachev 的 CMU 课堂笔记内容丰富。它包含一个如何传播图表上发生的动态变化的示例。还解释了一致性不足的概念，这对于理解算法非常重要。 http://www.cs.cmu.edu/~maxim/classes/robotplanning_grad/lectures/execanytimeincsearch_16782_fall18.pdf

于 2018-11-21T04:50:39.907 回答