Running IPP
How IPP Works
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.
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.
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).
Running IPP
IPP is started with the command
/home/TDDC17/bin/ipp -o <domain file> -f <problem file>
More options are available: run ipp without arguments
for a list.
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).
Known Problems
IPP, like FF, requires all the arguments to an operator to be different,
i.e. an action such as (move A B A) is considered
impossible regardless of the domain definition. This can cause a problem
in some domains: see
slidetile.pddl and
eight01.pddl for an example,
and eight01x.pddl for a
possible solution.