The differing mutex propagation rules in my lectures vs. Russell's chapter

[Subbarao Kambhampati <rao@asu.edu>]

Several of you have pointed out that I use an extra rule for detecting 
action mutexes, compared to Russell's description of mutex propagation, and 
wondered which one you should use for the homework question.

The simple answer is: Use Rao's rules

Here is a longer explanation of why...

---------

Start by noting that the only difference in the mutex prop rules is that I 
have an extra rule saying that any pair of non-no-op actions are mutually 
exclusive.

This extra rule encodes the fact that our plans are are "sequential" with 
one action done per time step. This increases the mutexes in the graph, and 
thus the level of a set S of propositions will be higher for me than for a 
plan graph constructed with russell's rules. [Call this "serial planning 
graph"]

Without this rule, you will be estimating the lengths of "parallel plans" 
to achieve a given set of literals. A parallel plan is one which can 
contain multiple non-interfering actions per time step. [Planning graphs 
were originally introduced in Graphplan, and Graphplan focused on building 
parallel plans.]

The level of a set S of literals in both parallel planning graph or serial 
planning graph is a provable lowerbound on the true length of the plan to 
achieve S. However, since in normal state search (progression or 
regression) we are interested in finding sequential plans, and for 
any  given problem, the length of parallel plan is less than or equal to 
the lengh of sequential plan, level in serial plan will be a more informed 
heuristic for our purposes.

[[If you are trying to compute parallel plans using progression or 
regression, then you should use level in parallel plan graph (since the 
other one will be inadmissible). However, it turns out that any obvious way 
of trying to construct parallel plans using progression or regression will 
quickly become infeasible since we will have to consider regression and 
progression not on single actions, but on sets of non-interfering actions. 
Given n actions, there will be 2^n subsets of actions to consider in the 
worst case--and this sheer branching factor kills progression/regression 
planners.]]

Rao