Welcome to the Homepage of IPP

1997 - 1999

Project History:

After the Dagstuhl Workshop on Control of Search in Planning, Jana Koehler decided to develop her own planning system as the topic of her habilitation thesis. It began with an extension of GRAPHPLAN by Avrim Blum and Merrick Furst to the ADL planning language handling conditional effects and more expressive preconditions. The first algorithm prototypes were discussed with Bernhard Nebel and Yannis Dimopoulos and soon the IPP planning system began to emerge. Bernhard Nebel later contributed the RIFO strategy to IPP. In march 1997, three students, Jörg Hoffmann, Frank Rittinger, and Michael Brenner, joined the team and implemented the first protopye of IPP as well as the subsequent revised versions.

Version 3.3 won the ADL track of the First International Planning Systems Competition in 1998. In 1998, a first investigation into metric planning/resource-constrained planning started and experimental algorithms were implemented. At the same time, the whole IPP system was reimplemented, which required more effort than expected. Jörg Hoffmann took mainly care of this. Andreas Schön and Dietmar Jäckle joined the team temporarily in 1999 and contributed to the reimplementation resulting in IPP version 4.0. To enter the 2nd Planning Competition 2000, RIFO was integrated into IPP again and several bugs were fixed resulting in IPP 4.1.

Between July 1997 and December 1998 IPP source code has been downloaded more than 200 times and the system has been used in several other projects. IPP was also used in two commercial environments: at Schindler for rapid prototyping of elevator domain models and at Celcorp as a source for own planning software development. In 2008, the first publication on IPP received a Honorable Mention for the ICAPS Influential Paper Award.

Source Code Available

  1. IPP 4.1 as of 5/1/00. This is the last version of IPP fixing bugs in release 4.0 and containing RIFO again. This version takes only PDDL syntax as input. The source code also contains files for the original IPP syntax, but they are not used anymore.
    ATTENTION! The IPP parser uses the bison/flex software. The parser dates back to 1996, and unfortunately bison/flex versioning is not downwards compatible. If you experience compilation problems, please do NOT contact me or Joerg by email, were are not ablt to help much. One thing you can try is to use bison 1.25 and flex version 2.5.4 (probably the versions we used at this time). You might also have to comment out the "void fcterr( int errno, char *par );" declaration at the start of "scan-fct_pddl.c ".
    Note that you need to specify full names of files (which can be arbitrary) in the -o and -f arguments, while in IPP 1.0 to 3.3 you need to use the .ops extension for operator files and the .fct extension for factfiles, which are omitted in the -o and -f arguments). The main differences to version 3.3 are
    1. true negation, i.e. we have positive and negative atoms represented in the graph and goal sets are checked for consistency,
    2. an improved parser for PDDL-ADL including a correct normal form computation for general FOL formulas without function symbols,
    3. the new instantiation algorithm handling inertia, which encodes ground operators (actions) and states as bitvectors,
    4. the implicit graph representation, which generates only a single action and fact layer.
  2. IPP 3.3 as of 6/1/98 won the ADL track of the planning competition having improved performance and memory management compared to version 3.2. This version above takes IPP syntax as input. To download the competition variant using PDDL as input language follow this link. Syntax descriptions for operators and fact files for versions 3.0 to 3.3.

Domains: Elevator domain variants, PDDL examples, old PDDL handbook, domains from the 1st planning competition, domains for IPP 3.0-3.3, domains using resources (see also the RIPP entry below)

Only for historical reasons:

  1. IPP 3.2 as of 3/5/98, IPP 3.1 as of 2/6/98, IPP 3.0 as of 11/1/97, IPP 2.0 as of 6/1/97, IPP 1.0 as of 5/1/97 showing all our attempts to get the backward search correctly to handle conditional effects in planning graphs, adding more details to the expressivity, and gradually improving the implementation techniques for subset memoization, mutex computation, and graph search.
  2. RIPP 0.1 as of 10/1/97. This is a very prototypical implementation of IPP with resources. The algorithm is incomplete and extremely slow. Some domains using resources. A description of the syntax of operators and fact files that can be parsed. Note that equations are not supported by the algorithm.

Publications related to IPP and links to additional webpages that explain some of the IPP features in more detail and also contain code for XGV, the graphical displayer for planning graphs, and IPP 3.3 with the goal agenda manager integrated.

The future: Development of IPP has stopped in 1999. Many new techniques are available, which would have been worth integrating into the algorithm, e.g. the techniques for TIM and STAN developed by Maria Fox and Derek Long and their approach on detecting symmetries (see their IJCAI-99 paper).

Many of the IPP ideas were further pursued in the FF planner developed by Joerg Hoffmann, which became one of the best heuristic forward search planners.

Besides this, it seemed to be worth to get rid of Graphplan's no-ops and build planning graphs that are no-op free, because no-ops cause a huge overhead in the computation of mutexes. In many domains, one has just a few hundred "real" ground actions, but many thousands facts each of them requiring a no-op. I also argue that keeping a disjunctive normal form of preconditions could be more effective than the conjunctive normal form and that different disjunctive preconditions should be separated into different actions. Both changes will require a modification of the backward search algorithm.

As for planning with metric constraints, I believe that using planning graphs and a backward search algorithm is not the most promising way to go. To solve such problems, which are extremely important for practical applications of planning systems, a forward searching algorithm appears more promising to me.

Jana Koehler, 02/Feb/2009