
## 4.2  Representation Of Conditional Plans

onditional plans are ob ects that map the current and past observations to the operators to be e ecuted.   y the   hurch Turing thesis, most general computable notions of such mappings are e uivalent to Turing maines.   owever, it is not necessary to consider mappings from arbitrary observations to se  uences of operations.    e consider only systems that are represented by finite sets of facts, and hence the plans do not have to be able to respond to arbitrarily comple behavior of the environment.

e consider conditional plans that are finite state; that is, in addition to the information obtained as observations, only a finite amount of information internal to the plan is used in determining which operations to perform and how the internal state evolves. The control ow in this kinds of plans is similar to that of finite automata, or e uivalently to that of programs in a simple programming language with iteration or a goto statement and simple if then else conditionals. The finite amount of information, that is the internal state of the plan during e ecution, can be characteri ed by a state variable that corresponds to a program counter.

onditional plans with unrestricted transition functions are very e pressive but the nmber of plans with even a small number of states and observable facts is very high, which makes plan search di cult. s there is, in general, a trade o between the e pressivity of the representation and the di   culty of finding plans, we also consider more restricted forms of conditional plans in  ections  . .  and  . . .

## 4.2.1 Plans With Unrestricted Transition Functions

The first formali ation of conditional plans uses finite automata for representing the internal state transitions the plan makes. The successor state of a state is determined by the truth value of an observable fact associated with the state, which we call the condition of the state.

The transition functions of the automata may be cyclic in the sense that an automaton may return to a state it has once left.

ach state of a conditional plan has an associated set of operators.

e say that for a given state, these operators are enabled in it. f an operator is enabled in the current state, it is e  ecuted if its preconditions are true.

n domains in which only plan e ecution may cause changes in the environment, this form of plans is su  cient  whenever a problem instance in conditional planning has a solution, that is, there is plan according to some reasonable notion of conditional plans, it has a solution as the kind of plan discussed in this section.   or the simpler notions of plans in ections . . and . . this is not the case see ample . in ection . . .

The number of automata with even a small number of states is fairly high and there is no a priori upper bound on the number of states needed, so parameteri ing the encoding with respect to the number s of states is necessary. olutions are first sought for by running a theorem prover with encodings with a small number of states and points of time, and then gradually increasing the values of these parameters.

The formulae for formali  ing conditional plans of this form are given in   igure   .

efine chemata and as state that for every state there is e actly one s s =
condition. chemata . state that for every state there is e actly one successor state for both the true and the false value of the condition. This is needed to ensure that the