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.
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.
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]).
The full results for the AAAI paper are available here (in pdf).
$
./fdp -NB_STEPS 100 -d domain.pddl -p problem.pddl
-NB_STEPS 100
-d domain.pddl
-p problem.pddl
Other options are also available :
-2SEQ
-TIMELIMIT 100
-PRINT_PROBLEM
-PRINT_SOLUTION
-IPC_OUTPUT
-INIT_RAND 1995
In this version FDP uses the following search strategy: problem decomposition by splitting the left most non singleton domain.
(dom/prob) naa nff [opts len/mksp] res chpts rmvls time
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
$
$ 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
$