My homepage has moved to www.fransoliehoek.net, please update your bookmarks. (you will be redirected in 5 seconds.)

The MultiAgent decision process toolbox

Introduction

The Multiagent decision process (MADP) Toolbox is a free C++ software toolbox for scientific research in decision-theoretic planning and learning in multiagent systems (MASs). It is jointly developed by Matthijs Spaan and me. We use the term MADP to refer to a collection of mathematical models for multiagent planning: multiagent Markov decision processes (MMDPs), decentralized MDPs (Dec-MDPs), decentralized partially observable MDPs (Dec-POMDPs), partially observable stochastic games (POSGs), etc.

The toolbox is designed to be rather general, potentially providing support for all these models, although so far most effort has been put in planning algorithms for discrete Dec-POMDPs. It provides classes modeling the basic data types of MADPs (e.g., action, observations, etc.) as well as derived types for planning (observation histories, policies, etc.). It also provides base classes for planning algorithms and includes several applications using the provided functionality. For instance, applications that use JESP or brute-force search to solve .dpomdp files for a particular planning horizon. In this way, Dec-POMDPs can be solved directly from the command line. Furthermore, several utility applications are provided, for instance one which empirically determines a joint policy's control quality by simulation.

Overview

The framework consists of the following parts, grouped in different libraries:

  • the base library
  • the parser
  • a support library
  • a planning library
These are discussed below.

The base library (libMADPBase)

The base library is the core of the MADP toolbox. It contains:

  • A representation of the basic elements in a decision process such as states, (joint) actions and observations.
  • A representation of the transition, observation and reward models in a multiagent decision process. These models can also be stored in a sparse fashion.
  • A uniform representation for MADP problems (e.g. POSGs, Dec-POMDPs, TOI-Dec-POMDPs), which provides an interface to a problem's model parameters.
  • Auxiliary functionality regarding manipulating indices, exception handling and printing.

The parser library (libMADPParser)

The parser library only depends on the base library, and contains a parser for .dpomdp files, which is a file format for problem specifications of discrete Dec-POMDPs. A set of benchmark problem files can be found in the problems/ directory, and the .dpomdp syntax is documented in problems/example.dpomdp. The format is based on Tony's POMDP file format, and the formal specification is found in src/parser/dpomdp.spirit. The parser uses the Boost Spirit library.

The support library (libMADPSupport)

The support library contains basic data types useful for planning, such as:

  • A representation for (joint) histories, for storing and manipulating observation, action and action-observation histories.
  • A representation for (joint) beliefs, both stored as a full vector as well as a sparse one.
  • Functionality for representing (joint) policies, as mappings from histories to actions.
  • An implementation of the DecTiger and FireFighting problem as C++ classes.
  • Shared functionality for discrete MADP planning algorithms, collected in PlanningUnitMADPDiscrete and PlanningUnitDecPOMDPDiscrete, computes (joint) history trees, joint beliefs, and value functions.

The planning library (libMADPplanning)

The planning library depends on the other libraries and contains functionality for planning algorithms. In particular it contains

  • Dec-POMDP solution algorithms: BruteForceSearchPlanner, JESPExhaustivePlanner, JESPDynamicProgrammingPlanner, DICEPSPlanner, GMAA_kGMAA and GMAA_MAAstar. They extend the planning units mentioned before.
  • A simple simulator to empirically test the control quality of a solution, see SimulationDecPOMDPDiscrete.
  • POMDP solution techniques: Perseus.
  • Functionality for building and solving Bayesian Games: see BayesianGame and BayesianGameIdenticalPayoffInterface.
  • Heuristic Q-functions: QMDP, QPOMDP, and QBG.

Windows port / StarCraft

Prashant Doshi and his students Christopher Jackson and Kennth Bogert used the MADP toolbox to compute policies in the game of StarCraft.

  • Watch the video that shows how Dec-POMDP strategies beat the built-in game AI.
  • The windows port of MADP will be made available soon.

More information

  • An example
  • Generate the html doxygen documentation (class reference) or download it (.tar.gz).
  • Some more details are explained in this Documentation (.pdf).
  • An overview is given by the following paper: "The MultiAgent Decision Process toolbox: software for decision-theoretic planning in multiagent systems" (pdf). This was written for v0.1, so some details may not be current.
  • Subscribe to the MADP-users mailing list

Download

The current version of the MADP toolbox is 0.2.2 and can be downloaded here:

Installation

The MADP toolbox makes use of GNU autotools. Therefore, a typical installation is as follows. First, unpack the tar. Go to the created madp directory and then

./configure
make
make install [optional]
Please see the enclosed README and INSTALL file for more information.

The MADP toolbox is being developed on Debian GNU/Linux Lenny, but should work on any recent Linux distribution.