Running IPP

How IPP Works

IPP finds parallel plans, i.e. plans in which actions that do not interfere with each other are planned simultaneously. All actions, however, are assumed to take the the same amount of time (or, alternatively, duration is simply not taken into account), so the the plan will consist of a sequence of "time steps", with one or more actions in each step. Plans found by IPP are optimal w.r.t. the number of time steps.

IPP is based on the Graphplan approach, which means it performs iterative deepening A^* search using an admissible heuristic. To compute the heuristic, Graphplan and related planners build a levelled graph structure which presents an "optimistic" view of the set of reachable states: to be precise, if a set of facts F are found at level k in the graph, it may be possible to reach a state in which all the facts in F are true in k time steps, but it is not guaranteed. If, on the other hand, all facts in F are not found at level k, it is guaranteed that there exists no plan with k or fewer time steps that achieves all the facts in F. Therefore, the planner starts by building the graph, level by level, until a level is reached in which all the goal facts can be found. Then, a backward search through the graph is made to check if the goals are actually reachable, and to find a plan if that is the case. If this fails, the graph is extended another level and the backward search tried again.

The graph constructed has the property that the set of "maybe reachable facts" is monotonically increasing with each level, so at some point, all possibly reachable facts will be included and extending the graph by another level will give nothing new. If at this point, all the goal facts are not found in the last level, the goal is provably unreachable and the planner exits.

Input

IPP accepts PDDL input, including some parts of ADL: it accepts quantified and conditional effects, and quantified preconditions and goals. It also accepts :typing, but seems to have problems with type hierarchies (i.e. where there are subtypes of types).

Output

Typically, IPP's output will look like the following: After some preamble (files read, etc.) comes the initial graph construction phase:


time:   0,    51 facts and       0 exclusive pairs
              57 ops   and      14 exclusive pairs
time:   1,    62 facts and      15 exclusive pairs
              78 ops   and     129 exclusive pairs
        .
        .
        .

time:  11,    90 facts and     144 exclusive pairs

goals first reachable in 11 time steps

From the first level where the goal facts are found, backward search is tried at each level. Eventually, all possibly reachable facts are in the graph (the graph "levels off"). At this point, IPP starts using something called a "wave front", which is a more memory-efficient representation for the graph:


             156 ops   and    1812 exclusive pairs
time:  12,    90 facts and     144 exclusive pairs (   39,     141 positives)

graph has leveled off! wave front mechanism is taking over

If the problem instance is solvable, the planner eventually reaches a level at which the backwards search succeeds and it finds a plan:


expanding wave front to level   13

found plan as follows:

time step    0: LOAD PACKET2 TRUCK3 OFFICE3
                DRIVE TRUCK2 AIRPORT2 OFFICE2 CITY2
                FLY AIRPLANE1 AIRPORT1 AIRPORT3
                DRIVE TRUCK1 AIRPORT1 OFFICE1 CITY1
time step    1: LOAD PACKET1 TRUCK1 OFFICE1
                DRIVE TRUCK3 OFFICE3 AIRPORT3 CITY3
                LOAD PACKET3 TRUCK2 OFFICE2
       .
       .
       .

Some clues about the behaviour of IPP on a particular problem can be elucidated from the output:

If the number of facts in each new graph level grows very quickly, the problem has a high branching factor. This leads to a large search space, and causes the planner problems (since both graph construction and search take more time).
If the difference between the level where goal facts are first found and the level where a plan is actually found is large, this indicates that the heuristic encoded in the graph is not very informative (it underestimates the problem difficulty too much).