自動運転の研究も! 機械学習 × 交通の論文を紹介

R&D部 高橋
初めまして!R&D部の高橋です。JapanTaxi Advent Calendar の13日目を担当させて頂きます。

R&D部ではタクシーに関する自動運転や画像処理を使ったプロジェクトも進めています。これらのプロジェクトを推進するために、最新の技術をフォローすることを目的として、論文の輪講会を実施しています。

今回は論文輪講会で紹介された交通と機械学習に関する論文を紹介します。

Learning to Estimate the Travel Time

Conference: KDD2018

Authors: Zheng Wang (Didi Chuxing); Kun Fu (Didi Chuxing); Jieping Ye (Didi Chuxing)

URL: http://www.kdd.org/kdd2018/accepted-papers/view/learning-to-estimate-the-travel-time

  • DiDiの到着時間予測をする論文で実際のサービスで使っているモデル
  • 到着時間予測とは
    • 出発地から目的地までにかかる時間を予測するタスク
  • 既存のアプローチ
    • 経路に基づいて、道路ごとにかかる時間を足し合わせて到着時間を予測する → 誤差が累積してしまう
    • 経路に関係なく実際の走行ログを使って機械学習を使って予測 → データのカバレッジに問題
  • 提案するアプローチ:Wide-Deep-Recurrent Learning
    •  特徴の異なる3つのモデルをconcatして予測
    • Wideモデル:FactorizationMachineで特徴量を抽出したものにロジスティック回帰で処理。ドライバー・乗客などのパーソナルな特徴を表現
    • Deepモデル:MultiLayerPerceptronで処理。グローバルな特徴を表現
    • Recurrentモデル:経路に従って道路ごとの特徴ベクトルをLSTMで再帰的に処理。ローカルな特徴を表現
  • 実験結果
    • 提案手法の精度が高く、特にRecurrentモデルが有効
    • 通勤ラッシュや休日の予測が外れやすい
    • サービス上でA/Bテストを実施し有効性を確認

実際のサービス上で動かしているものをトップカンファレンスに通せているのが素晴らしいですね。手法に関しても、課題感からシンプルなアプローチを選択しています。

End to End Learning for Self-Driving Cars

Conference: なし

Authors: Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, Karol Zieba(NVIDIA Corporation)

URL: https://arxiv.org/abs/1604.07316

  • カメラの画像のみを入力にして自動運転車のハンドル操作を推定する論文
  • 走行データ
    • 実際にカメラを取り付けた自動車を走らせて、多様な道、天気、光の状況の画像データとハンドル操作を収集
  • Data Augmentation
    • ハンドル操作をずらす、画像をずらす、左右のカメラを学習に使用
  • モデル
    • 5層のCNN層を含む9層のネットワーク
    • 最終層は1/radiusを学習(radius:曲率半径)
  • 実験
    • 実際に18kmを走行し、自動走行時間は98%
    • CNNの層を確認すると道路に沿ったアウトラインを確認

end-to-endの自動運転は実用は難しそうですが、技術的に面白いですね。道路のラインを直接学習していないのにCNN層でラインを認識しています。また、時間方向の情報を一切使わなくても操作ができている点も興味深いです。

Learning Combinatorial Optimization Algorithms over Graphs

Conference: NIPS2017

Authors: Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina(Georgia Institute of Technology), Le Song(Ant Financial)

URL: https://arxiv.org/abs/1704.01665

  • NP困難なグラフ問題のタスクに対してニューラルグラフ埋め込みと強化学習を適用した論文
  • NP困難なグラフ探索とは
    • 例えば、巡回セールスマン問題(TSP)
      • 全てのノードをちょうど一度ずつ巡り出発ノードに戻る巡回路の総移動コストが最小のものを求める
  • グラフ埋め込み:structure2vec
    • \(\mu^(t+1)_{v} \longleftarrow F(x_v, \{\mu^{(t)}_u\}_{u \in N(v)}, \{w(v,u)\}_{u \in N(v)}; \Theta ) \)
      • \(x\): ノードの特徴量
      • \(\mu\): ノードの特徴ベクトル
      • \(N(v)\): 近接ノード集合
      • \(w(v,u)\): ノードv,u間の重み
      • \(F\): 非線形関数 (ニューラルネットワーク)
      • \(\Theta\): パラメータ
    • グラフの構造を反映しながらイテレーションを繰り返す
  • 強化学習:Deep Q-learning
    • \(y=\Sigma^{n-1}_{i=0}r(S_{t+i}, v_{t+i}) + \gamma max_{v’} \hat{Q}(h(S_{t+n}),v’;\Theta ) \)
      • \(Q\): 選択した行動がどれだけいいかを計算する非線形関数(ニューラルネットワーク)
      • \(r\): 報酬。TSPの場合、移動距離
      • \(S\): 状態。TSPの場合、部分的なノード遷移
      • \(v\): ノード
      • \(\gamma\): 割引率
      • \(\Theta\): パラメータ
  • 実験
    • 巡回セールスマン問題、最小頂点被覆問題、最大カット問題で実験
    • 人手で設定した貪欲法よりも近似解に近い

グラフ埋め込みやDQNといったイマドキな技術を使って、グラフ問題に対するアプローチを一般化している論文。弊社で取り組んでいるタクシーの配車支援システムでも部分的に巡回セールスマン問題を解く必要があり、参考になりそうです。

まとめ

交通と機械学習をテーマに論文を3本紹介しました。交通の諸問題は、データサイエンス、画像処理、グラフなど機械学習で解くアプローチが多数あります。

JapanTaxiでは、ITの力で「移動で人を幸せに。」を実現するための一連のサービス開発に取り組んでいます。全部署にてメンバーも積極的に募集しているので、興味のある方はWantedlyもぜひご覧ください!

JapanTaxiに興味を持ったら、まずはお話しませんか?