Mutexes in Graphplan and their use to find a plan

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 conditions 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.