Planning

📎 Examples

Definition

Factored represenation of the world - each state in the world represented by a set of variables.

Planning

coming up with sequence of actions that will achieve a goal.

Reasoning about the results of actions

frame problem ... what are things that stay unchanged after action?

would require a lot of axioms to describe.

ramification problem ... what are the implicit effects?

qualification problem ... what are preconditions for actions?

deals with a correct conceptualisation of things (no answer).

Classical Planning Environments

Used in classical planning:

fully observable

deterministic, finite

static (change happens only when the agent acts)

discrete in time, actions, objects, and effects

STRIPS

Is a representation / planning language.

Describes the 4 things needed to define a search problem:

Initial state

Actions available in a state $\text{Action(s)}$

Result of applying action $\text{Result(s,a)}$

Goal state

Representations in STRIPS

states

conjunction of positive literals (atoms) that represent a state.

Any unmentioned state is assumed false (= closed world assumption).

literals are atomic fomulas or their negation - can be propositional-logic or first-order-logic.

literals must be ground (= variable free) and function free.

Example
Allowed $Rich \wedge InJail$
No allowed $\text{At}(x, y)$ or $\text {At(president(Russia), Kremlin)}$

goals

Is a state. Cannot contain negative literals

Example
The state $\text { Rich } \wedge \text { Famous } \wedge \text { InJail }$ satisfies the goal $\text { Rich } \wedge \text { Famous}$ .

actions

action schemas represent all different actions that can occur if we instatiate the variables with constants and consist of:

action name, parameter list

precondition (cannot contain negative literals)
stating what must be true in a state before the action can be executed - then the action is applicable.
Can only contain variables in the parameter list.

effect
describing how the state changes when the action is executed.
Can only contain variables in the parameter list
Some planning systems divide the effect into add list for positive literals and delete list for negative literals.

Example
action schema for flying a plane from one location to another:
$\operatorname{Action}(F l y(p, \text { from, to}), \\ \qquad \text{PRECOND: } A t(p, \text {from}) \wedge \text {Plane}(p) \wedge \text {Airport}(\text {from}) \wedge \text {Airport}(\text {to}) \\ \qquad \text {EFFECT:} \space\space\neg A t(p, \text {from}) \wedge At(p, to))$
Setting values for variables $\text{p, from, to}$ :
$\text {Action}\left(\text {Fly}\left(P_{1}, S F O, J F K\right)\right., \\ \qquad \text { PRECOND: } A t\left(P_{1}, S F O\right) \wedge \text {Plane}\left(P_{1}\right) \wedge \text {Airport}(S F O) \wedge \text {Airport}(J F K) \\ \qquad \text { EFFECT: } \left.\neg A t\left(P_{1}, S F O\right) \wedge A t\left(P_{1}, J F K\right)\right)$

results

The result of executing an action $a$ in state $s$ is a state $s'$ :

adding all positive literals from the effect of $a$ (only added once)

removing all positive literals where their negation appears in the effect of $a$

Every unmentioned literal remains unchanged (= STRIPS assumption)

Example
With the action $\text {Fly}\left(P_{1}, S F O, J F K\right)$
$DEL(\text{At}\left(P_{1}, S F O\right))$
$ADD(\operatorname{At}\left(P_{1}, J F K\right))$

solution

action sequence that when executed in the initial state - results in a state that satisfies the goal.

Every action sequence that maintains the partial order is a solution. (see: partially ordered sets)

Language variants

Action Description Language ADL

Variant of STRIPS.

Allows typing - $\text{p : Plane}$ means $\text{Plane(p)}$ .

Allows preconditions such as $\text{from} \not =\text{to}$ .

Allows quantors such as $\exist$ .

example
$\text {Action }(\text {Fly }(p: \text {Plane, from : Airport, to : Airport }) \\\qquad \text {PRECOND: } A t(p, \text { from }) \wedge \text { from } \neq \text { to } \\\qquad \text {EFFECT: } \neg A t(p, \text { from }) \wedge A t(p, t o))$

STRIPS vs. ADL

STRIPS

only positive literals in states

closed-world-assumption: unmentioned literals are false

Effect $P \wedge \neg Q$ means add $P$ and delete $Q$

only ground atoms in goals

Effects are conjunctions

No support for equality or types

ADL

positive and negative literals in states

open-world-assumption: unmentioned literals are unknown

Effect $P \wedge \neg Q$ means add $P$ and $\neg Q$ delete $Q$ and $\neg P$

goals contain $\exists$ quantor

goals allow conjunction and disjunction

conditional effects are allowed: $P:E$ means $E$ is only an effect if $P$ is satisfied

equality and types built in

Planning Domain Definition Language PDDL

includes sublanguages for STRIPS and ADL

Restrictions of ADL and STRIPS

cant derive other effects from more complex ones

classical planning systems do not attempt to address the qualification problem