最適制御のための分散前方ツリー探索：被覆性、複雑性、計算量

本論文は、非線形システムのための前方伝播に基づくkinodynamicプランナーを提案している。特に、differentially flatな非線形システムのクラスにおいて、決定的な有限サンプルでのnear-optimality保証を持つプランナーを開発する。提案手法はDispersive Forward Tree search (DFT*)と呼ばれ、前方ツリーを幅優先で展開し、並列ハードウェアに自然にマッピングされる。unicycle、trailer car、quadrotorなどのプラットフォーム向けに効率的なdispersive samplerを設計し、埋め込みプロセッサ上での挑戦的なプランニングタスクを評価している。

従来のsteering-basedプランナーは状態間の境界値問題の解決を必要とし、非線形プラットフォームでは困難である。前方伝播はsteering要件を回避するが、有限サンプルでの挙動は未解明で、実装は実用的に性能が劣っていた。本手法は、前方ツリーがcertified trajectory classをカバーするために指数サイズが必要であることを示しつつ、コスト条件付きのdominance pruningにより多項式サイズでnear-optimalityを維持する点が新しい。また、決定的な有限サンプル保証を提供する点で先行研究と異なる。

手法の核は、differentially flatシステムに対して局所的に分散する制御コマンドのセットを構築し、前方ツリーを展開することである。control-affineシステム向けの一般的なdispersive command setの構築メカニズムを提供する。また、コスト条件付きのdominance pruning手順を導入し、ツリーサイズを多項式に抑えつつnear-optimalityを保証する。DFT*は幅優先探索で実装され、並列化に適している。

unicycle、trailer car、quadrotorの各プラットフォーム向けにdispersive samplerを設計し、挑戦的なプランニングタスクを評価した。DFT*は、同等の解時間で最先端のkinodynamicプランナーと比較して、一貫して競争力があり、しばしば大幅に優れた解品質を示した。また、receding-horizonループでの実装により、動的環境でのリアルタイムプランニングを埋め込み級の計算予算で実証した。

要旨からは、提案手法の理論的保証はdifferentially flatシステムに限定されること、また、dispersive command setの構築がcontrol-affineシステムに依存することが議論の余地として考えられる。また、ツリーサイズの多項式性はコスト条件付きのdominance pruningに依存しており、コスト関数の性質によっては保証が弱まる可能性がある。しかし、要旨には明示的な議論は記載されていない。

要旨で参照されている関連研究としては、steering-based plannersやkinodynamic planningの既存手法が挙げられる。具体的には、RRTやRRT*などのサンプリングベースのプランナー、またdifferentially flatシステムのプランニングに関する研究が関連する。次に読むべき論文としては、kinodynamic planningの基礎的な論文や、differentially flat systemsのプランニングに関するサーベイが考えられる。