logo标签列表

我可以帮您翻译成中文：我在哪里可以找到关于D*或D* Lite寻路算法的信息？

algorithmpath-findingd-star
39

这里有一些关于D*的论文（链接在此），但它们对我来说数学内容有点深。是否有更适合初学者的D*/D* Lite信息？

3
您确定您的应用程序不仅需要A算法吗？因为D算法不是初学者所使用的一种算法，而且其使用案例相对较少。请注意，D*算法需要高级编程知识。 - Donnie
2
我需要一个机器人来绕过墙壁到达目标。玩家可以在机器人的路上放置障碍物，机器人应该能够实时找到新的路径。D*算法对于这种动态环境的变化是很好的选择，对吗？ - tehalynn
1
我完全同意。我已经多次实现了A算法，并在各种图形上进行了测试，我也一直想实现D(lite)算法。网络上有两三篇白皮书，但我还没有成功地从那些晦涩难懂的数学描述中获得有用的信息。 - Trillian
3
一旦您实施了它，请编写您正在寻找的教程 :) 就我个人而言，我很想看到它！ - Merlyn Morgan-Graham
1
这对您应该非常相关：http://cstheory.stackexchange.com/questions/11855 - BlueRaja - Danny Pflughoeft
7个回答
15
+1 我自己还没有搜索过，但根据这里的回答和阅读维基百科文章，这似乎是最接近 OP 所需求的东西。 - Merlyn Morgan-Graham
14

话虽如此，为什么不再添加一些论文呢，是的，它们也涉及到数学 :-) 但我会尽力获取更多更新的内容。随着时间的推移，人们通常会更擅长解释自己的工作，因此重点放在Stentz、Likhachev和Koenig身上。

  • Stentz,2007 - Field D* - 声称比D* Lite更好 :-)
  • Stentz,2010 - Imitation Lerning - 主要讨论了如何结合Field D*和LEARCH
  • Ratliff,2009 - LEARCH - 也谈到了如何与Field D*结合 - 是的，这是一个循环引用 :-)
  • Likhachev,2005 - Anytime D* - 与Stentz一起写作
  • Yanyan,2009 - BDD-Based Dynamic A*
  • 科尼希(J. Koenig)，2008年 - 比较实时和增量启发式搜索
    • 谢谢你提供更实用的答案。我之前没有找到大部分这些论文。为了防止你的另一个回答自动获得奖励，我可能会把奖励授予这个答案。毕竟，你的另一个回答更像是一种观点而不是答案，即使它激励我重新深入研究白皮书，只是为了证明我能够做到 :) - Trillian
    如果您想要轻松获取PDF文件，那么您需要在Springer的学术或公司网络上成为“订阅者”。一些作者会在其他期刊上发表略有改动的论文，而有些则不会。这就是为什么我的搜索启发式算法是首先尝试跟踪作者，而Springer网站是快速获取最新信息的简单方法。如果您对此感兴趣，第一个可能甚至值得购买，不仅仅是因为算法，还因为可以阅读Stantz论文，指出他的新算法基于D* Lite——这对于研究人员来说是非常难以承认的事情，即使是含蓄地。 - ZXX
    13

    如果伪代码对你来说很难（如果你知道标准算法，伪代码其实很简单）并且你抱怨发布的 C 和 C++ 代码，那么我想你需要去做一些其他的事情 :-)

    认真点，不要指望有人能在几个网页段落里教你一个高级算法。拿起笔和纸，在纸上写、画和跟随发生的事情。你可能需要读两遍，并谷歌一两个参考资料来了解一些相关概念，根本不需要深入研究定理和证明——除非你希望证明作者是错的 :-))

    没有更多的数学就不能继续往前走 —— 这就是生活。想象一下你让别人教你什么是矩阵求逆，但你不知道什么是向量。如果你不先学习足够的数学背景，没人能帮助你。

    6
    网上有很多关于A算法的清晰解释，所以我很惊讶为什么没有一篇针对D算法的解释，尽管我知道D算法比A算法更为复杂。但我本来期望会有人为非专业人士撰写一个解释。虽然这有些懒惰，但由于找不到合适的答案，我将再次深入研究论文。我只是觉得，数学满满的白皮书并不是开发对算法进行直观理解的最佳方式。 - Trillian
    4
    当你还不了解向量时，询问矩阵求逆之间有一个步骤；而当你已经了解A时，询问D就可以了。 - zneak
    9

    白话解释D* Lite算法

    D* Lite从起点到终点之间采用一条理想的直线路径，没有考虑障碍物（通常通过移动到相邻节点来处理）。也就是说，D* Lite在沿着这条理想路径移动之前，对任何障碍物都没有了解。

    任何路径规划算法的追求都是在获得最短路径或至少是一个合理路径（同时还要处理各种特殊情况——对于D* Lite而言，这就是处理未知地图，就像火星探测器一样）的同时保证其快速性。

    D* Lite面临的其中一个主要挑战是在遇到障碍时便宜地适应它们。找到它们很容易——只需移动时检查相邻节点的状态即可。但是，在不遍历每个节点的情况下如何调整现有地图的成本估计呢？这可能非常耗费时间和资源。

    LPA*使用巧妙的技巧来适应成本，这项技巧被D* Lite充分利用。当前节点会询问其邻居：“你们最了解我，你认为我对自己的实际情况评估准确吗？”具体而言，它询问自己的g值，即从初始节点到当前节点的已知花费。邻居们查看自己的g值，观察当前节点相对于它们的位置，然后给出他们认为应该是其代价的估计值。最小的提供值被设置为当前节点的rhs值，然后用于更新其g值。在估算成本时，邻居们考虑新发现的障碍物（或空闲空间），以便在使用rhs更新g值时将这些因素纳入考虑。

    一旦我们在全局范围内获得了现实的g值，当然就会出现新的最短路径。

    据说D* Lite已经取代了D*，所以我没有在这里包括后者。 - Engineer
    2

    D*与D* Lite: 首先，D* Lite算法比D*算法简单得多，并且由于它始终至少与D*一样快，因此它已经完全取代了D*。因此，没有任何理由使用D*；请改用D* Lite。

    D* Lite与A*： D* Lite算法的工作原理基本上是从目标开始反向运行A*搜索，试图返回起点。然后求解器输出当前解决方案并等待呈现给它的权重或障碍物发生某种变化。与重复的A*搜索不同，D* Lite算法避免了从头开始重新规划路径，并增量修复路径，使其修改局部地围绕机器人姿态。

    如果您真的想了解该算法。我建议您首先阅读A*的伪代码并实现它。首先尝试掌握如何从堆队列中选择和插入，以及算法如何使用另一个启发式而不仅仅是常规Dijkstra算法，以及为什么这允许算法探索较少的顶点而不是Dijkstra。

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

    优先队列概念

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

    实现

    我已经在Python中实现了优化的D* Lite算法（请参见此处的线程）。我建议您将代码和伪代码并排放置并阅读。那里还有测试模拟的说明，如果您愿意可以尝试。

    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 - 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* 也可以用于您想要的目的。

    是的，那些白皮书是我通过谷歌搜索找到的。解释都用了难以理解的数学术语，伪代码也不是很清晰。至于使用A*算法，在我的即时战略游戏中已经有高度优化的实现，但对于如此高动态的世界来说，它还不够快。 - Trillian
    0
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接