The Universal Multi-agent Obdd-based Planner (UMOP)

(:Title The Universal Multi-agent Obdd-based Planner (UMOP):)

UMOP (Jensen & Veloso, AIPS2000 and JAIR, vol. 13 2000 and Jensen, Veloso & Bowling ECP-01) 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.2 of UMOP includes five universal planning algorithms: strong planning, strong cyclic planning (Cimatti, Roveri & Traverso 1998), optimistic planning (Jensen & Veloso 2000), strong cyclic adversarial planning and optimistic adversarial planning (Jensen, Veloso & Bowling 2001). All of these algorithms perform a BFS backward search using efficient OBDD operations for generating sets of previous states. In addition version 1.2 includes several X-based execution demos and an interactive plan executor.

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 includes the BuDDy OBDD Package (Lind-Nielsen 1999). We have permission to distribute BuDDY ver. 2.0 in this release. Both UMOP and BuDDy may be used for research purposes only .

To download and install UMOP ver. 1.2 do the following:

• Download the source code with precompiled executable for a Pentium III running Linux Red Hat 7.1 umop12.tar.gz (3.1 MB).
• Unzip the file: "gunzip umop12.tar.gz"
• Untar the UMOP files: "tar xvf umop12.tar" The UMOP files are stored in the directory "UMOP-1.2". The precompiled executable is stored in subdirectory "bin" while the source code is in "src". Domain examples can be found in the subdirectory "domains". The demos and executor can be found in subdirs "demos" and "executor" respectively.

Please follow the instructions in the README file for compiling the source code and using UMOP. There are separate readme files in the demos and executor directories.

UMOP related Publications

• OBDD-based Universal Planning for Synchronized Agents in Non-Deterministic Domains, R.M. Jensen and M. M. Veloso, Journal of Artificial Intelligence Research, Volume 13, pages 189-226, 2000.
• OBDD-based Universal Planning for Multiple Synchronized Agents in Non-Deterministic Domains, R.M. Jensen and M. M. Veloso, In Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-00), AAAI Press, pages 167-176, 2000.
• OBDD-based Deterministic Planning using the UMOP Planning Framework, R.M. Jensen and M. M. Veloso, AIPS-00 Workshop on Model-Theoretic Approaches to Planning, 2000.
• UMOP 1.2 Software Demonstration, R.M. Jensen and M.M. Veloso, In Printed Notes of ICAPS-03 System Demos, 2003.
• OBDD-based Universal Planning in Multi-Agent, Non-Deterministic Domains, R.M. Jensen, Master's Thesis, Technical University of Denmark, Department of Automation, IAU99F02, 1999.