Isomorph-free Branch and Bound Search for Finite State Controllers

Software implemented by Marek Grzes; it contains algorithms introduced in:

Marek Grzes, Pascal Poupart and Jesse Hoey: Isomorph-free Branch and Bound Search for Finite State Controllers. Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). Beijing, China, 2013. [pdf] [poster] [bibtex]

Currently, only the Java jar files are publicly available, but I will try to release the full source code in the future.

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)


  1. The software is written in Java
  2. POMDPs have to specified in the Cassandra's format. The following POMDP parser was used: 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

    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)

This program is distributed in the hope  that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty  of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Back to main page