Memory-Bounded D* Lite

Denton Cockburn, Ziad Kobti

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.

Subjects: 15.7 Search; 1.8 Game Playing

Submitted: Feb 25, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.