Copyright ========= CPlan solves planning problems formulated as constraint satisfaction problems. Copyright (C) 1999 Peter van Beek and Xinguang Chen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details (in the file called Copying or contact the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA). I would appreciate receiving any bug fixes or enhancements that you make. I am especially interested in CSP models of new planning domains or improvements to the models for the existing domains. Address correspondence to: Peter van Beek School of Computer Science University of Waterloo Waterloo, Ontario, Canada N2L 3G1 Installation ============ First, gunzip and untar the file CPlan.tar.gz in a convenient location. The code has been successfully compiled using the gcc compiler under Linux, Solaris, and NT. For other systems, the code in Share/timer.c may need to be rewritten. For other C compilers, some local variable definitions may need to be changed (gcc allows "int a[n]", where n is a variable, other compilers require a fixed maximum size such as "int a[50]"). Compile the code that is common to each of the domains: cd Share make Compile the code for a particular domain. For example, cd logistics make Now you can solve some planning instances using either of the two solvers: solve_GAC or solve_GAC_CBJ. The "Problems" directory for each domain contains the instances from the AIPS'98 planning competition. The input format for planning instances is very restrictive and idiosyncratic to each domain (it was chosen to make our programming task simpler, not to be robust). If you want to run the planner on new instances, you will have to convert or write the problems to this syntax (see the existing instances for examples). Directory Contents ================== The constraint programming methodology has been applied to five planning domains: blocks world, grid, gripper, logistics, and mystery (and mprime). Each has its own directory and the files under each directory have a common structure. For example, the blocks world domain has the following files: Problems - directory with planning instances blocks.c - procedures for reading in an instance blocks.h and answering queries about it check.c - procedures for checking constraints generate.c - procedures for generating the CSP main.c - main program process.c - procedures for printing out a solution If you want to apply the approach to a new domain, these are the the files that must be rewritten or adapted. As well, there is a directory "Share" which contains the domain independent CSP solvers and some miscellaneous auxilliary routines. There are two solvers: solve_GAC contains a backtracking search algorithm which maintains a mixture of forward checking and generalized arc consistency at each node in the search and which does chronological backtracking upon hitting a dead end. solve_GAC_CBJ is like solve_GAC, except that it does more sophisticated backjumping upon hitting a dead end. This is the algorithm that was used in the experiments reported in the paper. References ========== Bacchus, F., and Kabanza, F. 1998. Using temporal logics to express search control knowledge for planning. Unpublished manuscript. Bacchus, F. 1998. TLPlan, (September, 1998). http://logos.uwaterloo.ca/~fbacchus. Baptiste, P., and Le Pape, C. 1995. A theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling. In IJCAI-95, 600--606. Blum, A. L., and Furst, M. L. 1997. Fast planning through plan graph analysis. Artif. Intell. 90:281--300. Bockmayr, A., and Dimopoulos, Y. 1998. Mixed integer programming models for planning problems. In CP98 Workshop on constraint problem reformulation. Bonet, B., and Geffner, H. 1998. HSP, (August, 1998). http://www.ldc.usb.ve/~hector. Fox, M., and Long, D. 1999. The detection and exploitation of symmetry in planning domains. Technical Report 1, Durham University, UK. Gerevini, A., and Schubert, L. 1998. Inferring state constraints for domain-independent planning. In AAAI-98, 905--912. Kautz, H., and Selman, B. 1992. Planning as satisfiability. In ECAI-92, 359--363. Kautz, H., and Selman, B. 1996. Pushing the envelope: Planning, propositional logic, and stochastic search. In AAAI-96, 1194--1201. Kautz, H., and Selman, B. 1998a. Blackbox, Version 3.1. http://www.research.att.com/~kautz. Kautz, H., and Selman, B. 1998b. The role of domain-specific knowledge in the planning as satisfiability framework. In Proc. of the 4th Int'l Conf. on AI Planning Systems (AIPS-98). Koehler, J., and Nebel, B. 1998. IPP, Version 3.3. http://www.informatik.uni-freiburg.de/~koehler. Marriott, K., and Stuckey, P. J. 1998. Programming with Constraints. The MIT Press. Nebel, B.; Dimopoulos, Y.; and Koehler, J. 1989. Ignoring irrelevant facts and operators in plan generation. Technical Report 88, Albert Ludwigs University. Prosser, P. 1993. Hybrid algorithms for the constraint satisfaction problem. Comput. Intell. 9:268--299. Van Hentenryck, P. 1989. Constraint Satisfaction in Logic Programming. MIT Press.