データ駆動型経路探索に関する研究がICML 2021に採択されました
この度、OSXにて取り組んでいたデータ駆動型の経路探索に関する研究が第38回 International Conference on Machine Learning (ICML 2021) に採択されました。
Ryo Yonetani*¹, Tatsunori Taniai*¹, Mohammadamin Barekatain², Mai Nishimura¹, Asako Kanezaki³. “Path Planning using Neural A* Search”, In Proceedings of the 38th International Conference on Machine Learning (ICML), PMLR 139:12029–12039, 2021. [論文] [arXiv] [Web] [コード] [プレス]
* Equal contributions, ¹ オムロン サイニックエックス株式会社, ² DeepMind (M.B.はオムロン サイニックエックスの過去のインターン), ³ 東京工業大学.
ICMLは、機械学習に関する研究を発表する国際会議として、Neural Information Processing Systems (NeurIPS) や International Conference on Representation Learning (ICLR) と並び、当該分野のトップ3の難関会議に数えられています。今年のICMLは、完全にバーチャル開催の運びとなり、7月18日から24日までオンライン上で開催されます。参加費は一般100ドル/学生25ドルと大変安く、参加者数の制限もありませんので、ご興味のある方はぜひ参加登録をしてみてください。OSXからの本研究のスポットライト発表は、日本時間 7月21日 23:05~23:10 で予定されてます。
本研究は、弊社のテクニカルアドバイザーである金崎先生をはじめ、インターンとして以前勤務していたM. Barekatainさんとの共同研究です。Barekatainさんは特に、とてもエレガントなコードを書いて本研究の実験や解析の部分を支えてくれました。
本研究では、新たなデータ駆動型の経路探索手法「 Neural A*」(ニューラル・エースター)と、そのコア技術となる新たなニューラルネットワーク用モジュール「微分可能A*」を提案しています。このモジュールは、標準的なA*探索アルゴリズムをネットワーク上で実行し、探索結果に対して直接損失を計算、逆伝搬することで、経路探索問題のend-to-end学習(一貫学習)を可能にするものです。本手法は、従来の最短経路問題に対して、経路探索アルゴリズムの最適性(厳密に最短の経路を見つける能力)を大きく損なうことなく、探索効率を飛躍的に向上させることができます。また、障害物の情報を持たない生画像のマップに対しても、人間が与えた経路例の学習データから、画像中の通れる場所・通れない場所を自動で学習して経路を探索することができます。
以下では、経路探索にまつわる2つの課題を紹介し、提案手法の基本的なアイディアや技術的詳細について解説します。
最短経路探索問題
はずはじめに、2次元グリッド状のマップに対する経路探索問題を紹介します。経路探索問題は、各問題インスタンスとして、マップと開始点・目標点の位置が与えられています。このとき、経路探索問題の目標は、開始点から目標点までの経路のうち、なるべく短い経路を見つけ出すことになります。では、以下の例を見てみましょう。
上のマップは、通行不可領域(障害物の位置)の情報を黒色で可視化して提示しています。通行可能領域(灰色)に対しては、マップは一般に、きめ細かな移動コストの情報を持つことができます。例えば、未舗装の道路には比較的高いコストを割り当てる、などです。ただ、ここでは議論の簡単化のため、すべての通行可能領域が同一の移動コストを持つことを考え、マップ上の各位置が1(通行可)あるいは無限大(通行不可)のコストを持つとしましょう。
さて、この設定を踏まえ先程の地図を見てみると、私たち人間はおそらく一瞬で(ほぼ)最短の経路を難なく見つける事ができたのではないでしょうか。では、同じことをコンピュータにやらせると、どうなるでしょう。
この動画は、最短経路探索アルゴリズムとして一般的なA*探索の実際の挙動を可視化したものです。ご覧の通り、マップには実は行き止まりがあり、アルゴリズムがそこにハマってしまっていることがわかります。しかし、このような行き止まりの存在に、先程気づきましたか? おそらく、マップを見た瞬間に、無意識のうちに行き止まりや通行路の形といった視覚的手がかりを認識し、ほぼ一瞬で有望な経路とそうでない経路を認識してしまったのではないでしょうか。
この観察から一つの問いが導かれます。それは、コンピュータも我々と同じように視覚的手がかりを利用して、より知的に経路を探索することができるか? というものです。
生画像上での経路探索
先程の例では、探索アルゴリズムが通行可・通行不可の領域を入力マップとして知った上で経路を探索するという、とてもベーシックな例を説明しました。このようなマップ情報は、A*のようなデータ駆動型でない従来の手法にとって不可欠なもので、例えば手動で画像の領域を通行可・不可のラベルでアノテーション等して与えなくてはなりません。では、そのようなアノテーションがなかったらどうなるでしょう。ここでもう一つの面白い問題があります。
上の図では、固定カメラで撮影された実際の屋外のシーンの写真を載せています。左の図を見ると、画像中の色や模様から、交差点や道路沿いに木々が並ぶシーンであることがわかると思います。なので、もし図中の2点の赤点を結ぶ経路を描きなさい、と言われたら、おそらく容易に右図のような道路沿いの経路を描くことができるのではないかと思います。
この観察から得られる、もう一つの問い。それは、コンピュータも我々と同じように視覚的手がかりを利用して、直接的に生画像の上で通行可能な経路を探索することができるか?というものです。
データ駆動型の経路探索
さて、これまでの内容で、経路探索における2つの問題シナリオと、それらに対する、私たちの能力と比べての古典的な探索アルゴリズムの限界点を説明しました。実は、ここで挙げた2つの問題は、実際に近年のデータ駆動型の経路探索に関する研究において、とても関心が高いものです。具体的には
- 最短経路問題に対しては、探索をより効率的に実行するためのデータ駆動型経路探索の研究があります (Choudhury et al., 2018; Qureshi et al., 2019; Takahashi et al., 2019; Chen et al., 2020; Ichter et al., 2020)。
- 生画像上の経路探索問題に対しては、探索アルゴリズムが直接的に生画像上で探索できるようにする研究が、模倣学習や逆強化学習などの観点で進められています (Tamar et al., 2016; Lee et al., 2018; Ichter & Pavone, 2019; Vlastelica et al., 2020)。
データ駆動型経路探索におけるもう一つの重要な観点は、どのようにして学習型探索アルゴリズムに対して教師信号を与えるかという問題です。いくつかの先行事例では、例えば各ノードから他のノードへの最適な経路距離を学習データ中の全マップに対して与えるもの (Takahashi et al., 2019) や、最適な経路を常に発見できる理想的な探索アルゴリズムを学習中に走らせるもの (Choudhury et al., 2018など) などがありますが、これらは計算量が膨大になりがちです。一方、learning-from-demonstrations と呼ばれる、事例からの学習アプローチ (Vlastelica et al., 2020など) は、学習データとして各問題インスタンスに対して実際の経路例(正解経路)を与えるだけのもので、学習データの作成が比較的容易な部類になります。
本研究の貢献
本研究の主な貢献として、これまで別々に研究されてきた上記の2つの課題を同じ枠組み内で扱うことができる手法 Neural A* を提案します。この手法は、両問題に対して事例からの学習アプローチを採用し、それぞれ以下のような結果を得ました。
- 最短経路問題においては、Neural A*は探索効率と最適性のトレードオフの関係を改善し、Choudhury et al. (2018) や Vlastelica et al. (2020) などの既存手法を上回る性能を達成しました。とくに本研究では、既存研究のように単に探索効率を上げるのではなく、同時に探索アルゴリズムの最適性を維持することも目的としています。
- 生画像上の経路探索問題においては、Neural A*は固定カメラ画像に映る歩行者の移動経路予測において、Vlastelica et al. (2020) の既存手法や、その他の模倣学習ベースの手法 (Ratliff et al., 2006; Tamar et al., 2016; Lee et al., 2018) よりも正確な予測を可能にしました。
Neural A*
では、実際にNeural A*がどのようにして上記の2つの異なる問題を同じ枠組み内で解くことができるのかを紹介しましょう。
ガイダンスマップ上での経路探索
さて、勘の良い方は、先程の2つの問題の説明において、共通性があることに気づいたかもしれません。つまり、両者に共通して大事なのは、探索アルゴリズムがアノテーションされたマップと生画像のどちらを対象とするかに関わらず、そのアルゴリズムが入力画像中の視覚的手がかりを探索に活用できるようになること です。
このために、コンピュータがどのように問題インスタンスを視覚的に理解したかを、各ノード(画素)に対するコストで表すことにします。ここでは、そのようなマッピング関数をガイドマップφと呼び、それが与えるコストをガイドコストと呼ぶことにします。そして、このマッピング関数、つまりエンコーダと呼ばれるものを、以下のような畳込みニューラルネットワークを用いて実装します。
ここでNeural A*の鍵となるアイディアは、A*探索をガイドマップ上で行い、ガイドコストの観点で経路コストが最小になる経路を探索する、というものです。ここで、ガイドマップは以下のような役割を果たすことになります。
- 最短経路問題においては、ガイドマップは、入力マップの情報を拡張し、探索中どのノードを優先して探索すべきか、あるいは避けるべきかの優先順位をノードに与え、探索効率と最適性のトレードオフの改善を図る。
- 生画像上の経路探索問題においては、ガイドマップは、通行可能な領域とそうでない領域を入力画像中の色や模様から認識し、それらを低コストなノードと高コストなノードとして探索アルゴリズムに伝える。
これらの工程はまさにNeural A*が実際に経路探索を行う挙動そのものになります。しかしながら、Neural A*が期待された通りに正しく動作するには、事前にエンコーダを適切に学習する必要があります。では、この学習はどのようにして行うのでしょうか?次のセクションで説明しましょう。
微分可能A*モジュールによるEnd-to-end学習
さて、期待されるようなガイドマップが出力されるよう、エンコーダをどのようにして学習するは、実際のところNeural A*のもう一つの要です。
基本的な方針は「ガイドマップ上でA*探索を行った際に求まる経路が、学習データで与えられる正解経路になるべく近くなるように、エンコーダを学習する」というものです。これは一見すると簡単 (?) に聞こえるかもしれませんが、勾配法に基づく学習では単純ではありません。なぜなら、A*探索アルゴリズムには、微分不可能な離散的操作が含まれており、そのため探索結果に対する損失を探索プロセスを介してエンコーダまで逆伝搬することができないからです。
これに対する本研究の提案は、A*探索アルゴリズム全体を微分可能なネットワーク・モジュールとして実現しよう、というものです。
上記のネットワーク図では、微分可能A*モジュールは学習パラメータなしの再帰的レイヤーとして見ることができ、このレイヤーはA*探索の反復操作に対応していて、ガイドマップ上での探索結果(探索ノード履歴マップ)を出力することができます。この探索ノード履歴マップは、前段のガイドマップやエンコーダと逆伝搬可能な計算グラフで接続されてます。このため、探索ノード履歴マップに対して損失を計算し、逆伝搬することで、エンコーダを学習することができます。
微分可能A*モジュールの詳細
もう少し詳しくこの微分可能A*モジュールについて知るために、まずは通常のA*探索がどのようにして行われるかを見てみましょう。
基本的にA*探索は、ノード選択とノード拡張の2つの操作を、目標点が選ばれるまで繰り返すものです。
ノード選択: ノード選択操作 (Algorithm 1の3行目) では、オープンリストと呼ばれるノードのリストから、その時点でもっとも有望なノードを1つ選択します。なお、オープンリストは開始点のみを含むように初期化されるため、最初の選択は必ず開始点ノードになります。ノードの選択は、以下の式によって行います。
ここで、g(v) は開始点からvまでの、その時点での最良経路に沿った移動コストの和で、g(v) は探索中に逐次的に更新されます。一方、h(v) はヒューリスティック関数と呼ばる、vから目標点までの見積もりコストを表す関数で、例えばvと目標点の間の直線距離などが用いられます。これらを合わせて、g(v)+h(v) は開始点から目標点までのvを介した最良経路のコストを見積もります。ここで、式 (1) には微分不可能な arg max操作が含まれていることに留意してください。
ノード選択の後は、選択されたノード v* をオープンリストから削除し、それを今度は別のクローズドリストに追加します (Algorithm 1の4行目)。このクローズドリストは、空の状態で初期化され、探索中に選択されたノードを蓄積的に記録していくものです。
ノード拡張: ノード拡張操作 (Algorithm 1の5~8行目) は、選択されたノードv*の近傍のうち、一度も開かれたことのないノードを、次のノード選択における新たな候補としてオープンリストに追加します。これらの一度も開かれたことのない近傍ノードは、以下の式によって表せます。
探索中、目標点が選択されれば、そこで探索を終了し、目標点からの親ノードをたどること(バックトレース)で見つかった経路を得ることができます。
基本的には、微分可能A*モジュールは、順方向の実行時においては、このA*探索アルゴリズムを1対1の対応で実行します。逆方向(逆伝搬時)においては、探索プロセスのほとんどのステップで厳密な勾配を計算できますが、一部の微分不可能な操作においては近似的な勾配を計算します。
変数定義: 提案手法では、探索アルゴリズムをネットワークのモジュールとして実装するため、変数をそれぞれ行列として表し、各操作を基本的な行列操作の組み合せで実行します。例えば、開始点や目標点などの単一ノードの位置は、2値のone-hot行列(該当ノードの要素のみ1、他は0をとる行列)で表します。ガイドマップ φ (v) や累積コストマップ g(v)、ヒューリスティック関数 h(v) などのマッピング関数は、実数の行列 (Φ, G, およびH) で表します。また、オープンリストやクローズドリストは2値の行列 (O と C) で表します。また、Xを入力マップを表す変数とします。最短経路問題では、Xは通行可ノードで1、通行不可ノードで0をとる2値行列とし、生画像上の経路探索問題では、Xは実数値のカラー画像とします。
微分可能なノード選択: 式 (1) の微分可能なバージョンは、微分可能A*モジュール内で最も重要な部分です。式 (1)の微分不可能性に対応するため、本研究では Hubara and Bengio et al. (2016) による活性化関数の離散化のテクニックを転用します。
ここで関数 I_max (A) は、順動作の際には、行列Aの argmax インデックスを2値のone-hot行列として計算します。逆動作(逆伝搬)時には、この関数は恒等写像、すなわち I_max (A)=A として振る舞うよう定義します。式 (3) での行列Aに相当する部分は、基本的には、負のコスト -(G + H) に対する softmax 関数を温度パラメータ τ 付きで計算するものです。ここで、オープンリスト行列Oは、ノードがオープンリストから選ばれるように制限するための2値のマスクとして機能しています。言い換えれば、式 (3) は 順動作時には負のコストに対するマスク付きのhardmax関数として動作し、逆伝搬時には、その関数があたかも softmax関数であったかのように動作します。
V*のオープンリストOから削除は O ← O - V*で行えます。同様に、V* のクローズドリストCへの追加は C ← C + V* で行えます。なお、V*はone-hot行列で、1回の探索中に同じノードが何度も選択されることはありませんので、OとCは探索プロセス中、常に0か1の2値行列であるように保たれます。
微分可能なノード拡張: V*がone-hot行列として与えられれば、ノード拡張操作は基本的な微分可能な行列操作の組み合わせで容易に実現できます。Xが2値のマップを表す最短経路問題では、式 (2) は以下のように表せます。
なお、実画像問題においては、Xによる乗算項は省略します。式 (4) では、最初の項はV*と固定カーネルKの間の畳み込みを計算することで、V*の近傍を以下のように抽出します。
式 (4) の残る3つの項は、近傍ノードに対してマスク操作をして、ノードが 1) 入力マップX中の通過不可領域にある、2) オープンリストOにある、3) クローズドリストCにある、のいずれかの場合に当てはまるノードがあればそれを除外します。なお、ここでXとOとCのいずれも、先述の通り2値の行列であることに留意してください。また、式 (4) の勾配は 自動微分機能により簡単に計算することができます。
この近傍ノードVnbrを用いれば、オープンリストの拡張は O ← O + Vnbr で行えます。提案手法は、この微分可能なノード選択とノード拡張を、目標点が選択されるまで繰り返します。探索が終了したら、クローズドリストCを、今までに選択されたノードの履歴マップとして、損失評価のために出力します。なお、親ノードのバックトレースにより実際に見つかった経路の計算もできますが、こちらは学習時には用いません。
損失関数: 損失は、探索ノード履歴マップCと学習データで与えられる正解経路マップ^Pとの差を評価します。^Pは、期待する経路上の要素で1、それ以外で0をとるような2値行列です。
提案手法の損失関数は、以下のような、マップサイズ|V|で平均化したL1ロスになります。
この損失関数は、次の2種類のノード選択誤りに対してペナルティを与えるものです。1) false-negativeエラー:本来^Pを見つけるためにはCに入ってなければいけなかったノード。2) false-positiveエラー:^Pと比べCの中で余計だったノード。言い換えれば、この損失はNeural A*に対し、1) なるべく得られる経路を正解のものへと近づける一方、2) より少ないノード探索で実現するよう働きかけます。
特に、最短経路問題の場合では、今回、正解経路 ^Pとして最短経路解を与えています。したがって、この場合の損失はNeural A*に対し、1) なるべく最短経路に近い解を、2) より少ないノード探索で見つけるよう働きかけます。これがまさに、Neural A*が、単に探索効率のみを改善するのではなく、探索の最適性とのトレードオフを改善することの仕組みとなります。
さらなる詳細: 論文では微分可能A*モジュールのさらなる詳細を説明しています。例えば、今回は割愛しましたが、累積コストマップGが開始点から各ノードへの最良経路の累積コストとなるよう、Gを逐次的に更新する方法も本論で説明しています。また、複数のマップに対してA*探索を同時にバッチ処理して学習効果を高める方法や、学習の安定化の方法についても述べています。
最短経路探索問題での評価実験
ベースライン手法
Neural A*の性能評価のため、以下の2つの類似したデータ駆動型の経路探索手法※と比較しました。
- SAIL (Choudhury et al., 2018): データ駆動型の最良優先探索手法であり、ヒューリスティック関数を事例データから学習することで高い探索効率を達成した手法。本実験では、学習サンプルを学習したヒューリスティック関数で導くタイプ(SAIL)と、理想的なオラクルで導くタイプ(SAIL-SL)の2バージョンを試した。
- BB-A* (Vlastelica et al., 2020): データ駆動型の探索手法であり、ブラックボックス微分と呼ばれる、組合せ最適化ソルバーの汎用的な近似的微分法を用いて学習。この手法は提案手法と似ている面があるが、A*探索アルゴリズムを完全なブラックボックスとして扱う点で異なる。
※ これら2つの手法は内部でNeural A*と同様のA*探索アルゴリズムを用いています。
また、今回は非データ駆動型の一般的な探索手法として、最良優先探索(BF)と重み付きA*(WA*)との比較も評価に加えました。さらに、提案手法の変形として、式 (3) で累積コストを無視して常にG = Φ を用いることで、最良優先探索のような挙動をするNeural BFも比較しました。
評価指標
探索性能の定量的な評価指標として、以下の3つを用いました。
- Opt: 手法がどれくらいの頻度で最適(最短)な経路を見つけられたかを 0–100 (%) の値で表す。
- Exp: 通常のA*探索と比べて削減できた探索ステップ数を 0–100 (%) の値で表す。
- Hmean: OptとExpの調和平均。これは探索の効率と最適性のトレードオフがどれだけ改善したかを示すもので、本研究の主たる評価指標として用いました。
結果
評価実験は、MP、Tiled MP、CSMという3種類のデータセットそれぞれに対して行いました。以下の結果が示す通り、Neural A*が最も高いHmeanスコアを達成し、探索の効率と最適性のトレードオフが最も大きかったことがわかります。
定性的な比較は以下の通りです。
生画像上での経路探索問題の評価実験
Neural A*のもう一つのシナリオとして、生画像上での経路探索性能の評価を行いました。ここでは、Stanford Droneデータセットの固定カメラからの屋外画像に対して、歩行者の移動経路の開始点・目標点を与えた際に、実際の歩行経路を正確に予測できるかを検証しました。
評価の際は、実際の歩行者の経路と、その予測結果との間のchamfer距離を計算することで、Neural A*とBB-A*の性能を比較しました。
上の表の結果が示すとおり、Neural A*のほうがより正解との距離が近い経路を予測できており、提案手法の有効性がわかります。
上の図は、実際のいくつかのシーンに対する入力データ、正解経路、および予測結果の例をしてしています。最後の例では、現時点での提案手法の限界点として、複数の可能な経路がある際に正解経路の予測に失敗している例を示しています。
まとめ
- 本研究では新たなデータ駆動型の経路探索手法「Neural A*」と、そのコア技術である微分可能A*を提案しました。
- Neural A*は経路探索にまつわる2つの異なる問題、すなわち従来の最短経路探索問題と生画像上の経路探索問題に対して、統一的なアプローチを提案しました。
- 最短経路探索問題に対しては、Neural A*は探索の効率と最適性のトレードオフを向上させました。
- 生画像上の経路探索問題に対しては、Neural A*は学習データで与えられた経路の実例により近い経路を予測することができました。
さらなる情報
- 論文本論 ではNeural A*のさらなる詳細を説明しています.
- 論文付随の補足資料 ではデータセット作成の際の詳細な手続きや、計算機資源、学習時間の情報、また、ほかの模倣学習ベースの手法との比較結果などを載せています。
- コードレポジトリー では、論文の結果が再現可能なNeural A*や他のベースライン手法の学習およびテスト用コードをはじめ、データセット作成用のコードなども公開しています。
- プロジェクトサイト ではICMLの発表で用いたプレゼンテーションやポスターなどの資料も公開する予定です。
- 問い合わせ: ryo.yonetani -at- sinicx.com
インターン募集の案内
本研究はOSXのPerception Groupのプロジェクトとして行われました。私たちは、他のグループ(Robotics GroupとInteraction Groups)とも合わせて、優秀なインターン生を募集しています。本研究の第3著者であるBarekatainさんもインターン生でした。彼は、実は2回目のインターンで、1回目の際は強化学習に関する研究を行い、その成果を以下の論文としてAIに関する難関会議IJCAI 2020にて発表しました。
Mohammadamin Barekatain, Ryo Yonetani, Masashi Hamaya. MULTIPOLAR:
Multi-Source Policy Aggregation for Transfer Reinforcement Learning
between Diverse Environmental Dynamics. In IJCAI, 2020.
今回は、グループ内で進行中のプロジェクトに加わる形で、短期間のインターン期間のなかで大きな貢献をしてくれました。
OSXでのインターンを希望する方は、こちらの募集案内をお読みいただき、研究業績やスキルなどを記載したCVを添えて internships -at- sinicx.com までご連絡ください。
参考文献(抜粋)
- Chen et al. Learning to plan in high dimensions via neural exploration-exploitation trees. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
- Choudhury et al. Data-driven planning via imitation learning. International Journal of Robotics Research (IJRR), 37(13–14):1632–1672, 2018.
- Hubara et al. Binarized neural networks. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pp. 4107–4115, 2016.
- Ichter and Pavone. Robot motion planning in learned latent spaces. IEEE Robotics and Automation Letters (RA-L), 4(3):2407–2414, 2019.
- Ichter et al. Learned critical probabilistic roadmaps for robotic motion
planning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 9535–9541, 2020. - Lee et al. Gated path planning networks. In Proceedings of the International Conference on Machine Learning (ICML), 2018.
- Qureshi et al. Motion planning networks. In Proceedings of the IEEE
International Conference on Robotics and Automation (ICRA), pp. 2118–2124, 2019. - Takahashi et al. Learning heuristic functions for mobile robot path planning using deep neural networks. In Proceedings of the International
Conference on Automated Planning and Scheduling (ICAPS), pp. 764–772, 2019. - Tamar et al. Value iteration networks. In Proceedings of the Advances
in Neural Information Processing Systems (NeurIPS), pp.2154–2162, 2016. - Vlastelica et al. Differentiation of blackbox combinatorial solvers. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.