Graphplan: mutexes and example

There are two types of binary mutual exclusion relations (called mutex) in Graphplan.
  1. mutexes between pairs of actions. They are marked between actions at the action levels (S0, S1, etc). The actions in the pair can be maintenance actions (or, as they are called in the texbook, persistence actions) or other actions, since from the point of view of being in a mutex the type of action does not make any difference. the
  2. mutexes between pairs of propositions. They are marked at the proposition levels (S0, S1, etc).

Extraction of a solution

To know if a solution has been reached the first step is to see if the propositions in the goal are all present at the current level and none are pairwise mutex. If not the planning graph needs to be expanded by adding another action and another proposition level. The existence of all the goal propositions at the current level is a necessary but not sufficient condition for having a solution.
The next step is to try to extract a solution. Here is where the mutexes are used to see if there is a consistent (i.e. with no mutexes) way of achieving all the subgoals. This is done as a search process that starts at the current level and searches backwards subgoal by subgoal and level by level. If the search fails after having tried all the ways of achieving each subgoal in every possible way, Graphplan extends the planning graph and tries again.

Graphplan example

Given the following STRIPS action schemas, initial state, and goal:

Action:MakeDrink,
    Precond: CleanCup ∧ HaveMilk
    Effect: HaveDrink ∧ ¬ CleanCup ∧ ¬ HaveMilk

Action:Drink,
    Precond: Thirsty ∧ HaveDrink
    Effect: Happy ∧ ¬ Thirsty ∧ ¬ HaveDrink

Initial State: Thirsty ∧ CleanCup ∧ HaveMilk

Goal: Happy

    The planning graph is

    drink example

    The goal is reached at level S2 with the action Drink. The action Drink can be done after the action MakeDrink, which can be done in the initial state S0.

    Copyright: © 2015 by the Regents of the University of Minnesota
    Department of Computer Science and Engineering. All rights reserved.
    Comments to: Maria Gini