NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Press Enter or click the Search button to begin your search.

Back to Results
The Logic of ReachabilityIn recent years, Graphplan style reachability analysis and mutual exclusion reasoning have been used in many high performance planning systems. While numerous refinements and extensions have been developed, the basic plan graph structure and reasoning mechanisms used in these systems are tied to the very simple STRIPS model of action. In 1999, Smith and Weld generalized the Graphplan methods for reachability and mutex reasoning to allow actions to have differing durations. However, the representation of actions still has some severe limitations that prevent the use of these techniques for many real-world planning systems. In this paper, we 1) separate the logic of reachability from the particular representation and inference methods used in Graphplan, and 2) extend the notions of reachability and mutual exclusion to more general notions of time and action. As it turns out, the general rules for mutual exclusion reasoning take on a remarkably clean and simple form. However, practical instantiations of them turn out to be messy, and require that we make representation and reasoning choices.
Document ID
20020052613
Acquisition Source
Ames Research Center
Document Type
Preprint (Draft being sent to journal)
Authors
Smith, David E.
(NASA Ames Research Center Moffett Field, CA United States)
Jonsson, Ari K.
(Research Inst. for Advanced Computer Science Moffett Field, CA United States)
Clancy, Daniel
Date Acquired
September 7, 2013
Publication Date
January 1, 2001
Subject Category
Systems Analysis And Operations Research
Meeting Information
Meeting: Sixth International Conference on Artificial Intelligence Planning and Scheduling
Location: Toulouse
Country: France
Start Date: April 23, 2002
End Date: April 27, 2002
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available