Incremental Sampling-based Algorithms for Optimal Motion Planning¶
本ノートは経路計画の有名なアルゴリズムRRT*が提唱され, その Asymptotic Optimality が証明された Karaman and Frazzoli による論文の読書ノートである.
Date: 2019/2/2
| Author: | Sertac Karaman and Emilio Frazzoli |
|---|---|
| Year: | 2010 |
| Accepted: | arXiv |
Abstract¶
個々数年でRRT(というかこいつ以外にあるっけ)のような incremental-sampling-basded algorithms が実用的であり, probabilistic completeness といった理論的な保証を得られている.
しかしこれらのアルゴリズムにより得られる解の理論的な上界は与えられていない. この論文の第一の趣旨は, RRTに含まれる最短の経路は, (本当に)最短の経路へと収束しないということである.
第二にRRGなるアルゴリズムが考案され, RRGにおける最短経路は, ほとんど確実に最短経路へと収束する.
第三にRRGのtreeバージョンであるRRT*が提案され, RRGのAsymptotic Optimalityを維持しながらRRTの木構造を保つ.
Introduction¶
第一, 第二パラグラフは省略. ありがちなアプリケーションやその重要性, 動作計画がどのような問題なのか, ということを書いている. 解が存在するならば必ず解を求めることのできるものは complete であるという.
初期の algorithmic なアプローチは complete な planner を開発することに焦点が当てられていた. 多角形の障害物における多角形のロボットとか, 代数的に解くやつとか. なんかどこかで聞き覚えがある. しかしそれらは計算複雑性の観点から formidable ではなく, 実用的でなかった(当時の計算機のパワーも問題だったのでは？).
これも motion plannning では有名な話. 1979にReifにより, motion planning の問題の基本的な定式化においてさえ, PSPACE-hard に属することが示されたため, complete な計画器は実用的ではないことを示唆した.
実用的な経路計画手法としては セル分解法, 人口ポテンシャル法, ロードマップ法などがある. これらの問題は completeness の要請を resolution-completeness に緩和した. つまりアルゴリズムの resolution が十分小さければ completeness が保証される. これらの手法は成功を収めたが, 実用的な利用は高々5次元程度までに制限されていた. セル分解法はセルの個数から, 人口ポテンシャル法は局所解から制限を受けたため.
最近の進展で最も影響があるのは, sampling-based である. 簡単に言えば, 障害物の存在しない領域からランダムに選ばれた点の集合を連結し, ロードマップを作成する(環境の強い connectivity, 特に初期状態と終端状態の connectivity を強く仮定する).
sampling-based のアルゴリズムは計算量を節約できる, 理由はほとんどの動作計画アルゴリズムと異なり障害物を陽的に表現する必要がないため. 純粋な completeness は持たないが, サンプルの数を増やすことで経路を求められない確率がゼロへと収束する, probabilistic completeness を有している.
また環境が良い可視性を持っているのなら, 減衰率は指数的である(途中に細長い corridor を含まないのならとか). sampling-based のアルゴリズムが経験的にうまく行っているのは, 環境が良い可視性を有しているからともいえる.
Sampling-Based Algorithms¶
sampling based にはPRMとRRTの2つがある. 状態空間においてサンプルを接続するというアイデアは両者のアプローチで同じであるが, ロードマップを構築する方法で異なる.
PRMとその変種はmuptiple-queryである, すなわち予め障害物の存在しない領域の大部分をカバーするグラフを構築し, 初期状態と終端状態を連結する最短経路を求めることで各queryを処理する.
PRMは障害物の陽的な表現が必要でないため, 高次元にも拡張できると報告されている[17]. またPRMprobabolistically completeであり, 探索に失敗する確率がゼロに指数的に収束する.
それから一時期PRMは研究の中心的なテーマであったらしい.
工場のフロアのような高度に構造化された環境ではmultiple-queryな手法は価値があるが, ほとんどのオンラインの問題はmultiple-queryは必要としない. そもそも環境を予め知らないこともあるため.
また予めロードマップを求めておくのが計算量的に厳しいこともある.
これらの問題にtailoredされて, サンプリングベースの手法がPRMのオンライン手法の代わりとして現れた. これらのアルゴリズムのincrementalな性質により解が求まったらすぐに終了することができる.