Classical planning - with state-space-search.

Totally ordered plan searches

in strictly linear order.

The state space is finite without function symbols - any graph search algorithm can be used.

Variants:

Progression Planning

Forward (progression) states search.

Goal test checks whether the state satisfies the goal of the planning problem

Step cost Usually 1 for each action

Regression Planning

Backward (regression) relevant -states search.

Chosen actions should be consistent : not undoing the made progress by changing correct literals.

Computing state predecessors with STRIPS

Given a goal description $G$ , let $A$ be an action that is relevant and consistent.

• Formally

  $g$ goal description

  $g'$ regression from $g$ over $a$

  $a$ ground action

  ---

  state description $g'$ defined by:

  True in $g'$ : $g^{\prime}=(g-\operatorname{ADD}(a)) \cup \operatorname{Precond}(a)$

• example

  with partially instantiated actions and states

  Goal = Delivering cargo $C_2$ to $SFO$ so that $At(C_2, SFO)$

  Action that leads to goal:

  $Action(Unload(C_2, p', SFO)),$

  $\text{PRECOND:} \operatorname{In}(C_{2}, p') \wedge A t(p^{\prime},SFO) \wedge \operatorname{Cargo}(C_{2}) \wedge \text {Plane}(p') \wedge \operatorname{Airport}(S F O)$

  $\text{EFFECT:} \operatorname{At}\left(C_{2}, S F O\right) \wedge \neg \operatorname{In}\left(C_{2}, p^{\prime}\right)$

  ($p'$is a "standardized variable" that can be substituted with any value)

  We can now use any plane for $p'$ :

  $g^{\prime}=\operatorname{In}\left(C_{2}, p^{\prime}\right) \wedge A t\left(p^{\prime}, S F O\right) \wedge \operatorname{Cargo}\left(C_{2}\right) \wedge \text { Plane }\left(p^{\prime}\right) \wedge \text { Airport }(S F O)$

Partial-order Planning

Order is not specified: can place to actions into a plan without specifying which one comes first.

Search in space of partial-order-plans.

Components of a plan

1. set of action

   The actions in this search are not actions in the world but actions on plans .

   ie. adding a step to the plan, setting an ordering that puts one action before another, ...

2. set of ordering constraints

   $A \prec B$ Action $A$ must be executed before action $B$ .

   Must be free of contradictions/cycles : $(A \prec B) \wedge (B\prec A)$

3. set of casual links

   $A \stackrel{p}{\longrightarrow} B$ Executing action $A$achieves precondition $p$ for action $B$ .

   Means $p$ must remain $\text{true}$ from time of action $A$ to the time of action $B$ .

   Otherwise there is a conflict$C$ that causes the effect $\neg p$ .

   ie:$\text {RightSock} \stackrel{\text {RightSockOn}}{\longrightarrow} \text {RightShoe}$

4. set of open preconditions

   Minimizing open preconditions (= preconditions not achieved by an action in the plan)

Partial order planning POP Algorithm

Defines execution order of plan by searching in the space of partial-order plans.

Returns a consistent plan : without cycles in the ordering constraints and conflicts in the casual links.

1. Initiating empty plan

   only contains the actions:

   $\text{Start}$ no preconditions, effect has all literals, all preconditions are open, no casual links

   $\text{Finish}$ has no effects, no open preconditions

   ordering constraint: $\text { Start} \prec \text {Finish}$

   no casual links

2. Searching

   2.1 successor function: repeatedly choosing next possible state.

   Chooses an open precondition $p$ of action $B$ and generates a successor plan (subtree) for every consistent way of choosing an action $A$ that achieves $p$ .

   2.2 enforce consistency by defining new casual links in the plan:

   $A \stackrel{p}{\longrightarrow} B, \space A \prec B$

   If$A$is new:$\text{Start} \prec A \prec\text{Finish}$

   2.3 resolve conflicts

   add $(B\prec C) \wedge (C\prec A)$

   2.4 goal test

   because only consistent plans are generated - just check if preconditions are open.

   If goal not reached, add successor states

Alternatives

Graphplan

Based on graphical data structure to extract plans.

• Planning graph = sequence of layers that correspond to time steps in the plan.

• Layer = superset of all the literals or actions that could occur at that time step.

SATPlan

Solve planning problems by translating them into formulas of propositional logic.

Planning as satisfiability.