
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.

	Peter van Beek
	Department of Computer Science
	University of Waterloo
	Waterloo, Ontario, Canada  N2L 3G1
	Email: vanbeek@uwaterloo.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 domain independent CSP solving code:

	cd Share
	make

    Compile the code for a particular planning 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).



Directory Contents
==================

    The directory "Share" 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 conflict-
	directed backjumping upon hitting a dead end.

    The constraint programming methodology has been applied to five
    planning domains: 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 logistics domain has the following
    files:

	Problems	- directory with planning instances
	logistics.c	- procedures for reading in an instance
	logistics.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.

