Classical Planning Problems and State Spaces

---

Introduction

To talk about classical planning we first have to introduce some terminologies:

• deterministic → for each action there is only one outcome
• stochastic → the effects of the actions can be uncertain or probabilistic
• single-agent → just one agent plans his actions
• multi-agent → multiple agents interact with the environment

And classical planning is deterministic, stochastic, fully-observable (you can acknowledge at every moment in which state it is), static (the changes can only by applied by us) and discrete (usually finite. It is indeed the simplest form of sequential decision making and the plan is the path from the unique initial state to a goal state.

Furthermore we can consider this kind of problems “relatively” simple (their general formulation is PSPACE-complete) but relevant. In further pages there will be stochastic multi-agent settings, which require (much) more complex plans prescribing how to act in every possible state (i.e. how to reach to every possible event/opponent move).

The search in this case consists of exploring the state space, even if there are many other search paradigms (encoding into constrains satisfaction, BDD representation) that we won’t consider.

---

Some example of classical planning problems

Finding a route in a map

• starting from an initial state → departure city
• apply actions → using a road segment
• reach a goal state → destination city
• performance measure → shortest time, shortest path, etc.

The “15-puzzle”

TODO: foto slide 6

• starting from an initial state → left
• apply actions → moving a tile
• reach a goal state → right
• performance measure: minimize summed-up action costs → each move has cost $1$, so we minimize the number of moves

FreeCell

• starting from an initial state → cards on table
• apply actions → moving a card
• reach a goal state → all cards “home”
• performance measure: minimize summed-up action costs → each move has cost $1$, so we minimize the number of moves

Finding bugs (in automata network)

TODO: foto slide 8

• starting from an initial state → both idle
• apply actions → automaton transitions
• reach a goal state → error (both in critical section $CS$)
• performance measure: minimize summed-up action costs → each move has cost $1$, so we minimize the length of the error path

---

Classical planning terminology

We need to distinguish between satisficing planning and optimcal planning:

• satisficing planning
  • input → a planning task $\Pi$
  • output → a plan for $\Pi$, or unsolvable if no plans for $\Pi$ exists
• optimal planning
  • input → a planning task $\Pi$
  • output → a cost-optimal plan for $\Pi$, or unsolvable if no plan for $\Pi$ exists

---

State spaces

Every problem $\Pi$ specifies a state space $\Theta$.

Def. state spaces

A state space is a tuple $\Theta =(S,A,c,T,I,S^G)$:

• $S$ → finite set of states
• $A$ → finite set of actions
• $c:A\to {\mathbb{R}}_0^{+}$ → cost function
• $T\subseteq S\times A\times S$ → transition relation. We require that $T$ is deterministic (i.e. $\forall s\in S,a\in A$ there is at most one state $s^{\prime }$ such that $(s,a,s^{\prime })\in T$). If such $(s,a,s^{\prime })$ exists, then $a$ is applicable to $s$ and results in state $s^{\prime }$. We denote by $A(s)$ the set of actions applicable to $s$
• $I\in S$ → initial state
• $S^G\subseteq S$ → set of goal states

We say that $\Theta$ has the transition $(s,a,s^{\prime })$ if $(s,a,s^{\prime })\in T$. We also write $s\stackrel{a}{\to }{s}^{\prime }$, or $s\to s^{\prime }$ when not interested in $a$.

We say that $\Theta$ has unit cost if, $\forall a\in A,c(a)=1$. We will often give each action $a\in A$ a name, and identify $a$ with that name.

Terminology

• $s^{\prime }$ successor of $s$ if $s\to s^{\prime }$, $s$ predecessor of $s^{\prime }$ if $s\to s^{\prime }$

• $s_n$ reachable from $s_0$ if there exists a sequence of transition $s_0\stackrel{a_1}{\to }{s}_1,\dots ,s_{n-1}\stackrel{a_n}{\to }{s}_n$

• $a_1,\dots ,a_n$ → is the path from $s$ to $s^{\prime }$

• $s_0,\dots ,s_n$ → is also called path from $s$ to $s^{\prime }$

• the cost of that path ${\sum }_{i=1}^{n}c(a_i)$

• $s^{\prime }$ reachable (without reference state) means reachable from $I$

• $s$ is solvable if some $s^{\prime }\in S^G$ is reachable from $s$, else $s$ is a dead end

Def. plans

Let $\Theta =(S,A,c,T,I,S^G)$ be a state space, and let $s\in S$. A plan for $s$ is a path from $s$ to some $s^{\prime }\in S^G$. The plan is optimal if its cost is minimal among all plans for $s$. A plan for $I$ is called plan for $\Theta$. If a plan exists then $\Theta$ is solvable

Directed graph

Directed graph + mark-up for initial state and goal states
TODO: foto slide 16

Question

• Does this $\Theta$ have unit cost? No
• Which actions are applicable to the initial state? actA, actB, actC
• Is $T$ deterministic? No, on $s_8$ and $s_{10}$, actG induces more than one outgoing transition
• What for do we allow $0$-cost actions? Negligible cost (e.g. switch light on)
• Are all states in $\Theta$ reachable? No, $s_7$ is not reachable
• Are all states in $\Theta$ solvable? No, $s_2$ is not solvable
• What are the optimal plans for $\Theta$? Any path that starts with actB, applies actE $n\in \{0,2,4,\dots \}$ times, then applies actC then actE and then no actions other than actG

Find a route to Bucharest (formalization)

• $S=\{at(x)\mid x\text{ city in Europe}\}$
• $A=\{move(x,y)\mid x,y\text{ linked by a road segment}\}$
• $c$ maps each $move(x,y)$ to the length of the road segment
• $T=\{(at(x),move(x,y),at(y))\mid x,y\text{limited by a road segment}\}$
• $I=at(\text{SB})$
• $S^G=\{at(\text{Bucharest})\}$

Koalas and gorillas

TODO: foto slide 22
$\Pi :\text{ cross river without being beaten up}$

Starting with everybody on the right bank we need to use the boat which carries $1\le x\le 2$ animals to get everybody to the left bank. If koalas are outnumbered by gorillas on either bank is game over.

We consider only the states at the end of each boat ride, not the situation during the boat ride. At the end of each move, everybody leaves the boat (in other words, the animals in the boat count as being on the target river bank); and the game is over in case that results in more gorillas than koalas on either bank. Moves after which the game would be over are disallowed (i.e. these action are not applicable).

Formalization

• $S=\{(K,G,B)\mid 0\le K,G\le 3,0\le B\le 1\}$ where $K,G,B$ respectively represent the number of koalas, gorillas and boats currently in the bank
• $I=(3,3,1)$
• $G^G=\{(0,0,0),(0,0,1)\}$
• $c:\text{unit }1$
• $A=$ if $B=1$, subtract $1$ or $2$ from $(K+B)$ and set $B:=0$, if $B=0$, add $1$ or $2$ to $(K+G)$ and set $B:=1$. Both subject to having, after the move, $)\le K,G\le 3$ as well as $K\ge G$ if $K>0$, and $3-K\ge 3-G$ if $3-K>0$
• $T=$ accordingly

However in some problems state spaces may be huge. In particular, the state spaces is typically exponentially large in the size of its specification via the problem $\Pi$; indeed huge space $\Theta$ are (almost always) specified by small $\Pi$ and so we wouldn’t be able to easily represent them. For this reason we need some specifications.

---

Specifications

Specifications are formal descriptions of what a system must do or the properties it must satisfy, necessary in order to solve a problem.

Let’s present the three possible ones.

Simulator specification

A simulator for a problem $\Pi$ implements the procedures necessary to generate paths in the state space (we don’t need to represent the whole state space in advance, we generate successor states on demand by applying actions to the current state using the simulator).

Problem simulator API

• InitialState() → returns the initial state of the problem
• GoalTest(s) → returns a Boolean, true iff state $s$ is a goal state
• Cost(a) → returns the cost of action $a$
• Actions(s) → returns the set of actions that are applicable to state $s$
• ChildState(s,a) → requires that action $a$ is applicable to state $s$ (i.e., there is a transition $s\stackrel{a}{\to }{s}^{\prime }$). Returns the outcome state $s^{\prime }$

In this case “specifying the problem” means programming the simulator.

A problem simulator provides procedures allowing to explore the state space incrementally and to determine goal states and plan cost. For this reason it’s required to respect the minimal functionality (i.e., only implement essential operations), but often is much easier to obtain than symbolic specification.

Symbolic (aka declarative) specification

A symbolic specification of $\Pi$ comes from a declarative language.

Symbolic specification of a problem

There are many ways to do this. Here’s one:

• $P$ → set of Boolean variables (prepositions)
• $I\subseteq P$ → indicating which propositions are true in the initial state
• $G\subseteq P$ → where $s$ is a goal state iff $G\subseteq s$ (all prepositions are satisfied)
• $A$ → set of actions $a$, each with precondition $pr{e}_a$, add list $ad{d}_a$, and delete list $de{l}_a$; $a$ applicable to $s$ iff $pr{e}_a\subseteq s$, outcome state is $(s\cup ad{d}_a)\setminus de{l}_a$
• $c$ → maps each $a\in A$ to its cost $c(a)$

This language is called “STRIPS”. In this case “specifying the problem” means writing STRIPS

This specification is strictly more powerful than simulator, as it allows to implement the simulator and allows to analyze the problem however often is more difficult to obtain than a simulator.

Furthermore symbolic specification enable general planning, but is not used for search algorithms.
TODO: foto slide 29

Example

$$\begin{array}{rl}P& =\{p,q,g\}\\ I& =\varnothing \\ G& =\{g\}\end{array}$$

Azione	PRE	ADD	DEL
$a_p$	$\varnothing$	$\{p\}$	$\varnothing$
$a_q$	$\varnothing$	$\{q\}$	$\varnothing$
$a_g$	$\{p\}$	$\{g\}$	$\varnothing$

obs

I don’t actually need $q$, and then neither $a_q$.

Starting from $S=\varnothing$, I apply $a_p$:

$$\text{apply}(a_p,S)=(S\cup \{p\})\setminus \varnothing =\{p\}$$

Closed-world assumption

We assume that what is inside $S$ is true, what is outside is false

$$S_0=\varnothing \stackrel{a_p}{\to }\{p\}\stackrel{a_g}{\to }\{p,g\}\supseteq G$$

The plan is $\pi =⟨a_p,a_g⟩$: $a_g$ is applicable because $\text{PRE}(a_g)=\{p\}\subseteq \{p\}$.

Enumerative specification

The enumerative specification describes $\Pi$ simply in terms of its state space.

Enumerative specification of a problem

$\Pi =\Theta$

We simply input the state space graph (in some implementation).

In this case “specifying the problem” means writing down the state space, but it’s impossible for large state spaces. However it can be solved easily in the size of the state space (Dijkstra’s algorithm).

Enumerative specifications do not, in difference to simulator and symbolic specification, compactly describe large state spaces. They are used if the state spaces are “small” (only 100.000s of states) and the runtime is very limited. This is typically the case in route planning.