Dstar算法

D*算法D*是动态A*（D-Star,DynamicA*）卡内及梅隆机器人中心的Stentz在1994和1995年两篇文章提出，主要用于机器人探路。是火星探测器采用的寻路算法。主要方法：1.先用Dijstra算法从目标节点G向起始节点搜索。储存路网中目标点到各个节点的最短路和该位置到目标点的实际值h,k（k为所有变化h之中最小的值,当前为k=h。每个节点包含上一节点到目标点的最短路信息1(2),2(5),5(4)，4（7）。则1到4的最短路为1-2-5-4。原OPEN和CLOSE中节点信息保存。2.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用上一步Dijstra计算出的最短路信息从出发点向后追述即可，当在Y点探测到下一节点X状态发生改变，如堵塞。机器人首先调整自己在当前位置Y到目标点G的实际值h(Y)，h(Y)=X到Y的新权值c(X,Y)+X的原实际值h(X).X为下一节点(到目标点方向Y-X-G），Y是当前点。k值取h值变化前后的最小。3.用A*或其它算法计算，这里假设用A*算法,遍历Y的子节点，点放入CLOSE,调整Y的子节点a的h值，h(a)=h(Y)+Y到子节点a的权重C(Y,a),比较a点是否存在于OPEN和CLOSE中，方法如下：while(){从OPEN表中取k值最小的节点Y;遍历Y的子节点a,计算a的h值h(a)=h(Y)+Y到子节点a的权重C(Y,a){if(ainOPEN)比较两个a的h值if(a的h值小于OPEN表a的h值){更新OPEN表中a的h值;k值取最小的h值有未受影响的最短路经存在break;}if(ainCLOSE)比较两个a的h值//注意是同一个节点的两个不同路径的估价值if(a的h值小于CLOSE表的h值){更新CLOSE表中a的h值;k值取最小的h值;将a节点放入OPEN表有未受影响的最短路经存在break;}if(anotinboth)将a插入OPEN表中;//还没有排序}放Y到CLOSE表；OPEN表比较k值大小进行排序；}机器人利用第一步Dijstra计算出的最短路信息从a点到目标点的最短路经进行。D*算法在动态环境中寻路非常有效，向目标点移动中，只检查最短路径上下一节点或临近节点的变化情况，如机器人寻路等情况。对于距离远的最短路径上发生的变化，则感觉不太适用。