観測コストを考慮した発生交通量推定のための多目的観測設備設計

本問題は2022年 進化計算コンペ 多目的部門の問題です．本問題では，1) シミュレーション結果と実観測データの誤差最小化, 2)観測コストの最小化を同時に行うカメラ・GPS設定の多目的最適化を行います．

問題の背景

近年，将棋倒しや群集雪崩などに代表される群集災害が大勢の人が集まるイベント/施設で問題となっています．群集災害を回避するためには，標識や警備員によって適切に群集の流れを制御する必要があります．しかし，費用や安全性の観点から様々な制御方策の是非を実際の環境で評価することは困難です．

多くの人やモノの動きを群集シミュレーションによりコンピュータ上（仮想世界）で模擬することで，現実世界に比べて迅速かつ定量的に制御方策を評価することが出来ます．とくに近年，各エージェントが個々の歩行者を表現するマルチエージェントシミュレーションを用いることで，制御方策の最適化を行う研究事例が多数報告されています3,4．

適切な群集制御最適化を行うためには，シミュレータを現実に近づけることが欠かせません．現実に則したシミュレーション結果を得るためには，i) 移動経路に関する地図情報，ii) 歩行者の発生時刻や起点終点に関する情報（OD交通量），iii) 移動速度や経路選択などの歩行者の挙動を表す数理モデル，iv) 群集制御や災害による通行止めなどの外的要因といった情報を正しく与える必要があります．本問題では，なかでも計測が困難なOD交通量と歩行者モデルのパラメータに注目し，群集シミュレーション結果と観測データの誤差最小化によりこれらのパラメータを推定します．

群集シミュレーションの概要

本問題では，帰宅者の移動のシミュレーションにCrowdWalkを利用します．CrowdWalkはひとりひとりの歩行者に対応するエージェントを生成してシミュレーションを行うマルチエージェント型の群集シミュレータです．各歩行者にエージェントを対応させることで，各歩行者のミクロな動きまで想定したシミュレーションを行う事ができます．

Fig. 1: CrowdWalkで使用する一次元のネットワークマップ

多数のエージェントの移動を高速かつ低メモリで計算するために，CrowdWalk ではFig. 1のように一次元のネットワークマップを利用してエージェントの位置計算を行います．また，全てのエージェントの位置は Social Force Model に従って更新されます．一次元ネットワークマップに適した Social Force Model の詳しい計算は，山下らの論文を参照ください5．

問題定義

概要

群集シミュレーションを用いた発生交通量推定は花火イベントにおいて観測データと一致するように観客の出発人数ヒストグラムを推定する問題です．この問題は，観測データの量は固定（駅前のカメラと一定間隔のGPS）されており，与えられた観測データに従う出発人数ヒストグラムを効率的に求める問題となっています．一方で，実際に出発人数ヒストグラムの推定精度を高めようとする場合には，より直接的な方法としてカメラやGPSによる観測データの量を増やすことが考えられます．
例えば，群集シミュレーションを用いた発生交通量推定では，駅（帰宅者の目的地）の到着人数をカメラで観測したデータを誤差評価に使用していますが，帰宅者の通るルート上にもカメラを追加設置することで出発人数ヒストグラムの誤差をより精密に測ることが出来ます．GPSについても同様にアルバイトの出発間隔を短くすることで誤差精度が高くなると考えられます．しかし，カメラ数やGPS頻度を高めるためには追加のコストが必要です．
このような観測コストと誤差評価精度のトレードオフを可視化するため，本問題では 1) シミュレーション結果と実観測データの誤差最小化, 2)観測コストの最小化を同時に行うカメラ・GPS設定の多目的最適化に取り組んでいただきます．

最適化の流れ

カメラ・GPS設定に対する誤差精度を評価するために，多目的部門では与えらえたカメラ・GPS設定を用いて単目的部門と同じ出発人数ヒストグラムの最適化を行います．すなわち，本問題では次のような2段階の最適化が行われます．

• 下位の単一目的最適化
  与えられた観測機器のデータを用いて出発人数ヒストグラムの推定を行います．
  ユーザが与えたカメラ・GPS設定をもとに，CMA-ESを用いた最適化を自動で行います．CMA-ESで得られた最良の出発人数ヒストグラムの誤差が与えたカメラ・GPS設定に対する誤差評価となります．
• 上位の多目的最適化
  内部ループで得られた誤差の最小化に加えて観測コストを最小化する２目的最適化を行います．

本問題では下位の単一目的最適化の実行と誤差精度の評価は自動で行うため，皆さまには得られた誤差値を利用する多最適化アルゴリズムの設計を行っていただきます．

決定変数

本問題では，カメラを設置できる候補地（全20カ所）に対してカメラを設置するか否かを0(設置しない), 1(設置する)のバイナリで表現する決定変数に対して多目的最適化を行います．また，GPSを持ったアルバイトの出発間隔を{2, 4, 8, 16, 32, 64}の整数で表現し，同様に決定変数とします(単位は分)．GPSを持ったアルバイトは指定された出発間隔ごとに花火会場から駅まで移動します．
カメラを設置できる候補地をC-1, C-2, ..., C-20としたとき，決定変数のフォーマットは以下の通りです．

目的関数

本問題では 1) 出発人数ヒストグラムの推定誤差の最小化，および 2)観測コストの最小化を行います．それぞれの計算式は以下の通りです．

推定誤差の評価

本問題では，候補地に設置したカメラで計測した通過人数（ヒストグラム）とアルバイトの持つGPSによる移動軌跡を用いて出発人数ヒストグラムの推定を行い推定誤差を求めるため，CMA-ESを用いた単一目的最適化を行います．この単一目的最適化では，単一目的部門と同様に二乗平均平方根誤差(RMSE)を用いた誤差の最小化を行います．誤差な評価はカメラの誤差値とGPS移動軌跡の誤差値の線形結合です．使用するそれぞれのカメラで通過人数に関する誤差値 ${ϵ}^{\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{t}}\backslash epsilon^\{\backslash rm\; dest\}$ を求めることが出来るため，CMA-ESに対する目的関数の計算式は以下のようになります．

${ϵ}^{\mathrm{o}\mathrm{b}\mathrm{s}}=\beta \frac{1}{C}{\sum }_{c=1}^C{ϵ}^{\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{t}}+(1-\beta ){\overline{ϵ}}^{\mathrm{p}\mathrm{a}\mathrm{c}}\backslash epsilon^\{\backslash rm\; obs\}\; =\; \backslash beta\; \backslash frac\{1\}\{C\}\backslash sum\_\{c=1\}^\{C\}\backslash epsilon^\{\backslash rm\; dest\}\; +\; (1\; -\; \backslash beta)\; \backslash bar\{\backslash epsilon\}^\{\backslash rm\; pac\}$

ここで， $CC$ は計測に使用するカメラの数です．

CMA-ESによる最適化の間で得られた最も目的関数の低い解が与えられた観測機器設定にたいする評価値となります．

観測コストの評価

本問題では，カメラとGPSの計測に必要なアルバイトの人件費を観測コストとします．カメラ計測では，使用するカメラ一台につき一人のアルバイトが必要となります．GPSの計測ではアルバイトの出発間隔を $ii$ とすると，ひとつのルートにつき $64\mathrm{/}i64/i$ 人のアルバイトが必要となります．これはそれぞれのアルバイトが64分間隔で駅まで移動することを意味します．駅まで移動したアルバイトが出発地点まで往復する時間と休憩時間を加味した間隔となっています．

第二目的関数 ${ϵ}^{\mathrm{o}\mathrm{b}\mathrm{s}2}\backslash epsilon^\{\backslash rm\; obs2\}$ の計算式は次の通りです．

${ϵ}^{\mathrm{o}\mathrm{b}\mathrm{s}2}={\sum }_{i=1}^{20}{n}_i+3\times 64\mathrm{/}{n}_{21}\backslash epsilon^\{\backslash rm\; obs2\}\; =\; \backslash sum\_\{i=1\}^\{20\}\; n\_i\; +\; 3\backslash times64/n\_\{21\}$

ここで， $n_{i}n\_i$ は $ii$ 番目の決定変数です．

---

参考文献

1. C. Antoniou et al. (2016), Towards a generic benchmarking platform for origin–destination flows estimation/updating algorithms: Design, demonstration and validation, Transportation Research Part C: Emerging Technologies, vol. 66, pp. 79-98.
   
2. D. Wolinski et al. (2014), Parameter estimation and comparative evaluation of crowd simulations, Computer Graphics Forum, vol. 33, no. 2, pp. 303-312.
   
3. R. K. Dubey et al. (2020), AUTOSIGN: A multi-criteria optimization approach to computer aided design of signage layouts in complex buildings, Computers & Graphics, vol. 88, pp. 13-23.
   
4. A. Abdelghany et al. (2014), Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities, European Journal of Operational Research, vol. 237, no. 3, pp. 1105-1118.
   
5. 山下倫央 et al. (2012), 一次元歩行者モデルを用いた高速避難シミュレータの開発とその応用, 情報処理学会論文誌, vol. 53, no. 7, pp. 1732-1744.