都市の警備配置問題を高速に解くAI--富士通研と電気通信大

NO BUDGET 2016年05月11日 07時20分

  • このエントリーをはてなブックマークに追加

 富士通研究所と国立大学法人電気通信大学は5月10日、人工知能(AI)を活用して警備計画の立案を支援する技術として、数学理論の1つであるゲーム理論を用いて、犯罪者を捕捉するための検問所などを想定した「都市道路ネットワーク警備問題」を高速に解くアルゴリズムを開発したと発表した。

 富士通研究所は今後、本技術を用いた警備計画立案の実用化を進めるほか、本技術の適用などにより警備計画立案の対象を拡大していく。また、富士通のAI技術「Human Centric AI Zinrai(Zinrai)」の1つとして、2017年度中の実用化を目指す。電気通信大学は、本技術の都市道路ネットワーク以外への拡張を進める。

 人の集まる場所でのセキュリティ対策では、完全に侵入経路や逃走経路を封鎖することは限られた警備資源の中では不可能なことが多く、警備員を効果的に配置し想定される被害を最小化することが求められている。そうした警備計画の立案はこれまで、専門家の経験と勘に委ねられていたが、近年では専門家の判断を支援する技術として、攻守双方を数理的に記述するゲーム理論が注目されている。

 しかし、ゲーム理論を用いて犯罪者を検問所などで捕捉する都市道路ネットワーク警備問題については、扱う道路のネットワーク規模に対して計算量が指数的に増加するため、実際の都市での膨大なノードの問題を現実的な計算時間で解くことが不可能で、実問題への適用が困難だった。

 それに対し今回、富士通研究所独自のネットワーク縮約技術によって、都市道路ネットワーク警備問題を高速に解くアルゴリズムを開発。また、電気通信大学と共同で、この技術に関する理論的な裏付けを行った。

 開発した技術の特徴は以下の通り。

TechRepublic Japan関連記事

ネットワーク縮約の技術

 検問配置の候補に応じて計算に用いるネットワークを大幅に簡単化する縮約技術を開発。道路ネットワークの中には検問所の配置による警備効果(攻撃を受けた際の被害額の期待値を低減させる効果)が高い箇所と低い箇所があるため、警備効果の低い箇所を検問配置の候補から外すことで警備側の行動パターンの数を削減することができる。

 さらに、道路ネットワークの中で警備員を配置しない箇所をまとめることにより、犯罪者側の行動パターンの数も大幅に削減できる。これにより、計算量を大幅に削減する事に成功した。

 本技術については、富士通研究所と電気通信大学が共同で、この縮約後の道路ネットワークを総当たりで求めた計画による警備効果が、縮約前の道路ネットワークを総当たりで求めた計画による警備効果と一致することを理論的に示している。

ネットワーク縮約による計算量の削減 (富士通研究所提供)
ネットワーク縮約による計算量の削減 (富士通研究所提供)

高速・高精度なアルゴリズム

 開発したアルゴリズムでは、まず、最も被害が想定されるノードに着目して決定した検問配置の候補を決め、検問を行う場所と、その割合について、全体として被害の期待値が最も小さくなる最適な組み合わせについて、ネットワーク縮約の技術を用いて高速に計算する。

 その結果、新たに被害の期待値が大きくなったノードに着目して検問配置の候補となる道路を追加し、同様に最適な組み合わせを計算する。これを繰り返すことにより、近似的な最適解を高速に計算していく。3万通りの擬似的な道路ネットワークを使ったシミュレーションでは、このアルゴリズムにより99%以上の問題に対して、より高い警備効果を持つ解が存在しない最適な解を見つけられることを確認した。

 新たなアルゴリズムにより、従来技術と比較して、100ノードの問題では平均20倍、200ノードの問題では平均500倍の速度で理論上最適な警備計画を見つけられるようになったという。本技術により、例えば、従来技術では計画立案に数日かかっていた東京都23区規模である20万ノードの問題において、本技術では一般的なPCを使って5分程度で警備計画を導出することが可能になるなど、計画立案への対話的な支援が実現するとのこと。

ZDNet Japan 記事を毎朝メールでまとめ読み(登録無料)

  • このエントリーをはてなブックマークに追加

この記事を読んだ方に

関連ホワイトペーパー

連載

CIO
デジタル“失敗学”
IT部門の苦悩
Rethink Internet:インターネット再考
インシデントをもたらすヒューマンエラー
トランザクションの今昔物語
エリック松永のデジタルIQ道場
研究現場から見たAI
Fintechの正体
米ZDNet編集長Larryの独り言
大木豊成「仕事で使うアップルのトリセツ」
山本雅史「ハードから読み解くITトレンド放談」
田中克己「2020年のIT企業」
松岡功「一言もの申す」
松岡功「今週の明言」
内山悟志「IT部門はどこに向かうのか」
林 雅之「デジタル未来からの手紙」
谷川耕一「エンプラITならこれは知っとけ」
大河原克行「エンプラ徒然」
内製化とユーザー体験の関係
「プロジェクトマネジメント」の解き方
ITは「ひみつ道具」の夢を見る
セキュリティ
「企業セキュリティの歩き方」
「サイバーセキュリティ未来考」
「ネットワークセキュリティの要諦」
「セキュリティの論点」
スペシャル
ざっくりわかるSNSマーケティング入門
課題解決のためのUI/UX
誰もが開発者になる時代 ~業務システム開発の現場を行く~
「Windows 10」法人導入の手引き
ソフトウェア開発パラダイムの進化
エンタープライズトレンド
10の事情
座談会@ZDNet
Dr.津田のクラウドトップガン対談
Gartner Symposium
IBM World of Watson
de:code
Sapphire Now
VMworld
Microsoft WPC
Microsoft Connect()
HPE Discover
Oracle OpenWorld
Dell EMC World
AWS re:Invent
AWS Summit
PTC LiveWorx
吉田行男「より賢く活用するためのOSS最新動向」
古賀政純「Dockerがもたらすビジネス変革」
中国ビジネス四方山話
ベトナムでビジネス
米株式動向
日本株展望
企業決算
このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]