# Constructing Conditional Plans By A Theorem-Prover

## Jussi Rintanen

RINTANEN@INFORMATIK. UNI-ULM.DE
Universitat Ulm Fakultat für Informatik Albert-Einstein-Allee 89069 Ulm, GERMANY

## Abstract

The research on conditional planning rejects the assumptions that there is no uncertainty or incompleteness of knowledge with respect to the state and changes of the system the plans operate on. Without these assumptions the sequences of operations that achieve the goals depend on the initial state and the outcomes of nondeterministic changes in the system. This setting raises the questions of how to represent the plans and how to perform plan search. The answers are quite different from those in the simpler classical framework.

In this paper, we approach conditional planning from a new viewpoint that is motivated by the use of satisfiability algorithms in classical planning. Translating conditional planning to formulae in the propositional logic is not feasible because of inherent computational limitations. Instead, we translate conditional planning to quantified Boolean formulae. We discuss three formalizations of conditional planning as quantified Boolean formulae, and present experimental results obtained with a theorem-prover.

## 1. Introduction

The purpose of automated planning is to construct instructions, a plan, by following which some predefined goals can be achieved. Plans consist of operators that make a set of facts true whenever their preconditions are fulfilled. The most basic and the most common in earlier research form of plans is se uence of operators that are e  ecuted unconditionally in the specified order. Plans of this form are su cient only if the world where a plan is carried out is completely predictable and known, and the e  ecution of the plan always starts in the same state.

hen not all changes in the world can be predicted or not all facts a ecting plan e ecution are known in advance, the structure of plans has to be more general.  f the task is to move ob ect a, that is in room or in room a trash can, the operations that achieve the goal depend on the initial location of . There is no single se  uence of operations that achieves the goal in both cases. ence parts of the plan have to be conditional on contingent plan that achieves the goal says that first go to room , if ob ect facts of the world. is not there go to room , pick up the ob ect, find a trash can, and drop the ob ect in it.

hen following this plan, room   is visited only if ob ect is not in room ost of the recent work on conditional planning has been carried out in the least commitment or partial order planning paradigm, the underlying idea of which has perhaps best been e  plicated in the planning algorithm SNLP
cllester osenblitt,
. This algorithm starts with an incomplete plan that consists of descriptions of the goal and the initial state. Plans are found by backtracking search. The children of a node in the search