有链接到d*一些文件在这里,但他们有点太数学对我来说.有没有关于D*/D*Lite的信息更适合初学者？
我正在尝试实现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’} …我希望处理的大型网络(小世界图形类型)本质上是动态的,经常添加和减去新节点.大概在A*上使用D*是检测这个动态环境中路径的更好方法吗？
D*有多坚固？它有任何现实世界的经验吗？像加密算法一样 - 是否通过大量的同行评审和测试来强化？你会用D*来解决这个问题吗？
我的A*实现适用于我的静态环境.如果我现在想要使用动态环境,即当我们从开始到结束时,我的节点之间的某些成本会发生变化.
从我的阅读到目前为止,我已经找到了可以帮助我的LPA*,D*和D*Lite算法.那么我最糟糕的情况就是实现所有并看看最有效的方法.
有没有研究比较这些算法的功能？ 到目前为止我读过的论文只关注一个算法,由于他们的实验环境不同,很难进行比较.
**一些背景信息:我正在使用C++,我的环境是一个3d场景,我的搜索图表使用navmeshes表示.
我正在实现一个模拟,需要我进行一些寻路.
当我的环境没有变化时,A*对我来说很好.
当我遇到不在原始地图中的静态障碍物时,LPA*和D*Lite对我来说很好.
但是,当这些障碍物以一定速度移动时,我该如何处理这种情况呢？
是否有LPA*或D*Lite算法的变体可以处理这个问题？
或者我是否必须将某种形式的转向行为与这些算法结合起来？
在我的模拟中,我希望让我的"代理人"从一个起点到一个终点,在一个会有障碍移动的环境中.
我已经实现了D*-Lite算法(这里是一个描述,当边缘成本随时间变化时,它是一个用于进行寻路的算法),但是我在进行边缘成本更新方面遇到了问题.它主要起作用,但有时会卡在一个循环中,在两个顶点之间来回传递.我正在尝试创建一个展示此行为的测试用例,目前在大型应用程序中使用时会出现这种情况,这使得调试变得困难.
我会尽快得到一个测试用例,但也许有人可以发现我从错误到C++的错误.(下面有一个测试用例)本文介绍了一个优化版本,图4,这是我实现的版本.伪代码粘贴在下面.
我的实施来源可以在这里找到.
如果它有帮助,我在我的代码中使用这些类型:
struct VertexProperties { double x, y; };
typedef boost::adjacency_list<boost::vecS,
boost::vecS,
boost::undirectedS,
VertexProperties,
boost::property<boost::edge_weight_t, double> > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef DStarEuclidianHeuristic<Graph, Vertex> Heuristic;
typedef DStarPathfinder<Graph, Heuristic> DStarPathfinder;
如果需要更多关于使用的信息,请问,粘贴太多了.
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, …