Transition Systems and Propositional Logic

Source slide: B1 Transition Systems and Propositional Logic

The previous chapter described planning as search for an action sequence. This chapter makes the search space explicit. A transition system is the mathematical object behind the picture: it tells us which states exist, which labeled transitions connect them, how much those transitions cost, where execution starts, and which states count as goals.

The chapter then explains why planners rarely receive transition systems in this explicit form. Even simple domains can have too many states to list. Propositional logic gives us a compact language for describing states and sets of states without drawing the whole graph.

The Formal Object

A transition system is a labeled directed graph with a little extra structure.

Definition: Transition system

A transition system is a tuple

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

where $S$ is a finite set of states, $L$ is a finite set of transition labels, $c : L \to \mathbb{N}_0$ is a label-cost function, $T \subseteq S \times L \times S$ is the transition relation, $s_0 \in S$ is the initial state, and $S_\star \subseteq S$ is the set of goal states.

If $\langle s,\ell,s'\rangle \in T$, we write

$$s \xrightarrow{\ell} s' .$$

Read this as: from state $s$, transition label $\ell$ may take us to state $s'$. In planning, the label will usually correspond to an action or operator.

How to Read the Components

Each component answers one practical question.

• $S$ says what complete world states are possible in the model.
• $L$ says what labels can appear on transitions.
• $c$ says how expensive each label is.
• $T$ says which labeled moves are actually allowed.
• $s_0$ says where execution starts.
• $S_\star$ says which states are acceptable endpoints.

A solution is not a state by itself. It is a path from the initial state to some goal state. If the path uses labels $\ell_1,\ldots,\ell_n$, its cost is

$$\sum_{i=1}^{n} c(\ell_i).$$

When every label has cost $1$, this is just the number of steps. With general non-negative costs, a shorter path need not be cheaper.

Determinism

Classical planning assumes deterministic change. In transition-system language, that means a state and a label determine at most one successor.

Definition: Deterministic transition system

A transition system is deterministic if, for all states $s$ and labels $\ell$, there is at most one state $s'$ such that $s \xrightarrow{\ell} s'$.

Determinism does not mean every action is always possible. It means that if a transition with label $\ell$ exists from $s$, there is no second different successor with the same label. An unavailable action is represented by the absence of such a transition.

Paths, Reachability, and Solutions

Most planning terminology in transition systems comes directly from graph search.

A state $s'$ is a successor of $s$ if some label leads from $s$ to $s'$. Conversely, $s$ is a predecessor of $s'$. A state is reachable from $s$ if there is a finite sequence of transitions from $s$ to that state. When no starting state is mentioned, reachability is usually from $s_0$.

A trace writes both states and labels:

$$s_0 \xrightarrow{\ell_1} s_1 \xrightarrow{\ell_2} \cdots \xrightarrow{\ell_n} s_n .$$

This trace is a solution from $s_0$ if $s_n \in S_\star$. A transition system is solvable if at least one such goal-reaching trace exists.

Blocks World and State Explosion

Blocks world is a useful running example because its rules are simple but its state space grows very quickly. Blocks can be stacked on the table or on top of one another. The exact table positions do not matter, and each block can have at most one block above it and at most one block below it.

The number of possible states grows as follows:

Blocks	States
1	1
3	13
5	501
8	394,353
10	58,941,091
15	65,573,803,186,921

These numbers explain why explicit transition systems are mainly a semantic model. They tell us what a planning problem means, but they are usually not a practical input format.

There is also a useful distinction between finding any plan and finding a best plan. In blocks world, a simple strategy can find some solution by clearing blocks to the table and rebuilding the target tower. Finding a shortest solution is much harder. This distinction will later reappear as satisficing versus optimal planning.

Why We Need Compact Descriptions

If a planner had to receive all of $S$ and all of $T$ explicitly, even small domains would be impossible to write down. Instead, we describe states using variables and describe transitions using operators. The explicit transition system is then induced by the compact description.

Propositional logic is the first compact language we need. With $n$ Boolean variables, there are $2^n$ possible truth assignments. A formula over those variables can describe a single state, many states, all states, or no states.

For example, if $p$ means “the package is in the truck” and $r$ means “the truck is at the right location”, then the formula

$$p \land r$$

describes all states in which both facts are true, regardless of other variables in the model.

Propositional Syntax

Let $A$ be a set of atomic propositions. Formulas over $A$ are built from the following ingredients:

• $\top$ and $\bot$, meaning truth and falsity;
• atoms $a \in A$;
• negation $\neg\varphi$;
• disjunction $\varphi \lor \psi$;
• conjunction $\varphi \land \psi$.

Implication and equivalence are common abbreviations:

$$\varphi \to \psi \quad\text{abbreviates}\quad \neg\varphi \lor \psi ,$$

and

$$\varphi \leftrightarrow \psi \quad\text{abbreviates}\quad (\varphi \to \psi) \land (\psi \to \varphi).$$

The syntax tells us which strings are well-formed formulas. It does not yet tell us whether a formula is true.

Propositional Semantics

Truth is evaluated relative to an interpretation. An interpretation $I : A \to \{T,F\}$ assigns each atom a truth value. Satisfaction, written $I \models \varphi$, is defined recursively:

$$I \models \top$$ $$I \not\models \bot$$ $$I \models a \quad\text{iff}\quad I(a) = T$$ $$I \models \neg\varphi \quad\text{iff}\quad I \not\models \varphi$$ $$I \models \varphi \lor \psi \quad\text{iff}\quad I \models \varphi \text{ or } I \models \psi$$ $$I \models \varphi \land \psi \quad\text{iff}\quad I \models \varphi \text{ and } I \models \psi .$$

For planning, interpretations will become states. A formula then represents the set of states that satisfy it.

Useful Logical Vocabulary

A formula is satisfiable if at least one interpretation satisfies it. It is unsatisfiable if none do. It is valid if every interpretation satisfies it.

Logical consequence is written $\varphi \models \psi$. It means every model of $\varphi$ is also a model of $\psi$. Logical equivalence, written $\varphi \equiv \psi$, means the two formulas have exactly the same models.

A literal is an atom $a$ or a negated atom $\neg a$. A clause is a disjunction of literals. A monomial is a conjunction of literals. Normal forms such as negation normal form, conjunctive normal form, and disjunctive normal form reorganize formulas into restricted shapes that are useful for algorithms.

Common Mistake

Do not confuse a transition system with its compact encoding. The transition system is the full state-space graph. A planning task is a compact description that induces such a graph. Algorithms often reason over the compact description while using transition-system concepts to define correctness.

Another common mistake is to treat determinism as totality. A deterministic system can still have no outgoing transition for a particular state-label pair.

Chapter Summary

A transition system is the explicit mathematical model of state-space search: states, labels, costs, transitions, an initial state, and goal states. A solution is a path from the initial state to a goal state, and its cost is the sum of the labels used. Classical planning focuses on deterministic transition systems, but explicit systems are usually too large to list. Propositional logic provides the compact language for describing states and sets of states, preparing us for planning tasks.

Study Check

1. What does each component of $\mathcal{T} = \langle S,L,c,T,s_0,S_\star\rangle$ represent?
2. Why does deterministic not mean every label is applicable everywhere?
3. What is the difference between a trace and a label path?
4. How many truth assignments are possible over $n$ propositional variables?
5. Why are transition systems useful even when planners do not receive them explicitly?