数理システムユーザ会2010

発表内容

ゲーム理論で使うＮＵＯＰＴ−施設警備問題に対する一提案

1. 美術館問題と研究の動機
2. 状況設定と３つの問題
3. ゲーム理論の話
4. 侵入スケジューリング問題

平成２２年１１月１９日

5. 警備巡回路選択問題（ゲーム）
防衛大学校・情報工学科

6. 視線配分問題（ゲーム）宝崎 隆祐

7. まとめ1

1. 美術館問題と研究の動機

警備員巡回路問題

美術館問題:

美術館内をくまなく見て回るための最短ルートの作成(O(n4); Tan, et al., 1993)

Kleeの問い(1973)
美術館定理（n=12の例）

単純多角形内の警備員数は多くて2s(Chvatal,1975)(時間)静的警備計画：計算幾何学

直交多角形問題：

可視的カットn=12の例

要塞問題：(時間)動的警備計画(スケジューリング etc…)：ＯＲ，探索理論
警備計画の評価，防犯カメラの時間制御，警備ロボットの探知センサーの制御『厳密性については，それほど問わなくても．．．』

刑務所問題：

3

施設警備の自動化への対応2. 状況設定と３つの問題

防犯カメラ，ロボット技術，セキュリティ技術の進歩

巡回警備ロボット「アルテミス」
ガードロボ「リボーグＱ」（（株）テムザック・ＨＰより）（ALSOK総合警備保障・ＨＰより）

防犯カメラ

オペレーションズ・リサーチを用いた動的警備計画
警備計画の評価，防犯カメラの時間制御，警備ロボットの探知センサーの制御
5

多段捜索割当ゲームの定常解について

4

スケジューリングされた巡回路と未スケジューリングの侵入ルート
地理空間：
離散時間 T={1,…,T}
T：到着時刻の上限
複数の警備巡回路：
スケジュールされている複数の侵入ルート：
経由地点のみ推定（停止可能）
一定速度使用
視界を遮る障害物侵入者及び警備員は，侵入者に対する警備員からの視認度に興味

2

視認度の定義：δα/d(1)侵入者が警備員の視界内にあるか(δ)(2)双方の距離(d)(3)侵入者地点の明るさ(α)
侵入者は警備員の行動を観察可能
経由点での経由時間を適応的に決めるが，遅くとも T までに目的地に到着したい．
61美術館警備の状況設定#j侵入ルートq(j,1): 可視: 不可視

q(j,2)

３つの問題

障害物

δ速度 u(1) 侵入スケジューリング問題
警備巡回路に対しある侵入路を使用した場合の視認度を最小にする最悪の侵入スケジュール

距離d
距離dα

視認度：

p(s,t)位置 r(2) 警備巡回路選択問題
上記で計算された各巡回路と各侵入路との相性を考慮した警備巡回路の選択（ゲーム）ＮＵＯＰＴを使用

目的地

q(j,Lj)障害物(3) 視線配分問題
巡回中の警備員（ロボット）による侵入スケジュールを考慮した視線配分（ゲーム） ＮＵＯＰＴを使用

t=10#s警備巡回路t=1

t=5
7

3．ゲーム理論の話（ゲーム理論とは？）

8

ゲーム理論の歴史
１９４４年:フォン・ノイマン,モルゲンシュテルン『ゲーム理論と経済行動』(Theory of Games and Economic Behavior)
１９５０年:ジョン・ナッシュ「非協力ゲーム」
ノーベル経済学賞（ゲーム理論家）① １９９４年:ナッシュ，ゼルテン，ハルサニ② ２００５年:オーマン，セリング③ ２００７年:マスキン,マイヤーソン,ヒューウィックス「意志決定」の理論であり，意志決定者を支援する分析ツールである．
「ゲーム的状況」：複数の意志決定者が存在し，結果が自らの意志決定だけでなく他者の意志決定にも依存する環境
適用範囲：
オペレーションズ・リサーチ（ＯＲ），数学，情報科学，生物学，政治学，経済学，社会学，心理学，及び社会・経済・軍事その他の実学

ミクロ経済学（商品価格，消費者の動向）では，ゲーム理論は無くてはならないもの
910（例） ラバウル−ラエの輸送作戦（８１号作戦）

２人ゼロ和ゲーム
戦略形の表現①プレイヤーは誰か？
②取る手（戦略）は何か？
③利益（支払）の値は？
ニューギニア

支払行列
ソロモン海

y1 y2

#1を取る確率：x1
x2
x3
x4y3
この値になる
確率 = x2 y3

自分だけが戦略を変えても得にならない（純粋）戦略の組みプレイヤーＡは＃２，プレイヤーＢは＃２，支払は４（ゲームの値）
混合戦略による均衡解：
自分だけが混合戦略を変えても支払の期待値からは得にならない
プレイヤーの混合戦略の組み結果の期待値をゲームの値
11多段捜索割当ゲームの定常解について

122

一般の行列ゲームの解法

線形計画法による均衡解の導出
y1 y2=1-y1
x1x2=1-x1

最適混合戦略
Simple のプログラム(x*1 , x*2 ) = (1/5, 4/5)
(y*1 , y*2 ) = (2/5, 3/5)

支払の期待値 = 3 x1 y1 + 1.5 x2 y1 + x1 y2 + 2 x2 y2
最適な (x*1, x*2 ) を求める線形計画問題
max λ
制約： 3 x1 + 1.5 x2 ≧ λ
x1 + 2 x2 ≧ λ
x1 + x2 = 1, x1, x2 ≧ 0

NUOPT使用
max λs.t. Σ i vij * xi ≧ λ , j∈JΣ i xi =1, xi ≧ 0, i∈I

Set I; Element i(set=I); //Aの戦略
Set J; Element j(set=J); //Bの戦略
Parameter v(index=(i,j)); //支払
Variable lambda, x(index=i);
Objective f (type=maximize);
f=lambda;sum(v[i,j]*x[i],i) >= lambda;
sum(x[i],i)==1; x[i] >=0;13

4. 侵入スケジューリング問題

14

1つの警備巡回路と１つの侵入ルート
侵入ルート

連続する経由点間の移動時点数:

１つの警備巡回スケジュール対する１つの侵入ルー
トの最悪スケジュールとは，視認度の総和を最小にするような各経由点での出発時間を決める問題

巡回路vj

経由点からある時点数移動後の位置:
時点数 nj
時刻tでの警備員位置から，侵入者位置が見えるか？（可視性）
可視判別関数：δ(r,t)={1, 0}

変数：各経由点での出発時間
min 目的関数 (総視認度）= Σ（ 経由地点間の移動中の視認度＋ 経由地点での停止中の視認度 ）vj+1

経由点からの出発時間が分かれば，経由地点間の各位置の視認度は分かる！

制約条件： 各経由点での出発時間の前後関係
経由点 jでの出発時間 + 移動時間 ≦ 経由点 j+1 での出発時間

qj

障害物

rp(t)

qj+1

p={p(t), t∈T}q={q(l), l=1,…,L}
v1 = vL=0 （可視性）（α(r)は地点 r の明るさ）

視認度：
1516

侵入スケジューリングの例

スケジューリングのための動的計画法

T={1,…, 35}, 地理空間と巡回路，侵入路は図のとおり
侵入ルート：L=7 ，vj=0，速度 u=2(セル/時点)，明るさ α(r)=10

動的計画法による定式化
fj+1(t) = minz [ fj(z) + (経由点 j と j+1 間での移動中の総視認度)+ (経由点 j に時間 z まで滞在中の総視認度) ]初期条件： f1(t) = 0

17

多段捜索割当ゲームの定常解について

経由点

最小累積視認度(fj)

到着時間

出発時間(zj)

座標

①
②
③
④
⑤
⑥
⑦

0
0.09620.21180.21180.42810.58010.5801

158
11
19
2224

3
58
17
19
22

(3,12)(3,10)(7,10)(7, 6)(7, 3)(3, 3)(1, 4)−18

3① 以後のスケジュールを円滑にするため，t=1〜3の間止まり，時間調整①：f1= 0t=20
② 遠いので視認度の増加は小さい．
③ ある期間，四角形，衝立の陰を移動②：f2= 0.096

侵入スケジュールの巧妙さ，危険性の評価③：f3= 0.212④ この経由地で近接状態をやり過ごす．

t=15

t=25
⑤ 暴露状態は遠距離になるように①②③④④：f4= 0.212⑥ 後半の移動は，四角形の死角になる．
⑦：f7=④0.58
衝立を間に挟んで巧く移動
t=30

t=10

⑦ 完全に四角形の死角に入る．
⑥：f6= 0.58

最小総視認度 fL(T)= 0.5801 は，侵入ルートに対する巡回路の危険性，脆弱性の定量的評価値⑤：f5= 0.428：侵入者位置
：警備員位置t=1

各経由点ｊまでの累積視認度 fjの変化で，経由点間での侵入者移動の巧妙さを測ることが可能．
「障害物の死角を利用した移動」「経由点での時間調整」「経由点でのやり過ごし」「暴露状態は遠距離で」経由点(j)

最小視認 到着 出発度(fj)
時間 時間

①01

3

②0.0962

55③0.2118

88④0.2118

1117⑤0.4281

1919⑥0.5801

2222⑦0.5801

24

−

t=519

20

警備巡回路の選択問題の例

5. 警備巡回路選択問題（ゲーム）

侵入路3

複数警備巡回路と複数侵入ルート
R(p,q): 巡回路p.vs.侵入ルートqの間の最小総視認度は両者の相性
警備員側は，侵入者のとるルートを予め推測できない．
侵入者も，どの巡回路を警備員が巡回しているかは分からないが，実際に美術館に侵入すれば，巡回路に対し適応的に対処する．

侵入路1

警備巡回路 ２本
侵入ルート ４本

t=20
t=20

侵入路2
侵入路4t=10

巡回路2

支払をR(p,q)とする巡回路と侵入ルート選択の２人ゼロ和ゲーム

t=30

t=10t=1t=30

巡回路1t=1

21

6. 視線配分問題（ゲーム）

支払行列：R(ps ,qj)
s＼j

1*

2223

4*

10.5801 0.9912 0.5295 0.6259

20.8814 0.1679 0.5625 2.4993

複数侵入路に対するセキュリティ上の脆弱性を考慮した巡回中の警備員（警備ロボ）の視線の配り方
時点 tでの効果：
視認度×視線配分の割合＊: 被支配戦略r

警備巡回路に対する選択確率：
警備計画への組込み(#1, #2)= (0.461, 0.539)
欠陥の少ない計画，リスクの少ない計画
侵入路に対する選択確率：(#1, #2, #3, #4 )= (0, 0.039, 0.961, 0)

E(r,t)
p(t)

侵入路 j の探知確率：= 1- exp( - Σ t 視認度×視線配分)1023

多段捜索割当ゲームの定常解について

x244

捜索配分ゲーム（探索理論）

視線配分問題（ゲーム）の最適解

侵入者の侵入路の選択

侵入者の進入路の最適選択確率：π*(j)警備ロボの最適視線配分：
ゲームの値： 視線配分の重みの付いた総視認度

ｊ …

１…
警備ロボの視線配分計画
・・（探知確率）警備員位置からどの侵入路も死角になる時間帯では，視線配分が無駄になる．
2. 効果的な視線配分要領：① できるだけ多くの侵入路を同時監視する注視とする．
② 視認度の大小を考慮を考慮して，全時間で侵入路間でのバランスをとる．
1.

経路を選択をして逃げる目標物と，手持ちの捜索資源を効果的に投入し目標物を見つけたい警備員との２人ゼロ和ゲーム

このゲームは線形計画法で解くことができる！！
25

最適視線配分26

侵入路3t=20

侵入路1t=18100%

効果的な視線配分要領
1. できるだけ多くの侵入路侵入路4を同時監視する．
2. 視認度の大小を考慮して，全時間にわたり侵入路間でバランスをとる．

侵入路3

警備巡回路 ２本
侵入ルート ４本

侵入路1t=20t=20

侵入路2

侵入路2
侵入路4t=108%

64%巡回路236%

t=3092%t=30t=10：侵入者位置

t=10

巡回路1

： 警備員位置t=1t=1t=30

巡回路1t=1t=5 t=627

7. まとめ

注視配分の結果による巡回路の評価
巡回路１の最適視線配分
侵入路 j
重み付き総視認度
侵入者の選択確率

1

重み付き総視認度
侵入者の選択確率

3

1. 動的要素（侵入スケジュール）を考慮した施設警備に関するＯＲ応用の基礎的な提案
2. 実例を用いた検証が不可欠
3. 曖昧さの許容部分と厳密性の必要な部分との切分け

40.4844 0.4823 0.4823 0.4823
0

巡回路２の最適視線配分
侵入路 j

W=0.4823
2

10.072

0.389

0.539

侵入スケジュールの厳密性？

3① 防犯カメラの視線制御やズームの制御② 移動ロボットの視野，視界制限（『投光器（Floodlight）問題』）③ 既存の巡回路問題：『スパイ侵入問題』，『d-警備員巡回路問題』，『d-掃除人問題』，『動物園巡回路問題』，『サファリ巡回路問題』，etc…

40.2222 0.1679 0.2031 0.2398
01

視線配分の時間との整合性？

4. 具体的な問題への拡張と既存の美術館問題との融合

W=0.16792

28

00

評価： 『巡回路１が，２より優れている．』
29

多段捜索割当ゲームの定常解について

30

5