基于搜索的算法：D*算法原理及代码

本文主要是介绍基于搜索的算法：D*算法原理及代码，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• • 一、基本知识
  • • 1、概述
    • 2、符号定义
  • 二、算法流程
  • • 1、主要流程：
    • 2、伪代码：
    • 3、流程理解：
  • 三、代码实现

一、基本知识

1、概述

A*在静态路网非常有效，但不适用在动态路网，环境如权重等不断变化的动态环境下。

D*是一种启发式的路径搜索算法，是火星探测器采用的寻路算法，适合面对周围环境未知或者周围环境存在动态变化的场景。

2、符号定义

（1） D *维护要评估的节点列表，称为“OPEN list”。G表示终点,两个点的记号中会省略。
c(X，Y): x和y的cost。

（2） t(x)表示x的状态，包括：
NEW：它从未被列入OPEN list
OPEN：当前在OPEN list中
CLOSED：已经从OPEN list中剔除

（3） D*的估计函数包括h(G,X)和k(G,X)：h函数会随着拓扑结构的变化而变化，key始终是h中最小的那一个。

Kmin：当前OPEN中key的最小值
Kold：上一次的最小值

OPEN的节点分为两类：
RAISE：它的成本比上次OPEN list时要高
LOWER：它的成本比上次OPEN list时要低

二、算法流程

1、主要流程：

D*主要包括两个部分：
PROCESS-STATE: 计算终点到当前节点的最优cost.
MODIFY-COST: 用来修正cost。
具体如下：
(1) 将所有节点的tag设置为NEW,h(G)设为0，将G放置在OPEN中。
（2）循环，直到当前的节点X从OPEN中移除，表示找到了一条从X出发到达终点的路径。
（3）根据获得的路径，从节点X往后移动，直到达到终点或者检测到cost发生变化。
（4）当cost发生变化时，调用MODIFY-COST，并将因为障碍物而cost受到影响的节点重新放入OPEN中。
假设Y是发现状态时机器人所处的节点。通过调用PROCESS−STATE直到kmin ≥ h(Y), 此时cost的变化已经传播到Y，因此可以找到一条新的从Y到终点的最优路径。

2、伪代码：

文末参考论文中伪代码如下：

3、流程理解：

（1） MIN -STATE: 返回的是最小的k值的节点。
GET - MIN: 返回Kmin。
INSERT(X, hnew)分为三种情况：
a）t(X)=NEW，k(X) = hnew
b）t(X)=OPEN，k(X)=min(k(X)，hnew）
c） t(X)=CLOSED，k(X)=min(h(X),hnew),h(X)=hnew
and t(X)=OPEN
最后一个条件就是针对已规划路径cost发生变化的状态。
（2）
1）在静态条件下，利用Dijkstra或A*算法找到一条最优路径，同时利用后向指针确定每个节点的下一节点。
2）机器人从起点出发，沿路径移动，考虑最简单的情况，假设机器人的传感器范围为1，也就是说，只要下一个节点没有障碍物，就移动到下一个节点。
3）假设下一节点出现障碍物，可以认为hnew=∞，也就是说，这时k仍是无障碍时的值，而h hh已经变成无穷了，并且，X被重新放入OPEN中。

三、代码实现

c++代码实现链接

参考论文
《Optimal and Efficient Path Planning for Partially-Known Environments》
参考链接
算法原理和变体
流程理解和伪代码

这篇关于基于搜索的算法：D*算法原理及代码的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！