FDP : Filtering and Decomposition for Planning

Stéphane Grandcolas & Cyril Pain-Barre
Laboratoire des Sciences de l'Information et des Systèmes (LSIS)
UMR CNRS 6168
Domaine Universitaire de Saint-Jérôme
Avenue Escadrille Normandie-Niemen
F-13397 MARSEILLE CEDEX 20 France

Summary

FDP is a planning system based on the paradigm of planning as constraint satisfaction, that searches for optimal sequential plans.

FDP does not use any external solver. Insteed, it integrates its own consistency rules and filtering and decomposition mechanisms that are specifically designed for the purpose of planning.

It works directly on a structure related to Graphplan’s planning graph: given a fixed bound on the length of the plan, the graph is incrementally built. Each time the graph is extended, a search for a sequential plan is made. The solutions returned are optimal in terms of the number of actions.

The input langage is PDDL with typing and equality.

Planning competition

FDP has competed in the optimal planning deterministic track of the 5th International Planning Competition, co-located with ICAPS-2006.

It was evaluated as the second best planner on 3 domains over 7.

Papers

This work has been published in the workshop "Constraint Satisfaction Techniques for Planning and Scheduling Problems" held in conjunction with ICAPS-2006 [pdf] [bib].

It has also been published in the french conferences JFPC 2006 [pdf] [bib] and JFPDA 2006 [pdf[bib].

It was also accepted for publication in AAAI'07 [pdf] [bib] (slides of the talk [pdf]).

Experimental Results for AAAI'07

The full results for the AAAI paper are available here (in pdf).

Download

fdp binary version for PC x86 on Linux

Usage

The program should be run for example in the following way :

$ ./fdp -NB_STEPS 100 -d domain.pddl -p problem.pddl

where
indicates that 100 is the maximum length/number of actions of the searched plan
indicates the domain (the definitions of the operators) must be read in the file domain.pddl
indicates the problem (the definitions of the initial state and of the goals) must be read in the file problem.pddl.

Other options are also available :

to avoid the construction of unordered 2-sequences
to fix the cpu time limit at 100
to print the problem
to print the solution plan
to comply with the IPC output policy. With this option a new file is created in the directory of the problem file, whose name is the problem name with the extension .soln
to fix the pseudo-random number generator (this should not be of interest however with the domain splitting decomposition).

In this version FDP uses the following search strategy: problem decomposition by splitting the left most non singleton domain.

Output

The output of fdp has the following form :

(dom/prob) naa nff [opts len/mksp] res chpts rmvls time

where :

Examples

Here is an example of fdp output when launched on a problem that has no solutions in less that the required length (it is hanoi problem with 7  discs) :

$ fdp -d domain.pddl -p problem7.pddl -NB_STEPS 100
(hanoi/hanoi7) 238a 94f [fs-Ss4p-Ms-left 100/0]  X  131996 38346751 14.54s
$

Here is an example of fdp output when launched on a problem that has at least one solution :

$ fdp -d domain.pddl -p problem7.pddl -NB_STEPS 150
(hanoi/hanoi7) 238a 94f [fs-Ss4p-Ms-left 127/127]  O  247209 71523900 27.26s
$

Here is an example on the same domain (but with 3 discs) with the printing of the solution :

$ fdp -d domain.pddl -p problem3.pddl -NB_STEPS 150 -PRINT_SOLUTION
(hanoi/hanoi3) 38a 30f SOLUTION :
1:move(d1, d2, peg3)
2:move(d2, d3, peg2)
3:move(d1, peg3, d2)
4:move(d3, peg1, peg3)
5:move(d1, d2, peg1)
6:move(d2, peg2, d3)
7:move(d1, peg1, d2)

[fs-Ss4p-Ms-left 7/7]  O  63 4408 0.00s
$

Sample files