AI技術開発部アルゴリズムグループの谷本です。今回はマップマッチ結果を複数出すロジックについて紹介します。GPSだけだと走った道路を特定し切らないときに「道路の走行軌跡の候補を複数出して」後で絞る、といった使い方をしたいときに用いることができます。

マップマッチとは

マップマッチとは、車両のGPS位置情報の軌跡から「車両がどの道路を走ったか」を推定する技術です。マップマッチはモビリティ関連で広く使われている技術で、MoTでは以下の用途で利用しています。

タクシーアプリ「GO」の車両位置の表示
お客様探索ナビ[1]

スクリーンショット 2021-10-18 18.50.14.png

従来のマップマッチは1つのGPS系列から1通りのマップマッチ結果（「道路の走行軌跡」と同義)を出力しますが、今回は曲がるタイミングが異なる複数のマップマッチ結果を推定を行います(下図で言う緑と赤の軌跡)

スクリーンショット 2021-10-19 9.31.53.png

複数のマップマッチ結果の使い道

GPS位置情報だけでは道路の走行軌跡を1つに絞れない時、ありえる走行軌跡のパターンを複数出力して、後で別な情報を元に正しく推定する、といったときに用いることができます。

たとえば、車両が高速道路の高架下を走っている場合、GPSの軌跡は下の地図のように高架を走っているか、下道を走っているか見た目だけでは判断がつかなくなるときがあります。この場合、マップマッチ処理で道路の走行軌跡を1つに絞らず、高架を走っているパターン・下道を走っているパターン両方の結果を出し、後で(ドラレコの動画があれば)ドラレコの動画を確認しどちらのパターンかを判断します。

スクリーンショット 2021-10-29 10.14.22.png

複数のマップマッチ結果の算出ロジック

マップマッチでは「隠れマルコフモデルベースのアルゴリズム[2]」がよく使われています。GPS系列 $x_t$ を観測状態、実際走っている道路の列 $r_t$ を隠れ状態(求めるべき状態)とし、

時刻 $t$ 時点でのGPS点 $x_t$ は実際走っている道路 $r_t$ にのみに依存する。
時刻 $t$ 時点で走る道路 $r_t$ は、一つ前の時刻 $t-1$ 時点で走る道路 $r_{t-1}$ にのみ依存する。

と仮定した状態空間モデルを使ったアルゴリズムになります。

スクリーンショット 2021-10-19 10.15.07.png

今回、複数のマップマッチ結果を算出するために確率の高い上位 k 個の道路列を求めます。その際に「隠れマルコフモデルベースのアルゴリズム」に以下の2つ工夫を行います。

(1) 時刻 $t$ での上位 $k$ 件の結果を求める際、時刻 $t-1$ の上位 $k$ 件の結果を利用する

隠れマルコフモデルベースのアルゴリズムでは、「時刻 $t$ で道路 $r_t$ に遷移する最も確率の高い道路列とその確率」は「時刻 $t-1$ で計算した最も確率の高い道路列とその確率」を用いて帰納的に計算することができます(Viterbiアルゴリズム[3])。この考え方を応用させて「時刻 $t$ で道路 $r_t$ に遷移する確率の高い上位 $k$ 個の道路列とその確率」は「時刻 $t-1$ で計算した確率の高い上位 $k$ 個の道路列とその確率」を用いて帰納的に上位 $k$ 件を計算していきます。(下図は $k=2$ の時の処理終了後のViterbiダイアグラム)

スクリーンショット 2021-10-28 2.22.27.png

(2) 第 $k$ 位( $k \ge 2$ )の道路列を計算する時に第 $k-1$ 位までの道路列と明らかに異なるものを取り出す

(1) のように上位 $k$ 件を単純に持ってくると、GPS点のマッチ先だけが変わって曲がるタイミングが異なる「複数のマップマッチ結果」は得られません。

スクリーンショット 2021-10-28 1.08.31.png

そこで、 $t$ 時点で道路 $r_t$ に遷移する第 $k$ 位( $k \ge 2$ )の道路列を計算する時に第 $k-1$ 位までの道路列と本質的に異なるものだけを扱うようにします。ここでいう「明らかに異なる」というのは以下の条件を満たすことを言います。

時刻 $t-1$ の道路 $r_{t-1}$ から道路 $r_t$ に遷移する際、「 $r_{t-1}$ → $r_t$ を繋ぐ道路列」が第 $k-1$ 位までのどの道路列も含まない、かつどの道路列にも含まれない

スクリーンショット 2021-10-28 2.04.23.png

こうすることで曲がるタイミングが異なる「複数のマップマッチ結果」を得ることができます。

最後のGPS点の道路 $r_i$ まで上位 $k$ 件の道路列が求まったら、道路列の中で確率が高い順に「明らかに異なる」上位 $k$ 件の道路列を求めていきます。

実験

上記ロジックを高速道路付近を走る道路に適用して、うまく異なる複数のマップマッチ結果が得られるか実験します。入力GPSデータは、5分間1秒間隔のデータ(GPS点300点)で、下の地図で拡大している付近は高架上の高速道路(首都高速３号渋谷線)と下道(玉川通り)が並行して並んでいます。この入力GPSデータに対して上位5件まで計算してみます。

スクリーンショット 2021-10-29 10.10.02.png

重複を加味せず上位5件を計算((1)のみ適用)し可視化したものを下図に示します(左側は入力GPSデータの一部、右側は上位5件のマップマッチ結果)。5件とも下道の方にマップマッチされて、高速道路を走る軌跡が表示されておらず、期待する異なる複数個のマップマッチ結果が得られません。

スクリーンショット 2021-10-28 0.39.09.png

重複を加味して上位5件を計算((1)(2)を適用)し可視化したものを下図に示します(左側は入力GPSデータの一部、右側は上位5件のマップマッチ結果)。高速道路にマッチされている赤点の軌跡、下道にマッチされている緑色の軌跡が表示されており、期待する異なる複数個のマップマッチ結果が得られています。

スクリーンショット 2021-10-29 10.12.02.png

おわりに

今回は[2]のアルゴリズムをベースに以下の工夫をすることで複数のマップマッチ結果を求めることができました。

時刻 $t$ での上位 $k$ 件の結果を求める際、時刻 $t-1$ の上位 $k$ 件の結果を利用する
第 $k$ 位( $k \ge 2$ )の道路列を計算する時に第 $k-1$ 位までの道路列と明らかに異なるものを取り出す

Reference

[1]AIでタクシーの収益性向上と人手不足解消へ次世代タクシー配車アプリ「MOV」 AI需給予測による「お客様探索ナビ」の商用化開始
- https://dena.com/jp/press/4550
[2] Newson P. & Krumm J., “Hidden Markov map matching through noise and sparseness,” Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems GIS 09, 336, 2009
- https://www.microsoft.com/en-us/research/publication/hidden-markov-map-matching-noise-sparseness/
[3] WIkipedia 「ビタビアルゴリズム」
- https://ja.wikipedia.org/wiki/ビタビアルゴリズム