Classical Planning

PDDL/STRIPS

It's an approach based on a particular subset of FOL. To define a STRIPS planning problem we need four elements:

$$\bold{P} = (Cond, Action, Init, Goal)$$

With:

• $Cond$, it's a finite set of ground functionless atomic formulas (also called conditions), which are predicative symbols applied to just constants:

  $Q(c_1, ..., c_n)$, where $Q$ is the predicative symbol and $c_1, ..., c_n$ are constants.

  Ground means that they do not used existential or universal quantifiers, functionless that they do not use function symbols, and atomic because they are made by just one predicates. If we're using DPLL we're good, but no negation is allowed in the STRIPS language.

  Note that states are subset of the Condition set: $\{ p_1, ..., p_n \} \subseteq Cond$. In fact states are made of conjunction of conditions.

• $Action$ is a finite set of operators. An action is made up by two elements:

  $a = (Precond, Effect) \in A$. The precondition defines the conditions under which we can execute $a$, while the effect describes how the state is modified after applying action $a$.

  • $Precond \subseteq Cond$

  • $Effect \subseteq (Cond \cup \bar{Cond})$, with $\bar{Cond} = \{ \neg p : p \in Cond \}$

    It's a conjunction of conditions and negations (only moment in which negation is allowed) of conditions.

• $Init \subseteq Cond$, it's the initial state

• $Goal \subseteq Cond$, it's the goal condition

Actions and Effects

Applicability of an action $a$ in a state $s$ is found by checking the following condition:

$a \in actions(s) \iff Precond \subseteq s$, or $Precond \models s$.

Execution of an action $a$ in a state $s$:

$Effect = Effect^+ \cup Effect^-$. The first set is called conditions, while the second is called negation of conditions. The former are going to be added to the state, while the latter conditions are going to be removed from the state. The result of execution an action on a state is a new state:

$result(s, a) = (s \backslash Effect^-) \cup Effect^+$

Some observations:

• Goal test: $is\_goal(s) \iff Goal \subseteq S$.

• Solution-plan: it's a sequence of actions which starts from $s_0$ and gets to a goal state $s_g$.

PDDL vs STRIPS

In base PDDL, you can use negative literals in preconditions and goal (unlike what you can do in STRIPS).

Some definitions

• Unique Name Assumption (UNA): different constants always denote different objects.

• Domain Closure Assumption (DCA): the environment includes only those objects that are denoted by a constant

• Closed World Assumption (CWA): all literals that are not explicitly mentioned in the description of the state are assumed to be false (i.e., their negation is assumed to be true).

Problem formulation

You need to specify:

1. Constants: used to denote object

2. Predicates: used to represent properties of the objects and relationships between the objects

3. Action schemas (parametric actions): family of actions parametrized with a variable $x$ (or, in general, with more variables) that is instantiated to satisfy the preconditions in a state. Recall that:

   $$\forall a \in A: \hspace{0.3em} a = <Precond, Effect>$$
4. $Init$, $Goal$

Example

• Two rooms

• One robot

• The robot can move between room and suck dirt

Constants: $Robot,R_1,R_2$

Predicates:

• $In(x,y)$: object $x$ is located into room $y$

• $Clean(x)$: room $x$ is clean

We also need special predicates to determine the nature of a given variable, which are needed while writing action schemas:

• $Robot(x)$: $x$ is a robot

• $Room(x)$: same but room

Example of state representation:

means that robot is in room 1 and that room 1 is clean, as seen in the picture. Note that we cannot have negate variables (only exception is in the $Effect$ set), which is why we did not include, for example, $eg Clean(R_2)$. Also STRIPS uses CNF, which means that to describe a state no or will be used between different clauses.

Action example

• $MoveRight$

  • $Preconditions = In(Robot, R_1)$

  As you can see $Effects$ is made up by new predicates and ones which previously belonged to the $Precondition$ set (those can also be negated).

Action schema example

Same as actions, but parametric:

• $Suck(x)$

  • $Preconditions = In(Robot, x)$

Forward/Backward search

• $Init \rightarrow Goal$

• $Goal \rightarrow Init$

Notes:

• Goal test at node generation

• DFS with closed list to avoid repeated states

Formulation as a classical search problem, conjunction of predicates as nodes, action [schemas] as arcs.

SATplan

• based on PL

• Application of DPLL to show that the goal is satisfiable after converting the STRIPS/PDDL representation to CNF form

Basically states (from the initial to the goal) are converted from FOL to PL. Then DPLL is applied to check if the SATPlan is satisfiable or not.