© 1994 by Oxford University Press
Original Articles |
ADL and the State-Transition Model of Action
AT&T Bell Laboratories 101 Crawfords Corner Road, Holmdel, NJ 07733-3030, USA E-mail: epdp{at}research.att.com
This paper provides a complete presentation of the syntax, semantics, and some of the properties of ADL, a formalism for representing and reasoning about the effects of actions. ADL is based on the state-transition model of action, combining much of the expressive power of the situation calculus with the notational and computational benefits of the STRIPS language. In combining these elements, ADL attempts to strike a better balance in the tradeoff between the expressiveness of a logical formalism and the computational complexity of reasoning with that formalism. ADL is defined from a semantic standpoint as a set of constraints on the general state-transition model of action. These constraints are general enough to enable situation-dependent effects to be described while being strong enough to provide a simple solution to the frame problem. The syntax of ADL can vary, allowing different syntactical variants to be developed without altering the underlying semantics. The syntax presented here resembles the STRIPS operator language augmented with conditional add and delete lists. Reasoning is accomplished by transforming ADL schemas into regression operators. It is shown that regression operators provide a sound and complete means for reasoning about the effects of actions represented in ADL. It is also shown that, in general, comparable progression operators cannot be constructed from ADL schemas. This result is surprising, since progression operators are conceptually the inverse of regression operators. Reasoning can also be accomplished by axiomatizing ADL schemas in the situation calculus. It is shown that a restricted form of the situation calculus can be defined that is effectively equivalent to ADL in that ADL schemas can be translated into equivalent sets of axioms in this restricted form, and vice versa. The restricted form is interesting in its own right, since it incorporates a solution to the frame problem that does not explicitly rely on circumscription. This solution is derived from the semantics of ADL.
Keywords: Knowledge representation,; reasoning about action,; automatic planning,; situation calculus,; STRIPS,; ADL.