Clustering in Discrete Path Planning for Approximating Minimum Length Paths
This addresses path planning efficiency for robotics applications, though it appears incremental as it builds on existing clustering approaches.
The paper tackles discrete robot path planning on metric graphs by proposing Gamma-Clustering to reduce feasible solutions while maintaining solutions within a constant factor of optimal, with results showing significant computation time reductions on traveling salesman instances with little quality loss.
In this paper we consider discrete robot path planning problems on metric graphs. We propose a clustering method, Gamma-Clustering for the planning graph that significantly reduces the number of feasible solutions, yet retains a solution within a constant factor of the optimal. By increasing the input parameter Gamma, the constant factor can be decreased, but with less reduction in the search space. We provide a simple polynomial- time algorithm for finding optimal Gamma-Clusters, and show that for a given Gamma, this optimal is unique. We demonstrate the effectiveness of the clustering method on traveling salesman instances, showing that for many instances we obtain significant reductions in computation time with little to no reduction in solution quality.