Topological trajectory clustering with relative persistent homology
Topological trajectory clustering with relative persistent homology
复制标题
具有相对持久同源性的拓扑轨迹聚类
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Kragic
中科院分区：
文献类型：
--
作者：
Florian T. Pokorny;Ken Goldberg;D. Kragic
基于从演示中学习的云机器人技术为机器人和自动驾驶汽车的手动编程提供了有前途的替代方案。一个挑战是，演示的轨迹可能会有很大的不同：它可以是非常困难的，如果不是不可能的，一个系统学习控制策略，除非轨迹聚类成有意义的一致的子集。基于距离度量的度量聚类方法需要二次时间来计算成对距离矩阵，并且不能自然地区分拓扑上不同的轨迹。本文提出了一种基于相对持久同调的拓扑聚类算法，该算法对于固定的底层单纯表示和轨迹离散化，只需要线性时间的轨迹数。该算法采用了全球性的约束形式化的功能的子级或上级集的拓扑结构，并可以扩展到将概率运动模型。在与真实的汽车和船舶GPS轨迹以及从视频中提取的行人轨迹的实验中，该算法将轨迹聚类成有意义的一致子集，并且正如我们在船舶轨迹的实验中所示的那样，比通过Frechet距离的度量聚类更快，更有效地聚类。
Cloud Robotics techniques based on Learning from Demonstrations suggest promising alternatives to manual programming of robots and autonomous vehicles. One challenge is that demonstrated trajectories may vary dramatically: it can be very difficult, if not impossible, for a system to learn control policies unless the trajectories are clustered into meaningful consistent subsets. Metric clustering methods, based on a distance measure, require quadratic time to compute a pairwise distance matrix and do not naturally distinguish topologically distinct trajectories. This paper presents an algorithm for topological clustering based on relative persistent homology, which, for a fixed underlying simplicial representation and discretization of trajectories, requires only linear time in the number of trajectories. The algorithm incorporates global constraints formalized in terms of the topology of sublevel or superlevel sets of a function and can be extended to incorporate probabilistic motion models. In experiments with real automobile and ship GPS trajectories as well as pedestrian trajectories extracted from video, the algorithm clusters trajectories into meaningful consistent subsets and, as we show in an experiment with ship trajectories, results in a faster and more efficient clustering than a metric clustering by Fréchet distance.