Formal Definition of Planning

Source slide: B3 Formal Definition of Planning

The previous chapters introduced planning as search through possible futures. This chapter makes that idea precise. We need a formal task description that says what a state is, when an operator may be used, how the operator changes the state, and what it means for a plan to succeed.

The result is a compact mathematical object, but it should be read operationally: it is a recipe for generating a transition system. A planner does not need the whole transition graph written out in advance. It needs a way to test preconditions, apply effects, and recognize goals.

Why Effect Semantics Come First

Operators are the moving parts of a planning task. An operator has a precondition, which says when it is applicable, and an effect, which says what changes if it is applied. The subtle part is the effect: effects may be conditional, combined by conjunction, or even try to set the same variable in conflicting ways.

For that reason, the formal definition starts with the question:

For a particular atomic effect, under which condition does it actually fire?

An atomic effect is either $v$, meaning that variable $v$ becomes true, or $\neg v$, meaning that $v$ becomes false. More complex effects are built from atomic effects, conjunctions, and conditional effects of the form $\chi \triangleright e$, read as “if $\chi$ holds, then apply effect $e$.”

Effect Conditions

Let $\ell$ be an atomic effect and let $e$ be an effect. The formula $\mathit{effcond}(\ell,e)$ describes exactly the current-state condition under which $\ell$ is triggered by $e$.

The definition is recursive because effects are recursive objects:

$$\mathit{effcond}(\ell,\top) = \bot$$ $$\mathit{effcond}(\ell,\ell) = \top$$ $$\mathit{effcond}(\ell,\ell') = \bot \quad\text{when }\ell\text{ and }\ell'\text{ are different atomic effects}$$ $$\mathit{effcond}(\ell,e \land e') = \mathit{effcond}(\ell,e) \lor \mathit{effcond}(\ell,e')$$ $$\mathit{effcond}(\ell,\chi \triangleright e) = \chi \land \mathit{effcond}(\ell,e)$$

Read these clauses from simple to complex. The empty effect $\top$ never triggers any atomic effect. An atomic effect triggers itself unconditionally. A conjunction triggers $\ell$ if either side triggers it. A conditional effect triggers $\ell$ only if the condition $\chi$ is true and the nested effect would trigger $\ell$.

For example, suppose an operator contains the effect:

$$(loaded \triangleright delivered) \land (\neg loaded)$$

Then $\mathit{effcond}(delivered,e)$ is $loaded$, while $\mathit{effcond}(\neg loaded,e)$ is $\top$. In a state where $loaded$ is true, both effects fire: the package becomes delivered and $loaded$ becomes false. In a state where $loaded$ is false, only the delete effect for $loaded$ fires, which leaves $loaded$ false.

Applying an Effect to a State

A state $s$ is an interpretation of the finite variable set $V$: every variable is assigned either true or false. Applying an effect $e$ to $s$ gives a new state $s\llbracket e \rrbracket$.

For every $v \in V$, the resulting value is:

$$s'(v) = \begin{cases} T & \text{if } s \models \mathit{effcond}(v,e) \\ F & \text{if } s \models \mathit{effcond}(\neg v,e) \land \neg \mathit{effcond}(v,e) \\ s(v) & \text{otherwise.} \end{cases}$$

The first line says that an add effect sets $v$ to true. The second line says that a delete effect sets $v$ to false, but only if no add effect for $v$ also fires. The last line is the frame assumption: variables not affected by the effect keep their old value.

The tie-breaking rule is called add-after-delete semantics. If an effect simultaneously tries to add $v$ and delete $v$, the add wins. This convention gives every effect a deterministic meaning, even when the syntax contains a conflict.

A common mistake is to treat the effect as if it were applied step by step from left to right. Planning effects are not interpreted that way here. The firing conditions are evaluated in the old state, and the new values are then assembled into the resulting state.

Operators

An operator packages a condition for use with an effect for change. In this chapter, an operator $o$ has at least:

• a precondition $\mathit{pre}(o)$,
• an effect $\mathit{eff}(o)$,
• and, when costs are considered, a cost $\mathit{cost}(o)$.

The operator is applicable in state $s$ exactly when:

$$s \models \mathit{pre}(o)$$

If it is applicable, the resulting state is:

$$s\llbracket o \rrbracket = s\llbracket \mathit{eff}(o) \rrbracket$$

This separation is important. The precondition decides whether the action is allowed. The effect decides how the state changes. A condition inside a conditional effect is not an applicability condition for the whole operator; it only decides whether that particular effect part fires.

Planning Tasks

We can now define the formal input to a classical planner.

Definition: Propositional planning task

A propositional planning task is a tuple

$$\Pi = \langle V, I, O, \gamma\rangle$$

where $V$ is a finite set of propositional state variables, $I$ is an interpretation of $V$ called the initial state, $O$ is a finite set of operators over $V$, and $\gamma$ is a formula over $V$ called the goal.

The tuple is small, but it represents a potentially enormous graph. If $|V|=n$, then there are $2^n$ possible truth assignments. The planner usually explores only a fraction of them, but the semantics define all of them.

The Induced Transition System

Every planning task $\Pi$ induces a transition system:

$$\mathcal{T}(\Pi) = \langle S,L,c,T,s_0,S_\star\rangle$$

The components are obtained directly from the planning task:

• $S$ is the set of all states over $V$.
• $L = O$, because operators label transitions.
• $c(o)=\mathit{cost}(o)$.
• $s_0 = I$.
• $S_\star = \{s \in S \mid s \models \gamma\}$ is the set of goal states.
• $T$ contains exactly the transitions produced by applicable operators:

$$T = \{\langle s,o,s'\rangle \mid s \in S,\; o \in O,\; s \models \mathit{pre}(o),\; s'=s\llbracket o\rrbracket\}.$$

This is the bridge from compact syntax to search. The task file describes variables and operators; the transition system is the graph that search algorithms conceptually traverse.

A sequence of operators is a plan for $\Pi$ when it is a solution path in $\mathcal{T}(\Pi)$ from $s_0$ to some state in $S_\star$.

Satisficing and Optimal Planning

There are two standard solution requirements.

Definition: Satisficing planning

Given a planning task $\Pi$, find any plan for $\Pi$, or report that $\Pi$ is unsolvable.

Definition: Optimal planning

Given a planning task $\Pi$, find a plan for $\Pi$ with minimum cost among all plans, or report that $\Pi$ is unsolvable.

Satisficing planning asks for reachability. Optimal planning asks for the cheapest reachable goal path. The same task semantics support both, but algorithms often differ sharply because “some path” and “best path” require different guarantees.

Positive Normal Form

Planning algorithms are easier to state when the input has a regular shape. One useful regularization is positive normal form.

First, an effect is simple if it is atomic or has the form $\chi \triangleright \ell$, where $\ell$ is atomic. An effect is flat if it is a conjunction of zero or more simple effects and no two simple effects mention the same atomic effect. An operator is flat when its effect is flat.

Definition: Positive normal form

A propositional planning task is in positive normal form when it is positive and all operator effects are flat. Positive means that no negation symbols occur in preconditions, effect conditions, or the goal.

At first this may look like a major restriction. It is mainly a syntactic convenience. A negated condition such as $\neg v$ can be represented by introducing a complementary variable $\hat v$. The new variable is initialized to the opposite truth value of $v$, occurrences of $\neg v$ in conditions are replaced by $\hat v$, and effects on $v$ are mirrored by complementary effects on $\hat v$.

The point is not that the world has no negative facts. The point is that algorithms can often work with a cleaner input language if negative tests have been compiled away into positive variables.

STRIPS

STRIPS is an even simpler formalism. It is historically important and still useful because many planning algorithms are easiest to introduce in STRIPS form.

Definition: STRIPS operator

An operator is a STRIPS operator if its precondition is a conjunction of state variables and its effect is a conflict-free conjunction of atomic effects.

Definition: STRIPS planning task

A planning task $\langle V,I,O,\gamma\rangle$ is a STRIPS task if all operators in $O$ are STRIPS operators and $\gamma$ is a conjunction of state variables.

A STRIPS operator can be read as three finite sets:

• $\mathit{pre}(o)$: atoms that must already be true,
• $\mathit{add}(o)$: atoms made true by the operator,
• $\mathit{del}(o)$: atoms made false by the operator.

For a small example, an operator load-truck might require $at\_package\_depot$ and $at\_truck\_depot$, add $in\_truck$, and delete $at\_package\_depot$. The operator is applicable only in states satisfying both preconditions. After applying it, the package is in the truck and no longer at the depot, while unrelated variables are unchanged.

STRIPS is restricted but not weak in the sense relevant here: the slides use it as a simple common language, and general planning tasks can be compiled into related restricted forms with controlled growth. Later chapters use STRIPS because it keeps the mechanics of progression, regression, and heuristics visible.

What Can Go Wrong

Three confusions are worth catching early.

First, preconditions and conditional-effect conditions play different roles. Preconditions decide whether the whole operator may be applied; conditional-effect conditions decide which parts of the effect fire.

Second, applying an effect is not a sequential program. All firing conditions are evaluated in the original state, and add-after-delete semantics resolves simultaneous add/delete conflicts.

Third, a planning task is not the same object as its transition system. The task is the compact description. The transition system is the explicit graph induced by that description.

Chapter Summary

A propositional planning task $\Pi=\langle V,I,O,\gamma\rangle$ describes variables, an initial state, operators, and a goal. Operator semantics are defined through preconditions and effects; effects are interpreted using recursive effect conditions and add-after-delete tie-breaking. The task induces a transition system whose paths correspond to plans. Satisficing planning asks for any plan, while optimal planning asks for a minimum-cost plan. Positive normal form and STRIPS are restricted syntactic forms that make later algorithms easier to state.

Check Your Understanding

1. What question does $\mathit{effcond}(\ell,e)$ answer?
2. Why are effect conditions evaluated in the old state rather than updated one at a time?
3. How does a planning task induce a transition system?
4. What changes when a problem is solved as optimal planning rather than satisficing planning?
5. What information is stored in the precondition, add, and delete sets of a STRIPS operator?