日本フィジカルAI新聞

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

運動計画arXiv:1709.07610

非ホロノミック拘束系における効率的な最近傍探索

Efficient Nearest-Neighbor Search for Dynamical Systems with Nonholonomic Constraints

シェア:XThreadsFacebookLINEはてブBluesky

非ホロノミック系の劣リーマン距離では従来のk-d木の最近傍探索が遅くなることを示し、その距離に特化したk-d木の構築・探索手法を提案して高速化を実現した。

著者: Valerio Varricchio, Brian Paden, Dmitry Yershov, Emilio Frazzoli

分類: cs.CG, cs.CC, cs.RO, cs.SY, eess.SY

原文アブストラクト

Nearest-neighbor search dominates the asymptotic complexity of sampling-based motion planning algorithms and is often addressed with k-d tree data structures. While it is generally believed that the expected complexity of nearest-neighbor queries is $O(log(N))$ in the size of the tree, this paper reveals that when a classic k-d tree approach is used with sub-Riemannian metrics, the expected query complexity is in fact $\Theta(N^p \log(N))$ for a number $p \in [0, 1)$ determined by the degree of nonholonomy of the system. These metrics arise naturally in nonholonomic mechanical systems, including classic wheeled robot models. To address this negative result, we propose novel k-d tree build and query strategies tailored to sub-Riemannian metrics and demonstrate significant improvements in the running time of nearest-neighbor search queries.

関連論文

  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