交通のAI研究動向まとめ

こんにちは、関学M１の太田です。ここ半年ぐらい交通×AIを追っかけていたのでまとめておきます。読者層は交通関連の研究したいと思っている人向けです。　　

本記事は、交通×AIの研究をするにあたって概要を掴むのに僕自身もお世話になった勉強教材をまとめました。 内容としては、以下の通りで紹介していきます。正直長くなりすぎたのでどっかで分割するかもです。
- 1. 交通×AIの概観を掴むスライド
- 2. サーベイ論文
- 3. 研究動向 様々な交通機関における需要予測
- 4. 研究動向 タクシーの配車と再配置アルゴリズム
- 5. 書籍
春から交通関連の研究したい人は、1. 2. 5.を読むといいかもしれません。

交通✖️AIまとめスライド

交通業界へのAI応用事例を網羅的に紹介

交通周りの研究をしたい人がトピックを探すのにオススメです！IJCAI2019のチュートリアル資料です。 https://outreach.didichuxing.com/IJCAI2019/tutorial/IJCAI19_Tutorial_AI_in_Transporation.pdf

スマート交通の構想図。上のスライドから引用

サーベイ論文の紹介

説明：交通のデータは、データの種類（画像、グラフ、系列）も多く、時空間データとして扱われることが多いです。タスクも予測、検知、クラスタリング、最適化と様々です。またアプローチも深層学習をはじめ、機械学習、強化学習とあります。なのでややこしくなるので以下３つに焦点を当てて整理すると良いです。
1. データの種類
2. タスク
3. アプローチ
この3つに分けて最近の動向と概観をつかめるサーベイ論文を紹介します。

[1906.04928] Deep Learning for Spatio-Temporal Data Mining: A Survey

深層学習のアプローチに絞り、時空間データマイニングの手法を紹介しています。seq2seqやGCN、ConvLSTMなどをとりあげ、データの種類に合わせて順番に紹介しています。タスクについては、分けて紹介していません。
小出しすると下の図は、生データからタスクまでのプロセスを紹介しています。

一連のプロセス

より具体的にデータのタイプと深層学習のモデルの関係性を分かりやすくまとめた図も紹介されています。

1. データの種類：Event, Trajectory, Point reference, Raster
2. タスク：はっきり分けて紹介していない
3. アプローチ：深層学習のアプローチに絞り網羅的

[1908.10218] Urban flows prediction from spatial-temporal data using machine learning: A survey

都市の人や車などの流入、流出を時空間予測するタスクに焦点を当てたサーベイ論文。アプローチでは、統計ベース、伝統的な機械学習ベース、深層学習ベース、強化学習ベース、転移学習ベースを紹介しています。 具体的なタスクのイメージ図です。

都市の人や車などの流入、流出を予測するタスク

1. データの種類：Point, Network (POI and Events, Road structure data)
2. タスク：流入、流出量の時空間予測
3. アプローチ：統計ベース、伝統的な機械学習ベース、深層学習ベース、強化学習ベース、転移学習ベース

[1711.04710] Spatio-Temporal Data Mining: A Survey of Problems and Methods

交通に限らず、時空間データに対する一般的なタスクをサーベイしています。 最初に各業界への時空間データの応用事例と課題が書いてあるのが特徴的です。
1. データの種類：Event, Trajectory, Point reference, Raster
2. タスク：Clustering, Predictive Learning, Frequent Pattern Mining, Anomaly Detection, Change Detection, Relationship Mining
3. アプローチ：統計ベース、伝統的な機械学習ベース、深層学習ベース

Spatial and Spatiotemporal Data Mining

内容は、上のと変わりません。好みの問題だと思います。ただこのサーベイの最後「Research Trend and Future Research Needs」に時空間ネットワークのデータマイニング（spatiotemporal network data mining）に関して言及していたのは良かったです。

1. データの種類：Event, Trajectory, Point reference, Raster
2. タスク：Anomaly Detection, Prediction, Partitioning, Summarization, Hotspot Detection
3. アプローチ：統計ベース、伝統的な機械学習ベース、深層学習ベース

Trajectory Data Mining: An Overview

都市データでは、良くよく出てくる軌跡データに関してまとめたサーベイ論文です。山でとったGPSデータは、実際の位置からずれていることが多く、そのズレをどう直すかといった前処理の話が前半に多かった印象です。

1. データの種類：Trajectory
2. タスク：Transfer, Anomalies detection, Classification, Pattern Mining, Uncertainty, Data Management
3. アプローチ：統計ベース、伝統的な機械学習ベース、深層学習ベース

[1906.05433] Tackling Climate Change with Machine Learning

気候変動に関する業界と機械学習の繋がりに関するサーベイです。交通は、気候と密接に関係しているのでとりあげられています。 下の表の交通の行だけ見ても、画像認識、時系列解析、強化学習/最適化、不確実性、因果推論、解釈性と様々な取り組みがされいるのが分かります。

交通のための深層強化学習入門

深層強化学習を基礎から説明しつつ、応用例で交通に焦点を当てています。AAAI2019のチュートリアルのスライド形式です。

Forecasting Big Time Series: Old and New

一般的な時系列予測に限ったサーベイスライドです。統計ベース（自己回帰、線形動的システム、テンソル分解）から始まり、深層学習ベース（CNN, LSTM, WaveNet, Seq2Seq）も紹介しています。交通の時空間データを扱うにあたって必要な時系列解析の技術がまとまっています。VLDB2018のチュートリアル資料です。

深層学習による交通の需要予測手法

交通の需要予測に関しては、単純に利用者の位置データだけでなく、線路のネットワーク情報、天気、バス停の情報をどうモデルに組み込むのかが焦点になっていると感じました。基礎技術を紹介した後、移動サービスごとの需要予測技術を紹介します。

基礎技術

DNN-Based Prediction Model for Spatial-Temporal Data

CNNベースでトレンド、周期性、直近の傾向をそれぞれ捉える仕組みを作っています。また、気候といった補助情報もMeta dataとして後からfusionし、一期先予測をしています。 このCNNの機構は、かなり多くの研究で使用されている枠組みです。 なので著者のTensorflowの実装を、pytorchで書き直したのも私のGithubに公開しています。 https://github.com/masamasa59/STResNet-pytorch-master 2016年の論文になります。

Grids versus Graphs: Partitioning Space for Improved Taxi Demand-Supply Forecasts

Taxiの需要と供給を予測するタスクでConvLSTM とGraphLSTMを比較するという論文です。 結果的には、ボロノイ分割時のGraphLSTMの方が精度が高いことを複数のデータセットと評価精度で調べられていました。 論文として、数式も丁寧に書かれているので分かりやすいと思います。実験でも超パラ値の候補まで書いています。
この二つも時空間予測の基本系になることが多いです。

Bike Sharing

バイクシェアリングは、サービス地域の中でも自転車の使用の偏り・駅の利用率の不均衡が問題視されています。そのため、現実問題として自転車を満車の駅から需要のある駅に移動させる必要があります。
そのため、バイクシェアリングのデータ分析、予測、再配置の最適化の論文が出ています。

Bicycle-Sharing System Analysis and Trip Prediction

自転車の利用状況を調査し、移動先予測と移動期間の推定をした論文です。この論文は、BSSの利用状況を年齢や性別、利用時間帯、曜日ごとに調べ結果を可視化しています。
2016年の論文です。

Traffic Prediction in a Bike-Sharing System

将来的に各駅に貸出・返却される自転車の台数を予測した論文です。具体的な手法としては、RGBTですが、細かく特徴量を作っており、現実問題を解くことに高い意識を感じました。

Dynamic repositioning strategy in a bike-sharing system; how to prioritize and how to rebalance a bike station

MDPアプローチで自転車の再配置のためのスケジューリングを行った論文になります。

Taxi

時空間予測モデルの研究の応用例として、乗り合いタクシーではなく普通のタクシーの利用データで各地域ごとの需要が予測されています。

Predicting Taxi Demand Based on 3D Convolutional Neural Network and Multi-task Learning

気候などの外部要因を組み合わせて、乗車と下車のタクシー需要を同時に予測する手法を提案しています。 ネットワークの構成は、基礎技術で紹介した方法と変わりなく、3DCNNを使っているかなどの微妙な違いになります。例えば、異なる時間の乗車と下車の需要の関係を捉えるために図のb内でアテンションを用いています。 3DCNNの畳み込みの図やResidual Unitの構成が分かりやすいので紹介しました。

Crowd Flow

流入(Inflow)と流出(Outflow)を予測するタスクです。例えば、歩行者の数、近くの道路を運転した車の数、公共交通機関（メトロ、バスなど）を利用している人の数が挙げられます。それらを知ることは、リスク評価と交通管理にとって非常に有益です。 Inflowは、特定の時間間隔中に他の場所からある場所に入る群集の交通量です。 Outflowは、特定の時間間隔中に他の場所に向けて今いる場所を離れる群集の交通量を示します。図の(b)で説明すると、歩行者は(Inflow, Outflow) = (3, 1)、車は、(Inflow, Outflow) = (0, 3)になります。

[1701.02543] Predicting Citywide Crowd Flows Using Deep Spatio-Temporal Residual Networks

この論文の良いところは、実験の設定が丁寧に書かれおり、NNのアーキテクチャも細かく書いていて実装しやすいです。この論文で提案されたST-ResNetsのアーキテクチャはくどいですが基礎技術に挙げた手法に酷使しています。 以下の図は既存手法と比較した複数ステップ先予測の結果です。時系列情報だけを頼りにする統計ベースな手法とLSTMの深層学習ベースな手法と空間情報も考慮した提案手法ST−ResNetsやDeepSTを比べています。 考察すると、１期先予測の場合、統計ベースな手法SARIMAと提案手法に差は少ないです。しかし、４期先から差が広がっていることが分かります。また、空間情報を用いないLSTMだと7期先から悪くなっているように見えます。この結果は、データによる部分もあるとは思いますが、別の論文でも似たような結果を見たことがあります。これは、深層学習ベースな時空間予測モデルが長期予測に強いことを示しています。

Estimating People Flow from Spatiotemporal Population Data via Collective Graphical Mixture Models

かなり、深層学習ベースな手法に偏っていますが、統計ベースな手法もあり、データ量が十分にないときでも予測の不確実性を含めて推定することができます。この論文は、時空間人口データから人の流れを推定するための集合的なグラフィカルモデルの混合モデルを提案し、提案モデルの変分推論法も開発しています。ベイジアンの人は、モデリングの部分で面白いと思うので是非読んでみてください。

Metro

旅客の人数を予測することは、メトロ運営側はタイムテーブルの最適化に繋がり、利用者側は目的地の選択、出発時刻、経路決定に役立つそうです。

DeepPF: A deep learning based architecture for metro passenger flow prediction

駅ごとに電車から降りる人数と乗る人数を予測するタスクになります。この論文は、メトロのドメイン知識（電車の時刻表やメトロネットワークの独自のトポロジー構造、流入と流出の保存、列車の到着時間、乗客の歩行時間、発生する遅延時間）をモデルに組み込んでいます。モデルの全体構造は、以下の図の通りです。 CNNではなくLSTMの理由は、タクシーの場合、地理をグリッドに分割しても、隣接するグリッドをタクシーは通ることができますが、地下鉄は隣接する駅が直接繋がっていない場合があるからです（2つの駅が全く異なる地下鉄線上にある）。そのため駅間の相関関係は、地理的距離の代わりに平均移動時間を用いています。それが、図の一番左の機構で駅間の空間特性を抽出しています。真ん中の機構は、駅の時刻表に基づく特徴量になります。交通の特性を上手く外部要因としてモデルに組み込む方法が提案されていることが分かりました。

Traffic Flow

高速道路の交通流量予測は、渋滞の緩和のために役立ち、交通管理局の車両を誘導する意思決定に繋がります。

Attention Based Spatial-Temporal Graph Convolutional Networks for Traffic Flow Forecasting

高速道路の交通流量予測において、新しいアテンションベースの時空間グラフ畳み込みネットワーク（ASTGCN）を提案しています。この論文も、地理をグリッド化せず、CNNを使わずに、交通ネットワークをグラフとしてみたて、近年盛んに研究されているGCNを採用しています。また、時空間アテンションも提案しています。データの種類とノードの持つ特徴が以下の図で示されています。 またアーキテクチャは、最初の技術（時間の近接性、トレンド、周期性をそれぞれ抽出する機構）が土台にあり、時空間アテンションがあるかの違いです。
アテンションの良さを解釈する結果が以下の図です。 左がSan Bernardinoの道路ネットワークから4本が可視化されています。右が空間アテンション行列（ノード間の相関の強さ）を可視化したものです。 ノード9を見るとノード3とノード8に強い相関が表れています。これは、交通ネットワークの空間的近さを上手く反映していることが分かります。

強化学習による配車・再配置アルゴリズム

説明： 配車の最適化と信号制御に強化学習が使用されているケースが多く、特に配車最適化アルゴリズムについて焦点を当てて紹介します。 配車最適化では、タクシー１台をエージェントとしてみなし、自分で設計した報酬を最大化するようにエージェントが方策を学習します。ここ数年では、複数台のタクシーを協調させるため、Multi-Agent RLが研究の中心になっています。また、報酬の設計は、ユーザーの利便性を最大化するか、会社の利益最大化を優先するかなど考える点があります。状態の定義は、論文によってバラバラですが、エージェントの位置や時間が多いです。行動は「再配置するか、配車に行くか」か、「地域がグリッド化されている場合、今のマスに残るか別のマスに進むか」のどちらかが多い印象です。

近年のDiDiの論文を４本紹介した資料

とても幅広く紹介していて分かりやすいです。 speakerdeck.com

上記紹介された論文以降の最近の研究を紹介します。

[2002.06723] Reward Design for Driver Repositioning Using Multi-Agent Reinforcement Learning

introductionに配車、再配置アルゴリズムの歴史が丁寧に書かれいるので、この論文の参考文献から広げて読むのがいいと思います。また、シングルエージェントとマルチエージェントによる行動の違いを図で分かりやすく説明しています。マルチエージェントの学習方法は、Mean Field Multi-Agent Reinforcement Learningを用いています。その説明も絵ときがあり分かりやすい印象でした。アルゴリズムだけ以下に載せときます。この論文自体は、報酬設計の部分にベイズ最適化を導入し、新規性を出しいます。

[1911.11260] Deep Reinforcement Learning for Multi-Driver Vehicle Dispatching and Repositioning Problem

ライドシェアリング会社は、利用可能なドライバーを近くの乗客に割り当てるか、近くにオーダーがないドライバーを再配置の指示をする必要があります。また、ライドシェアリング会社は、複数のドライバーを持ち、動的に変化する需給を考慮した配車と再配置が必要なため、この研究では、Multi-Driver Vehicle Dispatching and Repositioning Problem: MDVDRPという問題設定を作っています。報酬は、協調なしに自分の期待収益最大化を目指すドライバー中心の視点と全ドライバーの収益最大化を目指すシステム中心の視点を分けて実験しています。図で説明すると以下の通りです。

青矢印がドライバ中心の報酬設計におけるタイムスタンプ。赤矢印がシステム中心のそれになります。ドライバ中心だと個々のドライバーの軌跡から割引報酬和が計算されます。点線矢印はお客さんを目的地まで運んでいる状態です。矢印はオーダーです。

方策オフ型のDQNと方策オン型のPPOアルゴリズムで訓練された方策により実験し、DQNはPPOよりもサンプル効率が良いことがわかり、多くの環境で実験した結果、一般的にはドライバー中心の報酬定義の方がシステム中心のアプローチよりも優れているか、少なくともシステム中心のアプローチと競合することを発見したそうです。　　

[1901.11454] Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning

MARLによるオーダーの配車マッチングにのみ焦点を当てた論文です。オーダーの配車マッチングの課題は、短期的な報酬と長期的な報酬の間の最適なトレードオフを見つけることだそうです。最適なトレードオフを見つける理由は、収益の高いオーダーを取ることは、当面の収入に貢献しますが、そのオーダーがドライバーを人の少ない地域に連れて行ってしまうと、長期的には収益に悪影響を及ぼす可能性があるからです。イメージが以下の図です。

三角がオーダーで、丸がエージェントを表しています。

この論文では、Actor-Critic法を拡張することで、可変な行動集合と可変なエージェント数の2つの問題を解決しています。可変な行動集合になる理由は、エージェントの半径r以内のオーダーのどれに向けて配車するかが行動の選択肢だからです。可変なエージェント数は、運転手にも日中オフラインとオンラインがあるそうです。この課題を解決するために、Mean Field Multi-Agent Reinforcement Learningを採用しています。アルゴリズムは以下の通りです。 アルゴリズムの平均的な行動は、エージェントの半径2r 内にいるドライバの数をエージェントの半径r 内のオーダー数で割ったものとして定義されています。つまり、平均的な行動が大きいほど、供給過多、平均的な行動が０に近いほど需要過多を意味します。　　

報酬は、ピックアップまでの距離の短さ、個人の収益の高さ、目的地の需要数−目的地のドライバー数の差の3つです。報酬の3つ目の要因を入れることで、需要過多の地域を目的地とするオーダーを選ぶ行動をします。 実験としては、組み合わせ最適化やルールベースより高い収益を獲得したそうです。

[1905.11353] CoRide: Joint Order Dispatching and Fleet Management for Multi-Scale Ride-Hailing Platforms

再配置と配車アルゴリズムの両方に焦点を当てた論文です。変わっているのは、各タクシーをエージェントにするのではなく、地理のグリッドがエージェントになります。また、階層強化学習からヒントを得て、地理的な階層構造を導入して地域エージェントを作ります。ここでは、大規模な地域をマネージャーエージェント、小規模なグリッドをワーカーエージェントとして扱っています。というのも再配置と配車アルゴリズムの最適化に熱力学からヒントを得ているそうです。図１に示すように、車両とオーダーを別の分子に見立て、再配置と配車マッチングによって分子の数を減らすことでシステムの安定性を高めることを目指しています。そのため、報酬の定義にグリッド内のオーダーの分布と車両の分布のKL項があり、KL項が最小化されるとき、オーダーの数と車両の数を一致させる方法をとっています。発想が凄すぎて他とは状態も行動も違う定義なので興味ある方は読んでください。

Multi-Agent Reinforcement Learning for Order-dispatching via Order-Vehicle Distribution Matching

配車のマッチングに焦点を当てた論文です。報酬は、１日のオーダー全体のうち配車できた割合を示すオーダー応答率(ORR)と各タクシーの累積収入（ADI）の両方を改善しています。先ほどと同様オーダーの分布と車両の分布のKullback-Leibler (KL) ダイバージェンスを用いてDouble Q-learning Networkを拡張し、Centralized learning and Decentralized execution なMARL手法を提案しています。 目的関数は以下の通りです。

また、行動空間が一般に上下左右移動するように固定されているが、オーダーを受理することを行動にすると、行動空間は、時間に依存して変化します。そのため、この論文では、図２のようにQ関数の入力に状態と行動を与えています。

また、環境はグリッドベースなアプローチをとっています。

グリッドベースなアプローチ。三角形がオーダー、点が車両です。

[1903.03882] DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning

乗り合いタクシーを想定したDQNベースな配車アルゴリズムの論文になります。今までは、一台につきオーダーを一度受理するとその間は、他のお客さんを乗せることはできませんでした。乗り合いの場合、エージェントの行動は、目的地に向かう最中に他のお客さんを拾いに行くか、そのまま今のお客さんを目的地に届けるかです。 報酬は、４種類の和で表され、「ゾーンごとの需要と供給のミスマッチ」、「ピックアップの待ち時間」、「乗り合いで発生する追加の車内での待ち時間」と「配車している車の数」を最小化するように行動価値関数を学習します。配車している車の数を最小化する理由は、なるべく相乗りさせ、道路に走る車を減らすことで、渋滞を減らすことに繋がると考えているようです。状態には、将来のオーダーの需要や、車の位置などになります。

Planning and Scheduling Approaches for Urban Traffic Control

信号制御に関するまとめ資料になります。スライド形式です。 https://helios.hud.ac.uk/scommv/storage/TutorialSlides.pdf

書籍

交通関連の最新の書籍も紹介しておきます。

Urban Computing

https://www.amazon.co.jp/dp/0262039087/ref=cm_sw_em_r_mt_dp_U_FvSFEb8GK8TB9 Urban Computingに関する書籍で、広く浅く書かれた技術書だと思います。最後の方に、最近の研究動向としてマルチモーダルな話が書かれています。 買わずともざっくり知りたい方向けに以下の資料があります。
Urban Computing: Concepts, Methodologies, and Applications
http://urban-computing.com/pdf/UrbanComputing-zheng-tist2014.pdf

MaaS モビリティ革命の先にある全産業のゲームチェンジ

https://www.amazon.co.jp/dp/4296100076/ref=cm_sw_em_r_mt_dp_U_XeTFEb5WHA8XQ 私が初めて交通×AIのトピックを知るきっかけになった一冊です。ヨーロッパ中心にMaaSの取り組みを学ぶことができました。

Beyond MaaS 日本から始まる新モビリティ革命 ―移動と都市の未来―

上の続編が最近出版されたみたいです。今度読みます。 https://www.amazon.co.jp/dp/4296105280/ref=cm_sw_em_r_mt_dp_U_PfTFEbRQJ5Y91

スマートモビリティ革命

スマートシティ実現に向けたSAVS (Smart Access Vehicle Service)の概要から技術、実証実験まで広く書かれいています。特に、実証実験の内容がとてもリアルで良かったです。研究界隈や企業でMaaS、スマートシティだと騒いでも、実際に上手くいくかというとそんな簡単な話ではない現実が書かれていました。法律の話も含め、タクシー会社の高齢化など、アメリカや中国と違ってタクシーに高価なイメージが多く利用者が少ない日本でどう取り組むか考えさせられました。研究成果を実世界に落とし込む難しさが書いてあると感じた一冊です。 https://www.amazon.co.jp/dp/4764955563/ref=cm_sw_em_r_mt_dp_U_VgTFEbQ73G08Z

まとめ

どこかでまとめようと思っていたものを年度末までにまとめられて良かったです。 このまとめ記事にない話として画像や動画認識の部分はほとんどありません。自動運転系もしかりです。 強化学習は、まだ勉強途中なので上手く話がまとまっているか微妙ですが、これから理解を深めていきます。