"Real-Time Replanning for Unknown, Uncertain, and Changing Domains"

3/7/1997: [time not recorded]
[location not recorded]

Abstract: Planning operations for an autonomous agent is a much-studied problem. Most solutions require that the agent's domain be fully known at the time of planning and fixed during execution. For many domains, however, this is not possible. For example, consider a mobile robot equipped with a sensor, instructed to drive to a goal location with no initial map information. One approach to the problem is to produce an initial plan based on all known, believed, assumed, and estimated domain information, and then begin executing the plan. Whenever new information is learned about the domain (e.g., via the sensor), the information is logged and remaining portion of the plan is recomputed. This approach has been shown to yield excellent average case performance. The difficulty is primarily computational: replanning is expensive. In this talk, I present a search algorithm called D* (Dynamic A*) that can be used for real-time replanning. The algorithm is functionally equivalent to searching from scratch for each new piece of domain data, except that it is hundreds of times faster. D* uses an incremental graph theory approach to minimize recomputations. The algorithm was demonstrated on an actual mobile robot driving across unknown terrain. The approach was extended to planning for a fleet of vehicles tasked with achieving a coordinated set of goals, and work is underway to generalize the approach to STRIPS-like planning.

Last updated: Mon Jun 19 17:44:06 2006