2019-09-07

【強化学習】モデルベースとモデルフリー

強化学習

ベルマン方程式の記事で価値関数を再帰的な形で定義しました．

状態価値関数
$V^{\pi}(s) = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a) \bigl( R(s,a,s')+\gamma V^{\pi}(s') \bigr)$

行動価値関数
$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a) \bigl( R(s,a,s')+\gamma \sum_{a'} \pi(a'|s') Q^{\pi}(s',a') \bigr)$

おさらいすると強化学習は，この価値関数が最大となるような方策 $\pi(a|s)$ を求めることを目的としていました．

良い方策を求めるためには，価値関数を推定しなければなりません．価値関数の式を見ればわかるように遷移関数と報酬関数がわかっていれば価値関数を算出することができます．

環境（遷移関数や報酬関数）のことをモデルと呼び，方策を学習する際に，環境が既知の場合は「モデルベース」，環境が未知の場合は「モデルフリー」と呼びます．

モデルベース

モデルベースによる方策の最適化はプランニングとも呼ばれ，動的計画法に基づいて価値を推定します．推定する方法は「価値反復法」と「方策勾配法」の2種類あります．

価値反復法とは，価値関数が再帰的な形で定義できることを利用して，価値関数の値が収束するまで値を更新する（価値を反復して計算する）という手法です．

価値反復法では，エージェントは行動価値を最大化するような方策を選択すると仮定します．価値をベースに考えるので「value ベース」と呼ばれます．

一方，方策反復法では，価値関数が最大となるように方策を更新して求めます．方策を更新すると価値関数の値も変わるので，方策の更新（方策改善）と価値関数の算出（方策評価）を交互に行って方策を求めます．方策をベースに考えるので「policy ベース」と呼ばれます．

モデルフリー

モデルベースとは異なり，環境（遷移関数と報酬関数）が未知の場合は，エージェントと環境の相互作用により得られたデータを用いながら価値を推定していきます．モデルを陽に用いないで価値を推定し方策を学習する方法をモデルフリーと呼びます．

モデルフリーの場合は，数ステップ毎に価値関数の誤差（TD誤差）を小さくするように価値を学習するTD学習に基づく手法として，Q学習やSARSA などがあります．

ステップ毎ではなくエピソード完了時に価値を修正する手法としてはモンテカルロ法やProfit Sharing などがあります．

2019-09-05

【強化学習】ベルマン方程式と価値関数

強化学習

強化学習とはの記事で，強化学習の概要とマルコフ決定過程 (MDP) について触れました．

強化学習の目的は，長期的な報酬（割引報酬和）を最大化する方策を求めることでした．

この割引報酬和は即時報酬 $r$ と割引率 $\gamma$ を用いて次の式で表されるのでした．

$G_{t} = r_{t+1} + \gamma r_{t+2} + \gamma^{2} r_{t+3} + \dots + \gamma^{T-t-1} r_{T} = \sum_{k=0}^{T-t-1} \gamma^{k} r_{t+k+1}$

強化学習ではエージェント（行動する主体）は，状態 $s$ のときにどの行動 $a$ を選択するかを記述した方策 $\pi(a|s)$ に従って行動します．

ある状態 $s$ で方策 $\pi$ に従って行動したときの割引報酬和の期待値を状態価値と呼び，以下のような状態価値関数 $V$ で表します．

$V^{\pi}(s)=\mathbb{E}^{\pi} \big[G_{t}|s_{t} \big]=\mathbb{E}_{\pi} \bigg[\sum_{k=0}^{T-t-1} \gamma^{k} r_{t+k+1}|s_{t} \bigg]$

良い方策を求めるためには，良い方策とは何かを評価する必要があります．つまり，ある方策のもとでの価値関数を求める必要があります．価値関数の式を見ればわかるように，価値関数を求めるには将来の即時報酬がわかっておく必要があります．しかし将来の即時報酬は未知であることが多いです．そこでベルマン方程式を用いて価値関数を再帰的な形で表します．これにより価値関数を算出することができます．

状態価値関数

ある状態 $s$ で方策 $\pi$ に従って行動したときの状態価値関数 $V^{\pi}(s)$ は次のように表されるのでした．

$V^{\pi}(s)=\mathbb{E}^{\pi} \big[G_{t}|s_{t} \big]=\mathbb{E}_{\pi} \bigg[\sum_{k=0}^{T-t-1} \gamma^{k} r_{t+k+1}|s_{t} \bigg]$

この状態価値関数の値を求めるためには，将来の即時報酬がわかっている必要があり，実際に行動を起こして報酬 $r_{t+1}, r_{t+2}, \dots$ を算出しなければなりません．これだと，方策を変えるたびに全時刻ステップ実行しなければならないので，非効率です．

そこで，ベルマン方程式を用いて状態価値関数を再帰的に定義します．

まず状態価値関数を式変形すると次のようになります．

$V^{\pi}(s) = \mathbb{E}^{\pi}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\cdots | s_{t} \right]$

$= \mathbb{E}^{\pi}\left[r_{t+1} | s_{t}\right]+\mathbb{E}^{\pi}\left[\gamma r_{t+2}+\gamma^{2} r_{t+3}+\cdots | s_{t}\right]$

$= \mathbb{E}^{\pi}\left[r_{t+1} | s_{t}\right]+\gamma \mathbb{E}^{\pi}\left[r_{t+2}+\gamma r_{t+3}+\cdots | s_{t}\right]$

さらに式変形をするのですが，そもそもの強化学習の目的は，「長期的な報酬を最大化する方策を学習すること」でした．この長期的な報酬は，即時報酬の総和であり，割引率を用いて割引報酬和で表しました．そして割引報酬和は方策 $\pi(a|s)$ のもとで確率的な値をとるので期待値を扱ってました．

ここで即時報酬を，ある状態 $s$ で，ある行動 $a$ をとり，状態 $s'$ になったときにもらえる報酬として $R(s, a, s')$ で書き直します．また遷移確率 $P(s'|s,a)$ を用いて状態価値関数を式変形します．

$V^{\pi}(s) =\mathbb{E}^{\pi}\left[r_{t+1} | s_{t}\right] + \gamma \mathbb{E}^{\pi}\left[r_{t+2}+\gamma r_{t+3}+\cdots | s_{t}\right]$

の第一項は次のように変換できます．
$\mathbb{E}^{\pi} \left[r_{t+1} | s_{t}\right] = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a)R(s, a, s')$

この式の意味は，ある状態 $s$ のときに取れうる行動すべてと，行動を取ったときに遷移する可能性のある状態について報酬を考えるということです．つまり即時報酬の期待値を表しています．

第二項は次のように変換できます．

$\gamma \mathbb{E}^{\pi}\left[r_{t+2}+\gamma r_{t+3}+\cdots | s_{t}\right]$ $= \gamma \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a) \mathbb{E}^{\pi}\left[r_{t+2}+\gamma r_{t+3}+\cdots | s_{t+1}=s' \right]$

ここで， $\mathbb{E}^{\pi}\left[r_{t+2}+\gamma r_{t+3}+\cdots | s_{t+1}=s' \right]$ は， $V^{\pi}(s')$ とみなすことができるので，最終的には次のような形になります．

$\gamma \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a)V^{\pi}(s')$

これらより状態価値関数は，次のように表すことができます．
$V^{\pi}(s) = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a) \bigl( R(s,a,s')+\gamma V^{\pi}(s') \bigr)$

行動価値関数

状態価値関数は，ある状態 $s$ で方策 $\pi$ に従って行動したときの価値を表すものでした．しかし時には，実際にとる行動から価値を求めたい場合もあります．

そこで行動価値関数 $Q^{\pi}(s,a)$ というものを定義します，これは，ある状態 $s$ の時に，方策は考慮せず行動 $a$ をとり，その次からは方策 $\pi$ に従って行動をとった場合の価値を表しています．

行動価値関数については，こちらの記事の説明がとてもわかりやすかったのでリンクを貼らせてもらいます．ぜひ参照してみてください．

qiita.com

行動価値関数は行動が決まった状態での価値を表すので，状態価値関数での方策に対して期待値を考えていた部分を消して，次のように表すことができます．

$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a) \bigl( R(s,a,s')+\gamma V^{\pi}(s') \bigr)$

また行動価値関数 $Q^{\pi}(s,a)$ と，状態価値関数 $V^{\pi}(s)$ は次のような関係にあります．

$V^{\pi}(s) = \sum_{a} \pi(a|s) Q^{\pi}(s,a)$

ある状態 $s$ において行動 $a$ をとったときの価値である状態価値関数に対して，それぞれの行動が起こる確率を掛け合わせることで，ある状態 $s$ における価値，状態価値関数を求めることができます．

これを利用して，状態価値関数は次のように変形できます．

$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a) \bigl( R(s,a,s')+\gamma V^{\pi}(s') \bigr)$
↓
$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a) \bigl( R(s,a,s')+\gamma \sum_{a'} \pi(a'|s') Q^{\pi}(s',a') \bigr)$

まとめ

これで価値関数をベルマン方程式の形で定義することができました．これにより，将来の即時報酬がわからなくても再帰的に価値関数の値を求めることができます．

強化学習やマルコフ決定過程の問題では，長期的な報酬を最大化する方策を求めることを目的としていました．方策の更新，評価に価値を用います．つまり価値関数の値を求めることで，方策を求めることができます．

2019-09-05

【強化学習】強化学習とマルコフ決定過程

強化学習

AI囲碁のAlphaGoに使われていることで有名ですが，囲碁を例とすると，試合に勝つことを目的として，どのように碁石を打っていくかを学習する手法を強化学習といいます．

機械学習の教師あり学習では正解を与えますが，正解を与えることが困難なものもあります．例えば「自転車の漕ぎ方」を学習するとき，自転車を倒すことなく前に進めたら良いことはわかりますが，具体的に身体をどのように使うか（筋肉をどのように制御するか）を教えることは難しいです．そのため私たちは転んだり擦り傷を作ったりしながら試行錯誤して自転車の漕ぎ方を学習していきます．

このようにどのような状態になれば好ましいかは明確だが，それを達成する方法は明確でない（正解の方法を作るのが難しい）事柄を学習する方法を強化学習といいます．

強化学習では，行動，状態，環境，報酬，方策といった単語が出てきますが，囲碁だと，

行動：碁石を打つ
状態：盤面
環境：碁盤
報酬：勝敗
方策：ある状態のときにどこに碁石を打つか（そのような行動を取るか）

となります．

毎回自分の番に報酬を最大化するような行動をとったとしても，最終的に試合に勝てるかはわかりません．目的は試合に勝つことなので，長期的に見て，どういった行動を取ったら良いか，つまり，どのような方策が良いかを学習する必要があります．

そのため，強化学習では長期的な報酬を最大化するような方策を学習します．

マルコフ決定過程

強化学習はマルコフ決定過程をベースにしています．

ある事象 $X$ が $x$ となる確率を $p$ とするとき， $X$ を確率変数， $x$ を実現値といい，次のように表します．

$Pr(X=x)=p$

サイコロを例にすると，「サイコロを振るときに出る目」が「1」となる確率は「1/6」というのは，次のように表します．

$Pr(X=1)=\frac{1}{6}$

確率変数と確率を対応づけたものを確率分布といいます．

確率変数が時間に依存する場合を確率過程と呼び， ${X_t, t \in T}$ と表します．

確率過程では，ある時刻 $t$ の確率変数 $X_t$ の実現値が $x$ となる確率は，1時刻前までの実現値に依存します．

$Pr(X_t=x|X_1=x_1, \cdots, X_{t-1}=x_{t-1})$

ここで， $Pr(X_t=x)$ が1時刻前の実現値にのみに依存するという性質をマルコフ性と呼び，マルコフ性を持つ確率過程のことをマルコフ過程といいます．

確率変数を状態変数とすると， $Pr(X_t=x|X_{t-1}=x_{t-1})$ は状態遷移確率とみなせます．状態変数が離散的で有限なときをマルコフ連鎖 (Markov Chain) といいます．

さらにマルコフ連鎖に行動と報酬の概念を加えたものをマルコフ決定過程 (Markov Decision Process; MDP) といいます．つまりMDPとは「次の状態は直前の状態とそこでの行動のみに従う」という性質を持つ環境（動的システム）のモデルのことです．

強化学習とマルコフ決定過程

マルコフ決定過程 (MDP) の定式化について説明します．

MDP $\triangleq \langle S, A, P, R, \gamma, \pi \rangle$

行動： $a \in A$
状態： $s \in S$
遷移関数： $P(s'|s,a)$ （ダイナミクス）
報酬関数： $R(s, a, s')$ （即時報酬）
割引率： $\gamma \in [0,1$ ]
方策： $\pi(a|s)$

MDPでは，ある状態 $s$ において，方策 $\pi(a|s)$ に従って，行動 $a$ をとり，遷移関数の確率 $P(s'|s,a)$ に従って，次の状態 $s'$ に遷移し，報酬 $R(s, a, s')$ を受け取ります．

MDPの問題設定は，長期的な報酬を最大化するような方策を求めることです．つまり強化学習の目的と同じです．

長期的な報酬は，即時報酬の総和で表現します．( $R(s,a,s') = r_{t+1}$ )

$G_{t} = r_{t+1} + r_{t+2} + r_{t+3} + \dots$

しかし将来の即時報酬は確率てきな値であるので割り引いて考えます．割引率 $\gamma \in [0,1$ ]を用いて次のように表します．これを割引報酬和や収益と言ったりします．

$G_{t} = r_{t+1} + \gamma r_{t+2} + \dots + \gamma^{T-t-1} r_{T} = \sum_{k=0}^{T-t-1} \gamma^{k} r_{t+k+1}$

$\gamma$ が0に近い値のときは即時的な報酬に焦点を当てるようになり，逆に1に近い値をとるときは長期的な報酬に焦点を当てるようになります．割引率は問題設定によって異なります．

MDPでは，この割引報酬和を最大化するような方策を求めます． MDPでは，遷移関数と報酬関数が既知であることが前提であり，一般的に，線形計画法や動的計画法で解くことができます．しかし，遷移関数と報酬関数が未知の場合は，実際に行動しながら，これらの情報を得る必要があります．この問題を解くのが強化学習です．

以上，簡単に強化学習の基礎的な部分に触れました．

2019-09-05

【強化学習】目次

強化学習

強化学習とマルコフ決定過程
ベルマン方程式と価値関数
モデルベースとモデルフリー
モデルベース（価値反復法，方策反復法）
モデルフリー（モンテカルロ法，Q学習，SARSA，Actor-Critic）
方策勾配法，方策勾配定理
- REINFORCE
- DPG（決定論的方策勾配法）
- TRPO, PPO

逆強化学習，模倣学習

マルチエージェント強化学習

MADDPG

2019-08-22

SUMOチュートリアル「TraCI4Traffic Lights」

交通シミュレーション

オンラインでシミュレーションの値の取得や状態の変化を行うことができる機能「TraCI (Traffic Control Interface)」を使ったチュートリアルを行ったので記録しておきます．

TraCIは，TCPで制御する側（クライアントと言ったりコントローラと言ったりする）とSUMO間のメッセージを行います．

このチュートリアルでは制御する側はPythonのスクリプトで書き，シミュレーションの値を取得したり，指示を送ったりします．

C++, Python, Javaにはデータからメッセージを作成するクラスが用意されています．

実際のコードは， <SUMO_HOME>/docs/tutorial/traci_tls もしくは，<SUMO_HOME>/tests/complex/tutorial/traci_tls にあります．（自分のSUMOのバージョン0.32.0では前者の方でした．）

やること

北から南へ電車が，東西を車が通行する状況において，「電車が通行するときは，東西の信号を赤にし，車の通行を止める」といった動作ができるようにします．

f:id:ryonsd:20190822100108p:plain

python runner.py

で，シミュレーションを実行することができます．

解説

runner.py のコードを見ていきます．

内容としては，

TraCIのインポート
ルートファイル（車両の発生，経路の設定が記述されている）の生成
TraCIによる通信（信号の制御）方法の定義
シミュレーションの設定，実行

となります．

TraCIのインポート

Python用に用意されているTraCIのライブラリへのパスの設定，インポートを行います．

from __future__ import absolute_import
from __future__ import print_function

import os
import sys
import optparse
import subprocess
import random

# Python用に用意されているTraCIのライブラリへのパスを設定する
try:
    sys.path.append(os.path.join(os.path.dirname(
        __file__), '..', '..', '..', '..', "tools"))  # tutorial in tests
    sys.path.append(os.path.join(os.environ.get("SUMO_HOME", os.path.join(
        os.path.dirname(__file__), "..", "..", "..")), "tools"))  # tutorial in docs
    from sumolib import checkBinary  # noqa
except ImportError:
    sys.exit(
        "please declare environment variable 'SUMO_HOME' as the root directory of your sumo installation (it should contain folders 'bin', 'tools' and 'docs')")

# TraCIの機能を使うためにインポート
import traci

ルートファイルrou.xmlの作成

SUMOは，道路ネットワークファイルのnet.xml と車両の経路を設定したルートファイルrou.xml を用いてシミュレーションを行います．net.xml は事前に作成されているので，rou.xml を作成します．

def generate_routefile():
    random.seed(42)  # make tests reproducible
    N = 3600  # number of time steps
    # demand per second from different directions
    pWE = 1. / 10
    pEW = 1. / 11
    pNS = 1. / 30 #30秒ごとに電車が発生する
    # xml形式での記述
    with open("data/cross.rou.xml", "w") as routes:
        print("""<routes>
        <vType id="typeWE" accel="0.8" decel="4.5" sigma="0.5" length="5" minGap="2.5" maxSpeed="16.67" guiShape="passenger"/>
        <vType id="typeNS" accel="0.8" decel="4.5" sigma="0.5" length="7" minGap="3" maxSpeed="25" guiShape="bus"/>

        <route id="right" edges="51o 1i 2o 52i" />
        <route id="left" edges="52o 2i 1o 51i" />
        <route id="down" edges="54o 4i 3o 53i" />""", file=routes)
        lastVeh = 0
        vehNr = 0
        for i in range(N):
            if random.uniform(0, 1) < pWE:
                print('    <vehicle id="right_%i" type="typeWE" route="right" depart="%i" />' % (
                    vehNr, i), file=routes)
                vehNr += 1
                lastVeh = i
            if random.uniform(0, 1) < pEW:
                print('    <vehicle id="left_%i" type="typeWE" route="left" depart="%i" />' % (
                    vehNr, i), file=routes)
                vehNr += 1
                lastVeh = i
            if random.uniform(0, 1) < pNS:
                print('    <vehicle id="down_%i" type="typeNS" route="down" depart="%i" color="1,0,0"/>' % (
                    vehNr, i), file=routes)
                vehNr += 1
                lastVeh = i
        print("</routes>", file=routes)

TraCIによる通信の定義

シミュレーションのステップ毎にTraCIによりSUMOと通信を行い，車両の位置情報の受信，信号の制御命令の送信を行います．

net.xmlの中で次のように信号の状態を定義しています．この信号はID"0"が割り振られいます．Gが緑，rが赤，yが黄色で，信号の色を表しており，左から順に北東南西の信号です．

<tlLogic id="0" type="static" programID="0" offset="0">
    <phase duration="31" state="GrGr"/> <!-- index=0 -->
    <phase duration="6" state="yryr"/> <!-- index=1 -->
    <phase duration="31" state="rGrG"/> <!-- index=2 -->
    <phase duration="6" state="ryry"/> <!-- index=3 -->
</tlLogic>

この信号の定義をもとに，信号を制御しています．TraCIのPythonのAPIについては，こちらに詳しく載っています．

def run():
    """execute the TraCI control loop"""
    step = 0
    # ID"0"のこの信号のindex=2の状態に信号を設定しています．つまり東西の信号を青にしています．  
    traci.trafficlight.setPhase("0", 2)

    # traci.simulation.getMinExpectedNumber()で，道路ネットワーク上にある車両の数と，まだ開始を待っている車両の数を返します．
    # これが0より大きいときに traci.simulationStep()でシミュレーションを1ステップごと実行します．
    while traci.simulation.getMinExpectedNumber() > 0:
        traci.simulationStep()
        # 現在の信号の状態 (indexの値) が2の場合に
        if traci.trafficlight.getPhase("0") == 2:
            # 信号のある交差点上に車両が
            if traci.inductionloop.getLastStepVehicleNumber("0") > 0:
                # いる場合は
                traci.trafficlight.setPhase("0", 3)
            else:
                # それ以外の場合は，東西の信号が青(index=2) の状態を維持する
                traci.trafficlight.setPhase("0", 2)
        step += 1
    traci.close()
    sys.stdout.flush()

このようにTraCIを使い，現在のシミュレーション上の車両の状態を取得し，それによって信号を制御しています．

シミュレーションの実行

シミュレーション時にGUIを使用するかや，TraCIを起動したときに実行するファイルの設定などを行い，シミュレーションを実行します．

def get_options():
    optParser = optparse.OptionParser()
    optParser.add_option("--nogui", action="store_true",
                         default=False, help="run the commandline version of sumo")
    options, args = optParser.parse_args()
    return options


# this is the main entry point of this script
if __name__ == "__main__":
    options = get_options()

    # this script has been called from the command line. It will start sumo as a
    # server, then connect and run
    if options.nogui:
        sumoBinary = checkBinary('sumo')
    else:
        sumoBinary = checkBinary('sumo-gui')

    # first, generate the route file for this simulation
    generate_routefile()

    # this is the normal way of using traci. sumo is started as a
    # subprocess and then the python script connects and runs
    traci.start([sumoBinary, "-c", "data/cross.sumocfg",
                             "--tripinfo-output", "tripinfo.xml"])
    run()

まとめ

TraCIでは，こちらのようにTCPベースで通信の規定が細かく決まっていますが，Python用に用意されたライブラリを用いることで，直感的に使うことができます． C++, Python, Java以外のTraCIのクラスが設定されていない言語を使うときは，TCPの通信のプロトコルをチェックして使う必要があります． TraCIを使うことで，オンラインでシミュレーションの状態の把握や制御ができるようになります．

2019-08-22

TraCIの使い方

交通シミュレーション

SUMOの追加機能として，オンラインでシミュレーションの結果を取得したり，パラメータを変化させる「TraCI (Traffic Control Interface)」があります．

クライアント（制御する側）とサーバー（SUMO）といった関係で，クライアントからコマンドを送ったり，サーバー側から結果を応答したりすることで，シミュレーションの値の取得や状態の変化を行います．

コマンドの送信や結果の応答はTCPの形で行います．

このTraCIを使用したチュートリアルがあるので，やっていきながら使い方を理解します．

TraCI4Traffic Lights

2019-08-13

KDD2019交通系論文サーベイ（abstractメモ）

論文メモ

KDD2019で発表された論文のうち，"Traffic", "Transportation", "Travel", "Demand", "Urban", "Uber" のキーワードで引っかかった論文のメモです．

交通量予測（7件）
イベント予測（3件）
信号制御（2件）
配車アルゴリズム（2件）
レコメンデーション（2件）
チュートリアル（1件）
（計17件）

交通量予測

集中・発生量予測（どこで発生し，どこへ集中するか）

Urban Traffic Prediction from Spatio-Temporal Data Using Deep Meta Learning

(JD 他)

都市交通の予測のためには，時空間的な相関関係を扱う必要があるが，それはGPS上の位置や近くにあるPOI (Point of Interest：商業施設などの重要地点)，二点間の距離などによって異なってくる
そこで，まずmeta learningにより抽象的な特徴・関係を抽出し，それをもとに時空間的な相関をモデル化する手法「ST-MetaNet」を提案
交通予測にmeta learning を用いたのはこれが初めて
発生・集中量と交通速度を予測する問題設定で，一般的な時系列モデルのARIMAや，Seq2Seqよりも小さい誤差で予測できることを示した

f:id:ryonsd:20190808155921p:plain — ST-MetaNetの概要

UrbanFM: Inferring Fine-Grained Urban Flows

(JD 他)

監視カメラなどの都市をモニタリングするデバイスを大量に使用するにはコストがかかるため，より少ないデバイスからの粗い情報で，できるだけ正確に都市のモニタリングをする技術が必要
都市をグリッド分割し，各グリッドに入ってくる交通量（集中量）を算出．そのデータを画像として扱い，天気などの他のデータと組み合わせて，より細かい粒度で交通集中量を推定する手法を提案
タクシーの交通流と人流のそれぞれのデータセットで提案手法の評価実験を行い，既存手法よりも推定精度が向上したことを示した

f:id:ryonsd:20190811194101p:plain — 交通集中量を推定する提案手法の概要

OD推定（どこから，どこへの交通がどれくらいか）

DeepUrbanEvent: A System for Predicting Citywide Crowd Dynamics at Big Events

(東京大学，産総研)（人流が対象）

大規模なイベント（地震や台風，祭りなど）が行われるときは，人々の安全を守り，公共施設の運用を維持するために，群衆を管理する必要がある．しかしそのような大規模イベントでの人々の行動は日常的な行動とは異なるため，都市全体の群衆の行動を予測するのは難しい
そこで直近１時間の人口密度，人流のデータから，1時間後の人口密度，人流を予測するオンラインシステム「DeepUrbanEvent」を提案
動画のフレーム予測などによく使われるConvLSTMをEncoderとDecoderとして扱うMulti-Task ConvLSTMを予測モデルとして用いている
ARIMAや単純なConvLSTMよりも予測精度を向上した

f:id:ryonsd:20190808165957p:image:w300 — DeepUrbanEventの概要

Origin-Destination Matrix Prediction via Graph Convolution: a New Perspective of Passenger Demand Modeling

OD行列を予測する際に課題となるデータのスパース性を克服するためにGrid-Embedding based Multi-task Learning (GEML)を提案
地図をグリッドに分割し，グリッドをノード，エッジをそのノード間の移動とすることで人の移動をグラフとして扱う．GCNによりエッジの重み（＝移動人数）をモデル化し，LSTMによりそれらの時系列的な変動を学習し，OD行列の予測を行う
UCARとDiDi（中国のライドヘイリング企業）が収集した実際の乗客のODデータそれぞれ1ヶ月分を用いて学習し，1時間間隔のODおよび発生・集中量を予測．グリッドは2~3kmで分割されている（わりと広い範囲に感じるが，車で5分の距離だから許容範囲という主張）
LSTMやGCRN (Graph Convolutional Recurrent Network) などの既存手法よりもOD行列の予測精度を向上した

f:id:ryonsd:20190812162936p:plain — 提案手法GEMLの概要

Co-Prediction of Multiple Transportation Demands Based on Deep Spatio-Temporal Neural Network

タクシーとバイクシェアのpick-upとdrop-off (OD) を推定する問題設定．従来はタクシーやバイクシェア，ライドヘイリングのODを別々に推定していたが，これらは相互に関係し合っているため，まとめて推定する方針をとった
地図をグリッド分割し，OD行列を作成し，それを画像データとして入力．CNN Autoencoder でEncodeし，時刻毎にLSTMに入れて，その後Decodeし，次時刻のOD行列を推定する
この提案手法 CoST-Net (Co-prediction method based on Spatio-Temporal neural Network) は複数交通手段の移動の特徴を統合することで既存手法よりも良い精度でNYのタクシーとバイクシェアのODを予測できることを示した

f:id:ryonsd:20190812170727p:plain — 提案手法のネットワークの概要

配分量予測（どの経路をどれくらい利用するか）

Predicting Path Failure In Time-Evolving Graphs

(香港中文大学, Huawei)

道路ネットワークはノード（センサ局）とエッジ（道路）からなるグラフとして表現できるが，ハードウェアの故障や事故・自然災害による道路閉鎖によりグラフの構造は時間とともに変化する
グラフ構造による交通流の違い，時空間的な関係（通勤時間帯は混雑するなどの時間依存性，ノード間の相関）を扱うために，Long Short-Term Memory R-GCN (LRGCN) を提案
LRGCNで動的に変化するグラフを扱い，Self-Attentive Path Embedding（←Self-Attentive Sentence Embedding）により，固定長ベクトルに落とし込み，そのベクトルをもとに経路が混雑しているかを分類
グラフを動的に扱うことで分類予測精度が向上することを示した

f:id:ryonsd:20190808134939p:plain — Long Short-Term Memory R-GCN (LRGCN) を用いた予測フレームワーク

Graph-based Semi-Supervised & Active Learning for Edge Flows

グラフのエッジの流れ（交通流）が部分的にわかっているときに全体の交通流を推定する半教師あり学習 graph-based semi-supervised learning (SSL) を提案
従来のGraph-based SSLは，ノードがデータ点で，エッジはそのノード間の類似度を表すに過ぎなかったが，提案手法はエッジ情報に着目し，全体の交通量の保存などの制約を入れることでエッジ情報を扱えるようにし，かつSSLという問題設定に取り組んだ
Appendixには，Julia での実装コードがある

f:id:ryonsd:20190811204645p:plain — 全体の40%の交通流（黒線）がわかっている状態から残りの交通流（赤線）を推定する

イベント予測

Deep Mixture Point Processes: Spatio-temporal Event Prediction with Rich Contextual Information

(NTT サービス，コミュニケーション)

イベント（タクシーのpick-upなど）が発生する確率を，天気や地理情報，交通規制・社会イベントのスケジュールなどの要素から予測する
地理情報はマップ＝画像で，交通規制・社会イベントのスケジュールはテキストで与えられる
それらを組み込むために深層学習と混合モデルをベースとした点過程モデルDMPP (Deep Mixture Point Processes) を提案．深層学習(CNN+Attention)で画像・テキストから特徴抽出し，それをもとに混合モデルを構築
従来手法より高い精度でシカゴ市の犯罪を予測している

f:id:ryonsd:20190808113004p:plain — 提案手法の流れ（論文紹介動画より引用）

Learning Dynamic Context Graphs for Predicting Social Events

時系列的なイベントの文書を動的なグラフで表現し，GCN (Graph Convolutional Network) で将来のイベントを予測する手法を提案
ロジスティック回帰＋TF-IDFや時系列データを用いないGCNよりも，Dynamic GCNは精度良くイベント予測できることを示した

f:id:ryonsd:20190812103232p:plain — Dynamic Graph Convolutional Network の概要

Short and Long-term Pattern Discovery Over Large-Scale Geo-Spatiotemporal Data

天気や交通のデータから短期的および長期的なパターンを発見する手法を提案
短期的なパターンとしては雨→事故→渋滞のような伝搬するものを，長期的なパターンとしては道路の建設→交通の変化のようなものを扱っており，ノードが事故，渋滞などのラベル，エッジがそれらの依存関係を表す木構造を構築し，頻出するものを短期的なパターンとして抽出．また時間，場所，タイプの観点から長期的なパターンを抽出．
アメリカでの2年間のデータから90の短期的なパターンを発見し，また長期の混雑，雪，雨，霧などの発生が最も交通流に遅れの影響を与えることを発見した

f:id:ryonsd:20190812145023p:plain — 短期的・長期的パターン発見の流れ

信号制御

PressLight: Learning Max Pressure Control to Coordinate Traffic Signals in Arterial Network

強化学習による信号制御の研究が増えているが，報酬と状態の設計が経験的であり，報酬の要素の重みによって結果が異なってくる，交差点での状態の複雑化が学習時間を増加させるという問題があった
交通分野では，Max Pressure (MP)という，各交差点の圧力（詰まり具合）を最小化することにより交通ネットワーク全体の流れを最大化する分散型交通信号制御戦略がSOTAとなっているが，最適化は貪欲法を用いている
そこで強化学習の，報酬はMPと同じ設定にし，状態はMPで状態遷移の定式化に使われている発展方程式の変数を用いて定義することで，上記の問題を解決する信号制御の手法を提案
交通工学で使われていた手法や強化学習を適用した既存手法よりも移動時間を短縮する信号制御ができることを示した

Time Critic Policy Gradient Methods for Traffic Signal Control in Complex and Congested Scenarios

先行研究よりもより複雑な交差点の状況での信号制御を深層強化学習により行っている研究
信号制御の問題をエピソードベースの設定にし，方策勾配ベースのREINFORCEで方策を学習
交通シミュレーションSUMOで複雑な状況による信号制御をシミュレーションし，提案手法がトータルの待ち時間，排気量を減らし，交通渋滞を減らすことを示した

配車アルゴリズム

A Deep Value-network Based Approach for Multi-Driver Order Dispatching

(DiDi AL Labs 他)

複数のドライバーの長期的な報酬を最大化するような配車アルゴリズムを提案．セミマルコフ決定過程として配車問題を定式化
cerebellar embedding でダウンタウン，郊外，コミュニティパークなど空間的な範囲に応じて階層的になっている位置情報を表現する（階層的な感じが小脳の構造と似ているから？）
価値関数の更新の際に最小化するLoss関数にリプシッツ定数を加えることで価値関数が大幅に変化するのを防ぎ，学習を安定させる
転移学習で他の都市でも使えることを示している

f:id:ryonsd:20190813110023p:plain — caption

Two-Sided Fairness for Repeated Matchings in Two-Sided Markets: A Case Study of a Ride-Hailing Platform

UberやLyft, Ola, DiDiなどのシェアリングエコノミーのエコシステムが成長するにつれて，より多くのドライバーが生活を確保するためにオンラインプラットフォームとそのアルゴリズムに財政的に依存することになるが，そのようなプラットフォームでの収入の分配はドライバー毎に差がある状態である
そこでライドヘイリングプラットフォームにおけるマッチング機能の公平性を最適化するフレームワークを提案
あるドライバーがあるユーザーとマッチするか否かを0-1変数で表し，ドライバー毎の収入の差，ユーザー毎の待ち時間の差を目的関数とする，整数最適化問題として定式化している（ソルバーはGurobi）

レコメンデーション

Hydra: A Personalized and Context-Aware Multi-Modal Transportation Recommendation System

(Baidu 他)

既存の経路検索システムではタクシー，バス，自転車などは別々に扱い，単一交通手段による経路が推薦され，またその時の状況は考慮されていなかった．しかし状況によってはタクシーでバス停まで行ってそこからバスに乗るというような経路が良い場合もあり，ユーザーを十分に満足させる経路推薦はできていなかった
そこで複数の交通手段を組合せた経路を，POI (Point of Interest：商業施設などの重要地点)や天気，個人の嗜好を考慮し状況に応じて推薦するシステム「Hydra」を構築
Baiduの経路検索サービスやBaidu search, Baidu Appの利用データから，交通手段の好みやODペア，ユーザーのprofileを抽出．graph embeddingを用いてユーザーの交通手段の好みを表現
抽出した特徴をもとに勾配ブースティング木(XGBoost)で多クラス分類し，複数経路（自家用車，タクシー，バス，自転車，徒歩，タクシー＆バス，バス＆自転車）のうちユーザーに合っているものを推薦している
なおBaidu Mapでは実際にタクシー＆バス，バス＆自転車の経路も推薦され，Hydraは実サービスとして稼働している模様

f:id:ryonsd:20190809120959p:image:w300 — Hydraで推薦する経路の例（タクシー→バスを含む）

Effective and Efficient Reuse of Past Travel Behavior for Route Recommendation

経路検索で推薦する経路は基本的に最短経路であるが，その経路だと移動しづらいために実際には使われていない場合がある．また同じような嗜好を持つユーザーは同じような経路，場所を好む傾向にある．
そこでGoogle Map などの経路検索サービスやモバイルGPSで得られる使用経路のデータをもとに，よりユーザーにとって効率的で意味のある経路を推薦する手法を提案
使用経路データを分割し，目的地・POIをできるだけ経由する経路に合成する．全ての組合せを考えると計算量が膨大になるので，並列計算できるように工夫している

f:id:ryonsd:20190812234815p:plain — 緑と赤の経路を分割し組合せて，O1~O4（POIやライドヘイリングのpick-up地点など）を通る経路（τ3-1+τ1-2）を生成

チュートリアル

Deep Reinforcement Learning with Applications in Transportation

(DiDi AI Labs)

交通課題に対して深層強化学習をどう使っているかのチュートリアル．（スライドはこちら．AAAI2019のものとほぼ同じ）
DiDi AI Labs のJieping Ye らは，KDD2018やACML2018, IJCAI2019など国際会議でよくチュートリアルを行っており，KDD2019では他にも，Transportation: A Data Driven Approach というタイトルでInvited Talk を行っている
DiDi は，ドライバーの乗客へのリアルタイムの割当や経路計画，信号制御などに対して深層強化学習を用いた研究を行っている

個人的感想

DiDi, Baidu, Huawei, JDなど中国の企業，大学からの発表が多いです．JD DigitsのYu ZhengはMSRA時代からずっと都市交通に関わる研究をしていますし，DiDi AI LabsのJieping YeなどとともにUrbCompというワークショップをKDDで開催しています．CV系と同様に中国勢が強い印象で，この状況は数年変わらないのかなと思います．
内容としてはKDDですのでデータマイニングの要素が強い，交通量予測の研究が多かったです．逆に信号制御や配車アルゴリズムなどの強化学習や最適化手法を用いた研究は比較的少なかったです．
地図をグリッド分割しデータを画像として扱いディープのSOTAの手法で予測する，道路ネットワークをグラフとして扱いGCNで予測する，といった流れが多いように感じました．その中でもmeta learningを適用したり，複数交通手段を扱ったり，新しい流れもできつつあるように感じました．

モデルベース

モデルフリー

状態価値関数

行動価値関数

まとめ

強化学習とマルコフ決定過程

深層強化学習

逆強化学習，模倣学習

階層型強化学習

マルチエージェント強化学習

やること

解説

TraCIのインポート

ルートファイルrou.xmlの作成

TraCIによる通信の定義

シミュレーションの実行

まとめ

交通量予測

集中・発生量予測（どこで発生し，どこへ集中するか）

Urban Traffic Prediction from Spatio-Temporal Data Using Deep Meta Learning

UrbanFM: Inferring Fine-Grained Urban Flows

OD推定（どこから，どこへの交通がどれくらいか）

DeepUrbanEvent: A System for Predicting Citywide Crowd Dynamics at Big Events

Origin-Destination Matrix Prediction via Graph Convolution: a New Perspective of Passenger Demand Modeling

Co-Prediction of Multiple Transportation Demands Based on Deep Spatio-Temporal Neural Network

配分量予測（どの経路をどれくらい利用するか）

Predicting Path Failure In Time-Evolving Graphs

Graph-based Semi-Supervised & Active Learning for Edge Flows

イベント予測

Deep Mixture Point Processes: Spatio-temporal Event Prediction with Rich Contextual Information

Learning Dynamic Context Graphs for Predicting Social Events

Short and Long-term Pattern Discovery Over Large-Scale Geo-Spatiotemporal Data

信号制御

PressLight: Learning Max Pressure Control to Coordinate Traffic Signals in Arterial Network

Time Critic Policy Gradient Methods for Traffic Signal Control in Complex and Congested Scenarios

配車アルゴリズム

A Deep Value-network Based Approach for Multi-Driver Order Dispatching

Two-Sided Fairness for Repeated Matchings in Two-Sided Markets: A Case Study of a Ride-Hailing Platform

レコメンデーション

Hydra: A Personalized and Context-Aware Multi-Modal Transportation Recommendation System

Effective and Efficient Reuse of Past Travel Behavior for Route Recommendation

Deep Reinforcement Learning with Applications in Transportation

個人的感想