Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems

Citation

Andrew, A.M. (2002), "Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems", Kybernetes, Vol. 31 No. 6. https://doi.org/10.1108/k.2002.06731fae.005

Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems

Raymond ReiterMIT PressCambridge, MA2001xx + 424 pp.ISBN 0-262-18218-1hardback, £34.50

This is a detailed account of "situation logic", with recent enhancements that make it a powerful tool for the design and analysis of a wide range of dynamical systems. The word "dynamical" is used to indicate interaction with an environment over time, not necessarily implying the movement of bodies having mass and inertia as would be implied in a physics text.

The main ideas of "situation logic" have been around since at least a paper by John McCarthy in 1963 and were hinted at in his paper in the symposium on "Mechanisation of Thought Processes" in the National Physical Laboratory, Teddington, in 1958. They are part of a highly formal approach to Artificial Intelligence based on an assumption that human thought, or at least that part of it on which attention is focused, is accurately modelled by the increasingly complex "orders" of formal logic. The viewpoint is discussed in the book's Introduction, and is formalised in a Knowledge Representation Hypothesis quoted on page 2.

John McCarthy is an early pioneer of Artificial Intelligence, and in fact the adoption of that term to denote the subject area is generally attributed jointly to him and Marvin Minsky, in the mid-nineteen fifties. The present book is welcomed by him, in one of the quotes from reviews on the back cover, as being "especially important for the ambitious student who wants to look beyond immediate applications toward the goal of human-level artificial intelligence".

It is claimed that the full potential of the approach was not realised until relatively recently, when the book's author and a colleague realised that "situation logic" or "situation calculus" could be extended to include features like time, concurrency and probability, and devices corresponding to the procedures of ALGOL-type programming languages, and that this could be done in ways that allowed efficient implementations. This book reports the development of these ideas. It begins by reviewing preliminary requirements in first-order and second-order logic before embarking on situation logic.

The material in the book has been used by its author in postgraduate teaching in the University of Toronto, and aroused interest in students from all branches of computer science, as well as control theorists and electrical and computer engineers and mathematicians. Once they were familiar with the approach the students found applications in diverse fields including databases, computer animation, simulation of physical systems, program verification, theoretical foundations, and high-level robotics.

The approach allows rigour in a way that is similar to the use of formal methods in verifying computer programs. As it is expressed in the Preface:

In a nutshell, the central idea of the book is this: When faced with a dynamical system you want to simulate, control, analyze, or otherwise investigate, first axiomatize it in a suitable logic. Through logical entailment, all else will follow, including system control, simulation and analysis.

The value of the rigour that this allows is indicated even more pithily in the slogan:

No implementation without a sitcalc specification.

That situation logic, or calculus, is a "suitable logic" is demonstrated in the subsequent development. Its expressions can be expressed readily as computer programs in a language termed Golog. This is sufficiently compact that working programs for all the examples in the book are easily given in full (and can also be downloaded from a website). The necessary Golog interpreter is also given and occupies one and a half pages, and uses a version of Prolog. The system needed to run the latter is available from a website of Imperial College, London, and is free to universities and other verifiably non-commercial organisations.

As implied by the reference to "high-level" robotics, the approach is most readily applicable to robotics in the situation typified by references to a "blocks world" in which knowledge manipulation and decision making are seen as the core of the problem, with sensors and actuators assumed to be infallible and available as lower-level adjuncts. The much-acclaimed work of Winograd (1973) dealt with the "blocks world" but is not referred to in the present work, justifiably since its emphasis is on natural-language reasoning rather than on use of formal logic.

In recent work the rigid compartmentalisation of function has not found favour, though there are undoubtedly situations in which it is permissible, as for instance in the control of a lift in a multi-storey building, an example that is treated in the book.

On the other hand, the enhanced version of situation logic that is described is such that it probably can be extended beyond the "blocks world" situation and could even incorporate principles of dynamics in the sense understood in physics, though it is difficult to imagine this being done with a rule base of manageable size except in illustrative "toy" applications. In any case the possible applications of situation logic are not confined to robotics, and this rigorous technique will find many applications wherever computers are employed on complex interactive tasks.

Alex M. Andrew

Reference Winograd, T. (1973), Understanding Natural Language, Edinburgh University Press, Edinburgh.