DS-MPI is also called Dijkstra Sweep for Monotone Pessimistic Initialization [1]. It is used for finding an efficient upper bound initialization for BRTDP. This repo includes an implementation of BRTDP and DS-MPI.
For all my homies out there struggling to implement DS-MPI.
Watch it visit only a small part of the whole state space!
[1] McMahan, H. Brendan, Maxim Likhachev, and Geoffrey J. Gordon. "Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees." Proceedings of the 22nd international conference on Machine learning. ACM, 2005.
This is basically a stripped down version of osmnx_mdp, which solves routing with uncertainty using Markov decision processes.
I decided to keep everything intact so it is clear how BRTDP is used. In this case, a single simulation of an agent trying to get from A to B on the Munich map using BRTDP.
Basically, BRTDP_DS_MPI/algorithm/cpp_brtdp.cpp has the main implementation and BRTDP_DS_MPI/simulation.pyx applies BRTDP.
Running/Development:
sudo docker build -t brtdp-ds-mpi -f Dockerfile .
sudo docker run -v $(pwd):/app -it brtdp-ds-mpi bash
To run the current simulation:
cd BRTDP_DS_MPI
setup
run