GP-CSP Home Page
Although the deep affinity between Graphplan's backward search, and the process
of solving constraint satisfaction problems has been noted earlier,
these relations have hither-to been primarily used to adapt CSP search
techniques into the backward search phase of Graphplan.
This paper describes GP-CSP, a system that does
planning by automatically converting Graphplan's planning graph into a
CSP encoding, and solving the CSP encoding using standard CSP
solvers. Our comprehensive empirical evaluation of GP-CSP demonstrates
that it is superior to both standard Graphplan and Blackbox system, which
compiles planning graphs into SAT encodings. Our results show that
CSP encodings outperform
SAT encodings in terms of both space and time requirements. The space
reduction is particularly important as it makes GP-CSP less
susceptible to the
memory blow-up associated with SAT compilation methods.
Our work is inspired by the success of van Beek and
Chen's CPLAN system. However, in contrast to CPLAN, which expects
hand-coded CSP encodings for individual domains and problems, GP-CSP
is able to take domain descriptions in STRIPS (PDDL) representation,
and automatically generate the CSP encodings.
Here is a longer version of a paper presented at AIPS-2000
This version is going to appear in Artificial Intelligence journal.
are the slides from a talk on GP-CSP given at AIPS-2000
Here is the code for GP-CSP
Minh Binh Do
Last modified: Sun Oct 28 11:01:32 MST 2001