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