Progression vs. Regression planner performance on Project 3

[Subbarao Kambhampati <rao@parichaalak.eas.asu.edu>]

Some hardy souls who did the extra credit portion with progression
planner were surprised to find that the progression planner was much
worse than regression planner in terms of performance. They were
surprised because this seemed to be inconsistent with what I said in
class--that current state of the art is that progression planners
perform better (in particular, a planner called FF does better than
regression planners). 

Turns out that there are several explanations as to why progression
planner didn't work as well when you ran it. 

1. My planning graph construction code is woefully slow. I put
   propositions and actions at each level in big long lists. Using
   hashtables (and even better, doing a bi-level planning graph which 
   only keeps track of when each action/prop comes in first) will be
   better.  Since progression planners call the  planning graph code 
   for every child of every node they expand, any inefficiency in the 
   PG code gets multiplied many-fold

2. The compute-pg code, by default, propagates mutexes. As I mentioned 
   while discussing Progression and Regression that mutexes are more
   important for regression than for progression (which already
   generates "legal" states). Since mutex computation and propagation
   takes close to 80% of the time in pg construction, we could
   significantly improve performance by not doing it (there is a
   switch you could have set to disable mutex propagation in my
   code). This is what FF does.

   [[Of course, when you don't to mutex propagation, then in the level
   heuristic computes the number of steps and not the number of
   actions (since many actions can be done per step). To get the #
   actions,  you need to extract a "relaxed plan" from the
   graph. Specifically if the top level goals appear in level k, we
   pick any set of actions for supporting P,Q, then collect their
   preconditions. If these are p1...pn we recurse and pick actions to
   support p1..pn in level k-1 and so on. Once we reach level 0, we
   count the number of actions we picked, and use that as the
   heuristic cost]]

These two optimizations should make progression "competitive" with
regression. FF goes beyond this. One important one is "enforced hill
climbing". What enforced hillclimbing does is--roughly--is to make
introduce multiple actions--in sequence (not in parallel)--at once,
until adding actions starts worsening the heuristic value. This, in theory,
leads to incompleteness, but seems to work quite well in practice. 

That is the story..

rao