
| variable                                                                      | description                                                         |                         |             |
|-------------------------------------------------------------------------------|---------------------------------------------------------------------|-------------------------|-------------|
| The fact is true at time like in satisfiability planning.                     |                                                                     |                         |             |
| i t                                                                           | The operator is e ecuted at time like in satisfiability planning.   |                         |             |
| i t                                                                           | n state , proposition the condition determines the successor state. |                         |             |
| i j                                                                           | The successor of state is if the condition is true.                 |                         |             |
| i j                                                                           | The successor of state is if the condition is false.                |                         |             |
| i j                                                                           | The plan is in state at time .                                      |                         |             |
| i t                                                                           |                                                                     |                         |             |
| i t                                                                           | The operator is enabled at time                                     | etion . .   or in state | ections . . |
| and . . : that is, it is e ecuted if its preconditions are true.              |                                                                     |                         |             |
| The operator is applicable at ; that is, it is enabled, its preconditions are |                                                                     |                         |             |
| i t                                                                           | true, and some of its postconditions are false.                     |                         |             |

Ta ble eaning of propositional variables in the encodings be characteri ed by the length of its e ecutions mer and the number of internal states it may be in. Plan e  istence corresponds to the truth of the   uantified   oolean formula in uestion, and the plan is represented by the truth values of propositional variables that represent plan elements.

To illustrate the translations, we interleave the presentation of the encodings with e amples on encoding a simple blocks world problem. There are two blocks, and . The blocks may be on the table or on the top of the other block. To represent this scenario we use the facts ontableB, onBA, clearB, ontableA, clearA, and onAB. The blocks may be moved as specified by the following four operators.

0

| onAB clearA       | onta ble A   | on A B clear B     |
|-------------------|--------------|--------------------|
| onBA clearB       | ontableBB    | onBA clearA        |
| ontable A clear B | on A B       | clearB  ontableA   |
| ontableB clearA   | onBA         | clear A  ontable B |

## 4.1 Representation Of Executions Of Plans

iven a se uence of  sets of  operators determined by a plan and an initial state, the e ecution of the plan involves producing a se uence of successor states, the last of which should be a goal state. To represent plan e ecutions we need formulae that describe the initial states and produce for each state a successor state that corresponds to the application of the operators determined by the plan.  n classical planning the plan e plicitly gives a set of operators to be e ecuted at each point of time, whereas in conditional planning the set of operators may depend on truth values of facts or the internal state of the plan. discuss the formulae that determine the operators to be e ecuted later together with the di  erent formali  ations of conditional plans, as the former depend on the latter.

Plan e  ecutions are represented like classical planning as a satisfiability problem     aut elman,
. This is because in classical planning plans coincide with their uni ue e ecutions  both are se uences of  sets of  operators.  Plan e ecutions are formali ed as formulae that state the preconditions and postconditions of operators  schema and