Isomorph-free Branch and Bound Search for Finite State Controllers

Software Download

1. mgjpomdp-ALL.jar - the main application with all features (contains "Meuleau’s B&B" and "improved B&B with pruning" from our paper mentioned above)
   
2. mgjpomdp-ALL-NoPruning.jar - the same as the previous file but without isomorph-free pruning (used to compute "improved B&B" in our paper)
   

Implementation

1. The software is written in Java
   
2. POMDPs have to specified in the Cassandra's format. The following POMDP parser was used: https://github.com/mgrzes/libpomdp It can parse most POMDPs from Cassandra's repository. When parsing fails, it is usually sufficient to make rewards depend on (s,a) instead of (s,a,s')
   
3. A Java reimplementation of GapMin is included in the package as well. GapMin is used to compute tighter upper bounds for branch-and-bound as explained in our paper
   
4. Entire application is contained in one jar file and it does not require any additional Java packages except for CPLEX if GapMin is executed with interpolation by linear programming instead of saw-tooth approximation

How to run it?

1. Run "improved B&B with pruning" on tiger.95.POMDP
   
   mkdir /tmp/tigerPrune/
java -jar mgjpomdp-ALL-ijcai13subm.jar --pomdp ~/_data/Cassandra_POMDPs/tiger.95.POMDP --outpath /tmp/tigerPrune/ --id prune --alg-class SearchStartFixedMTJ --use-augmented --bound fib --nodes 5 --value-rank-type _default_ocf

   
2. Run "improved B&B" on tiger.95.POMDP
   
   mkdir /tmp/tigerNoPrune/
java -jar mgjpomdp-ALL-NoPruning-ijcai13subm.jar --pomdp ~/_data/Cassandra_POMDPs/tiger.95.POMDP --outpath /tmp/tigerNoPrune/ --id noPrune --alg-class SearchStartFixedMTJ --use-augmented --bound fib --nodes 5 --value-rank-type _default_ocf

   
3. Run "Meuleau’s B&B" on tiger.95.POMDP
   
   mkdir /tmp/tigerMeuleau99/
java -jar mgjpomdp-ALL-ijcai13subm.jar --pomdp ~/_data/Cassandra_POMDPs/tiger.95.POMDP --outpath /tmp/tigerMeuleau99/ --nodes 5 --meuleau99 --id tiger.95Meuleau99
   
4. Run GapMin on tiger.95.POMDP. For that, you'll need to download and compile a small Java program
   
   javac RunGapMin.java
java -cp mgjpomdp-ALL-ijcai13subm.jar:. RunGapMin ~/_data/Cassandra_POMDPs/tiger.95.POMDP /tmp/

   
5. Help
   
   java -jar mgjpomdp-ALL-ijcai13subm.jar --help
   
6. Repeat all experiments from our paper
   Run the following bash script on a cluster that runs Open PBS (qsub required)