Memory-Bounded D* Lite
Denton Cockburn, Ziad Kobti · 2008
A * is a well-established pathfinding algorithm. Focussed D* is one of the more popular variations thereof. D * Lite in turn is based upon Focussed D*. Being based upon A*, D * Lite suffers from similar high memory usage as A*, as all nodes being expanded need to remain in the algorithm’s OPEN list. D * Lite repairs the solution path as changes are detected, but oftentimes without any bounds on the amount of items placed on the update queue, creating a situation in which it is possi-ble that all nodes within the map are placed on the queue, in the worst case. Memory-Bounded D * Lite (MD * Lite) aims to provide the same advantages of D * Lite, while applying memory usage constraints.