We provide runtime comparisons of SV-PRM to the PRM baseline for different graph sizes on the Intel BHM planning problem. We initialize vertices using uniform sampling with rejection in both cases, and run 100 steps of optimization for SV-PRM before graph construction. The planning problem is comprised of fixed start/goal locations at the northeast and southwest corners of the map, respectively.  Each runtime result is averaged over 50 random seeds, and experiments are conducted using the following hardware configuration:  Intel Core i9-9900K CPU @ 3.60GHz, 64 GB DDR4 RAM, NVIDIA GeForce RTX 2080 Ti GPU.

The left-hand figure depicts the average runtimes for each experiment, divided into the sampling and planning phases. The average sampling time for PRMs (just initialization) is 5.4 milliseconds, and is barely visible in the graph.  The average time for the SVGD sampling step (initialization + optimization) is 212 milliseconds, and remains effectively constant  with increasing vertex count due to the parallelized pytorch-CUDA implementation.  As expected, the runtime for the planning phase grows exponentially with increasing vertex count / graph size.  The total runtimes are comparible for both SV-PRM and PRM, even with additional optimization in the former case. However, the benefit of vertex refinement using SVGD are clearly depicted in the neighboring plot; success rates for planning problems are exceptionally higher for SV-PRM in the regime of coarse graphs with lower node counts. 

This example clearly demonstrates the advantage of performing additional SVGD optimization for sampling-based planning on differentiable Bayesian occupancy maps. The resulting graph better represents the map topology and generates improved planning solutions, at virtually no additional computational cost. 

Markov Chain Monte Carlo (MCMC) methods are a common class of algorithms used for sampling from un-normalized probability distributions. Like SVGD, these can also make use of gradient information to guide the sampling process, but with the addition of random noise at each step to induce exploration. 

We make a comparison of our approach to two popular MCMC algorithms, which are used here to generate the graph vertices for PRM construction.  The first method is the Metropolis-adjusted Langevin Algorithm (MALA) [1] .  Using identical random initializations to SV-PRM and baseline PRM, each sample is optimized using MALA for 300 steps, with the final value used as a candidate node.  For the graph sizes used here (50-500 nodes), this was found to perform significantly better than taking states visited by a single MALA run, or multiple MALA runs with random restarts (and shorter sequences), which failed to generate feasible paths. 

The second MCMC method examined is the No U-turn Sampler (NUTS) [2] , an extension of the Hamiltonian Monte Carlo (HMC) [3] method. The efficacy of the exploration steps makes it feasible to use visited states from multiple  sampler runs as candidate vertices. We use 5 random restarts for each experiment, where the number of nodes sampled from each run is the total divided by the number of restarts. A burn-in of 100 is used,  with a step size of 2.5 and 25 steps taken in between vertex samples.

The comparisons are made on the BHM distribution, derived from the Intel dataset. All experiments are initialized with samples drawn from a uniform distribution with rejection. Results are average over 50 random seeds. We observe that the MCMC baselines require many samples (>500) to sufficiently explore high-probability areas in the map. This is likely a result of the locally-driven, sequential sampling strategies these algorithms employ, which does not perform distributed optimization across a set of particles, spanning the map.

[1]  Roberts, G.O., Stramer, O. Langevin Diffusions and Metropolis-Hastings Algorithms. Methodology and Computing in Applied Probability 4, pages 337–357, 2002. doi: 10.1023/A:1023562417138. URL https://link.springer.com/article/10.1023/A:1023562417138.

[2] Hoffman, Matthew D; Gelman, Andrew (2014). "The No-U-turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo". Journal of Machine Learning Research. 15 (1): 1593-1623 URL www.jmlr.org/papers/volume15/hoffman14a/hoffman14a.pdf 

[3] Neal, Radford M (2011). In Steve Brooks; Andrew Gelman; Galin L. Jones; Xiao-Li Meng (eds.). Handbook of Markov Chain Monte Carlo. Chapman and Hall/CRC. ISBN 9781420079418. URL www.mcmchandbook.net/HandbookChapter5.pdf