Introduction to Planning Tasks

Source slide: B2 Introduction to Planning Tasks

Transition systems tell us what planning means: solve a graph-search problem from an initial state to a goal state. Planning tasks tell us how to write such problems compactly. Instead of listing every state and every transition, we describe the state variables, the formulas that pick out important states, and the operators that generate transitions.

This chapter introduces those ingredients one at a time. The formal definition in the next chapter will assemble them into a complete planning-task tuple.

The Question

The state explosion problem is the reason planning tasks exist. An explicit transition system may contain exponentially many states and transitions. To build a useful planner, we need a representation whose size is closer to the natural size of the domain description.

The compact representation has three main ideas:

1. describe each state as a truth assignment to variables;
2. describe sets of states using formulas;
3. describe many transitions at once using operators.

Together, these ideas let a small input induce a very large transition system.

State Variables and States

A propositional state variable names one Boolean feature of the world. It might mean “truck 1 is at location L”, “the package is inside a truck”, or “block A is clear”.

Definition: Propositional state variable and state

Let $V$ be a finite set of propositional state variables. A state over $V$ is an interpretation of $V$, that is, a function

$$s : V \to \{T,F\}.$$

If $|V| = n$, then $V$ induces $2^n$ possible states. This is exponential in the number of variables, which is exactly why the representation is compact. We can name $n$ features and thereby define a much larger state space.

In blocks world, one can use variables to describe relations such as one block being on another block or on the table. The variables do not list every legal stack arrangement individually; instead, complete truth assignments encode arrangements.

State Formulas as Sets of States

Once states are interpretations, formulas become a way to describe sets of states.

Definition: State formula

A state formula over $V$ is a propositional formula whose atoms are variables in $V$. It represents the set of states

$$\{s \mid s \models \varphi\}.$$

This is how planning tasks describe goals and preconditions. A goal formula does not need to name every goal state. It only needs to state what must be true in any acceptable final state.

For example, suppose $i$ means “the package is inside a truck” and $w$ helps encode the package’s location. The formula

$$\neg i \land \neg w$$

can describe the set of states where the package is at the desired location and not currently loaded. Any state satisfying that formula is a goal state, even if other variables vary.

Operators

State formulas describe where we are allowed to be. Operators describe how we can move.

Definition: Operator

An operator $o$ over state variables $V$ consists of:

• a precondition $\mathit{pre}(o)$, a formula over $V$;
• an effect $\mathit{eff}(o)$, describing how variables change;
• a cost $\mathit{cost}(o) \in \mathbb{N}_0$.

Operators are often called actions. The precondition says when the operator is applicable. The effect says what changes if it is applied. The cost says how expensive the corresponding transition label is.

For a loading action, the precondition might say that the package is not already inside a truck and that the package is at the same location as the truck. The effect then says that the package becomes inside the truck. This one operator schema-like description can stand for many possible transitions in the induced transition system.

Effects

Effects have their own syntax because state change is not just another state formula. A formula describes a set of states. An effect describes an update to a state.

Definition: Effect

Effects over $V$ are defined inductively:

• $\top$ is an effect, called the empty effect;
• if $v \in V$, then $v$ and $\neg v$ are atomic effects;
• if $e$ and $e'$ are effects, then $e \land e'$ is a conjunctive effect;
• if $\chi$ is a formula over $V$ and $e$ is an effect, then $\chi \triangleright e$ is a conditional effect.

The empty effect changes nothing. An atomic effect $v$ sets $v$ to true, while $\neg v$ sets $v$ to false. A conjunctive effect applies several changes together. A conditional effect applies its inner effect only when the condition $\chi$ holds in the current state.

The phrase “current state” matters. In a conditional effect $\chi \triangleright e$, the condition is checked before the effect changes the state. This prevents circular readings such as making a condition true and then using that newly true condition in the same effect application.

A Small Delivery Example

Consider a toy delivery task with two trucks, one package, and two locations, L and R. The slide example uses variables such as:

• $t_1$: truck 1 is at L;
• $t_2$: truck 2 is at L;
• $i$: the package is inside a truck;
• $w$: a variable used to encode where the package is when it is not inside a truck.

Four Boolean variables induce $2^4 = 16$ truth assignments. The domain model decides which of these assignments correspond to meaningful situations, but the compact state space comes directly from the variables.

A move operator for truck 1 may have precondition $\top$, meaning it can always be applied, and an effect that flips the truth value describing truck 1’s location. A loading operator for truck 1 needs a stronger precondition. In the slide notation, one such precondition is

$$\neg i \land (w \leftrightarrow t_1).$$

Read this in two parts. The package must not already be inside a truck, and the package’s location encoding must match truck 1’s location encoding. If the condition holds, the load action can make $i$ true.

An unload operator has the opposite flavor. Its precondition is $i$, because the package must be in a truck before unloading can make sense. Its effect records that the package is no longer inside a truck and updates the package-location information.

From Operators to Transitions

The connection back to transition systems is direct. Each state $s$ and operator $o$ are checked together:

1. If $s \not\models \mathit{pre}(o)$, the operator is not applicable in $s$, so it contributes no transition from $s$.
2. If $s \models \mathit{pre}(o)$, the effect $\mathit{eff}(o)$ determines a successor state $s'$.
3. The induced transition system contains the labeled transition $s \xrightarrow{o} s'$ with cost $\mathit{cost}(o)$.

Thus an operator compactly describes many possible transitions: one for every state in which its precondition holds.

Common Mistake

The most important distinction in this chapter is between formulas and effects. The formula $\neg i \land \neg w$ describes a set of states. It does not by itself change anything. The effect $\neg i$ is an instruction to set $i$ to false when the effect is applied. The symbols look similar, but their roles are different.

Another common mistake is to think compact means small state space. The compact description can be small precisely because the induced state space is large.

Chapter Summary

Planning tasks compactly represent transition systems. State variables define the possible truth assignments, state formulas describe sets of states such as preconditions and goals, and operators describe transitions through preconditions, effects, and costs. Effects may be empty, atomic, conjunctive, or conditional. The next chapter turns these ingredients into the formal definition of a propositional planning task and its induced transition system.

Study Check

1. Why do $n$ propositional state variables induce $2^n$ possible states?
2. How does a goal formula represent many goal states at once?
3. What are the three components of an operator?
4. Why is an effect not the same kind of object as a state formula?
5. In $\chi \triangleright e$, when is $\chi$ evaluated?