ICAPS Conference 2000 Conference Paper
- Minh Binh Do
- Subbarao Kambhampati
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 quite competitive with both standard Graphplan and Blackbox system, which compiles planning graphs into SAT encodings. We discuss the many advantages offered by focusing on CSP encodings rather than SAT encodings, including the fact that by exploiting implicit constraint representations, GP-CSP tends to be less susceptible to memory blow-up associated with methods that compile planning problems into SAT encodings. Our work is inspired by the success of van Beek & Chen’s CPLAN system. However, in contrast to CPLAN, which expects handcoded 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. learning and dependency directed backtracking strategies from CSP to backward search phase of Graphplan. More recently, researchers from CSP have started taking interest in applying constraint programming to classical planning. van Beek & Chen [30] describe a system called CPLAN that achieves impressive performance by posing planning as a CSP problem. However, an important characteristic (and limitation) of CPLAN is that it expects a hand-coded encoding–humans have to setup a domain and problem encoding independently for each problem and domain. In this paper, we propose a different route to exploiting the similarities between the planning graph and CSP problems. We describe an implemented planner called GP-CSP that solves the planning graphs by automatically converting them into CSP encodings. GP-CSP generates implicitly specified constraints wherever possible, to keep the encoding size small. The encoding is then passed onto the standard CSP solvers in the CSP library created by van Beek[29]. Our empirical studies show that GP-CSP is significantly superior to Graphplan as well as Blackbox which compiles planning problems into SAT encodings. While GP-CSP’s dominance over standard Graphplan is in terms of runtime, its advantages over Blackbox’s SAT encodings include improvements in both runtime and memory consumption. The relative advantages of GP-CSP can be easily explained: Unlike the backward search in standard Graphplan, GP- CSP is not constrained by any directional search, and is able to to exploit all standard CSP search techniques straight out of the box. This involves nondirectional search [24] as well as speedup techniques such as arc-consistency, dependency directed backtracking, explanation-based learning and a variety of variable ordering techniques. In practice, GP-CSP is found to be orders of magnitude faster than standard Graphplan on many benchmark problems.