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

```
 -NB_STEPS 100 
```

indicates that 100 is the maximum length/number of actions of the searched plan

```
 -d domain.pddl
```

indicates the domain (the definitions of the operators) must be read in the file domain.pddl

```
 -p problem.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 :

```
 -2SEQ
```

to avoid the construction of unordered 2-sequences

```
 -TIMELIMIT 100
```

to fix the cpu time limit at 100

```
 -PRINT_PROBLEM
```

to print the problem

```
 -PRINT_SOLUTION
```

to print the solution plan

```
 -IPC_OUTPUT
```

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

```
 -INIT_RAND 1995
```

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 :

dom is the domain name
prob is the problem name
na is the number of actions of the problem
nf is the number of facts (propositions) of the problem
opts is a summary of the options
len is the length of the plan (number of actions)
mksp is only informative and does not correpond to an optimal makespan. It is just trivially deduced from the solution
res is the result of the search : It can be X (the problem has no solutions, given the maximal length) or O (the problem has at least one solution)
chpts is the number of choice points made by the search procedure
rmvls is the number of removals made by propagation
time is the cpu time in seconds

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

domain.pddl is the file containing a PDDL description of the Hanoi domain
problem3.pddl is the file containing a PDDL description of the Hanoi problem with 3 discs
problem7.pddl is the file containing a PDDL description of the Hanoi problem with 7 discs