MoTLab -Mobility Technologies Engineering Blog-MoTLab -Mobility Technologies Engineering Blog-

複数結果を返すマップマッチロジックの紹介

AIAlgorithm
October 29, 2021

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


マップマッチとは

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

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

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

An image from Notion

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

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

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

An image from Notion

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

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

  • 時刻tt時点でのGPS点xtx_tは実際走っている道路rtr_t にのみに依存する。
  • 時刻tt時点で走る道路rtr_tは、一つ前の時刻t1t-1時点で走る道路rt1r_{t-1}にのみ依存する。

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

An image from Notion

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

(1) 時刻ttでの上位kk件の結果を求める際、時刻t1t-1の上位kk件の結果を利用する

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

An image from Notion

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

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

An image from Notion

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

  • 時刻t1t-1の道路rt1r_{t-1} から道路rtr_tに遷移する際、「rt1r_{t-1}rtr_t を繋ぐ道路列」が第k1k-1位までのどの道路列も含まない、かつどの道路列にも含まれない

An image from Notion

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

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

実験

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

An image from Notion

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

An image from Notion

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

An image from Notion

おわりに

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

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


We're Hiring!

📢
Mobility Technologies ではともに働くエンジニアを募集しています。

興味のある方は 採用ページ も見ていただけると嬉しいです。

Twitter @mot_techtalk のフォローもよろしくお願いします!

Reference