The Transition Calculus: a high-level formalism for reasoning about action and change

Abstract

Abstract. The majority of existing formalisms for reasoning about action and change require explicit references to low-level entities such as time points or situations whether or not these are a relevant feature of the problem in hand. Transition calculus is an alternative, high-level approach, in which actions are directly modelled in terms of the state changes that they bring about. It is argued that this provides a more natural way of representing and solving many action and change problems and it is shown how the formalism can be applied to the AI planning domain. Although primarily intended as a purely high-level formalism, transition calculus may also be given a temporal semantics and can thus also be used to solve problems reformulated in terms of explicit temporal references. Any useful action and change formalism must be capable of handling the frame problem. Transition calculus accomplishes this via a novel nonmonotonic reasoning mechanism based on minimization of unexplained state change. This is readily implementable and has been shown to solve a wide variety of canonical problems.

Keywords:

• Action
• Change
• Planning
• Non-monotonic Reasoning