離散経路計画におけるクラスタリングによる最短経路近似
Clustering in Discrete Path Planning for Approximating Minimum Length Paths
メトリックグラフ上のロボット経路計画で、探索空間を大幅に削減しつつ最適解の定数倍以内の解を保つGamma-Clusteringを提案し、巡回セールスマン問題で計算時間の削減を実証した。
著者: Frank Imeson, Stephen L. Smith
分類: cs.RO
原文アブストラクト
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.
