D* / D* Lite

地图边走边变时，只修补受影响的部分、快速重算最短路径的图搜索算法。

D* 是 Anthony Stentz 在 1994 年提出的增量式路径搜索算法，名字来自 Dynamic A*；2002 年 Sven Koenig 和 Maxim Likhachev 在 LPA* 的基础上提出更简洁的 D* Lite，如今用得更多。它解决「地图不完全已知」的导航：机器人先按已知信息规划一条路（未知区域通常先当作可通行），边走边用传感器发现新障碍。普通 A* 每次都要从头搜索；D* 系列从终点往起点反向搜索，并保留上一轮算出的代价值，某些边的代价一变，只修补受影响的节点，所以重规划很快。据维基百科，基于它的导航系统曾在火星车 Spirit 和 Opportunity 上做过原型测试，也用在 CMU 赢得 DARPA 城市挑战赛的无人车上。它属于全局规划，常和 DWA 等局部规划器搭配。

例子仓库里的移动机器人按旧地图规划了一条穿过某条通道的路线，走到一半激光雷达发现通道被托盘堵住。D* Lite 只更新被堵格子附近节点的代价，就能给出绕行路线，不必对整张地图重跑一遍 A*。

也叫

D*、D* Lite、Dynamic A*、Focused D*、增量式重规划算法

相关

A* 算法、Dijkstra 算法、重规划、路径规划、全局规划与局部规划、代价地图

来源

Wikipedia: D*
Koenig & Likhachev, D* Lite (AAAI 2002)