Approximate POMDP Planning (APPL) Toolkit

Copyright (c) 2008-2010 by National University of Singapore.

APPL is a C++ implementation of the SARSOP algorithm [1], using the factored MOMDP representation [2]. It takes as input a POMDP model in the POMDP or POMDPX file format and produces a policy file. It also contains a simple simulator for evaluating the quality of the computed policy. More information can be found at http://motion.comp.nus.edu.sg/projects/pomdp/pomdp.html.

For bug reports and suggestions, please email <motion@comp.nus.edu.sg>.

[1] H. Kurniawati, D. Hsu, and W.S. Lee. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Proc. Robotics: Science and Systems, 2008.

[2] S.C.W. Ong, S.W. Png, D. Hsu, and W.S. Lee. POMDPs for robotic tasks with mixed observability. In Proc. Robotics: Science and Systems, 2009.


========================================================================
TABLE OF CONTENTS
========================================================================

* Requirements
* Quick start
* Documentation
* Package contents
* Acknowledgments
* Release notes


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

Operating systems:        Linux
                          Mac OS X (unofficial)
                          Windows (unofficial)

Tested compilers:         gcc/g++ 4.0.1 under Linux
                          gcc/g++ 4.1.2 under Linux
                          gcc/g++ 4.2.3 under Linux
                          gcc/g++ 4.3.2 under Linux
                          gcc/g++ 4.4.0 under Linux
                          gcc/g++ 4.8.1 under Linux
                          gcc/g++ 3.4.4 under Windows(Cygwin)
                          Microsoft Visual C++ 9 in Visual Studio 2008 with SP1 under Windows

* General
  For gcc/g++ tool chain, GNU make is required for building.

* Mac OS X
  - For Mac OS X, physical memory size cannot be automatically determined yet. Currently APPL will assume 1G physical memory for Mac OS X. If your physical memory size is different, use "--memory" command-line option to set the correct memory limit.

  - For Mac using PowerPC processor, remove the option "-msse2 -mfpmath=sse" from CFLAGS in src/Makefile.

* Windows
  The Visual Studio port is experimental. The generated binaries may behave differently from its Linux counterpart.
  For Visual Studio 2010, refer to FAQ at http://bigbird.comp.nus.edu.sg/pmwiki/farm/appl/index.php?n=Main.FAQ for more information

========================================================================
QUICK START
========================================================================

* For Linux or Windows (Cygwin), at the top-level directory, type the commands:

    gunzip appl-v0.91.tar.gz
    tar -xvf appl-v0.91.tar
    cd appl-v0.91/src
    make

A total of 4 executables are generated in the current directory.
  "pomdpsol" computes a policy.
  "pomdpsim" is the policy simulator.
  "pomdpeval" is the policy evaluator.
  "polgraph" outputs a graphical representation of a policy.
  "pomdpconvert" converts a POMDP model file to POMDPX file format.

Please read "doc/Usage.txt" for command-line options.

- Try solving an example problem. Type the command:
    ./pomdpsol ../examples/POMDPX/Tiger.pomdpx

  The generated policy is written to "out.policy" by default.

- Try simulating a policy. Type the command:
    ./pomdpsim --simLen 100 --simNum 1000 --policy-file out.policy ../examples/POMDPX/Tiger.pomdpx

  The simulation results are written to the console.

- Try evaluating a policy. Type the command:
    ./pomdpeval --simLen 100 --simNum 1000 --policy-file out.policy ../examples/POMDPX/Tiger.pomdpx

  The evaluation results are written to the console.

- Try generating a graphical representation of a policy . Type the command:
    ./polgraph --policy-file out.policy --policy-graph tiger.dot ../examples/POMDPX/Tiger.pomdpx

   The generated graph is written to "tiger.dot". You can view the output "tiger.dot" using Graphviz (http://www.graphviz.org/).  A pdf file generated from "tiger.dot" is in "../examples/POMDPX/tiger.pdf".

- Try converting a POMDP file to POMDPX file format:
    ./pomdpconvert ../examples/POMDP/Tiger.pomdp

  The generated POMDPX file is in the same directory as the POMDP model file.

Sample results from the above commands are in "../examples/POMDPX/tiger.log".

* For Windows with Microsoft Visual Studio 2008
    Unpack the zip file

    Open the solution file : src\momdp.sln

    Select from Menu Build -> Build Solution
    (generated binaries is in appl\src\release directory, pomdpsol.exe is the Solver, pomdpsim.exe is the Simulator, pomdpeval.exe is the Evaluator, polgraph is the policy graph generator.))

- Try solving an example problem:
    Open up a command-line console:
        1: Click on Start Menu -> Run
        2: Key in "cmd" and press Enter
    Go to the directory where the generated binaries are
        Example (assume the source code is located at c:\appl\src):
            c:
            cd c:\appl\src\release
    Key in command:
        pomdpsol.exe ..\..\examples\POMDPX\Tiger.pomdpx

    The policy will be written to "out.policy".

-Try simulating the generated policy
        pomdpsim.exe --simLen 100 --simNum 1000 --policy-file out.policy ..\..\examples\POMDPX\Tiger.pomdpx

  The simulation results are written to the console.

-Try evaluating the generated policy
        pomdpeval.exe --simLen 100 --simNum 1000 --policy-file out.policy ..\..\examples\POMDPX\Tiger.pomdpx

  The evaluation results are written to the console.

- Try generating a graphical representation of a policy . Type the command:
   	polgraph.exe --policy-file out.policy --policy-graph tiger.dot ..\..\examples\POMDPX\Tiger.pomdpx

- Try converting a POMDP file to POMDPX file format:
	pomdpconvert ..\examples\POMDP\Tiger.pomdp

  The generated POMDPX file is in the same directory as the POMDP model file.


========================================================================
DOCUMENTATION
========================================================================

Documentation can be found in the directory "doc". See PACKAGE CONTENTS for a detailed listing.


========================================================================
PACKAGE CONTENTS
========================================================================

README.txt                                This file
doc/FAQ.txt				  Frequently asked questions
doc/Install.txt                           Detailed compilation instruction
doc/Usage.txt                             Explanation of command-line options
doc/POMDP/PomdpFileFormat.html            POMDP file format
doc/POMDPX/PomdpxFileFormat.pdf           POMDPX file format
doc/POMDPX/Pomdpx.xsd                     POMDPX XML schema file
license/License                           License
license/Notice                            Attribution notices as required by Apache License 2.0
src/Parser                                POMDP and POMDPX parsers
src/Models                                POMDP model representation
src/Core                                  Core data structures
src/Algorithms                            POMDP algorithms
src/Bounds                                Value functions
src/MathLib                               Math library
src/OfflineSolver                         Offline solver
src/Simulator                             Simulator
src/Evaluator                             Evaluator
src/Utils                                 Cross platform utility code
src/Makefile                              Linux make file
examples/                                 Example POMDP and POMDPX model files

* Windows-specific files
src/miniposix                             POSIX compliance code for Windows
src/OfflineSolver/OfflineSolver.vcproj    Visual Studio 2008 Project file for Offline solver
src/Simulator/Simulator.vcproj            Visual Studio 2008 Project file for Simulator
src/Evaluator/Evaluator.vcproj            Visual Studio 2008 Project file for Evaluator
src/PolicyGraph/PolicyGraph.vcproj	  Visual Studio 2008 Project file for Policy graph generator
src/momdp.sln                             Visual Studio 2008 solution


========================================================================
ACKNOWLEDGMENTS
========================================================================

Part of the APPL toolkit makes use of code based on an early version of ZMDP by Trey Smith (http://www.cs.cmu.edu/~trey/zmdp/). ZMDP in turn uses code from pomdp-solve by Tony Cassandra (http://www.cassandra.org/pomdp/code/index.shtml). The POMDPX parser uses TinyXML by Lee Thomason (http://www.grinninglizard.com/tinyxml/).


========================================================================
RELEASE NOTES
========================================================================
9-Jun-2014
* Fixed compilation issues with gcc version >= 4.7
* Various matrix operation optimizations

6-Mar-2012
* Added support for intra-slice dependency between variables in POMDPX model. Only edges fully observable state X to partially observable state Y are allowed.

9-Aug-2011, version 0.95
* IMPORTANT: Fixed a bug that caused pomdpsim to output wrong maximum likelihood unobserved state in log file
* Fixed a bug in parsing POMDPX file with XML comments (We thank Alex Goldhoorn for bug report and patch)

28-Apr-2010, version 0.94
* Fix a bug that terminal states are not correctly recognized in some model.

22-Apr-2010, version 0.93
* Solves MDP specified in POMDPX file format.  Output MDP solution in PolicyX format.

12-Mar-2010, version 0.92

* Fixed a bug in POMDPX file format parser when reward is a function of current state R(s',a).
* Output policy file in XML format.
* Added POMDP to POMDPX converter.

24-Nov2009, version 0.91

* Fixed several bugs in the POMDPX file format parser.
* Cleaned up POMDPX file format parser code and reduced memory usage.


04-Sep-2009, version 0.9

* Substantially restructured the code base.
* Added support for the new factored .pomdpx file format.
* The main POMDP solver now uses the SARSOP algorithm with the MOMDP representation.
* Added policy graph generator.


01-Feb-2009, version 0.3

* Added option for memory limit.
* Reduced memory usage.
* Added policy evaluator.

25-Jul-2008, version 0.2

* Minor bug fixes.

01-Jul-2008, version 0.1

* Initial release.