The Transition Calculus: A High-Level Formalism for Reasoning about Action and Change

John Gooday and Antony Galton

Journal of Experimental and Theoretical Artificial Intelligence, Volume 9, Number 1, January-March 1997, pp. 51-66.
ISSN 0952-813X.

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. In this paper we present Transition Calculus, an alternative, high level approach, in which actions are directly modelled in terms of the state changes that they bring about. We argue that this provides a more natural way of representing and solving many action and change problems and show 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.