路径规划之D*算法

系列文章目录

路径规划之Dijkstra算法
路径规划之Best-First Search算法
路径规划之A*算法
路径规划之D *算法

---

---

前言

之前说过A是目前应用最广泛的寻路算法，但是A算法存在它的局限性，那就是A*算法只能在静态环境中有着良好的表现，但是在动态环境中发挥有限，动态环境指路障会变化。因此为了应对该问题，科学家们提出了D *算法。

一、D*算法

1.1 起源

“D* 算法”的名称源自 Dynamic A Star,最初由Anthony Stentz于1994年在“Optimal and Efficient Path Planning for Partially-Known Environments”中提出；
它是一种启发式的路径搜索算法，特点在于其增量路径规划能力，当环境发生变化时，它允许机器人在已经找到路径的基础上，仅重新计算必要的部分，而不需要重新规划整个路径。
这使得它适用于实时系统，特别是需要在运动中适应未知、动态环境的移动机器人等应用。

1.2 思想

不同于A算法从起点出发搜索，D算法从终点出发搜索；简单来说核心思想就是反向搜索；

原因：从终点出发，如果本来规划的路径上突然出现路障需要重新规划时，由于从终点出发到对应的点上的路径都是最短路径，因此可以有效利用这些已经搜索过的信息进行重新规划。

1.3 阶段

D*分为两个阶段，如下：

1. 先使用Dijkstra / A*算法找到起点到目标点的静态可行路径；
2. 动态避障搜索阶段。

1.4 个人理解

当路径上出现一个障碍物时，此时移动机器人到障碍物之间的路径必然要收到影响，接下来的就是找到一段新的路径，能够绕过障碍物；
找到障碍物节点的子节点，再找到子节点的邻接节点，通过反向搜索找到代价最小的节点作为下一个选择的节点；
为什么要用反向搜索来重新规划路径呢？因为之前已经使用A* / Dijkstra计算出一条静态情况下的最短路径了，此时重新规划路径，如果能保留之前走的路径，可以节省很大的计算量同时也可以保证最短路径，因此此时使用反向搜索重新规划从终点出发绕过该路障点。

1.5 应用