To illustrate, figure 5 shows mutexes for the first two levels of the planning graph PG([S.
However, serial planning graphs are not often used in practice because they require a large number of additional mutexes (and also make the planning graph achieve level-off much later).
With mutexes the heuristic value is 2 because the propositions do not appear together without a mutex until [P.
Mutexes were originally introduced in Graph-Plan (Blum and Furst 1995), but Nguyen and Kambhampati (2000) realized their application to adjusting heuristics.
One can correct this problem by propagating mutexes on the planning graph and using the set-level heuristic.
Mutexes play a larger role in regression by improving the ability of search to prune inconsistent partial states.
The approach involves using mutexes to measure the conflict between two goals and adjusting the heuristic measure of cost.
It is also possible to compute mutexes in the temporal planning graph, but they require generalization to deal with concurrent actions that have different durations.
Analogous to their role in classical planning, mutexes can help improve makespan estimates by reducing optimism in the planning graph.
The explicit proposition layers can aid mutex propagation, allowing TPSys to compute more mutexes than Temporal GraphPlan (Garrido, Onaindia, and Barber 2001).
For instance, Sapa adjusts its heuristic to account for negative interactions by using mutexes to reschedule its temporal plan to minimize conflicts, resulting in a better makespan estimate.
Since action layers contain noop actions, technically speaking, mutexes can also exist between actions and propositions (through the associated noop actions), but mutexes are marked only between elements of the same layer.