Java教程

基于搜索的算法: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*算法原理及代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!