Anytime Motion Planning

• 別名: anytime planning, anytime planner
• カテゴリ: Planning & manipulation › Motion planning
• タグ: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

有効な経路をすばやく返し、時間の許す限りそれを改善し続けるモーションプランニング。プランナーをいつ止めても使える答えが手元にある。

定義

エニタイム・モーションプランナー（anytime motion planner）は、実行可能で衝突のない最初の解をできるだけ早く出し、その後は残りの時間を使ってその解を改善する。改善は通常、経路長、実行時間、またはその他のコストを下げる形で行われる。最初の解が得られた後のどの時点でも、それまでで最良の答えを保持しており、中断されればそれを返すことができる。この考え方は、人工知能におけるより広いエニタイムアルゴリズムの概念に由来する。これは 1980 年代後半に Dean と Boddy が導入したもので、解の質と計算時間をトレードオフし、両者の関係を性能プロファイル（performance profile）で記述する。

グラフ探索では、エニタイムな振る舞いは通常、まず重みを付けて膨らませたヒューリスティックで探索を実行し、その後それまでの探索結果を再利用しながら重みを絞っていくことで得られる。Anytime Repairing A（ARA）がその例である。サンプリングベースの計画では、RRT や確率的ロードマップの PRM 変種のような漸近最適なプランナーは本来的にエニタイムである。最初の解の後もサンプリングと再配線を続け、サンプル数が増えるにつれて最良経路のコストは最適値に近づく。Informed RRT や Batch Informed Trees（BIT）は、より良い経路を含みうる領域にサンプルを限定することで改善段階を速める。素の高速探索ランダム木**はこの意味でのエニタイムではない。ゴールにつながった時点で停止するからである。ただし、再起動や後処理を外側に組み合わせることはできる。

時間に伴う改善が滑らかであることはまれである。コストはしばしば階段状に下がり、とくにプランナーが障害物の間の別の隙間を通るルート、つまり新しいホモトピー類に属する経路を見つけたときにそうなる。また、長い間ほとんど改善が得られないこともある。そのため、いつ止めるかの判断はそれ自体が一つの問題になる。早く止めすぎれば質を損ない、遅く止めすぎればロボットが動くのに使えたはずの時間を無駄にする。固定の時間予算が一般的なやり方であり、メタ推論の手法は、それ以上の計算がもはや割に合わなくなる時点を学習または推定する。

重要な理由

ロボットが計画に使える時間が固定され、事前にわかっていることはまれである。エニタイムプランナーはほぼ即座に安全な代替案を示し、余った時間をすべてより良い動作に変えるので、期限内に行動しなければならないが、経路の質、エネルギー、サイクルタイムも重視するシステムに適している。

主な用途

• マニピュレーションのパイプラインにおける、クエリごとの時間予算の下でのロボットアームのモーションプランニング
• 固定の制御周期で行動しなければならない移動ロボットや車両の再計画
• 経路が短いほどバッテリーを節約できる飛行ロボットの経路計画
• ARA* 式に重みを減らしていく、グリッドやラティス上のヒューリスティックなグラフ探索
• いつ計画をやめて行動を始めるかを決めるメタ推論の研究

実際の使われ方

あるモバイルマニピュレータは、OMPL などのライブラリにある漸近最適なサンプリングベースのプランナーでアームの動作を計画する。各クエリには時間予算があり、プランナーは通常その予算の早い段階で最初の経路を見つけ、その後も経路を短くし続ける。チームは記録した多数のクエリについて、経過時間に対する最良コストを記録し、改善の大半が早い段階で得られること、そして障害物を回るより短いルートが遅れて見つかったときにときどき大きく下がることを確認する。毎回予算を使い切る代わりに、一定時間コストが改善しなければ止めるか、学習した停止規則を使い、その後結果にショートカット処理と時間パラメータ化をかけてからコントローラに送る。

よくある誤解

• エニタイムとは最初の解がほぼ最適であることを意味する — 最初の解は最適から遠いことが多く、質はプランナーをどれだけ長く動かすかで決まる
• コストは時間とともに着実に改善する — 通常は不均一な段差で下がり、段差の間には長い停滞がある
• 漸近最適性は時間予算内で良い経路を保証する — それは計算が際限なく増えたときの極限を述べるだけで、有限の期限については何も言わない
• 時間予算を使い切るのが常に最善である — 計画に使う時間は動作に使えない時間なので、早めに止めるほうが良いトレードオフであることが多い

知っておくべき人

• サンプリングベースまたは探索ベースのプランナーを設定するモーションプランニングエンジニア
• リアルタイムの制約の下で作業するモバイルマニピュレーションやナビゲーションの開発者
• 限られた計算での計画を研究するロボット研究者
• 最適なモーションプランニングを学ぶ学生

関連技術

• ARA（Anytime Repairing A）
• RRT*
• Informed RRT*
• BIT*（Batch Informed Trees）
• OMPL

関連用語

• RRT*
• Rapidly-exploring random tree
• Probabilistic Roadmap
• Homotopy Class
• Warm Start
• Motion Planning

関連プロジェクト

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
• Dora AI: Dataflow middleware for AI robotics applications, built in Rust
• OpenMind OM1: AI-native operating system for robots with modular perception, cognition, and action
• Fast DDS: eProsima's high-performance DDS middleware — the default transport under ROS 2