データ駆動型マルチエージェント経路計画に関する研究がAAMAS 2022に採択されました
この度、OSXにて取り組んでいたデータ駆動型のマルチエージェント経路探索に関する研究がInternational Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022) に採録されました。本研究に関する発表は、セッション1A3–1（5/12 0:00–1:00）および2C3–3（5/12 18:00–19:00）に予定されています。
Keisuke Okumura, Ryo Yonetani, Mai Nishimura & Asako Kanezaki. “CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces.” AAMAS 2022 (In Press). [arXiv] [Project] [Code]
本成果は、東京工業大学からインターンでお越しいただいていた奥村圭祐さん、技術アドバイザの金崎朝子先生 との研究によるものです。
研究の背景
マルチエージェント経路計画
本研究では、マルチエージェント経路計画（Multi-agent path planning; MAPP）と呼ばれる問題に取り組みました。これはある環境において、複数のエージェントが互いにぶつかることなく自身のスタートからゴールまで移動できるような経路の組を計画する問題で、工場や倉庫におけるモバイルロボットによる自動搬送、自動運転車両やドローン群の協調的な移動など、多くの応用先があります。
マルチエージェント経路計画に対する既存アプローチの多くは、環境を碁盤目のようなグリッドで表現し、その上をエージェントが前後左右に移動できるという前提で経路を計画します。これに対して我々は、エージェントが環境中において障害物のない任意の場所に移動できうる、いわば「連続空間における」マルチエージェント経路計画問題に注目しました。同問題に対しては、環境中からランダムに選ばれた地点を頂点として構成するグラフ（ロードマップ）を構築し、その上で複数エージェントの経路を探索するアプローチが知られています。このようなロードマップを用いることで、エージェントの動きが前後左右といったように制約されないので、より良い経路を発見できることが期待されます。
マルチエージェント経路計画に効果的なロードマップとは？
しかしながら、連続空間におけるマルチエージェント経路計画問題において、どのようなロードマップが効果的であるかは、実のところ自明ではありませんでした。これは、ロードマップの頂点数に基づいて、経路計画で得られる解の良さと計画コストとの間にトレードオフがあるためです。もしロードマップが多数の頂点で構成されている場合ーつまり、エージェントが移動可能な場所を多数考慮する場合、より良い経路が得られる可能性が高まりますが、一方で経路計画のための計算コストは莫大になります。逆に、ロードマップを構成する頂点数が少ない場合は計算コストを大きく削減できますが、良い解を得ることのみならず、そもそも衝突のない経路の組を見つけることすら難しくなっていきます。
提案手法
Cooperative Timed Roadmaps (CTRMs)｜”協調的”なロードマップ
これに対して我々は、Cooperative Timed Roadmaps (CTRMs)と名付けられた、マルチエージェント経路計画に適したロードマップのあり方と、その具体的な構成法を提案しました。CTRMsは、エージェントごとに個別に用意されたロードマップ（群）であり、少数の頂点で構成されつつも、エージェントはそのロードマップ上で互いを避け合いつつも良い経路を見つけることができます。下図に、典型的なグリッド型のロードマップ、ランダムな頂点から構成されるロードマップ、そしてCTRMの比較を載せました。他のロードマップと異なり、CTRMsは環境の一部の頂点のみ構成された小さなグラフとして表現されていることが分かります。
深層ニューラルネットの学習によるCTRMsの構築
それでは、このようなCTRMsは一体どのようにして構築することができるでしょうか？我々は、この問題に対して、機械学習を活用したアプローチを提案しました。提案手法では、あらかじめ時間をかけて収集した大量のマルチエージェント経路計画問題とその解経路を用いて深層ニューラルネットワークモデルを学習します。このモデルは各エージェントについて、自身およびその周辺エージェントの情報を入力とし、「そのエージェントが他のエージェントと衝突することなくゴールに到達するために次に進むべき地点」を予測することができます。このような予測プロセスを、各エージェントのスタート地点からゴール地点に至るまで複数回繰り返すことで、それぞれに特化した、少数の頂点からなるロードマップを構築することができるようになります。
CTRMsの効果
実験では、21–40のエージェントと多数の障害物からなるマルチエージェント経路計画問題について、CTRMsを使った場合とその他のロードマップを用いた場合での性能比較を行いました。全体的に、CTRMsは大幅に少ない頂点で構成されながらも、他のロードマップと同等の経路計画成功率を達成でき、またその経路長も他手法と同等～場合によっては改善も確認できました。
提案手法の詳細
ここでは提案手法の詳細についてもう少しだけ解説します。
本研究で学習するモデルは、基本的には条件付き変分オートエンコーダ(conditional variational autoencoder; CVAE) [Sohn et al., NeurIPS-15] を拡張したものになります。このCVAEは、ある時刻ステップにおける各エージェントについて、自身および周囲のkエージェントについて、現在位置やゴールの相対位置、自身の周りの障害物の配置、自身の大きさや最大速度などを入力xとしてエンコードし、そのエージェントが次の時刻ステップに進むべき位置yについての条件付き確率分布 p(y|x) を学習します。
とりわけエージェント数が多い場合、それぞれのエージェントの移動方向が周囲のどのエージェントからどのように影響を受けるかは非自明です。これに対して本研究は、VAIN [Hoshen et al., NeurIPS-17] と呼ばれるアテンション機構ベースのモジュールを用いることで、エージェント数に依存しない形で上記の影響を学習します。
また、各エージェントの移動方向に関する分布は、周囲のエージェントや障害物の配置に応じて「左に迂回する」「直進する」といった離散的な戦略に影響され、複数のモードを持ちます。Gaussian reparameterizationをベースにしたスタンダードなCVAEではこのような複数モードの分布をうまく扱えないことから、提案手法は(1) 観測から移動方向に関する戦略をワンホットベクトルとして推定し、(2) 推定された戦略に条件付けられる形で次の移動先を予測する、という多段のアプローチを採用しています。実験では、このような戦略の推定の有無によって、プランニングの成功率が大きく異なることを確認しています。
いったんCVAEが学習されると、新たな問題インスタンスに対しても、エージェントの配置を入力として次の移動先を予測し、またその移動先を入力として次の移動先を予測し、・・・という手続きにより、移動経路の「候補」を生成することができるようになります。この候補経路を多数生成し、互いにつなぎ合わせることによって、各エージェントのスタートからゴールを効率的かつ多様につなぐロードマップ＝CTRMが構築できます。このとき、各エージェントの移動先をすべて学習モデルによって生成するのではなく、一定の割合で移動先をランダムに選択することで、ロードマップの多様性をより向上させることができます。
ソースコードの公開とライブラリ開発
本研究成果を再現するPyTorchコードはGitHub上で公開されています。さらに、同成果をJAXで再実装し、連続空間におけるマルチエージェント経路計画のためのロードマップ構築・評価のためのライブラリも開発しました。オムロンサイニックエックスでは、成果を論文として発表するだけではなく、オープンソースの形で広く公開することでのコミュニティ貢献を目指します。
インターンの募集
本論文は、筆頭著者である奥村さんのインターン中の取り組みの成果です。インターン期間の様子は、彼自身のブログでも見ることができます。
オムロンサイニックエックスでは、2022年度も引き続き通年でインターンを募集しています。深層学習とマルチエージェント経路計画の融合的アプローチに加え、マルチエージェントのためのローカルプランニング、実環境への適応を目指した転移学習など、本研究をさらに発展させるためのプロジェクトが用意されています。さらに、マニピュレーションのためのロボット学習やソフトロボットの開発をふくめ、ロボティクス、機械学習、コンピュタービジョン、HCI分野における幅広いプロジェクトについてインターンを募集中です。皆様のご応募をお待ちしています。
