
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
	Department of Computing Science
	University of Alberta
	Edmonton, Alberta, Canada  T6G 2H1

	vanbeek@cs.ualberta.ca



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.

