What's going on
Graphplan takes the initial conditions and operator
definitions and uses them to construct a leveled graph. The initial
conditions are the first level of the graph. The next level consists
of actions that might be performed at time 1. The level after that consists
of facts that
might be true at time 2. The level after that is actions that might
be performed at
time 2, etc. In the animation, the initial conditions are in a column
at the left edge of the page and the levels go left to right.
When we create the graph, we also propagate exclusion relations left
to right. These are properties of the graph that are used to limit
search. This part is all fairly quick and in any case is polynomial time.
In the searching phase, Graphplan performs a fairly standard sort
of backward-chaining search, but using the information propagated when
creating the graph. This limits the amount of searching performed.
Notice in the animations that the searches get cut off pretty quickly.
One thing to mention: depending on your machine, the time to view the
animation is likely a lot longer than the actual time the program
takes to construct a plan. For instance, even on a slow DEC2100, it
takes less than 1.5 seconds to solve the fixit problem.
avrim@cs.cmu.edu