当前位置：首页 > article >正文

D*算法学习

article 2024/11/18 8:30:45

系列文章目录

A*算法学习-CSDN博客

弗洛伊德算法（Floyd）和路径平滑弗洛伊德算法（Smooth Floyd）学习-CSDN博客

系列文章目录

前言

一、D*算法是什么？

二、D* 算法是对 A* 算法的改进

三、增量搜索是什么

总结

前言

之前弄了离线的，当然离线的Dijkstra算法没总结，A*算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A*算法中估价值为0的情况。然后今天看了下适合动态的D*算法。

参考资料：

original_dstar_icra94.pdf (mit.edu)

最短路经算法简介(Dijkstra算法，A*算法，D*算法)（转载）_d星算法和dijkstar算法-CSDN博客

D*路径搜索算法原理解析及Python实现_d*算法-CSDN博客

D*算法超详解（D星算法 / Dynamic A*算法/ Dstar算法）(死循环解决--跟其他资料不一样奥)-CSDN博客

D*算法图文详解_d*算法图解_一叶执念的博客-CSDN博客

路径规划五种算法简述及对比 - 知乎 (zhihu.com)

资料好多，主要我感觉都是大家的思考，没有实现（之后可以试试）。

一、D*算法是什么？

D* (D-Star) 算法是一种用于路径规划的增量式搜索算法，它在已知地图上找到从起点到目标的最短路径。与 A* 算法不同，D* 算法具有增量搜索的特性，允许在环境发生变化时更新路径而不必重新计算整个路径。

D* 算法的基本思想是：

初始化： 从目标点开始，向起点搜索，计算每个节点的代价值（g值）。
路径改进： 当环境发生变化，或者机器人移动到新位置时，根据新的代价值信息，以增量方式更新路径。
迭代： 不断迭代，根据新的代价值信息改进路径，直至达到起点。

D* 算法主要包括两个核心函数：

ComputeShortestPath： 从机器人当前位置开始，向目标搜索，并计算每个节点的代价值。
ImprovePath： 根据新的代价值信息，对路径进行增量式的改进。

以下是 D* 算法的一个简化版本的伪代码

function ComputeShortestPath():
    while (有未被探索的节点) {
        选择代价最小的节点 u；
        for (u 的每个邻居节点 v) {
            计算节点 v 的新代价值 g_new；
            如果 g_new 比 v 当前的代价值小，则更新 v 的代价值，并将 v 添加到 OPEN 列表；
        }
    }

function ImprovePath():
    while (机器人移动或环境发生变化) {
        更新机器人的位置；
        将机器人当前位置标记为已被修改；
        for (每个已被修改的节点 v) {
            for (v 的每个邻居节点 u) {
                计算节点 u 的新代价值 g_new；
                如果 g_new 比 u 当前的代价值小，则更新 u 的代价值，并将 u 添加到 OPEN 列表；
            }
        }
        从 OPEN 列表中选择代价最小的节点作为机器人的下一个移动目标；
        移动机器人到目标位置；
    }

二、D* 算法是对 A* 算法的改进

D* 算法是对 A* 算法的改进，主要用于路径规划问题。以下是 D* 算法相对于 A* 算法的主要改进点：

增量搜索： D* 算法支持增量式搜索，可以在环境变化时有效地更新路径而不必重新计算整个路径。这使得 D* 算法更加适用于实时应用，例如机器人导航。
反向搜索： D* 算法从目标点开始搜索，向起点移动。这种反向搜索的方式对于机器人等应用而言，通常更符合实际情况，因为机器人通常知道目标位置而不知道起点位置。
减少重新规划次数： D* 算法通过增量更新路径，减少了对节点的重新规划的次数。只有在发生环境变化或机器人移动到新位置时，才会进行必要的更新，提高了算法的效率。
灵活的数据结构： D* 算法使用了灵活的数据结构，如优先队列（Priority Queue）来维护待处理的节点。这样可以更高效地选择下一个待处理的节点，提高搜索效率。
自适应性： D* 算法具有自适应性，能够在搜索过程中根据需要灵活地调整搜索策略，以适应不同的环境和实际情况。

尽管 D* 算法在某些方面改进了 A* 算法，但在某些情况下，A* 算法可能仍然更适用。选择算法应根据具体应用场景、性能需求和实际情况进行权衡。

三、增量搜索是什么

增量搜索是指在原有路径的基础上，只对发生变化的部分进行重新规划，而不必重新计算整个路径。D* 算法通过增量搜索实现了对路径的高效更新。

在 D* 算法中，主要有两个核心的数据结构：

Priority Queue（优先队列）： 用于按照节点的启发式值（通常是代价估计）维护待处理的节点，以便在每一步选择最有希望的节点进行拓展。
Key Value： 每个节点都有一个键值对 (k, v)，其中 k 是节点的当前估计代价，v 是节点的实际代价。节点的排序依据是键值对 (k, v)。

D* 算法的增量搜索过程可以概括为以下几个步骤：