Notes - Artificial Intelligence MT24, Planning

A logical language for encoding planning problems.

• Predicates: A set of possible predicates (relations) used in formulating the problem.
• Constants: A set of constants (objects) used in formulating the problem.
• States: A set of positive ground atoms describing what holds currently, in terms of these predicates and constants
  • e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Milk})\}$
• Initial state
• Goal: A set of ground atoms to be made true (also allowed a superset):
  • e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Drill})\}$.
• Action: A precondition and postcondition
  • Precondition: What must be true before an action is carried out
  • Postcondition: A set of atoms to be added (appear positively) and a set of atoms to be removed (appear negatively)

• Action: $\text{Buy}(\textit{Drill})$
• Precondition: $\text{At}(\textit{HardwareStore})$, $\text{Sells}(\textit{HardwareStore, Drill})$.
• Postcondition: $\lnot \text{Sells}(\textit{HardwareStore, Drill})$, $\text{Have}(\textit{Drill})$

$x$ might not be an object and $p$ might not be a place. In order to fix this, you need to add new atoms which effectively “type” the variables:

• Action: $\text{Buy}(\textit{x})$
• Precondition: $\text{At}(\textit{p})$, $\text{Sells}(\textit{x, p})$, $\text{IsPlace}(p)$, $\text{IsObject}(x)$.
• Postcondition: $\lnot \text{Sells}(\textit{p, x})$, $\text{Have}(\textit{x})$

STRIPS does not allow negative literals in preconditions of actions, whereas PDDL does.

• Start with a goal state $G$
• Pick an action $A$ that is:
  • Relevant: achieves literal in $G$, so contains a literal $B$ such that $B$ is in $G$
  • Consistent: doesn’t undo a literal in $G$, so the postcondition doesn’t contain a literal $\lnot B$ such that $B$ is in $G$
  • For simplicity, consider actions where variables occuring in the postcondition of the action also occur in the precondition (otherwise searching gets complicated)
• Compute the predecessor state
• Use $A^\ast$ to do this repeatedly until the initial state is reached

• Forward planning:
  • Disadvantage: Many actions can be applicable to a state, so the branching factor is very high.
  • Advantage: Each state is described fully as a set of ground atoms (there are no variables that need filling).
• Backward planning:
  • Disadvantage: Partial state descriptions may contain atoms still in terms of variables.
  • Advantage: It has a lower branching factor and is more goal-oriented (“the fan-in factor is usually lower than the fan-out factor”)
• Partial order planning:
  • Disadvantage: More complex searching process (?)
  • Advantage: It can decompose a planning problem into independent subproblems, each of which can be solved independently.

• Ignore preconditions
  • Every action becomes applicable in every state
• Ignore negative effects
  • No action can remove an atom from the current state
• State abstraction
  • Remove all atoms over some predicate in pre- and post-conditions
• Subgoal independence
  • Split all goal atoms into disjoint subsets, and consider min-cost plans to solve the subsets

Remove all preconditions so that every action in available in every state. This leads to the new action:

• Action: $\text{Slide}(t, a, b)$
• Precondition: …
• Effect: $\text{On}(t, b)$, $\text{Empty}(a)$, $\lnot \text{On}(t, a)$, $\lnot \text{Empty}(b)$

and an optimal solution to this planning problem corresponds to the “number of tiles out of place” heuristic.

(also, this relaxed problem is at least as hard as the $\mathbf{NP}$-hard $\mathbf{SetCover}$ problem, since you’re picking the least number of actions to cover all atoms in the goal, but this could be seen as a good thing as $\mathbf{SetCover}$ has efficient approximation algorithms).

Remove all negative atoms from the effect/postcondition. This leads to:

• Action: $\text{Slide}(t, a, b)$
• Precondition: $\text{Tile}(t)$, $\text{On}(t, a)$, $\text{Adjacent}(a, b)$, $\text{Empty}(b)$
• Effect: $\text{On}(t, b)$, $\text{Empty}(a)$

Drop all atoms over some predicate. In the case of the $\text{Empty}$ predicate, this is

• Action: $\text{Slide}(t, a, b)$
• Precondition: $\text{Tile}(t)$, $\text{On}(t, a)$, $\text{Adjacent}(a, b)$
• Effect: $\text{On}(t, b)$, $\lnot \text{On}(t, a)$

The optimal solution to this relaxed problem corresponds to the Manhattan distance heuristic.

• Let $G _ 1, \ldots, G _ n$ be disjoint subsets of goal atoms.
• Let $P _ 1, \ldots, P _ n$ be min-cost plans that achieve $G _ 1, \ldots, G _ n$

Then take as heuristic

Instead take as heuristic

This is possible when the plans $P _ i$ and $P _ j$ are independent, i.e. the effects of actions in $P _ i$ leave the preconditions and effects of all actions in $P _ j$ unchanged.