日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

経路計画arXiv:1702.08410

離散経路計画におけるクラスタリングによる最短経路近似

Clustering in Discrete Path Planning for Approximating Minimum Length Paths

シェア:XThreadsFacebookLINEはてブBluesky

メトリックグラフ上のロボット経路計画で、探索空間を大幅に削減しつつ最適解の定数倍以内の解を保つ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.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI