都市の警備配置問題を高速に解くAI数理技術とは?
2016年5月15日 20:34
人の集まる場所でのセキュリティ対策では、完全に侵入経路や逃走経路を封鎖することは限られた警備資源の中では不可能なことが多く、警備員を効果的に配置し想定される被害を最小化することが求められている。これまで警備計画の立案は専門家の経験と勘に委ねられていたが、近年、専門家の判断を支援する技術として、攻守双方を数理的に記述するゲーム理論が注目されている。しかし、ゲーム理論を用いて犯罪者を検問所などで捕捉する都市道路ネットワーク警備問題については、扱う道路のネットワーク規模に対して計算量が指数的に増加するため、実際の都市への適用が困難だった。
今回、富士通研究所と国立大学法人電気通信大学は、AIを活用して警備計画の立案を支援する技術として、数学理論の一つであるゲーム理論を用いて、犯罪者を捕捉するための検問所などを想定した「都市道路ネットワーク警備問題」を高速に解くアルゴリズムを開発した。
開発したアルゴリズムでは、まず、最も被害が想定されるノードに着目して決定した検問配置の候補を決め、検問を行う場所と、その割合について、全体として被害の期待値が最も小さくなる最適な組み合わせについて、ネットワーク縮約の技術を用いて高速に計算。その結果、新たに被害の期待値が大きくなったノードに着目して検問配置の候補となる道路を追加して、同様に最適な組み合わせを計算する。これを繰り返すことにより、近似的な最適解を高速に計算します。3万通りの擬似的な道路ネットワークを使ったシミュレーションでは、このアルゴリズムにより99%以上の問題に対して、より高い警備効果を持つ解が存在しない最適な解を見つけられることを確認した。
従来手法と比較して、100ノードでは平均20倍、200ノードでは平均500倍の速度で最適な警備計画を見つけることができるという。さらに、従来手法では数日かけても良い解を見つけられなかった10万ノード規模の道路ネットワークの場合でも、本技術では数分で解が得られる。東京23区を含む20万ノードの道路ネットワークに50箇所の検問所を配置するシミュレーションでは、一般的なPCを使って5分で警備計画を導出することに成功した。
今後、富士通研究所は、同技術を用いた警備計画立案の実用化を進める。また、技術の適用などにより警備計画立案の対象を拡大していく。また、この技術を、富士通<6702>のAI技術「Zinrai」の1つとして2017年度中に実用化することを目指す。電気通信大学は、都市道路ネットワーク以外への拡張を進める予定だ。(編集担当:慶尾六郎)