時空間プランニング2026/9/24arXiv:2609.30533

ST-pRRTC: 適応的ゴール時間フォレストを用いた並列時空間RRT-Connect

ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests

障害物の軌道が既知で到着時刻が未指定の動的環境に対し、GPU並列の時空間RRT-Connectプランナを提案。共有前向き木と適応的な後向きゴール時間木のフォレストで探索し、到着時刻の最適性を保証する。

詳しい要約

1. どんなもの？

- 動的な障害物の軌道が既知で、到着時刻が未指定の問題に対するGPU並列のspace-time RRT-Connect motion plannerであるST-pRRTCを提案。 - 共有のforward treeと適応的なbackward goal-time treesのforestを構築する。 - 到着時刻を連続的にサンプリングするinterval root formulationを採用し、限られた時間領域で確率的完全性と漸近的到着時刻最適性を保証する。 - 実用的なroot recycling policyは保証を持たないが、固定数のbackward treesを適応させ、後のrootを置き換えつつ有用な探索進捗を保持する。

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

- 従来のST-RRT*やSI-RRTと比較して、3つの動的ベンチマークで平均初回解時間が短く、平均最終到着時刻が早い。 - 到着時刻が未指定の問題において、多くの到着時刻を探索することで時間的カバレッジを広げつつ、限られた計画予算をより多くのbackward treesに分割する課題に対処している。 - 広い到着時刻範囲でのrecyclingの利点も示している。

3. 技術・手法の肝は？

- GPU並列のspace-time RRT-Connect motion planner。 - 共有のforward treeと適応的なbackward goal-time treesのforestを構築。 - interval root formulationにより到着時刻を連続的にサンプリング。 - 確率的完全性と漸近的到着時刻最適性を保証（ただしroot recycling policyは保証なし）。 - root recycling policyは固定数のbackward treesを適応させ、後のrootを置き換えつつ有用な探索進捗を保持。

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

- 3つの動的ベンチマークでの実験により、ST-RRT*とSI-RRTと比較して、全ての手法が解いた問題で平均初回解時間が低く、平均最終到着時刻が早いことを示した。 - 広い到着時刻範囲でのrecyclingの利点を追加実験で示した。 - 実ロボット実証として、UR5eが移動するCrazyflie quadrotorsの間でroot-recycling ST-pRRTCが動作計画を行うことを示した。

5. 議論はある？

- interval root formulationは確率的完全性と漸近的到着時刻最適性を保証するが、実用的なroot recycling policyにはそのような保証がない。 - 到着時刻が未指定の問題において、多くの到着時刻を探索することの課題（限られた計画予算の分割）に対処する必要がある。 - その他の議論や限界については要旨からは不明。

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

- ST-RRT*: 比較対象として挙げられているspace-time RRT*の研究。 - SI-RRT: 比較対象として挙げられているSI-RRTの研究。 - その他の関連手法や同分野の定番については要旨からは不明。

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

著者: Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu

分類: cs.RO

原文アブストラクト

We propose ST-pRRTC, a GPU-parallel space- time RRT-Connect motion planner for problems with known obstacle trajectories and unspecified arrival time. Searching over many arrival times broadens temporal coverage but divides a finite planning budget among more backward trees. To address the challenge, ST-pRRTC builds a shared forward tree and an adaptive forest of backward goal-time trees. Its interval root formulation samples goal arrival times continuously and guarantees probabilistic completeness and asymptotic arrival- time optimality under the stated assumptions in a bounded time domain. The practical root recycling policy has no such guar- antees. It adapts a fixed number of backward trees, replacing later roots while retaining useful search progress. Experiments on three dynamic benchmarks show that both variants achieve lower mean first-solution times and earlier mean final arrivals than ST-RRT* and SI-RRT on problems solved by all compared methods. Further experiments demonstrate the benefit of recy- cling over broad arrival-time ranges. Real-robot demonstrations show root-recycling ST-pRRTC planning motions for a UR5e among moving Crazyflie quadrotors.

arXivで原文を読む →arXiv概要ページ

← 論文一覧