GP-CSP Home Page

Abstract

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.

Paper

Here is a longer version of a paper presented at AIPS-2000 This version is going to appear in Artificial Intelligence journal.

Talk

Here are the slides from a talk on GP-CSP given at AIPS-2000

Code

Here is the code for GP-CSP

Minh Binh Do

Last modified: Sun Oct 28 11:01:32 MST 2001