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 commandMore 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 stepsFrom 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 overIf 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,
Page responsible: Fredrik Heintz
Last updated: 2019-09-24