Home Online Resources Table of Contents

Journal of Logic and Computation, Volume 8, Issue 3: June 1998.

Applying the mu-calculus in planning and reasoning about action

MP Singh

Department of Computer Science, Box 7534, North Carolina State University, Raleigh, NC 27695-7534, USA, E-mail: singh@ncsu.edu

Planning algorithms have traditionally been geared towards achievement goals in single-agent environments. Such algorithms essentially produce plans to reach one of a specified set of states. More general approaches for planning based on temporal logic (TL) are emerging. Current approaches tend to use linear TL, and can handle sets of sequences of states. However, they assume deterministic actions with all changes effected solely by one agent. By contrast, we use a branching model of time that can express concurrent actions by multiple agents and the environment, leading to nondeterministic effects of an agent's actions. For this reason, we view plans not as sequences of actions, but as decision graphs describing the agent's actions in different situations. Thus, although we consider single-agent decision graphs, our approach is better suited to multiagent systems. We also consider an expressive formalism, which allows a wider variety of goals, including achievement and maintenance goals. Achievement corresponds to traditional planning, but maintenance is more powerful than traditional maintenance goals, and may require nonterminating plans. To formalize decision graphs requires a means to 'alternate' the agent's and the environment's choices. From logics of program, we introduce the propositional mu-calculus, which has operators for least and greatest fixpoints. We give a semantics, a fixpoint characterization, and an algorithm to compute decision graphs.

Keywords: Mu-calculus, planning, reasoning about action, temporal logic.

Pages 425-445


This page is run by Oxford University Press, Great Clarendon Street, Oxford OX2 6DP, UK
as part of the OUP Journals World Wide Web service.
Comments and feedback: www-admin@oup.co.uk
URL: http://www.oup.co.uk/logcom/hdb/Volume_08/Issue_03/080425.sgm.abs.html
Last modification: 22 July 1998.
Copyright© Oxford University Press, 1998.