Persistent Homology for Path Planning in Uncertain Environments
Persistent Homology for Path Planning in Uncertain Environments
复制标题
DOI：
10.1109/tro.2015.2412051
复制
发表时间：
2015-06-01
影响因子：
7.8
通讯作者：
Kumar, Vijay
中科院分区：
文献类型：
--
作者：
Bhattacharya, Subhrajit;Ghrist, Robert;Kumar, Vijay
我们解决了不确定环境中目标导向路径规划的基本问题，以概率（占用）图表示。大多数方法通常使用阈值将灰度图减少为二值图，然后再应用现成的技术来找到最佳路径。这就提出了一个有点不恰当的问题：地图阈值的正确（最佳）值是多少？相反，我们建议对问题采用持久同源方法 - 一种拓扑方法，其中我们寻找对于给定概率图最持久的轨迹同源类。换句话说，我们希望轨迹类别在最大阈值范围内没有障碍。为了使这个问题易于处理，我们在 Z(2) 系数（而不是标准 Z 系数）中使用同源性，并描述如何使用基于图搜索的算法来查找不同同源类中的轨迹。我们的仿真结果证明了本文提出的算法的效率和实际适用性。
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 Z(2) coefficients (instead of the standard Z 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.