日本フィジカルAI新聞

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

運動計画arXiv:2605.30647

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

Bidirectional Incremental Generalized Hybrid A*

シェア:XThreadsFacebookLINEはてブBluesky

複雑なダイナミクスを持つシステムの anytime 運動計画問題に対し、解を隠す凍結頂点の問題を双方向探索で緩和する Bi-IGHA* を提案し、計算効率を大幅に改善した。

詳しい要約

1. どんなもの?

本論文は、複雑な dynamics を持つシステムのための anytime kinodynamic planning 手法である Bi-IGHA*(Bidirectional Incremental Generalized Hybrid A*)を提案する。 - 対象は、motion primitives の事前計算が不可能な非構造環境での高次元 planning。 - IGHA* を bidirectional search に拡張し、frozen vertices が解を隠す問題を緩和。 - R3, R4, R6 の planning 問題と高速オフロード自律走行の kinodynamic planning で評価。

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

先行研究との比較での利点は以下の通り。 - Hybrid A* は state space を離散化するが、tree discovery と離散化解像度が結合する問題があった。 - IGHA* は解像度の階層を anytime に探索し、vertex を pruning せず freezing することでこの結合を解消したが、frozen vertices が解を支持する vertex を隠す可能性があった。 - 古典的 bidirectional search は探索深さの削減を目的とするが、Bi-IGHA* は frozen vertices が解を隠す挙動を根本的に緩和する追加の利点を得る。 - Bi-IGHA* は IGHA* の monotonic cost improvement と termination の保証を維持する。

3. 技術・手法の肝は?

技術や手法の肝は以下の通り。 - IGHA* を bidirectional 設定に拡張(Bi-IGHA*)。 - 解像度の階層を anytime に探索し、vertex を freezing して後の反復で利用。 - bidirectional search により、frozen vertices が解を隠す問題を緩和。 - monotonic cost improvement と termination の保証を維持。

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

有効性の検証は以下の通り。 - R3, R4, R6 の planning 問題で expansions を大幅に削減することを実証。 - 高速オフロード自律走行の kinodynamic planning で、同等の closed-loop performance を達成しつつ、必要な expansions を大幅に削減。 - 詳細な実験設定やベースラインは要旨からは不明。

5. 議論はある?

議論点は以下の通り。 - frozen vertices が解を支持する vertex を隠す問題を bidirectional 化で緩和。 - IGHA* の保証(monotonic cost improvement, termination)を Bi-IGHA* が維持することを示す。 - 限界や今後の課題については要旨からは不明。

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

次に読むべき論文は以下の通り。 - Hybrid A*(元論文) - Incremental Generalized Hybrid A* (IGHA*) - 古典的 bidirectional search の手法 - 関連する anytime kinodynamic planning の研究

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

著者: Sidharth Talia, Oren Salzman, Siddhartha Srinivasa

分類: cs.RO

原文アブストラクト

We focus on the problem of efficient anytime kinodynamic planning for systems with complex dynamics in unstructured environments that make precomputing motion primitives infeasible. Directly applying A* to such problems is computationally infeasible due to the curse of dimensionality. Methods such as Hybrid A* addressed this burden by discretizing the state space, but in turn creating a coupling between tree discovery and the discretization resolution. The Incremental Generalized Hybrid A* (IGHA*) performs search over a hierarchy of resolutions in an anytime fashion to break this coupling, by freezing vertices to use in later search iterations rather than pruning them. However, the frozen vertices can hide solution-supporting vertices from the search at a particular iteration. While classical bidirectional search is motivated by the reduction of search depth, extending IGHA* into the bidirectional setting (termed Bi-IGHA*) obtains additional benefit by fundamentally mitigating the behaviour induced by frozen vertices hiding solutions. We show that Bi-IGHA* preserves IGHA*'s guarantees on monotonic cost improvement and termination. We empirically show that Bi-IGHA* substantially reduces expansions on R3, R4, and R6 planning problems, and achieves equivalent closed-loop performance with kinodynamic planning for high-speed off-road autonomy while requiring significantly fewer expansions. Website: https://personalrobotics.github.io/IGHAStar/biighastar.html

関連論文

  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