著者:ryo.kabutan
MoveItの各プランナーについての解説（WMD 2019 in Tokyo 準備編）
0. はじめに
本記事はWorld MoveIt Day 2019 in Tokyo（WMD 2019 in Tokyo）へ参加するにあたり，MoveItで使用できるプランニングアルゴルリズムに関して解説します．
MoveItでは非常に多くのプランニングアルゴリズムが利用できます．プランニングアルゴリズムは理論や実装方法によって軌道の計算時間や軌道そのもののが大きく変わるため，ユーザにあまり意識させないような実装にMoveItは設計されているものの，実は非常に重要な要素です．しかしその豊富さが災いして，結局どのアルゴリズムがよいのかわからなくなっているのが現状です．そこでこの記事では現段階で実装されているアルゴリズムについて整理しようと思います．
アルゴリズム内部を理解していると，適用先のロボット，環境によってどのアルゴリズムが適しているかを判断しやすくなりますので，この記事を読んでアルゴリズムの理解を進めていきましょう．
1. プランニングアルゴリズム
MoveItで利用可能なアルゴリズムの系統図を作りました．
MoveItにはplanning_interfaceというインターフェースで，様々なプランニングアルゴリズムのライブラリ等に接続できるように設計されています．そのため現在進行形でMoveItで使用できるアルゴリズムは増えています．
Planners Available in MoveIt
https://moveit.ros.org/documentation/planners/
1.1 OMPL
MoveItではOpen Motion Planning Library (OMPL)というオープンソースのライブラリを使用することができます．OMPLは，種々の乱数ベースの探索アルゴリズムが実装されています．ランダムサンプリングベースの手法とも呼ばれます．OMPLはMoveIt Setup Assistantを使用して作成したパッケージ内で自動的に利用できるようになっていますので，特に意識したことはないかもしれません．OMPLはMoveItとは独立したライブラリで，MoveItはOMPLをプラグインという形で利用します．有名どころだとRRTやPRM，その他にも非常に多くのアルゴリズムを使用できます．
Open Motion Planning Library (OMPL)
https://ompl.kavrakilab.org/
OMPLに関しては大きく分けて，木構造を構築する手法とロードマップを構築する手法に分けられます．
そして更に高速化を目指した手法，解の最適性を目指したものと細分化されます．基本的に計算時間と解の最適性はトレードオフの関係です．どちらを重視するかによってアルゴリズムは使い分けるとよいでしょう．例えば，同じ軌道を何回も使用する場合は最適性を重視したほうがいいですし，その場限りの軌道を生成したい場合は高速で解の探索性能が高いものを選ぶといった感じです．
この系統図には載せることができていないものがたくさんあるので，使用できるアルゴルズムはここを参照してください．ただしOMPLにはMoveIt側が対応していないアルゴルズムも存在します．
Available Planners
http://ompl.kavrakilab.org/planners.html
1.2 CHOMP
Covariant Hamiltonian Optimization for Motion Planning (CHOMP)というアルゴリズムで，軌道自体の最適化を行う手法です．動作の滑らかさと障害物との距離に関する指標の和で表現した評価関数を最小化することでロボットの軌道を得ます．上記で説明したOMPLで実装されたランダムサンプリング手法では直接的な軌道を評価することが難しいため，CHOMPではその問題を解決することができます．
元論文
CHOMP: Covariant Hamiltonian Optimization for Motion Planning
https://ieeexplore.ieee.org/document/5152817
公式チュートリアル
https://ros-planning.github.io/moveit_tutorials/doc/chomp_planner/chomp_planner_tutorial.html
1.3 STOMP
Stochastic Trajectory Optimization for Motion Planning (STOMP)というアルゴリズムで，こちらも軌道最適化アルゴリズムの一つです．STOMPはCHOMPと似ているアルゴリズムです．CHOMPは与えられた評価関数を最適化する（＝軌道を求める）際に，勾配を計算する必要があります．一方でSTOMPは勾配を計算することなく確率的な手法によって与えられた評価関数の最適化を行います．STOMPはCHOMPと比較して計算時間がかかるものの，解の発見に関するロバスト性は向上しています．
元論文
STOMP: Stochastic trajectory optimization for motion planning
https://ieeexplore.ieee.org/abstract/document/5980280
公式チュートリアル
https://ros-planning.github.io/moveit_tutorials/doc/stomp_planner/stomp_planner_tutorial.html
1.4 SBPL
Search Based Planning Library (SBPL)に実装されているアルゴリズムを利用することができます．このライブラリでは，グラフ探索ベースのプランニングでダイクストラ法やA*などのアルゴリズムが使用できます．ただしMoveItのチュートリアルでも解説がなく，MoveItのインターフェースもあまり更新されていないようです．
一応，SBPLをMoveItで使用できるリポジトリがあったので紹介しておきます．
GitHubリポジトリ
https://github.com/aurone/pr2_sbpl_interface_config
https://github.com/aurone/moveit_planners_sbpl
1.5 その他
最近アップデートされ，今後活発になるのではないかと思われるプランナの紹介をしておきます．
- TrajOpt Planner：CHOMP，STOMPと同じ軌道最適化手法．公式チュートリアルあり．
- MoveIt planning plugin for RapidPlan：FPGAを使用したプランニング手法．アルゴリズム自体はランダムサンプリングベース．
２. ランダムサンプリング手法と軌道最適化手法について
ランダムサンプリング手法，軌道最適化手法，これらの2つの手法は解を求めたあとに後処理（Post Processor）が必要か否かが異なります．
RRTなどで得られた解はランダムサンプリングが故に，得られた軌道はギクシャクしたものになります．そのためMoveItの実装では解導出後に追加処理を実行しています．この処理自体をPost Processorと呼びます．
この処理もOMPLが提供しています．MoveItが呼び出している処理を図に示します．
図のように無駄な経由点を削除したり置き換えたりすることで，解の洗練を行っています．
逆に，軌道最適化手法ではこの処理は必要ないため，計算時間の節約になるケースも考えられます．
またMoveItではOMPLを用いて大まかな経路を求めたあと，その解を初期解としてCHOMPやSTOMPに入力し更に最適な解を得る方策をとっているチュートリアルもあります．すごいですね！！
Planning Adapter Tutorials
https://ros-planning.github.io/moveit_tutorials/doc/planning_adapters/planning_adapters_tutorial.html
3. ベンチマークのすすめ
前章までで，MoveItで使用できるアルゴリズムの簡単な説明を行いました．
実際のところ理論的な話だけでは，現実はうまくいまないものです．
どのアルゴリズムがどんな問題にむいているのかはまだ体系的にはわかっていないので，経験的に知る必要があります．
したがって適用先のロボットと環境で各手法のベンチマークを行いましょう．
MoveItでは，実際の環境とロボットの条件（使用ロボット，開始終了姿勢）を設定し，また検証したいアルゴリズムを指定することで，各アルゴリズムでのベンチマーク結果を自動的にPDFやCSVに出力してくれる機能があります．この機能によって，得られた解の経路長，滑らかさ，解の発見率，計算時間などのベンチマーク結果を得ることができます．
Benchmarking
https://ros-planning.github.io/moveit_tutorials/doc/benchmarking/benchmarking_tutorial.html
MoveItを使用してアプリケーションを開発している方にも，アルゴリズム開発をしている研究者の方にも非常に使えるツールなのでぜひ使ってみてください．
4. 最後に
この記事では，MoveItで使用されているアルゴリズムの説明を行いました．
MoveItでは現段階でも非常に多くのアルゴリズムを試すことができます．
また慣れてくると自分で作成したアルゴリズムをMoveItに対応させることもできます！
この記事でMoveItを使うだけでなく中身の実装や，アルゴリズムに少しでも興味を持っていただけたら幸いです．
ryo.kabutan editor
コメントを投稿するにはログインしてください。
著者について