A Topological Approach to Finding Coarsely Diverse Paths

Abstract

We present a topological method for finding coarsely diverse pathways. The use of pre-computed paths for online planning in a dynamic context reduces the overhead of re-planning alternate routes. Our algorithm applied the notion of discrete Morse theory to identify critical points incident on the obstacles and used this information to identify and return a diverse set of coarse paths. Three sampling-based planning approaches are converted to topology-aware planners and compared to another that employs the SPARS2 path planning algorithm. We report on the number of coarse pathways found, computation time, and average path length and show that our approach outperformed previously published path diversity algorithms.