Partially Observable Markov Decision Processes |

Version 5.3

written by A. R. Cassandra

The 'pomdp-solve' program solves problems that are formulated as partially observable Markov decision processes, a.k.a. POMDPs. It uses the basic dynamic programming approach for all algorithms, solving one stage at a time working backwards in time. It does finite horizon problems with or without discounting. It will stop solving if the answer is within a tolerable range of the infinite horizon answer, and there are a couple of different stopping conditions (requires a discount factor less than 1.0). Alternatively you can solve a finite horizon problem for some fixed horizon length. The code actually implements a number of POMDP solution algorithms:

**Enumeration **

(*Sondik '71, Monahan '82, White '91*)

**Two Pass**

(*Sondik '71*)

**Linear Support **

(*Cheng '88*)

**Witness **

(*Littman '97, Cassandra '98*)

**Incremental Pruning **

(*Zhang and Lui '96,
Cassandra, Littman and Zhang '97*)

**Finite Grid (instance of PBVI)**

(*Cassandra '04*)

Many of the algorithms extensively uses linear programming (LPs) to solve POMDPs. There are two options for LP packages: one is to use the public domain lp_solve program by Michel Berkelaar (which is included); the other is to use the commerical package CPLEX. The CPLEX package is numerically more robust, but so is its price tag. If you have CPLEX, or money is no object when it comes to solving POMDPs, then CPLEX is defnitely recommended, otherwise the lp_solve program tends to work just fine, though some precision and numeric stability is sacrificed.

This is new as of 10/16/2005 and has successfully been compiled in GNU/Linux and MAC OSX. Biggest differences from the 5.2 version surround the finite-grid algorithm. You can now read in a set of points from a file, you can force numeric rouding after each epoch, and a bunch of other niceties to help converegence.

Installing this should be as easy as:

Download the file tar zxvf pomdp-solve-5.3.tar.gz cd pomdp-solve-5.3 ./configure makeI haven't yet testing the '

This was new as of 10/10/2004 and has successfully been compiled in GNU/Linux and MAC OSX. Many minor additions and bug fixes are included, but the biggest change is the manner in which the command line optons are handled. The names have changed, and you can now use a configuration file.

Another big addition is the `pomdp-tools` executable, which
is the home for POMDP utility programs. A few are implemented and a
few are planned for the future.

Documentation for these changes exists, but is scattered and patchy, so it will not be available until I find the time to organized and revise it.

This was new as of 12/17/2003 and has successfully been compiled in GNU/Linux and in MS Windows under Cygwin. The big change here is that is uses the autoconf/automake tools. There are also a few additional optimizations that were not present in version 4.0.

This is a complete re-write of the code (done in Summer 1998) and supercedes the code available at Brown Univserity's site.

Input file formats:

© 2003-2013, Anthony R. Cassandra |