Memory-Bounded D* Lite

All Papers

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 possible 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.