日本フィジカルAI新聞

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

経路計画arXiv:2508.13392

増分一般化ハイブリッドA*

Incremental Generalized Hybrid A*

シェア:XThreadsFacebookLINEはてブBluesky

大規模な木探索を効率的に整理するため、動的に頂点展開を組織化する anytime 木探索フレームワーク IGHA* を提案し、従来の Hybrid A* より少ない展開で高速な計画を実現した。

詳しい要約

1. どんなもの?

- 大規模な探索木上での探索を効率的に組織化する問題に取り組む研究。 - 背景は off-road autonomy で、real-time planning が必須。 - 古典的手法は motion primitives のグラフと dominance による枝刈りを用いるが、複雑な dynamics では two-point boundary-value problems の反復求解が遅い。 - Hybrid A* (HA*) は motion primitives の木探索と grid-based dominance check による近似枝刈りで対処したが、grid resolution の選択が難しく、粗すぎると失敗、細かすぎると展開過多で遅くなる。 - 提案は Incremental Generalized Hybrid A* (IGHA*)。rigid pruning なしで vertex expansions を動的に組織化する anytime tree-search framework。

2. 先行研究と比べてどこがすごい?

- 従来の HA* は grid-based dominance check の解像度依存があり、粗いと失敗・細かいと展開過多というトレードオフがあった。 - IGHA* は rigid pruning をせずに vertex expansions を動的に組織化することで、この解像度選択の問題を回避。 - 理論的に HA* と同等以上 (provably matches or outperforms HA*) であることを示す。 - on-road kinematic および off-road kinodynamic の car-like robot のクエリで、最適化版 HA* (HA*M, internal baseline) に比べ best solution までの expansions が 6x 少ない。

3. 技術・手法の肝は?

- anytime tree-search framework として IGHA* を提案。 - rigid pruning を行わず、vertex expansions を動的に組織化する。 - 詳細なアルゴリズム構成は要旨からは不明。 - HA* の grid-based dominance check に代わる、解像度に依存しない展開順序付けが肝と考えられるが、具体的機構は要旨からは不明。

4. どうやって有効だと検証した?

- on-road kinematic と off-road kinodynamic の car-like robot の planning queries で評価。 - IGHA* の variants が最適化版 HA* (HA*M) より best solution まで 6x 少ない expansions を使用。 - high-fidelity simulator での off-road 実験で、model predictive controller と組み合わせた in-the-loop で HA*M を上回る。 - simulation と small-scale off-road vehicle の両方で real-time performance を実証。

5. 議論はある?

- grid resolution 選択の困難さを回避できる点が議論の中心。 - HA* と同等以上という理論保証がある一方、具体的な計算コストやスケーラビリティの限界は要旨からは不明。 - 実車 small-scale off-road vehicle での real-time 性能は示されるが、大規模車両や他 dynamics への一般化は要旨からは不明。 - model predictive controller との統合時の挙動や失敗ケースの議論は要旨からは不明。

6. 次に読むべき論文は?

- Hybrid A* (HA*):比較対象の基盤手法。 - HA*M:internal baseline として用いられた最適化版 HA*。 - motion primitives のグラフと dominance を用いる古典的アプローチ(two-point boundary-value problems を反復求解する手法)。 - model predictive controller:in-the-loop 評価で併用。 - anytime tree-search や kinodynamic planning の関連研究(具体的論文名は要旨からは不明)。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Sidharth Talia, Oren Salzman, Siddhartha Srinivasa

分類: cs.RO

原文アブストラクト

We address the problem of efficiently organizing search over very large trees, which arises in many applications ranging from autonomous driving to aerial vehicles. Here, we are motivated by off-road autonomy, where real-time planning is essential. Classical approaches use graphs of motion primitives and exploit dominance to mitigate the curse of dimensionality and prune expansions efficiently. However, for complex dynamics, repeatedly solving two-point boundary-value problems makes graph construction too slow for fast kinodynamic planning. Hybrid A* (HA*) addressed this challenge by searching over a tree of motion primitives and introducing approximate pruning using a grid-based dominance check. However, choosing the grid resolution is difficult: too coarse risks failure, while too fine leads to excessive expansions and slow planning. We propose Incremental Generalized Hybrid A* (IGHA*), an anytime tree-search framework that dynamically organizes vertex expansions without rigid pruning. IGHA* provably matches or outperforms HA*. For both on-road kinematic and off-road kinodynamic planning queries for a car-like robot, variants of IGHA* use 6x fewer expansions to the best solution compared to an optimized version of HA* (HA*M, an internal baseline). In simulated off-road experiments in a high-fidelity simulator, IGHA* outperforms HA*M when both are used in the loop with a model predictive controller. We demonstrate real-time performance both in simulation and on a small-scale off-road vehicle, enabling fast, robust planning under complex dynamics. Website: https://personalrobotics.github.io/IGHAStar/

関連論文

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

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI