POPF

POPF is forwards-chaining temporal planner. Its name derives from the fact that it incorporates ideas from partial-order planning — during search, when applying an action to a state, it seeks to introduce only the ordering constraints needed to resolve threats, rather than insisting the new action occurs after all of those already in the plan. Its implementation is built on that for the planner COLIN, and it retains the ability to handle domains with linear continuous numeric effects.

The source code for POPF is available to download from the POPF sourceforge repository. The latest version available, POPF2, corresponds to POPF2 from the 2011 International Planning competition plus fixes for a few bugs that have been found since then.

PDDL Supported

POPF supports a substantial portion of PDDL 2.1 level 5, including actions with (linear) continuous numeric effects and effects dependent on the durations of the actions. Its support for ADL, though, is limited: in the general case, it cannot handle negative preconditions, disjunctive preconditions, conditional effects etc. As a compromise, it will attempt to preprocess ADL preconditions and effects into STRIPS-like conjuncts, through grounding existential quantifiers, and using some simple elimination rules for static facts), which allows it to support a few useful PDDL constructs, including:

• forall quantifiers, where the resulting clause is obviously a conjunct, e.g. the precondition:

  (forall (?to - truck) (and (some conjunct of facts on ?to)))

  ... or the effect:

  (forall (?r - resource) (assign (level ?v ?r) 0))

• implications, where the antecedent is a static fact
• equality
• negation of static facts, including equality

Compiling POPF

POPF should be fairly easy to compile. To build it, you will need:

• cmake
• the CBC mixed integer programming solver
• perl, bison and flex (used to build the parser)

Packages of these are available for most linux distributions. For Ubuntu, the following should install CBC and the other build pre-requisites:

sudo apt-get install cmake coinor-libcbc-dev coinor-libclp-dev \
                              coinor-libcoinutils-dev coinor-libosi-dev coinor-libcgl-dev doxygen bison flex
                              

Once these are installed, download the source archive from the POPF sourceforge repository, unpack it, and run:

            cd tempo-sat-popf2
                              ./build
                            

Running POPF

Once POPF has been compiled, from within the tempo-sat-popf2 directory, run:

./plan domain.pddl problem.pddl solutionfilename
                  

As POPF is an any-time planer, it will save sequentially numbered plans.

Benchmarking Using POPF

We welcome the use of POPF as a benchmark system for temporal planning in the scientific literature.  When using POPF as a benchmark system there are several important considerations to take into account.  The first is that POPF is an expressive PDDL 2.1 temporal planner, and is therefore reasoning with a harder problem than any planner that simply compresses actions.  Generally this is not a major problem, however, significant issues do arise when actions can self-overlap (or overlap other related actions, e.g. Move A B can overlap Move A C).  This has, in fact, been shown by Rintanen to change the complexity of temporal planning from PSPACE complete to EXPSPACE complete.  Such domains cause the performance of POPF (and related planners) to decrease dramatically, as it is reasoning with many plans that simply are not considered by other planners due to their incompleteness.  It has been shown that it is rare to achieve a realistic situation in which self-overlapping actions would be necessary, Fox and Long "A Note on Concurrency and Complexity in Temporal Planning" (we are very interested to hear from anyone who has a compelling application for them).  However, such actions often appear in the benchmark domains due to modelling bugs; these have been previously unnoticed since no planners supported self-overlapping actions.  These bugs make the domain semantically incorrect, as well as unnecessarily hard for POPF to solve.  We therefore request that if you use POPF (COLIN/OPTIC or CRIKEY3) for benchmarking on any of the following domains, you use these debugged versions of the IPC temporal domains.

Domains: Airport Strips Time, TPP Metric TIme, Rovers Simple Time, Rovers Metric Time, Rovers Time, Transport Time, Openstacks Time, Openstacks Metric Time, Zeno Simple Time, Zeno Time.

For those interested in developing a better understanding, consider the following action:

(:durative-action move 
:parameters (?from ?to)
:duration (= ?duration 10)
  :condition (at start (at ?from))
             
 :effect (and
             (at end (not (at ?from)))
             (at end (at ?to))
 )
)

This is a common modelling mistake, and, supposing we have (at A) in the initial state the following action sequence is applicable:

0.001: (move A B)
0.002: (move A C)
0.003: (move A B)

Most temporal planners do not allow self-overlapping actions, so will not consider overlapping (move A B) with itself.  Many other temporal planners also would not consider overlapping (move A B) with (move A C), as they simplify the temporal semantics in a way that avoids this issue. However, the model does allow this so POPF must consider it to preserve completeness.  Note also that the state resulting from the execution of these actions also contains (at B) and (at C) meaning that generally the model is incorrect. It is therefore important to ensure delete effects go at the start of actions where appropriate to prevent self overlaps, and avoid incorrect models.  Modelling the action thus aleviates the problem:

(:durative-action move 
:parameters (?from ?to)
:duration (= ?duration 10)
  :condition (at start (at ?from))
             
 :effect (and
 (at start (not (at ?from)))
 (at end (at ?to))
 )
)

If you find any other temporal domains with self-overlapping actions caused by modelling bugs we would be interested to hear from you.

Bugs

The code for POPF is now quite mature, and each release is tested against a library of several hundred test-cases. But, there will almost certainly still be some outstanding bugs, and we'd welcome any feedback you have.  Known bugs are:

• Using 'over all' conditions that refer to timed initial literals fails in some cases.  The timed initial literal code in POPF is relatively un-tested, due to a lack of benchmark domains.  This was improved somewhat when working on OPTIC, when we wrote several such domains ourselves.  As such, if you have this problem, the bug fix is to download and install OPTIC.

The three most common causes of bugs (over 90% of bug reports) are:

• Using ADL. As noted above, POPF doesn't particularly support ADL, so using it tends to cause it to report problems as being unsolvable.
• Domain modelling bugs. POPF supports the full start--end semantics of PDDL 2.1, and self-overlapping actions, so errors in the temporal placement of preconditions and effects (at start, at end etc.) are more likely to cause issues with POPF than with other planners. For instance, if a 'move' action is written (erroneously) as deleting the old location at the end (rather than at the start), then POPF will consider concurrent move actions for the same vehicle; whereas planners which do not make as clear a distinction between the start and end-points of durative actions would not consider this. Thus, in domains with errors such as this, POPF might have to consider a far larger search space than other temporal planners.
• If POPF is producing plans, but they do not validate, ensure you are passing the '-t 0.001' flag to VAL: POPF uses an epsilon value of 0.001, smaller than the default 0.01 value used in VAL.

If all else fails, find as small as possible a domain and problem file that causes the error you're observing, and email it to Andrew Coles.

Publications

The original paper on POPF, explaining how its search space is structured:
"Forward-Chaining Partial-Order Planning." A. J. Coles, A. I. Coles, M. Fox, and D. Long. Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS-10). May 2010. PDF (BibTeX) (Slides)

A paper explaining the modifications in POPF2 to support cost-optimisation:
"Cost-Sensitive Concurrent Planning under Duration Uncertainty for Service Level Agreements." A. J. Coles, A. I. Coles, A. Clark, and S. T. Gilmore. Proceedings of the Twenty First International Conference on Automated Planning and Scheduling (ICAPS-11). June 2011. Abstract (BibTeX)