Persistent Homology for Path Planning in Uncertain Environments

• Published in: IEEE transactions on robotics 2015-06, Vol.31 (3), p.578-590
• Main Authors: Bhattacharya, Subhrajit, Ghrist, Robert, Kumar, Vijay
• Format: Article
• Language: English
• Subjects: Algorithms; Homology; Joining processes; persistent homology; Planning; planning under uncertainty; robot path planning; Robots; Simulation; Topology; Trajectory; Uncertainty; Windings
• ISSN: 1552-3098; 1941-0468
• DOI: 10.1109/TRO.2015.2412051

We address the fundamental problem of goal-directed path planning in an uncertain environment represented as a probability (of occupancy) map. Most methods generally use a threshold to reduce the grayscale map to a binary map before applying off-the-shelf techniques to find the best path. This raises the somewhat ill-posed question, what is the right (optimal) value to threshold the map? We instead suggest a persistent homology approach to the problem-a topological approach in which we seek the homology class of trajectories that is most persistent for the given probability map. In other words, we want the class of trajectories that is free of obstacles over the largest range of threshold values. In order to make this problem tractable, we use homology in ℤ 2 coefficients (instead of the standard ℤ coefficients), and describe how graph search-based algorithms can be used to find trajectories in different homology classes. Our simulation results demonstrate the efficiency and practical applicability of the algorithm proposed in this paper.paper.