あなたがGoogleマップを利用する目的は何だろうか？地図を眺めて、まだ見ぬ地に思いを馳せたり、ストリートビューで訪問先の様子をあらかじめ見学したりする事もあるだろう。だが、恐らく最も使われている機能は「どうやって目的地に辿り着けるのか」を調べるルート検索に違いない。
今回、Googleの研究者らは、AIアルゴリズムにより、Googleマップのルート提案を、ユーザー自身の好みに合うようなルート案内を提案してくれる、新たな方法を開発した事を発表している。
逆強化学習
Googleマップの中心的な機能であるルート検索は、有料道路料金、路面状況、到着予定時刻、ユーザーの好みなど、さまざまな要素を考慮した複雑なプロセスである。このような複雑な要因の中で推奨ルートを洗練させるには、高度な技術が必要だ。
Googleによると、3億6,000万ものパラメーターを含むこの新たなモデルは、Googleマップユーザーの実際の運転データを使用して、彼らがルートを決定する際にどのような要素を考慮するかを分析する。AIの計算には、所要時間、通行料、道路状況、個人の好みなどの情報が含まれる。
Googleは、AIと観察された逐次的な意思決定行動を結びつける機械学習の一形態である「逆強化学習（Inverse Reinforcement Learning: IRL）」と呼ばれるアプローチで解決する事にした。
IRLの目的は、エージェントの行動に基づいてその嗜好を解釈することであり、Googleマップにおいてはユーザーの旅行パターンを推測することを意味する。しかし、このような意思決定をモデル化するために使用されるマルコフ決定過程（MDP）の規模と複雑さは、IRLアルゴリズムを拡張する上で大きな課題となる。このようなモデルは、好みの移動時間から地形のタイプまで、ユーザー体験の様々な側面を考慮するのだ。
Google Research、Googleマップ、Google DeepMindのコラボレーションは、この点でのブレークスルーを予告した：Googleマップ用の「大規模スケーラブルな逆強化学習」プログラムの導入である。この取り組みでは、意思決定プロセスにおいて最も重要なノードを決定することで大規模データの管理を支援するグラフ圧縮や、複数の計算やプロセスの同時処理を可能にする並列化などの重要な技術的進歩が活用されている。
このイニシアチブの中心となるのが、新しいIRLアルゴリズムである「Receding Horizon Inverse Planning (RHIP)」である。RHIPは、アルゴリズムの性能とスケーラビリティを大幅に飛躍させるとともに、計画水平線の深さやグリッド解像度などのトレードオフを大幅に制御できることを実証した。これらの要素はルートマッチ率の向上に重要な役割を果たし、AIの意思決定プロセスの有効性と効率性を実証している。
RHIPの導入により、ルート一致率が顕著に向上した。トライアルでは、RHIPに基づくルート提案は、ユーザーによってより頻繁に選択され、アルゴリズムが成功した意思決定プロセスを理解し、再現する能力を実証した。
近くて遠い “Receding Horizon Inverse Planning”
Googleによると、DeepMindとは数年にわたりRHIPに取り組んできたという。実際に移動したルートのすぐ近くでは、このアルゴリズムは計算集約的な確率モデルを使用して、ありそうもない選択肢を検討する。より遠方では、RHIPは電力を節約するため、より単純な決定論的手法に切り替わる。
テストでは、RHIPは、よくチューニングされたマップのベースラインと比較して、運転および二輪車（スクーター、オートバイ、原付など）のルート提案の精度を平均16～24％向上させることができた。AIアプローチを組み合わせることで、それぞれの長所を最大限に活かすことができる。システムはマップユーザーの動きから学習し、時間とともにどのルートを好むかを予測する能力が向上するはずだ。
Googleによれば、これまでAIシステムを大規模に使ってルート計画を立てようとしても、現実の道路網の複雑さゆえに失敗することが多かったという。アルゴリズムが無数の可能性に対応できなかったのだ。
RHIPは現在、洗練されたアプローチでこのハードルを乗り越えることができる。Googleの開発者によると、RHIPはルート計画への逆強化学習の応用としてはこれまでで最大規模であり、データセットとモデルの複雑さの両方において、より優れた性能は規模に関係するという傾向を裏付けるものだという。
このアルゴリズムは世界中のGoogleマップデータに適用されている。しかし、この技術が実際に機能し、実際に一貫してより良いルートを生成するかどうかを判断するには、広範なユーザーテストが必要である。
論文
参考文献
- Google Research: World scale inverse reinforcement learning in Google Maps
- CJ&CO: Google DeepMind Ushers in New Era for Google Maps using Inverse Reinforcement Learning to Sharpen Route Recommendations
研究の要旨
人間の潜在的な嗜好を最適化することは、経路推薦における壮大な課題である。先行研究により、逆強化学習（IRL）に基づく一般的な手法が提供されつつあるが、何億もの状態やデモの軌跡を持つ世界規模のルーティング問題へのスケーリングに成功したアプローチはない。本論文では、グラフ圧縮、空間並列化、および支配固有ベクトルに基づく問題初期化を用いてIRLを拡張する手法を提供する。古典的なアルゴリズムを再検討し、大規模な設定で研究することで、安価な決定論的プランナと高価だが頑健な確率的ポリシーの間にはトレードオフが存在するという重要な観察を行う。我々はこの洞察を、計画地平線を介して性能トレードオフをきめ細かく制御する、古典的IRLアルゴリズムの新しい一般化であるRHIP(Receding Horizon Inverse Planning)に活用する。我々の貢献は、16-24%の大域的な経路品質の改善を達成する政策に結実し、我々の知る限り、実世界の設定におけるIRLの最大インスタンスに相当する。ベンチマーク結果は、より持続可能な交通手段にとって重要な利点を示しており、そこでは所要時間以外の要素が重要な役割を果たしている。最後に、主要コンポーネントのアブレーション研究を実施し、代替固有値ソルバーによる否定的な結果を示し、IRL特有のバッチ戦略によってスケーラビリティをさらに向上させる機会を明らかにする。
コメントを残す