%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Author: Pascal Poupart (copyright 2011)  
%
% While this code is made publicly available, all work that uses this
% code, extends this code or makes a comparison to this code is
% required to cite the following paper which describes the GapMin
% algorithm: 
%
% Pascal Poupart, Kee-Eung Kima and Dongho Kim, 
% Closing the Gap: Improved Bounds on Optimal POMDP Solutions, 
% International Conference on Automated Planning and Scheduling (ICAPS), 
% Freiburg, Germany, 2011.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table of Contents:

1) Installing GapMin
2) Running GapMin
3) Benchmark problems

=============================

1) Installing GapMin
--------------------

A) Unpack the code:

tar -xvzf gapMin-2011-06-13.tgz

B) Start matlab in the directory code-2011-06-13. This is important to
make sure that matlab automatically executes some files at startup.

cd code-2011-06-13
matlab

C) Download and install the cplex package from IBM to solve linear
programs.  It is available for free to academics.

D) Compile the cplex interface. You may need to change some of the paths
depending on where the relevant libraries are. The following command
worked for me with cplex 10.0 and matlab 2009a on a linux machine

mex -I/usr/local/cplex/include/ilcplex -L/usr/local/cplex/lib/x86_rhel4.0_3.4/static_pic -lcplex cplexint.c

E) Solve a POMDP from the directory gapMin-2011-06-13/problems. It will
run until the upper bound and the lower bound agree on at least 3
significant digits. Try the "cheese-taxi" problem which is quite small.

main('cheese-taxi')

2) Running GapMin
-----------------

To run GapMin, call the main function with the following arguments:

main(problemName,maxTime,ubInterpolation)

problemName: string indicating the name of a POMDP problem (without
the .POMDP extension) in the directory gapMin-2011-06-13/problems.
Following matlab's convention, the string should be in quotes.
Example: main('cheese-taxi')

maxTime: maximum amount of elapsed time (i.e., wall clock time) that
gapMin will run for.  GapMin will also terminate when the lower and
upper bounds agree on the first three significant digits.
Example: main('cheese-taxi',1000)

ubInterpolation: string indicating the upper bound interpolation
technique {'LP','sawtooth'}.  The default is 'LP'.
Example: main('cheese-taxi',1000,'sawtooth')

After each iteration, gapMin stores some statistics in a file in the
directory gapMin-2011-06-13/results.  These statistics include the
cpuTime, elapsedTime (wall clock time), lower bound, upper bound and
size of the belief set for each bound at each iteration.  You can load
the file and view the statistics by running:

load('results/cheese-taxi-time1000-sawtooth1.mat');
cpuTime
elapsedTime
lbInitVal
ubInitVal
sizeLbBeliefSet
sizeUbBeliefSet

3) Benchmark problems
---------------------

64 benchmark problems from Cassandra's repository (www.pomdp.org) are
included in this package.  Note that some of the problems have been
modified slightly from the originals posted on Cassandra's website.
In some cases, this is because the problems did not follow Cassandra's
grammar and therefore needed to be modified to ensure proper
parsing. In other cases, the parser did not recognize the entire
grammar specified by Cassandra and I found it easier to modify the
problems instead of the parser.  The parser included in the package is
Matthijs Spaan's Matlab parser, which is freely available at
http://staff.science.uva.nl/~mtjspaan/software/pomdp/

