Upgrade to Pro — share decks privately, control downloads, hide ads and more …

タクシー配車アルゴリズムへの強化学習活用:Reinforcement Learning App...

タクシー配車アルゴリズムへの強化学習活用:Reinforcement Learning Applications in Taxi dispatching and repositioning domain

タクシー配車における強化学習活用の動向について、DiDi AI Labのアルゴリズムを勉強会用にまとめた資料です。

A survey of reinforcement learning application in taxi dispatching/repositioning domain. The papers are selected mostly from DiDi AI Lab's publications.

Jun Ernesto Okumura

July 07, 2019
Tweet

More Decks by Jun Ernesto Okumura

Other Decks in Technology

Transcript

  1. 自己紹介:奥村 エルネスト 純 • データアナリスト@DeNA ◦ 領域:ゲーム、オートモーティブ • AI研究開発エンジニア@DeNA ◦

    ゲームAI・強化学習チームリーダー ◦ 案件推進、AI戦略策定 • コミュニティ活動 ◦ 強化学習アーキテクチャ勉強会(https://rlarch.connpass.com/) ◦ Data Analyst Meetup Tokyo(https://data-analyst.connpass.com/) @pacocat 『データサイエンティスト養成読本 ビジネス活用編』(技術評論社) ※成果はGDC2019 / Google Cloud Next 2019で発表 https://dena.ai/news/201905-gdc-next-material/
  2. 本日主に紹介する論文 A Taxi Order Dispatch Model based On Combinatorial Optimization

    (Zhang et al. 2017 KDD2017) ドライバーが配車依頼を自由に選択できる場合にsuccess rateを最適化する問題、乗客のdestination予測 https://www.kdd.org/kdd2017/papers/view/a-taxi-order-dispatch-model-based-on-combinatorial-optimization Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach (Xu et al. 2018; KDD2018) プラットフォームによる配車割り当ての最適化、系列的な意思決定フレームの導入(長期的なmetricを最大化) https://www.kdd.org/kdd2018/accepted-papers/view/large-scale-order-dispatch-in-on-demand-ride-sharing-platforms-a-learning-a Deep Reinforcement Learning with Knowledge Transfer for Online Rides Order Dispatching (Wang et al. 2018; ICDM2018) 深層学習を組み合わせることによる都市間の転移学習の試み https://ieeexplore.ieee.org/application/enterprise/entconfirmation.jsp?arnumber=8594886 Deep Q-Learning Approaches to Dynamic Multi-Driver Dispatching and Repositioning (Holler et al. 2018; NeurIPS2018 WS) マルチエージェントの検証 https://drive.google.com/file/d/0B_utB5Y8Y6D5MGdfQktjQXgySDdPeG0wYnFxRnBJNDl3UlhF/view ※ 主にDiDi AI Labによる論文を紹介します
  3. Overview • 概要 ① ◦ 背景:Taxi 配車では、acceptance rate※を上げることがUX観点で大切 ▪ 特に一部時間/地域では需要過多になり、全体の走行効率の改善が課題になる

    ◦ やったこと:オーダーの受諾確率を推定 した上で、配車効率を最適化 ◦ 結果:北京でA/Bテストを行い、acceptance rate が 80 → 84% に改善 ▪ 合わせて、待ち時間などの metrics も改善 • 概要 ② ◦ 背景:乗客の行き先入力の手間を省くために、行き先の予測機能を導入したい ◦ やったこと:乗車パターンをガウス分布でモデル化 し、行き先候補のlisting機能を開発・提供 ◦ 結果:baseline model と比較して Top3 accuracy が 89 → 93% に改善 ▪ 論文投稿時点で、数千万ユーザー /日に対してserveされている ※ オーダーに対して(供給不足やキャンセルなどなく)マッチさせられる割合(success rate, completion rateなども)
  4. 背景① Taxi order dispatchingのこれまでの傾向 • 「最短距離」「到着時間が短い」ドライバーを探すのが主流 ◦ サービス全体でオーダーの accept rateが最適化されているとは限らない

    ◦ ドライバーの受諾傾向も考慮されていない • DiDiでの状況 ◦ A* algorithmを使って、渋滞情報を加味しながら最短時間で到着する車両を探索 ◦ ラッシュ時には数十万 /秒間のオーダーマッチをする必要がある ▪ 需要過多だとマッチングしないこともあり、配車効率が UXやビジネスに直結する
  5. Driver’s Action Prediction: モデル • Notation ◦ : オーダー がドライバー

    にacceptされる確率 ◦ : 運賃、乗車地、目的地などの情報をエンコードした feature vector(次頁) ◦ : acceptを受けたかどうか(二値) • 例えばLRを使う場合は、ドライバーのaccept確率は以下でモデル化できる
  6. Driver’s Action Prediction: 特徴量 • Order-Driver related features ◦ Pick-upまでの距離

    ◦ ドライバーに送られたオーダー数 ◦ 運転方向とオーダー方向が一致しているか、 … • Order related features ◦ 距離、ETA ◦ 目的地属性(空港、病院、学校、オフィス街、 …) ◦ 経路上の渋滞情報 ◦ 目的地におけるオーダー発生頻度、 … • Driver related features ◦ 過去のaccept rate、直近のaccept傾向 ◦ 普段の営業場所、… • Supplemental features ◦ 曜日、時間(hour of the day) ◦ 近隣のドライバー数、オーダー数、 …
  7. Experiment Design • 北京でのある1日を使って実験 ◦ 配車をランダムに3アルゴリズムに振り分け ◦ データ量は~100万オーダー、8万ドライバー • 比較モデル1(DiDiが当初使っていたアルゴリズム)

    ◦ A* algorithmを使って(渋滞情報を加味しながら)最短時間で到着する車両を探索 ◦ 探索結果に従ってOrder-Driverのマッチングスコアを算出 ◦ 一番スコアの高かった合わせに割り当て • 比較モデル2: ◦ 同じ地理区域の複数のオーダーを、地理的に近い複数のドライバーに割り当て ◦ GlobalなPick-up距離を最小化する ◦ マッチしなかった場合は他ドライバーに渡される
  8. 背景② Destination Prediction • 同じユーザーでも時間帯や乗る場所によって目的地は様々 ◦ 目的地を入力する手間をかけさせるよりは、推薦出来たほうが嬉しいはず • 過去のアプローチ ◦

    Simmons+06:MLPを利用した目的地の予測 ▪ 入力:現在のtrajectory、driver id、ユーザー属性、出発時間、 … ▪ 予測精度は出発地点にかなり依存していた ◦ de Brébisson+15:HMMを使った目的地の予測 ▪ 時間帯が区切られているために連続性が消えてしまう • 今回の文脈 ◦ APP起動時の予測を目指すため、使える情報が限られる(現時点の trajectoryは使えない) ◦ 既存研究は目的地と予測地の距離を最小化していたが、行きたい場所を直接予測したい ▪ ユーザーにとって座標や住所は Unfamiliar ▪ 同じ場所でもユーザーによって認知のされ方は違う( Personalizeが必要)
  9. データから発見できるパターン • ユーザーごとのルーチンがある(通勤やいつもいくお店など) ◦ 同じユーザーは同じ行き先に同じ時間帯に向かう傾向 • 平日と祝休日の傾向は分離できる ◦ 平日は目的地が職場と自宅に集中、休祝日はショッピングセンター、等 •

    同じユーザーは、ある程度限られたset内から行き先を決めている ◦ 週末のショッピングでさえ、目的地が絞り込める ◦ 例外は突然の病院や出張など頻度の低いもの • 目的地と相関のある特徴は、出発時間と出発座標 ◦ 逆に、ドライバー情報、渋滞情報、車両速度、等は相関が弱い
  10. Overview • 背景 ◦ 過去の配車アルゴリズムはその時点におけるマッチングのみを考えていた ◦ より長期的な視点も加味したプラットフォーム全体での最適化 にチャレンジしたい • やったこと

    ◦ 配車を時系列の意思決定過程としてとらえて、長期的視点でのリソース配分を最適化 ▪ 学習:過去データから売上期待を状態価値関数として表現 ▪ プランニング:「即時報酬 +将来の期待収益」が最大になるよう Order-Driver pairを評価 • 結果 ◦ 4都市で行ったA/Bテストで 0.5-5% の売上増を達成 ◦ 実際にDiDiのproductionに反映され、20都市で展開 ▪ 強化学習をこの規模で実適用した例は珍しい?
  11. 配車システムの概要(on-demand ride hailing) • Centralized: 中央サーバーが配車を管理 • 前論文との違い ◦ 前論文ではドライバーが配車受諾を決定していた

    (driver-select-order mode) ◦ 本論文時点では中央サーバーによる割当 (platform-assign-order-to-driver mode)に代わった ◦ DiDiの統計では10%の completeion rate 改善を達成
  12. MDPの定義 • State ◦ t, gはそれぞれ時間とドライバーの場所区域( hexagon mesh)のインデックス • Action

    1. オーダーを割り当てる:乗車地に向かい、乗客を運んで目的地でおろす 2. オーダーを割り当てない( idle):場所を変えずに、時間を 1step進める ▪ 空港や駅に滞在するような場面を想像すればイメージしやすい • Reward ◦ 運賃:エージェントは Gross Merchandise Volume (GMV)最大化する • Discount factor ◦ 将来の報酬をどの程度考慮するか( γ=0.9を採用)
  13. Order Dispatch Optimization • 学習した行動価値関数Qを重みとする2部グラフを考える ◦ i=0, j=0はマッチされないことを表す(デフォルトノード) • Driver-Order

    pairをつないで、Q値の合計を最大化する問題 Driverは一つのOrder node としかつながらない Orderは一つのDriver node としかつながらない
  14. Advantage Function Trick • 最適化にはハンガリアン法(Kuhn-Munkresアルゴリズム※)を利用 ◦ しかし、デフォルトノードの存在によって計算量が多くなってしまう ◦ デフォルトノードとの結合を無視することで計算を効率化 ▪

    具体的には、driver iにつながっている全てのノードから Q(i, 0)≒V(i) を引く ▪ Q - Vのような量を扱うため、強化学習における Advantage Functionを連想 ※ 例えば以下のスライドが分かりやすい https://www.slideshare.net/binnasser2007/kuhn-munkres-algorithm
  15. Experiment 1: Toy Example • Grid world: 空間方向に9 x 9、時間方向に20

    time stepの世界を考える • 以下2種類のオーダーを発生させる(朝と夜のピークのような状況を想定) • その他設定 ◦ ユーザーがオーダーをキャンセルするまでの時間は μ=2.5, σ=2のガウス分布 ◦ ドライバーの初期位置とオーダーの目的地はランダム • 検証パターン ◦ 需要(オーダー数)と供給(ドライバー数)のバランスに応じて 3種類を検証 ◦ 100:25, 100:50, 100:75 座標(6,6), 時刻15を中心に 空間分散 (2,2), 時間分散3 の需要を発生
  16. Experiment 1: Toy Example • 比較モデル ◦ Distance: 最短距離のオーダーを取る ◦

    Myopic: 即時報酬だけを考える ◦ Mdp: 即時報酬+長期的なゲインを考える(提案手法) • 結果 ◦ 提案手法ではTotal Revenue、Answer Rateが共に高かった ◦ Pickup距離もdistanceモデルほどではないが myopicモデルよりはまし
  17. Experiment 2: Simulatorを使った実験 • 現実に近い検証をするため、シミュレータを構築 ◦ 4都市のデータを用いてオーダーをモデル化 ◦ シミュレータと現実の実績差分は小さい ▪

    現行アルゴリズム(distance-based policy)で検証して、 Metrics(acceptance rate, GMV)が高々2%の差しかないことを確認 • 結果 ◦ baselineのモデル(distance-based policy)と比較 ◦ 4都市で +0.5-5% の売上改善を確認(時間に寄っては+10pt程度の差)
  18. Experiment 3: 実証実験 • A/B testing design ◦ 複数アルゴリズムが同時間に混在すると他の車両ポリシーにも影響してしまう ▪

    1日を3, 6時間の時間区分に区切って、その間のアルゴリズムは統一 ◦ 時間の交絡を除くため、日によってアルゴリズムの適用順を巡回させる ◦ 曜日の交絡を除くため、 2週間の期間に渡って実験を回す • 結果 ◦ Global GMVとcompletion rateが +0.5-5% 改善 ◦ この結果を受けて、中国 20都市への展開が完了している(論文投稿時点)
  19. Overview • 背景 ◦ 強化学習を使った配車最適化は効果が出ていた(全論文; +0.5-5%の売上改善) ◦ 一方、これを他の都市に展開する場合には課題がある ▪ 都市ごとにゼロから学習を回す必要があって非効率(転移させたい)

    ▪ 都市によらない共通のポリシーがあるはずだがテーブル型だと表現しにくい • 本論文の提案 ◦ 価値関数をDNNで近似する ◦ Correlated Feature Progressive Transfer (CFPT)という転移学習の手法を活用 ▪ 既存ポリシーを使い回す形で、他都市に展開できるかを模索する
  20. MDPの定義 • State ◦ 基本は全論文と同様(座標+時間) ◦ 新たにfeatureを追加できるようにしている(需給統計、近隣の充足度合いなど 5次元) • Action

    ◦ 移動先の座標・時間(どこに移動するか) ◦ 配車を割り当てる、idleのままにする、の両方を含む • Reward ◦ 運賃 • Action Value Function ※ episodeは0:00-23:59までが1単位
  21. Deep Q-Network with Action Search • ネットワークはゲーム等で実績のあるDQNを踏襲 • DQNとは異なり、状態と行動を入力して、Q値を出力する構成 ◦

    Atari2600では特定数(4-18)の行動しか考えなかったが、今回は行動が連続値であるため • Action Search Mechanismを使うことで行動setを定義する(後述)
  22. 学習フレームワーク • ゲームでは、環境を再現するシミュレータを利用することで、 エージェントが試行錯誤しながら経験を貯めて学習を行う • 今回の問題では、現実世界を再現することは難しい • 一方で、大量の移動データがあるので、それを活用したい ◦ Replay

    buffer内に大量の軌跡データを投入して学習(シミュレータは使わない) 環境 エージェントが挙動方策に従って行動 行動と結果をReplay Bufferに保存 経験をランダムに取り出し Q関数を更新 経験のサンプリングによって作られるtgarget 現在のQ関数 Replay Buffer Agent
  23. Action Search • argmax Qを求めるためには、各状態において可能な行動setが必要 ◦ しかし現実のデータは sparseなので、複数の行動が選択できるとは限らない • Action

    Searchという手法で行動setを拡張 ◦ まず、過去の履歴データから時間 -空間の区域内に入るものを探してくる ▪ B(s)は状態sが含まれる時間-空間区域(空間はhexagon mesh) ◦ 履歴データがない場合には検索範囲を広げる ▪ 時間方向:座標は同じまま時間だけ進めて履歴データを探す ▪ 空間方向:現時点から探索layerを広げながら、L_maxまで探索
  24. Multi-City Transfer • スケーラビリティの課題 ◦ 学習時間:中規模都市で1ヶ月のデータを使うと 30h程度(6-core CPUs, signle GPU)

    ◦ 学習効率:都市間で共通のポリシー(通勤ラッシュなど)は使いまわしたい • 転移学習のトライアル(以下3アプローチ) 1. Fine-Tuning 2. Progressive Network 3. correlated-feature progressive transfer (CFPT) • Context Feature ◦ 5次元ベクトル:現時点の idle driver数、過去1minのオーダー数、…
  25. Fine Tuning / Progressive Network 1. Fine Tuning ◦ 他の都市で学習したネットワークを

    trainableにして対象都市で追加学習 2. Progressive Network ◦ Source Cityの隠れ状態をどれだけ反映させるかを学習
  26. Correlated Feature Progressive Transfer (CFPT) 3. 時間-空間状態 s(地域固有)と Context Feature

    fを分離して学習 ◦ 転移時には f を扱うNNを固定、s を扱うNNだけを追加で学習
  27. 実証実験 • 学習データ ◦ 過去の配車データから、 2/3をTraining、1/3をTestデータとしてsplit • 設定 ◦ Discount

    factor γ=0.9 ◦ 40,000 episodeの学習中、5箇所で Testに対する評価を行う ▪ Seedを変えながら 100episode を 5回繰り返し報酬量を評価 ◦ 都市Aで学習したネットワークを都市 B, C, Dに転移 • ネットワーク ◦ 3層の隠れ層を持った MLPで構築
  28. Overview • 背景 ◦ Taxi dispatching / repositioningについて、DRLをどのように更新するべきかを考察したい ▪ Driver-centricな更新とSystem-centricな更新の差分のどちらが実用的か

    • 概要 ◦ Global Context vectorをAttentiton機構を使って表現 ◦ 問題系をsmi-MDPとして扱い、以下2通りのDQNを比較 ▪ Single-Driver DQN (SDDQN) : 各ドライバーの収益を最大化する ▪ Multi-Driver DQN (MDDQN) : 協調行動を取って全体収益を最大化する ◦ シミュレータ上で複数の実験を行った結果 ▪ MDDQNの有用性を確認しつつも、 SDDQNが comparable もしくは好成績だった ※ ※ この辺りの議論に若干の煮えきれなさを感じつつ、実用上はdriver-centricなDQNでも十分、というメッセージング
  29. Global Representation of State • 各オーダー (oj) と各ドライバー (di) の状態表現

    ◦ o(6dim): 乗車座標、降車座標、運賃、待ち時間 ◦ d(6dim): 車両座標、配車可能になるまでの時間、 reposition先座標、reposition回数 • Attention機構を使った状態表現 ◦ 全オーダー、ドライバーの隠れ状態から global context Cを構成してDQNの入力にする
  30. Dispatching Q vs. Repositioning Q • Order dispatchとRepositioningは別のQ-Networkとして訓練 ◦ Attention

    Networkもそれぞれ別に学習する dispatching repositioning 状態s, context Cで、 d i がo j を取る状態行動価値 状態s, context Cで、 d i がreposition action m j を行う状態行動価値 (m は 周辺セルへの移動 8 パターン + 静止 の 9次元ベクトル)
  31. SD-DQN vs. MD-DQN • SD-DQNもMD-DQNもネットワーク構造は同じ • 次状態と報酬のみが異なる ◦ SD-DQN: あるドライバーに着目した時に次状態が「空車になったタイミング」で定義される

    ▪ t’-t は配車で10-30min程度、repositioningで2-3min程度 ▪ 報酬は該当ドライバーが得る運賃 ◦ MD-DQN: 全ドライバーに着目し「ある車両が空車になったタイミング」で次状態を定義 ▪ t’-t は~second程度 ▪ 報酬はシステム全体が得る運賃
  32. Toy Domains • Surge domain:3ヶ所で需要を発生させる ◦ 右下から中央に行く運賃だけが高い • Hot/Cold domain:上部でのみ需要を発生させる

    ◦ 半分は行き先が上部、半分は行き先が下部(ダウンタウン⇔住宅地の需要パターンを想定) ◦ 下部に行くのは運賃は高いが、上部に repositionする必要がある ここだけ運賃が高い Surge Hot/Cold 一度下部に行くと、何度か上に repositionしないと需要が拾えない
  33. Toy Domains: Results • SD-DQN、MD-DQN以外に、以下の方策を比較 ◦ MRM (Myopic Revenue Maximization),

    MPDM (Myopic Pickup Distance Minimization), LPI (Local Policy Improvement; 20x20x144のspatial-temporal space上でTD(0)学習) Myopic PoliciesよりもRLを使ったほうが好成績 SD-DQNはMD-DQNとcompetitive
  34. Historical-Statistics Real-World Domain • DiDiがGAIA programで提供している実データからシミュレータを構築 ◦ 成都市の30日のタクシー配車データ( ~数千万件) ◦

    空間を20x20のgridに区切り、poisson分布で需要を表現 ▪ パラメータκは乗車位置、降車位置、時間 (hour)それぞれについてもとめる ▪ 需要分布のパラメータ数は (20^2) * (20^2) * 24 = 3.84M ◦ ETAはガウス分布で表現してサンプリング(到着時間の分散等も考慮)
  35. Historical-Statistics Real-World Domain: Results • SD-DQNが好成績 ◦ RevenueだけでなくPickup ETAや配車成功率もMD-DQNに比べてよかった※ ※

    考察が少なかったのでここでは「実用上はSD-DQNでも問題なさそう」程度に留める   (MD-DQNは計算量が多かったり学習が安定しにくいハンデがあることが影響?)
  36. まとめ • タクシーのDispatching/Repositioningに関する4つの論文を紹介 ◦ 問題を時系列の意思決定問題として捉えた強化学習のアプローチが成果を出している ▪ 強化学習のアプリケーションとしてはかなり大規模に可動している ◦ DNN近似を使った転移学習など、 Cold

    Start問題にも対応できる手法も登場している ▪ 地域特性やコンテキストの表現学習は今後も面白い研究が出てきそう ◦ マルチエージェント性はそこまで考慮しなくても実用上は上手くいってそうな気配 ▪ タクシードメインにおいて、競合他社がいる状態での需要の取り合いや協調行動は 他にも多くの研究があり、ゲーム理論やマルチエージェント文脈での議論は続いている