     THIS SOURCE CODE IS SUPPLIED  ``AS IS'' WITHOUT WARRANTY OF ANY KIND, 
     AND ITS AUTHOR AND THE JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 
     (JAIR) AND JAIR'S PUBLISHERS AND DISTRIBUTORS, DISCLAIM ANY AND ALL 
     WARRANTIES, INCLUDING BUT NOT LIMITED TO ANY IMPLIED
     WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, AND
     ANY WARRANTIES OR NON INFRINGEMENT.  THE USER ASSUMES ALL LIABILITY AND
     RESPONSIBILITY FOR USE OF THIS SOURCE CODE, AND NEITHER THE AUTHOR NOR
     JAIR, NOR JAIR'S PUBLISHERS AND DISTRIBUTORS, WILL BE LIABLE FOR 
     DAMAGES OF ANY KIND RESULTING FROM ITS USE.  Without limiting the 
     generality of the foregoing, neither the author, nor JAIR, nor JAIR's
     publishers and distributors, warrant that the Source Code will be 
     error-free, will operate without interruption, or will meet the needs 
     of the user.


Release 1.0 of the Universal Multi-agent Obdd-based Planner.
============================================================

UMOP (Jensen & Veloso, AIPS2000 and Jensen & Veloso, JAIR, vol. 13 2000)  
is a universal planning system for multi-Agent and non-Deterministic
domains. As input UMOP takes a planning problem described in the Non-deterministic 
Agent Domain Language (NADL). The NADL problem is translated to a Kripke structure
search problem. The Kripke structure is represented by a conjunctive partitioned 
transition relation encoded symbolically as a set of Ordered Binary Decision 
Diagrams (OBDDs, Bryant 1986).

Version 1.0 of UMOP includes three universal planning algorithms:
strong planning, strong cyclic planning (Cimatti, Roveri & Traverso 1998) and 
optimistic planning. All of these algorithms perform a BFS backward search using 
efficient OBDD-based algorithms for computing sets of previous states.

Due to the BFS algorithms the universal plans produced are optimal in the number
of expected steps. Please consult the literature for precise definitions of the
properties of the different algorithms.

The UMOP planner uses the BuDDy OBDD Package (Lind-Nielsen 1999). We have 
permission to distribute BuDDY ver. 1.6 in this release (UMOP-1.0/src/buddy16), 
but notice that Buddy has separate copyright terms.


REQUIREMENTS
============

In order to install/solve problems you will need an ANSI C++ compiler
(like g++) and some general unix tools: make, lex, yacc etc. 
The provided source code has compiled on a pentium III running Red Hat Linux 
release 5.2. With a few changes it should also compile on a SPARC 5 or 20 
running Sunos4_1_3 or later. 


QUICK INSTALLATION
==================

1) unpack distribution files, for example

    $ gzip -dc umop-2.0.tar.gz | tar -xvf -

2) If you are using Linux 5.2 on a pentium III then try the precompiled 
   executable in UMOP-1.0/bin. Otherwise:
  
3) run "make" in /UMOP-1.0/src.   


RUNNING SOME INSTANCES
====================== 

A few domains are found in the UMOP-1.0/domains directory 

Here is an example of usage:

1) change to dir UMOP-1.0/domains/gripper.

2) solve instance prob01.pddl using optimistic planning:

    $ ../../bin/umop -d prob01.nadl -a 2


OPTIONS
=======

There are several options for selecting planning algorithms and 
controlling the partitioning of the transition relation. 

    -d <domain file>.nadl    (default "domain.nadl")
	
	The domain file is the input text file containing the planning 
 	problem described in NADL.
	
    -o <planfile>.out        (default "plan.out")

	The plan file is the output file. It is a text file describing  
        the OBDD based universal plan. Consider the output for "prob01.nadl" 
	of the gripper domain solved using optimistic planning: 

	action        fl  fr  pr  p0    p1    p2    p3    
	...
	MoveRobotA2B  0 * 1 * 0 * 1 **  2 **  1 **  1 **  
	MoveRobotA2B  0 * 1 * 0 * 1 **  2 **  1 **  1* ** 
	MoveRobotA2B  0 * 1 * 0 * 1 **  2 **  1* ** 1 **  
	MoveRobotA2B  0 * 1 * 0 * 1 **  2 **  1* ** 1* ** 
	MoveRobotA2B  0 * 1 * 0 * 1 **  3 **  1 **  1 **  
	MoveRobotA2B  0 * 1 * 0 * 1 **  3 **  1 **  1* ** 
	MoveRobotA2B  0 * 1 * 0 * 1 **  3 **  1* ** 1 **  
	...

	The shown rows describe in which states the robot should move 
	from room A to room B. The state is encoded in current state 
	variables (thus only left columns of state variables contains
	values). fl, fr encodes if the left or right robot gripper is free.
   	pr encodes the position of the robot (0:rooma, 1:roomb). p0, ..., p4
        encodes the position of the balls (0:rooma, 1:roomb 2:leftgripper 
	3:rightgripper). Thus, the first row says that the robot should move 
	from room A to room B if it is in room A and holds ball 1 in its 
	left gripper and Ball 2 to 4 are in room B. Note that the remaining rows
	define other state configurations where MoveRobotA2B should be
	executed. '*' means any value. '*' combined with '1' and '0' represents
        sets of natural numbers where '*' can be either '1' or '0'. Thus,
	'1*' represent the set of numbers: {2,3}.


    -n bdd node count        (default 100000)

	The number of OBDD nodes the OBDD package allocates initially. 
	The package will dynamically allocate more nodes as needed.

    -c bdd cache size        (default 10000)

	The cache size used for dynamic programming in the OBDD package.
	Should be about 10 percent of the number of OBDD nodes allocated.


    -t partition threshold   (default 10000)

	An optimization algorithm collapse partitions until the number 
	of BDD nodes in each partition is above the partition threshold. 
	In this way a large number of small partitions can be reduced to 
	a few large partitions which often is more efficient for computing 
	sets of previous states. 
 
    -v verbosity level       (default 0) 

	Possible values are 0,1,... . The higher values the more information
	UMOP prints to the screen during execution.

    -h write usage                          

	Write option list to the screen.

    -a algorithm             (default 0)

	Selection of planning algorithm:

	0: Strong
	1: StrongCyclic
	2: Optimistic

    -r dynamic reorder alg.  (default 0)

	The performance of the OBDD algorithms depend on the ordering of the
	boolean OBDD variables used to encode actions and states. The OBDD package 
	can change the ordering of the variables dynamically during execution. 
	Users can choose between two strategies or disable dynamic reordering:

	0: WIN2ITE
	   
		Reordering using a sliding window of size 2. This algorithm swaps two
		adjacent variable blocks and if this results in more nodes the two blocks
		are swapped back again. The process is repeated until no progress is done.

	1: WIN2

		As above but the process is only repeated for all variable blocks.

	2: reordering off
	
		No dynamic reordering 


Documentation
=============

For further description of UMOP please download papers on UMOP from:

http://www.cs.cmu.edu/~runej/publications/publications.html

Please send comments, bugs, and suggestions to runej@cs.cmu.edu

Rune M. Jensen
Manuela M. Veloso

