[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Progression vs. Regression planner performance on Project 3
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