[Serial vs. parallel planning graphs] Re: homework 3 solutions

[Subbarao Kambhampati <rao@asu.edu>]

At 03:14 PM 10/18/2003, you wrote:

> Hello,
>
> I'm reviewing for the exam on Tuesday and am looking over the
> homework
> solutions.  On problem three of homework 3 where we had to draw
> the
> planning graph and planning graph with mutexes I'm a bit confused. 
> You
> have actions O1 and 03 mutexed as well as O2 and O3.  I don't
> understand
> why as neither the prequisites or the effects seem to conflict in
> either
> case.  Could you help me out a bit
> here?


Good question. 

The graph that is shown in the solutions is a _serial_ planning graph,
which
means that _every pair of non-no-op actions_ is marked mutex (so only
one real action can happen per level. (see the rule 1 in the action
mutexes slide).

------------the rest of the mail is _not_ needed for answering your
question, but...
Now for a related digression.

As we know, the cost of literals is estimated in terms of the level at
which they appear in the 
planning graph (without any mutexes between them). 

Consider a scenario where we have 100 actions 
a1 to a100, each of which give p1 .. p100 respectively. There is one
action a* that takes p1...p100 and gives G. 
We are interested in the cost of G.  It is clear that the plan for
achieving G requries 101 actions (a1...a100 followed by a*).

If we don't mark  every pair of non-no-op actions mutex, then the
plannng graph in essence assumes that 
actions that are not interfering can be done in parallel. Thus G will
appear in level 2 (level 1 will have p1..p100, and thus 
at level 2, a* comes in and gives G). 2 of course is a pretty  steep
under-estimate on the cost of G, which is 101 actions (progression as
well as 
regression searches will need to go 101 depth to get a plan for G). 
 
To avoid this problem, the serial planning graph adds the additional
mutex constraint saying that every pair of non-no-op actions are mutex.
In the above case, 
this will ensure that G will actually appear in level 100. 

===========
One deeper level digression

Having said the above, I should point out that in practice, the improved
estimation of serial planning graph is a mixed blessing. It increases the
cost of heuristic computation (we had to grow the PG to 101 levels before
G came in, instead of just growing it to 2 levels).  More over, the
idea of serial planning graph doesn't make any sense if we are ignoring
mutex propagation. 

For progression planners which don't care as much about -ve interactions,
but do want to estimate the number of actions rather than number of
parallel steps, 
there is another idea that can work--use the normal parallel planning
graph, but extract a plan for supporting the literals, and count the # of
actions in that plan 
--rather than the level--as the cost of the literals. In the example
above, after G comes in at level 2, we proceed to "extract" a
plan for supporting G.

this involves picking actions to support top level goals, and recursively
picking actions to support preconditions of the actions that have been
picked.
 --picking an action to support G (a*)
 --picking actions to support all the preconditions of a*
      --which brings in a1...a100
 
Because we are not considering interactions between actions, this
extraction procedure is polynomial--and gives a much better value.



> Thanks,
> Rich

you are welcome ;-)
Rao
-----------------
  "My student came to me with a desire to know the time, and
    I taught her how to make a watch" 
 
                               
-Chris in Morning (Northern Exposure)