2022年 進化計算コンペ

進化計算コンペティションは，進化計算の実応用と産学交流を促進するために，2017年に始まった最適化コンペティションです．過去4年のコンペティションでは，製造業・航空宇宙・ゲーム・行政分野における最適化問題を出題してきました．

• 2017年：複数車種の同時設計
• 2018年：月着陸地点の選定
• 2019年：発電用風車の設計
• 2020年：ゲーム用乱数の設計
• 2021年：経済支援施策の設計

今回は群集シミュレーションを用いた発生交通量推定問題を扱います．大規模イベントにおける人の混雑をシミュレーションするために，発生交通量をできるだけ精度よく推定することを競います．

EC-Comp 2022: 群集シミュレーションを用いた発生交通量推定

お知らせ

• 2022年11月26日12時00分: 多目的部門の本番問題を公開しました．
• 2022年11月26日03時00分: コマンドラインツールv1.8.1を公開しました．
  • 以下のコマンドでアップデートできます：pip install -U opthub-client-cli
  • 変更点：optコマンドを並列実行しているときに，まれにコマンドが失敗する問題を修正した（アクセストークンの有効期限が切れてトークンを更新している最中に，別プロセスのoptがアクセストークンを読みだすことが原因．それを防止する排他制御を追加した）
• 2022年11月18日14時00分: 多目的部門のデモ問題mop-demoを公開しました．本番問題の公開予定日は未定です．
• 2022年11月12日00時30分: 多目的部門の問題公開を再び延期いたします．公開予定日は未定です．
• 2022年11月10日02時00分: 多目的部門の問題公開を11月11日に延期いたします．それに伴い，競技終了を12月11日23:59に延長いたします．
• 2022年11月10日01時30分: sop-demo2とsop-2の入力フォーマットの説明の間違いを訂正しました．すでに送信された解につきましては，運営にてフォーマットを訂正し，評価と採点を再計算いたします．ご迷惑お掛け致しましたことお詫び申し上げます．
  • 【誤】長さ900の配列
  • 【正】サイズ3×300の2次元配列
• 2022年10月29日08時00分: 単目的部門の目的関数計算式の間違いを訂正しました．こちらはコンペシステムの評価値計算とは関係ない，Webページの数式の訂正になります．これ以前に送信された解の評価値も正しく計算されています．
• 2022年10月10日08時00分: 単目的部門の競技sop-1, sop-2を公開しました．多目的部門については10月20日の公開を予定しております．
• 2022年10月10日08時00分: 練習用の競技はsop-demo1, sop-demo2に移行しました（それに伴い旧sop-demo1は削除しました）．この競技はコンペの成績には関係ありません．入出力の確認やプログラムの動作検証にご活用ください．
• 2022年10月05日14時00分: 練習用の競技sop-demo1を公開しました．この競技はコンペの成績には関係ありません．入出力の確認やプログラムの動作検証にご活用ください．
• 2022年09月12日16時00分: Webサイトを公開しました．

問題の概要

群集シミュレーションとはカメラやGPSなどの観測情報をもとに，コンピュータ上で歩行者の動きを模擬する技術です．高精度なシミュレーションを行うためには，「いつ」・「どこからどこへ」・「どのような人が」といった現実の歩行者情報を正しく再現する必要があります．しかし，数千～数万人規模の人流が発生するイベントにおいて，これらの歩行者情報を正確に計測することは困難です．仮想世界と現実世界のギャップを埋めるためには，不十分な実観測データから正しい歩行者情報を推定しなくてはいけません．

例えば，ある起点Oから終点Dへと向かう起終点間の歩行者交通量（OD交通量）を推定する場合には，部分的に観測された交通量と一致するようなシミュレーション結果を求めることで全体の交通量を求めます1．このように歩行者の発生時刻と発生場所を求めるケースは，「いつ」・「どこからどこへ」の歩行者情報を推定していると言えます．また，パラメータキャリブレーションと呼ばれる分野では，ビデオから抽出された移動軌跡と一致するように、歩行者の挙動を表す数理モデルの内部パラメータをチューニングします2．これは「どのような人が」の歩行者情報を推定する研究と言えるでしょう．

本コンペティションでは，あるイベントから帰宅する歩行者の観測データをもとに，正しい歩行者情報を推定する最適化問題を扱います．与えられた任意の歩行者情報から得られた群集シミュレーション結果と観測データの誤差を最小化することで，歩行者の出発時刻，経路選択に関する歩行者モデルを推定します．

第22回進化計算学会研究会で行った説明会の内容はこちらの動画でご覧いただけます．

スケジュール

結果発表に参加するためには，進化計算シンポジウム2022へのお申込みが必要です．詳しくは進化計算シンポジウム2022のページをご覧ください．

参加方法

どなたでも無料で参加できます．

こちらのチュートリアルにしたがって，所属組織のメールアドレスでアカウントを作成してください．

==過去にコンペに参加された方へ==
昨年に作成したアカウントは引き続きお使いいただけます．クライアントツールを最新版に更新してプレイしていただきますようお願いいたします．

pip install -U opthub-client-cli

コンペティションは単目的部門と多目的部門に別れており，各アカウントはいずれか一方または両方の部門に参加することができます．それぞれの部門には，問題を解くことで参加したとみなされます．1つの部門は複数の問題からなり，参加した部門のすべての問題を解く必要があります．

1人で参加することも，複数人が1チームとして参加することもできます．1チームの人数に制限はありません．チームで参加する場合は，代表者を1人決めて代表者がアカウントを作成してください．１人の参加者が複数のチームに所属することはできません．ただし指導教員は禁止事項に違反しない範囲で複数のチームにアドバイスできます．Q&Aもご覧ください．

禁止事項

以下に違反した場合は失格となります．

• 1人で複数のアカウントを作成してはいけません．
• アカウントおよびアクセストークンを他人に譲渡してはいけません．
• 競技期間中は，サーバに送受信したデータおよびその派生物（データを使って構築した応答曲面やソルバプログラム等）をチームメンバー以外の人に教えてはいけません．また，SNS等の不特定多数が閲覧できる場所に公開してはいけません．
• コンペティションに関するソフトウェアをリバースエンジニアリングしてはいけません．
• 悪意をもってコンペティションサーバを停止または不安定化する行為をしてはいけません．

結果発表について

12月17日のプログラム（暫定）

表彰

単目的部門・多目的部門のそれぞれの問題に賞を用意します．受賞者には進化計算学会から表彰がございます．詳しくは後日発表いたします．

参加者へのお願い

• 参加者には，結果発表においてプレゼンテーション（発表5分，質疑なし）をお願いします．以下の点について説明してください．スライドは12月15日までにお問合せ先にご提出ください．
  • 利用したアルゴリズムの説明
  • 工夫した点
  • 結果
• 「結果の総括」において，皆さまから提出していただいたデータの比較を行いますのでご了承ください．
• 実問題の研究を促進するために，皆さまから提出していただいたデータは後日コンペサーバ上で公開させていただきます．特にご希望がなければ，データの所有権はデータを送信したアカウントの所有者に帰属するものとし，ライセンスはクリエイティブコモンズ 表示 - 継承 3.0とさせていただきます．これは，誰もが皆さまのデータを利用して研究を行ったり，論文を執筆したりできることを意味します（データを利用した論文には皆さまの名前が記載されます）．データの非公開や異なるライセンスをご希望でしたらお知らせください．

問題の背景

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

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

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

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

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

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

単目的部門

単目的部門では，実際の花火大会（関門海峡花火大会）における帰宅時のシミュレーション結果が観測データに近づくよう，帰宅者の出発時刻および経路選択の推定（最適化）に取り組んでいただきます．
出題数は以下の２問です．

• sop-1: 帰宅者の出発時刻のみを最適化する問題
• sop-2: 出発時刻および経路選択を最適化する問題

詳しい内容は各問題のページをご覧ください．

多目的部門

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

チュートリアル問題

単目的部門

単目的部門のチュートリアル問題: sop-demoを公開中です．

多目的部門

多目的部門のチュートリアル問題: mop-demoを公開中です．

Q&A

Q1. 進化計算を使って解かなければいけませんか？

A. どんな方法で解いても構いません．人力でいくつか解を送って様子をみたり，応答曲面を構築したり，途中でソルバーを打ち切って再スタートすることもできます．ホワイトボックスな関数については，ローカルでプログラムを組んで好きなだけ評価しても構いません．要するに，禁止事項に抵触しない限りは何でもアリです．もし判断に迷うことがあれば，お問合せ先までご質問ください．

Q2. 間違って解データを送信してしまいました．やり直せますか？

A. 今年のコンペは一定の評価回数で競うため，一度送信したデータを取り消すことはできません．デモ問題で十分にテストしてから本番の問題を解くようにしてください．

Q3. 問題を解いている最中にソルバープログラム（またはコンペサーバ）が落ちました．途中から再開できますか？

A. 一度送信したデータはサーバに記録されており，opt list solutionsコマンドで取得できます．しかし，ソルバーを同じ状態から再開するためには，ソルバーの状態変数や乱数種なども復元する必要があるはずです．これらはご自身で定期的にファイルに保存するなどして，突然のトラブルに備えてください．

Q4. コンペ運営に関わっている教員とその学生はコンペに参加できますか？

A. 参加できます．代表幹事以外の委員は，問題を解くうえで有利になるようなインサイダー情報は知ることができません．そのため，運営に関わる教員やその学生であっても，一般参加者と同じ公平な条件で参加できます．

Q5. うちの研究室からは複数のチームが参加します．教員はすべてのチームに参加したいのですが？

A. 教員は指導目的で複数のチームにアドバイスできるものとします．ただし，お互いのチームのデータを教えないようにしてください．アドバイスの内容も，個々のチームのデータだけから分かることに限定してください．

Q6. アカウントを削除できますか？

A. 競技期間終了後に削除できます．お問合せ先までご連絡ください．なお，アカウントを削除すると，そのアカウントで送信したデータも削除されます．

Q7. 解は並列に送信できますか？

A. できます．複数の競技に同時に解を送信することもできますし，同じ競技に複数の解を同時に送信することもできます．並列数に上限はありません．解は（競技・ユーザーごとに）サーバに登録された順番に評価されます．期限までにサーバに登録された解は，期限後に順次評価され，成績計算の対象になります．解を並列に送信するには，以下のような方法があります．

• 複数の端末を起動してそれぞれでopt submitコマンドを実行する．
• 1つの端末で複数のopt submitコマンドをバックグラウンド実行する．
• opt submitコマンドに--no-waitオプションを指定する．この場合，サーバでの評価・採点を待たずにコマンドが終了します．評価・採点の結果を取得するには，しばらく待ってから以下のコマンドを実行します．

opt list solutions --query "_and: [{match_id: {_eq: MATCH}}, {owner: {name: {_eq: USER}}}]"

ここでMATCHには競技IDを，USERにはあなたのユーザ名を入力します.

Q8. 今回のコンペでは，ローカルで試行錯誤できる評価プログラムは配布されますか？

A. 配布しない予定です．今年は本ページ内にいくつかのデモ問題を用意しますので，それを使って本番問題に挑戦する前の試行錯誤をしていただく形になります．理由としましては，昨年までは新しいコンペシステムに慣れるための経過措置として評価プログラムを配布してきましたが，評価プログラムを様々なOSに対応するために出題者の負担が大きいことや，ローカルで際限なく試行錯誤できるために本番問題で上位プレイヤーのスコアに差がつかないといった弊害がありました．そのため，今回は評価プログラムは配布しない形での競技を試してみる予定です．

お問合せ先

進化計算学会 実世界ベンチマーク問題分科会
sig-rbp@googlegroups.com

参考文献

• 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.
  
• D. Wolinski et al. (2014), Parameter estimation and comparative evaluation of crowd simulations, Computer Graphics Forum, vol. 33, no. 2, pp. 303-312.
  
• 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.
  
• 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.
  
• 山下倫央 et al. (2012), 一次元歩行者モデルを用いた高速避難シミュレータの開発とその応用, 情報処理学会論文誌, vol. 53, no. 7, pp. 1732-1744.