Clustering in discrete path planning for approximating minimum length paths

In this paper we consider discrete robot path planning problems on metric graphs. We propose a clustering method, Г-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 Г, the constant factor can be decreased, but with less reduction in the search space. We provide a simple polynomial-time algorithm for finding optimal Г-Clusters, and show that for a given Г, 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.