A Topology-Based Path Similarity Metric and its Application to Sampling-Based Motion Planning

摘要

Many applications of robotic motion planning benefit from considering multiple homotopically distinct paths rather than a single path from start to goal. However, determining whether paths represent different homotopy classes can be difficult to compute. We propose metrics for efficiently approximating the homotopic similarity of two paths are, instead of verifying homotopy equivalence directly. We propose two metrics: (1) a naive application of local planning, a common subroutine of sampling-based motion planning, and (2) a novel approach that reasons about the topologically distinct portions of the workspace that a path visits. We present three applications of our metric to demonstrate its use and effectiveness: extracting topologically distinct paths from an existing roadmap, comparing paths for robot manipulators, and improving the computational efficiency of an existing sampling-based method, Path Deformation Roadmaps (PDRs), by over two orders of magnitude. We explore the trade-off between quality and computational efficiency in the proposed metrics.