ソーシャルディスタンスを維持できる避難ってなに！？深層強化学習を活用した、ソーシャルディスタンスを考慮した避難方針の導出アルゴリズムの提案！
3つの要点
✔️ COVID-19パンデミックにより、ソーシャルディスタンスを置くことの重要性が指摘されている
✔️ 強化学習を活用し、こうしたソーシャルディスタンスを考慮した、緊急時における避難活動での最適な指針を導出するモデル構築
✔️ 評価の結果、従来アルゴリズム—Sweepアルゴリズム—と比較し、提案モデルでは効率的なルーティングを導出できることを確認
Routing algorithms as tools for integrating social distancing with emergency evacuation
written by Yi-Lin Tsai, Chetanya Rastogi, Peter K. Kitanidis, Christopher B. Field
(Submitted on 5 Mar 2021 (v1), last revised 13 Oct 2021 (this version, v4))
Comments: Published on arxiv.
Subjects: Artificial Intelligence (cs.AI); Computers and Society (cs.CY); Human-Computer Interaction (cs.HC); Machine Learning (cs.LG)
code：
本記事で使用している画像は論文中のもの、紹介スライドのもの、またはそれを参考に作成したものを使用しております。
背景
ソーシャルディスタンスを考慮した最適な避難経路を導出することは可能なのか？
本研究では、深層強化学習を活用し、COVID-19におけるパンデミックなどの状況下において発生した災害—i.g.地震・台風—を想定し、ソーシャルディスタンスを考慮した最適な避難方針の導出、を目指す。
依然として猛威を振るうCOVID-19に対して、ソーシャルディスタンスを維持することは今後も不可欠であると考えられる；一方、災害—i.g. 洪水、山火事、地震、土砂崩れ—は、パンデミックの最中においても発生する可能性が想定され、ソーシャルディスタンスをおきながら、最適な避難方針を導出することが必要とされている—実際、インフルエンザ，SARS-CoV-1，SARS-CoV-2などの感染症の発生増加が，数十年前の気候変動と関連していることを報告されており、COVID-19収束後も、次のパンデミックに対する備えが必要である。そのため、将来のパンデミックを想定し、複合災害の準備と対応においてソーシャルディスタンスを考慮した避難方針を明確化する必要がある。
本研究では、パンデミックおよび予知された災害—i.g. 地震・津波—の両方を含む、複合イベントにおける避難操作の改善を実現できるRLモデルの構築を目的としている：具体的には、避難時間の延長・避難に必要な緊急車両数の増加におけるソーシャルディスタンスの役割を調べ、深層強化学習に基づく最適化車両ルーティングを用いて、非DNN手法—Sweepアルゴリズム—と比較して、避難効率の向上させるアルゴリズムの開発をおこなう。Sweep アルゴリズムでは、避難民の運搬に対し事前に運用ルールを決める必要がある一方、深層強化学習では、環境・エージェントにおける行動選択に基づき戦略を学習し、最適なルーティングを探索できる。
COVID-19とは？
初めに、本研究の解析対象である、COVID-19について解説する。
COVID-19は、2019年に中国武漢市で発見され、その後、全世界に感染拡大し、パンデミックを引き起こした。ウイルス感染後、4、5日後ほどで発現する—長ければ2週間たってから症状が出る。主な症状は、次のようなものである：発熱；咳；息苦しさ；体のだるさ；においや味がわからなくなる。高齢者や心臓病、糖尿病等の基礎疾患を持つ人では、重篤な肺炎を引き起こす可能性が高く、そのほかの世代も、呼吸器症状、高熱、下痢、味覚障害などが報告されている。遺伝子配列解析から、このウイルスは、コウモリ、センザンコウのコロナウイルスと類似する報告があり、これらが遺伝子組み換えを起こした可能性が指摘されている。2021年９月までに、世界で感染が確認された人は2億2千万人、死亡者は455万人であると報告されている。咳や飛沫を介してヒトからヒトへ感染し、主に空気感染により拡大する。現在、有効性の高いワクチンの開発により、感染防止が進められている。
研究目的
本研究では、COVID-19の蔓延した状況を想定し、ソーシャルディスタンスを考慮した最適な避難方針を導出するアルゴリズムの構築、を目指す。
パンデミックの状況下でも、地震などの災害が発生する可能性はあり、ソーシャルディスタンスを維持しながら、最適な避難方針を導出する必要がある。本研究では、こうした方針の導出にあたり、深層学習強化学習を活用したモデルを提案している：具体的には、避難経路を定式化し、制約条件のもと、目的関数を最大化させるような避難方針を導出する。評価結果では、従来手法—Sweepアルゴリズム—と比較し、提案アルゴリズムがより効率的な避難方針を導出できることを確認した。
手法
ここでは、本研究における提案手法の概要・評価環境について述べる。
ケーススタディ
本研究では、ソーシャルディスタンスが必要となる災害に関するシミュレーション環境として、ニューオーリンズでの避難方針をケーススタディとしている—ニューオーリンズでは，72時間のハリケーン避難における避難方針があり，海岸に到達前の42時間で，地域住民を自宅からピックアップし，市全体の救助センターであるスムージーキングセンターに搬送する計画が示されている。
問題の定式化
本研究では、災害前の避難における車両経路問題—Vehicle Routing Problems：VRP—の一つである、Capacitated Vehicle Routing Problem —CVRP—を対象としている：この問題は、災害前の避難に対して、救援センター—デポ—とノード—顧客—と呼ばれる集合に基づき、下記のように定式化できる：
これらの式は、上から以下のことを意味している：近隣の総合コスト—総避難時間—を最小化する目的関数；各家を一度だけ訪問する制約条件；緊急車両が救助センターから出発できるのは，Kの各ルートに対して1回だけとする制約条件；各家・救助センターに到着・出発する緊急車両の数が同じである制約条件；1つのルートで緊急車両が拾う人数が車両容量Cを超えないことを保証する制約条件；救助センターから切り離されたルートは避ける制約条件； 決定変数が1（訪問済み）か0（未訪問）であることを表す制約条件。
こうして定式化された目的関数・制約条件から、各アルゴリズムは避難方針を導出する。
アルゴリズム設計
ここでは、本研究で活用した、従来手法—Sweepアルゴリズム—および提案手法に関するモデルを概説する。
Sweepアルゴリズムでは、デポ—救助センター—から任意の線でスタートする；この線を反時計回りに掃引し、線が家と交差したときに家を一つずつ追加し、緊急車両が訪問すべき家の順番を決定する。また、緊急車両は乗車定員を超えると救護センターに戻る必要がある。
提案モデルでは、深層強化学習、特にアテンションモデルを活用している—このアルゴリズムは、CVRを含む経路問題にて、優れた性能を示すことが示されている。アテンションモデルは、アテンションベースのTransformerと、自己アテンション層をマスクしたCNN—Convolutional Neural Networks—が、グラフ構造のデータを効率的に分析するGAT—Graph Attention Networks—の一種に対して、RLを統合したものである。
結果
このセクションでは、本研究にておこなった評価結果について解説する。
地域の広さとソーシャルディスタンスのトレードオフ
ここでは、緊急車両が定員に達するまで住民を乗せる過程を繰り返す、CVRPをシミュレーションし、地域の広さとソーシャルディスタンスのトレードオフを対象として、分析した—地域サイズが大きくなると、ソーシャルディスタンスを維持する必要性も高まることが想定される。この評価では、標準的な CVRP データセットのノード—家屋—とデポ—救助センター—の位置を使用した。通各ノードの需要—世帯サイズ・緊急車両における各家の人数—は，ニューオーリンズの平均世帯サイズを使って生成した．使用した4データセットにおける地域規模は，20，35，52，68軒であった．ここでは、ソーシャルディスタンスにより、1台の救助車両に乗れる人数が制限される—1台の人数は64、32、16、8、4、2人、とした。緊急車両が地域住民を乗せ終えた後、総時間と経路数を合計し出力した—下図参照。
ここでは、嵐が海岸に到達する54時間前から住民を乗せ始め，海岸に到達する30時間前までに最後の住民を集める計画、を想定した—嵐が海岸に到達する30時間前から12時間前までの間に、市は必要に応じて避難活動を継続できる。そのため、DNNベースモデルと非DNNモデルの評価にあたり、42時間と24時間を閾値として、期待されるタイムライン内にて、緊急車両が避難ミッションを完了したか、を判断した。さらに、時間性能をSatisfactory—24時間未満—、Borderline—24-42時間—、Not Allowed—42時間以上—に分類した。
地域規模に対する評価
ここでは地域規模の変化に対する評価を示す。
評価結果から、救助車両1台あたりの収容人数—ソーシャルディスタンス—に関わらず、地域規模が大きくなるほど、避難にかかる総時間は増加した—下図参照。
提案手法と従来手法は、全地域サイズにおいて、ソーシャルディスタンスが大きくなるほど、総時間がより増加していた：緊急車両に32人が乗っている場合、地域サイズを20から68に増やすと、1.89 h—提案手法—と4.79 h—従来手法—の総時間が増加した；また、より厳しいソーシャルディスタンス—車両あたり2人—の場合、23.37 h—提案手法—と22.18 h—従来手法—の総時間が増加していた。
加えて、6つの車両容量—1台あたり2、4、8、16、32、64人—に対する平均総時間は、地域サイズに応じて上昇し、直線的に比例していた—下図参照
例えば、1台あたり16人の場合、地域サイズを20から68に増やした場合、通過時間が最小—+0時間/ルート—と最大—+2時間/ルート—のケースで、2.37倍、2.97倍に増加した。また、各ルートに乗り換え時間を追加しない場合と比較し、長い乗り換え時間を追加した場合、地域の広さと平均総時間の関係は直線的な比例関係に近似された。
ソーシャルディスタンスの取り方
ここではソーシャルディスタンスと避難時間の関係について述べる。
評価結果から、ソーシャルディスタンスを長くすると、総避難時間が増加することがわかった—下図参照
最も厳しい場合、乗り換え時間が0のときのみ、避難時間は42時間未満となった。また、1車両あたり32人—より制約の少ないソーシャルディスタンス—では、提案手法と従来手法解で、乗客制限に対する避難時間の感度がほぼ同一であった。
DNNベースと非DNNソリューションの有効性
ここでは、従来手法と提案モデルの有効性に対する比較結果について述べる。
各ルートのシナリオにおいて、提案手法は、従来手法と比較し、66.67%のケースで総避難時間を短縮化していた—下図参照
提案手法は、8.33%のシナリオで、よりも少ない経路を必要とした。また、提案モデルでは、平均して、より少ない時間でより多くの経路を使用した結果が示された。一方、各経路の通過時間が増えると、提案手法の優位性は減少した。また、地域サイズ・車両容量が小さい場合以外では—一般的な車両例では—、提案モデルの有効性が示された—提案モデルは、従来手法を最大40.18%上回り、高容量車両、軽度のソーシャルディスタンス、大規模な地域の条件で最大となる。また必要な経路数はほぼ同数であった。
考察
本研究では、深層強化学習を活用し、COVID-19をはじめとするパンデミックの発生時において、適切なソーシャルディスタンスを維持できる避難経路に対する導出モデルの構築をおこなった。評価結果として、従来のルーティングアルゴリズム—Sweepアルゴリズム—と比較し、本モデルで導出された避難方針により、避難効率が増大した一方、ソーシャルディスタンスへの要求が強くなるケース—i.g. より大きな地域サイズ—、では有効性が減少していた—深層強化学習の活用により、効率性の向上は見込める一方、各避難ルートにソーシャルディスタンスを加えるために必要な時間を充足することは困難である、とが推察された。こうした知見は、COVID-19だけでなく、各地域の登録情報に基づく他の災害時避難にも関連するため、こうした事態にも適応することが見込まれる。また、避難時における、緊急車両サイズが小さい場合では本モデルでの有効性が減少した一方、車両の容量が各世帯のより大きい場合では、本手法を有効的に活用することができる、と考えられる：こうした場合、複数の世帯がルート上で組み合わされるため、効率的なルーティング戦略をヒューリスティックに導出することは困難である、と考えられる—RLモデルは、正解を設定することが困難な複雑な状況下でも、正解なしに自己学習することができるため、こうした課題に対して有効である可能性が高い、と考察できる。
本研究における課題として、車両サイズを考慮した学習・評価、が挙げられる。提案モデルでは、緊急車両の容量が1世帯—ノード—のサイズに近い場合、特に有効性が失われる傾向にあった。一般的には、車両容量は各ノードの需要よりはるかに大きいため、低容量の車両がある状況に対する学習・評価をおこなう必要がある。また、ソーシャルディスタンスが長くなる場合、提案モデルによる指針でも十分な時間を確保できない、という結果から、実用化には十分でないことが想定される。この点については、そのほかのRLアルゴリズムを活用するといった解決策が考えられる。
この記事に関するカテゴリー
