「《探索モデルと探索の運動学》」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(3人の利用者による、間の6版が非表示)
1行目: 1行目:
 
'''【たんさくもでるとたんさくのうんどうがく (search model and kinematics of search) 】'''
 
'''【たんさくもでるとたんさくのうんどうがく (search model and kinematics of search) 】'''
  
 [[探知探索]]は3つの類型に大別できる. 探索の事前に目標位置情報 ([[デイタム情報]]) があり, [[デイタム点]]を基準に行われる探索を[[デイタム探索]] (datum search) という. しかし移動目標物は速やかに拡散し目標分布は急速に一様化するので, 時間が経てば目標存在領域を一様に探索せざるを得なくなる. この段階を[[区域探索]] (area search) という. また明確な目標情報はないが目標存在領域が推定され, [[目標存在分布]]は領域内で一様と見なされる場合にも同様の状況となる. もう1つの探索は目標出現時間や位置は不明だが, 地理上の制約等からある幅の目標移動径路帯が推定できる場合である. このとき探索者は目標径路を抑える線上で通過する目標物の待ち受け探索ができる. これを[[バリヤー哨戒]] (barrier patrol) と呼ぶ.
+
 [[探知探索]] の現実的活動はその特徴から3つに大別できる. 探索の事前に目標位置情報 ([[デイタム情報]]) があり, [[デイタム点]]を基準に行われる探索を[[デイタム探索]] (datum search) という. しかし移動目標物は速やかに拡散し目標分布は急速に一様化するので, 時間が経てば目標存在領域を一様に探索せざるを得なくなる. この段階を[[区域探索]] (area search) という. また目標情報のある無しにかかわらず, [[目標存在分布]] が一様と見なされる場合にも同様の状況となる. 今1つの探索は目標出現時間や位置は不明だが, 地理上の制約等からある幅の目標移動径路帯が推定できる場合である. このとき探索者は目標径路帯をカバーする線上で通過する目標物の待ち受け探索ができる. これを[[バリヤー哨戒]] (barrier patrol) と呼ぶ.
  
'''[デイタム探索]''' デイタム探索はデイタム点の誤差が大きい場合や,移動目標物の場合が問題になる. 後者では拡散する目標分布を追跡する探索となる. 既知のデイタム点から全周に速度 <math>u\, </math> で拡散する目標物を探索者が速度 <math>v(v>u)\, </math> で追跡する径路は極座標では, <math>r=r_0 exp(\pm\lambda\theta)\, </math>, ただし <math>r_0=ut_0, t_0:\, </math> 探索開始時間, <math>\lambda = \xi/\sqrt{1-\xi^2},~ \xi=u/v\, </math> ,(指数の+符号は反時計方向の探索径路)で表わされる. デイタム点を一周する所要時間 <math>T=t_0 [exp(2\pi\lambda)-1]\, </math> は速度比 <math>\xi\, </math> が1に近づけば急激に増加する. また初期存在領域が円(半径 <math>a\, </math> )で一様に逃避する目標物を, <math>[t_0,t]\, </math> の間, [[有効探索率]] <math>Q\, </math> の探索者が目標存在領域の拡大に合わせて探索領域を拡大しつつランダムに探索するとき, 目標探知確率 <math>P(t)\, </math> は次式となる.
+
'''[デイタム探索]''' デイタム探索はデイタム点の誤差が大きい場合や,目標物が移動する場合に問題となる. 後者では拡散する目標分布を追跡する探索をとる. 既知のデイタム点から全周に速度 <math>u\, </math> で拡散する目標物を探索者が速度 <math>v(v>u)\, </math> で追跡する径路は極座標表現では, <math>r=r_0 exp(\pm\lambda\theta)\, </math>, (ただし <math>r_0=ut_0, t_0:\, </math> 探索開始時間, <math>\lambda = \xi/\sqrt{1-\xi^2},~ \xi=u/v\, </math>, 指数の+符号は反時計方向の探索径路)で表わされる. デイタム点を一周する所要時間 <math>T=t_0 [exp(2\pi\lambda)-1]\, </math> は速度比 <math>\xi\, </math> が1に近づけば急激に増加する. また初期存在領域が半径 <math>a\, </math>の円であり, そこから一様に逃避する目標物を, [[有効探索率]] <math>Q\, </math> の探索者が目標存在領域の拡大に合わせて探索領域を拡大しつつ時間<math>[t_0,t]\, </math> の間ランダムに探索するとき, 目標探知確率 <math>P(t)\, </math> は次式となる.
  
  
:<math>
+
<center>
 +
<math>
 
P(t) = 1 - \exp \left\{ - \frac{Q}{\pi ua} \left( \tan^{-1} \left( \frac{ut}a \right)  
 
P(t) = 1 - \exp \left\{ - \frac{Q}{\pi ua} \left( \tan^{-1} \left( \frac{ut}a \right)  
 
- \tan^{-1} \left( \frac{ut_0}a \right) \right) \right\}.
 
- \tan^{-1} \left( \frac{ut_0}a \right) \right) \right\}.
 
\, </math>
 
\, </math>
 +
</center>
  
  
'''[区域探索]''' 目標分布が目標存在領域内で一様な場合, 探索者は領域内をしらみつぶしに一様に探索せざるを得ない. ここで一様な探索は規則的パターンで探索する方法と, 各地点を確率的に一様に探索し期待カバレッジの一様性を図る方法とがある. 前者の最も簡単な探索法は, 等間隔 <math>S\, </math> (掃引幅)の平行径路で一様に目標存在領域を走査する[[平行探索]] (parallel sweep, raster scan) であり, 後者は各時点の探索地点を目標存在領域内で一様な確率でランダムに選んで探索する[[ランダム探索 (探索理論における)|ランダム探索]] (random search) である. 目標物と探索者の相互探索状況では, 平行探索は目標側の先制探知により回避されやすいが, ランダム探索は探索径路を目標側に察知させない利点がある. また一方的探索ではランダム探索は探索径路が乱れ,ランダムな重複や空隙を生ずる場合の極限的な状況に対応する.
+
'''[区域探索]''' 目標分布が目標存在領域内で一様な場合, 探索者は領域内をしらみつぶしに一様に探索せざるを得ない. ここで一様な探索は規則的パターンで探索する方法と, 各地点を確率的に一様に探索する方法とがある. 前者の代表的な探索法は, 等間隔<math>S\,</math> (掃引幅) の平行経路で規則的に走査する[[平行探索]] (parallel sweep, raster scan) であり, 後者の代表例は各時点の探索地点を目標存在領域内で一様な確率でランダムに選んで探索する[[ランダム探索 (探索理論における)|ランダム探索]] (random search) である. 目標物と探索者の相互探索状況では, 平行探索は目標物側に探索者の意図を見透かされ回避されやすいが, ランダム探索は探索径路を目標側に察知させない利点がある. またランダム探索は, 探索径路が乱れランダムな重複や空隙を生ずる場合の極限的な状況に対応する探索だとも言える.
  
 平行探索径路の1つを <math>y\, </math> 軸, 直交して <math>x\, </math> 軸をとる. <math>F(z)\, </math> を横距離 <math>z\, </math> の直線径路の[[探知ポテンシャル]]とし, 探索区域端辺部の条件の不均質を無視して無限領域を考えれば, 掃引幅 <math>S\, </math> の平行探索の目標探知確率 <math>P(S)\, </math> は次式となる.
+
 平行探索径路の1つを <math>y\, </math> 軸, 直交座標に <math>x\, </math> 軸をとる. <math>F(z)\, </math> を横距離 <math>z\, </math> の直線径路の[[探知ポテンシャル]]とし, 探索区域端辺部における探索効果の近似を行えば, 掃引幅 <math>S\, </math> の平行探索による目標探知確率 <math>P(S)\, </math> は次式となる.
  
  
:<math>
+
<center>
P(S) = 1 - \frac1S \int_0^S \exp \left( - \sum_i F(|x-iS|) \right) {\mbox{d}}x.
+
<math>
 +
P(S) = 1 - \frac1S \int_0^S \exp \left( - \sum_{i=-\infty}^{\infty}  F(|x-iS|) \right) {\mbox{d}}x.
 
\, </math>
 
\, </math>
 +
</center>
  
  
発見法則が決まれば <math>F(\cdot)\, </math> が定まるので <math>P(S)\, </math> が計算される. [[定距離発見法則]]や逆3乗法則の場合の <math>P(S)\, </math> が求められている [1]. 上式は静止目標物の探知確率であるが, 目標物が動き回る場合, 平行探索径路はランダム化される.  
+
 センサーの発見法則が決まれば <math>F(\cdot)\, </math> が定まるので <math>P(S)\, </math> が計算される. [[定距離発見法則]]や逆3乗法則の場合の <math>P(S)\, </math> は公式化されている [1].  
  
 
 ランダム探索において, 目標領域面積 <math>A\, </math>, 探索者の有効探索率 <math>Q\, </math>, 探索時間 <math>t\, </math>, 探索速度 <math>v\, </math>, 目標速度 <math>u\, </math> の場合の目標探知確率 <math>P(t)\, </math> は次式となる.  
 
 ランダム探索において, 目標領域面積 <math>A\, </math>, 探索者の有効探索率 <math>Q\, </math>, 探索時間 <math>t\, </math>, 探索速度 <math>v\, </math>, 目標速度 <math>u\, </math> の場合の目標探知確率 <math>P(t)\, </math> は次式となる.  
  
  
:<math>
+
<center>
 +
<math>
 
P(t) = 1 - \exp \left( - \frac{Q f(\xi,n) t}{A} \right), ~~ \xi=\frac{u}v,~~ n:
 
P(t) = 1 - \exp \left( - \frac{Q f(\xi,n) t}{A} \right), ~~ \xi=\frac{u}v,~~ n:
 
\, </math>発見法則の形状係数,  
 
\, </math>発見法則の形状係数,  
35行目: 40行目:
 
2)/\{2(n-1)\} } {\mbox{d}}\theta, ~~n>2 .
 
2)/\{2(n-1)\} } {\mbox{d}}\theta, ~~n>2 .
 
\, </math>
 
\, </math>
 +
</center>
 +
  
 +
 <math>f(\xi,n)\, </math> は目標物が動き回るために探索者との遭遇が増加する率を表し, [[逆n乗発見法則]]を仮定したときの有効探索率の[[動的増分係数]] (factor of dynamic enhancement) と呼ばれる.  <math>f(\xi,n)\, </math> は <math>\xi\, </math> 及び <math>n\, </math> の単調増加関数となり, <math> f(0,n) =1 \,</math>である.
  
 <math>f(\xi,n)\, </math> は[[逆n乗発見法則]]を仮定したときの有効探索率の[[動的増分係数]] (factor of dynamic enhancement) であり, <math>f(0,n) = 1,f(\xi,n)\, </math> <math>\xi\, </math> 及び <math>n\, </math> の単調増加関数である. <math>f(\cdot)\, </math> は目標物が動き回るために探索者との遭遇が増加する率を表す.  
+
 速度 <math>v\, </math> の探索者を中心に半径 <math>R\, </math> の円を考えたとき, ランダム運動をする速度<math>u\, </math>の目標物が相対方位 <math>[ \alpha, \alpha+ \Delta\alpha]\, </math> で円内に入る確率 <math>g(\alpha)\Delta\alpha\, </math> は次式となる [1] .
  
 速度 <math>v\, </math> の探索者を中心に半径 <math>R\, </math> の円を考えたとき, ランダム運動の目標物(速度 <math>u\, </math> ) が相対方位 <math>[ \alpha, \alpha+ \Delta\alpha]\, </math> で円内に入る確率 <math>g(\alpha)\Delta\alpha\, </math> は次式となる [1] .
 
  
  
52行目: 59行目:
 
\, </math>
 
\, </math>
  
<table>  
+
:::<table>  
 
<tr>  
 
<tr>  
 
<td rowspan="4">  <math>q_{ij}=  
 
<td rowspan="4">  <math>q_{ij}=  
79行目: 86行目:
 
<td><math>0,~~~ \alpha <  - \cos^{-1}(- \xi) ~~\, </math>又は<math>~~ \alpha > \cos^{-1}(- \xi) ~~\, </math>のとき</td>  
 
<td><math>0,~~~ \alpha <  - \cos^{-1}(- \xi) ~~\, </math>又は<math>~~ \alpha > \cos^{-1}(- \xi) ~~\, </math>のとき</td>  
 
</tr>  
 
</tr>  
</table>
+
:::</table><br>
  
  
 +
探索者の針路を<math>0\,</math>度とし方位 <math>[-\alpha, \alpha]\, </math>間で の遭遇確率は <math>\textstyle G(\alpha) = \int_{-\alpha}^{\alpha} g(x) {\mbox{d}}x\, </math> であり, <math> \xi=0 \, </math>の静止目標物の場合は 50% が探索者の針路を挾む約 <math>\pm30\, </math> 度の範囲で遭遇する.<br>
  
探索者の針路方向 <math>[-\alpha, \alpha]\, </math> の遭遇確率は <math>\textstyle G(\alpha) = \int_{-\alpha}^{\alpha} g(x) {\mbox{d}}x\, </math> であり, 静止目標物 <math>( \xi=0 )\, </math> の場合は 50% が探索者の針路を挾む約 <math>\pm30\, </math> 度の範囲で遭遇する.
+
 時間制限 <math>T\, </math> 内で速度 <math>v\, </math>の探索者に小さな速度 <math>u\, </math>の目標物がが会合できるのは, 探索者から前方に距離 <math>vT\, </math>の点を中心とする半径 <math>uT\, </math>の円と探索者の進路から左右に角度<math> \theta = \pm \sin^{-1}(u/v), v>u\, </math> (近接限度角)の2本の直線とで囲まれる領域 ([[近接可能領域]](region of approach))に目標物がいる場合である.目標物の速度の方が大きい場合, 時間制限がなければ常に探索者に会合できるが, 時間制限があれば探索者の前方 <math>vT\, </math> の点を中心とする半径 <math>uT\, </math> の円内が近接可能領域となる.<br>
  
 探索者(速度 <math>v\, </math> )に劣速の目標物(速度 <math>u\, </math>)が会合できるのは, 探索者の針路から <math>\pm \sin^{-1}(u/v), v>u\, </math>, (近接限度角)の楔形領域に目標物がいる場合である. また時間制限 <math>T\, </math> 内の目標物の[[近接可能領域]](region of approach) , 探索針路を挾んで中心角 <math>2\theta\, </math>, 弦 <math>vT\, </math> , 弧の曲率半径 <math>uT\, </math> の扇形領域となる. 目標物が優速ならば時間制限がなければ常に探索者に会合できるが, 時間制限があれば探索者の前方 <math>vT\, </math> の点を中心とする半径 <math>uT\, </math> の円内が近接可能領域となる.
+
'''[バリヤー哨戒]''' 海峡を通峡する場合のように目標径路がある幅内を通ることが予測できるとき, 探索者はこの径路をカバーする線上で待ち受け探索ができる. このときの探索法は, 目標径路帯を横断して往復しつつ通過する目標物を探索する[[往復哨戒]] (back-and-forth barrier patrol), 目標速度 <math>u\, </math> と同じ遡上速度を保ちながら径路帯を往復する[[8の字哨戒]] (crossover or bow-tie type barrier patrol), 径路帯の中央で待ち受ける定点哨戒(fixed point barrier patrol), 径路帯上 の一定区域でランダム探索を行うランダム哨戒 (random patrol) 等があり, これらの評価モデルが定式化されている. 以上は1つの目標径路帯に対する哨戒問題であるが, 複数の目標径路への探索者の最適配置問題, ネットワーク状の目標径路網での最適バリヤー問題 [2]等に関しても研究されている.<br>
  
'''[バリヤー哨戒]''' 目標径路がある幅で予測できるとき, 探索者は目標径路を抑える線上で待ち受け探索ができる. このときの探索法は, 目標径路帯を横断して往復しつつ通過する目標物を探索する[[往復哨戒]] (back-and-forth barrier patrol), 目標速度 <math>u\, </math> と会合針路で往復する[[8の字哨戒]] (crossover or bow-tie type barrier patrol), 目標径路帯の中央で待ち受ける定点哨戒(fixed point barrier patrol), 目標径路帯上 の一定区域でランダム探索を行うランダム哨戒 (random patrol) 等がある. これらの評価モデルが定式化されており, 更に双方的な探索で目標側が探索者を先制探知したときは哨戒線の弱点とタイミングを選んで突破する場合の研究もある. 以上は1つの目標径路帯の哨戒パターンの評価問題であるが, 複数の目標径路への探索者の最適配置問題, ネットワーク状の目標径路網上の最適配置問題 [2], 目標側の最適径路選択のゲーム・モデルも研究されている.
+
'''[探索のマルコフ連鎖モデル]''' これまで3つの探索形態の定式化モデルを述べ たが, 探索中に目標状態, センサー能力, 環境条件等が変化する場合の探索プロセスをマルコフ連鎖モデルにより定式化した研究もなされており, 出現/消滅形目標物の探索, 先制探知のある探索, 虚探知を含む探索等のモデルが報告されている.
 
 
'''[探索のマルコフ連鎖モデル]''' 上では3つの探索形態の定式化モデルを述べ たが, 探索中に目標状態, センサー能力, 環境条件等が再帰的に変化する場合の探索プロセスは, マルコフ連鎖モデルに定式化される. 出現/消滅形目標物の探索, 先制探知のある探索, 虚探知を含む探索等のモデルが報告されている.
 
  
  
99行目: 105行目:
 
[1] B. O. Koopman, ''Search and Screening'', OEG Report No.56, 1946.
 
[1] B. O. Koopman, ''Search and Screening'', OEG Report No.56, 1946.
  
[2] 宝崎隆祐, 飯田耕司, 寺本昌義, 「ネットワーク上の待ち伏せ捜索における離散捜索努力量の最適配分」, 『防衛大学校理工学研究報告』, '''36''' (1998), 39-46.
+
[2] R. Hohzaki, K. Iida and M. Teramoto, "Optimal Search for a Moving Target with No Time Information Maximizing the Expected Reward," ''Journal of the Operations Research Society of Japan'', '''42'''(1999), 167-179.
 +
 
 +
[[category:探索理論|たんさくもでるとたんさくのうんどうがく]]

2007年8月8日 (水) 01:27時点における最新版

【たんさくもでるとたんさくのうんどうがく (search model and kinematics of search) 】

 探知探索 の現実的活動はその特徴から3つに大別できる. 探索の事前に目標位置情報 (デイタム情報) があり, デイタム点を基準に行われる探索をデイタム探索 (datum search) という. しかし移動目標物は速やかに拡散し目標分布は急速に一様化するので, 時間が経てば目標存在領域を一様に探索せざるを得なくなる. この段階を区域探索 (area search) という. また目標情報のある無しにかかわらず, 目標存在分布 が一様と見なされる場合にも同様の状況となる. 今1つの探索は目標出現時間や位置は不明だが, 地理上の制約等からある幅の目標移動径路帯が推定できる場合である. このとき探索者は目標径路帯をカバーする線上で通過する目標物の待ち受け探索ができる. これをバリヤー哨戒 (barrier patrol) と呼ぶ.

[デイタム探索] デイタム探索はデイタム点の誤差が大きい場合や,目標物が移動する場合に問題となる. 後者では拡散する目標分布を追跡する探索をとる. 既知のデイタム点から全周に速度 で拡散する目標物を探索者が速度 で追跡する径路は極座標表現では, , (ただし 探索開始時間, , 指数の+符号は反時計方向の探索径路)で表わされる. デイタム点を一周する所要時間 は速度比 が1に近づけば急激に増加する. また初期存在領域が半径 の円であり, そこから一様に逃避する目標物を, 有効探索率 の探索者が目標存在領域の拡大に合わせて探索領域を拡大しつつ時間 の間ランダムに探索するとき, 目標探知確率 は次式となる.



[区域探索] 目標分布が目標存在領域内で一様な場合, 探索者は領域内をしらみつぶしに一様に探索せざるを得ない. ここで一様な探索は規則的パターンで探索する方法と, 各地点を確率的に一様に探索する方法とがある. 前者の代表的な探索法は, 等間隔 (掃引幅) の平行経路で規則的に走査する平行探索 (parallel sweep, raster scan) であり, 後者の代表例は各時点の探索地点を目標存在領域内で一様な確率でランダムに選んで探索するランダム探索 (random search) である. 目標物と探索者の相互探索状況では, 平行探索は目標物側に探索者の意図を見透かされ回避されやすいが, ランダム探索は探索径路を目標側に察知させない利点がある. またランダム探索は, 探索径路が乱れランダムな重複や空隙を生ずる場合の極限的な状況に対応する探索だとも言える.

 平行探索径路の1つを 軸, 直交座標に 軸をとる. を横距離 の直線径路の探知ポテンシャルとし, 探索区域端辺部における探索効果の近似を行えば, 掃引幅 の平行探索による目標探知確率 は次式となる.



 センサーの発見法則が決まれば が定まるので が計算される. 定距離発見法則や逆3乗法則の場合の は公式化されている [1].

 ランダム探索において, 目標領域面積 , 探索者の有効探索率 , 探索時間 , 探索速度 , 目標速度 の場合の目標探知確率 は次式となる.


発見法則の形状係数,


  は目標物が動き回るために探索者との遭遇が増加する率を表し, 逆n乗発見法則を仮定したときの有効探索率の動的増分係数 (factor of dynamic enhancement) と呼ばれる. 及び の単調増加関数となり, である.

 速度 の探索者を中心に半径 の円を考えたとき, ランダム運動をする速度の目標物が相対方位 で円内に入る確率 は次式となる [1] .


の場合,
の場合,
   のとき,
又はのとき,
又はのとき

探索者の針路を度とし方位 間で の遭遇確率は であり, の静止目標物の場合は 50% が探索者の針路を挾む約 度の範囲で遭遇する.
 時間制限 内で速度 の探索者に小さな速度 の目標物がが会合できるのは, 探索者から前方に距離 の点を中心とする半径 の円と探索者の進路から左右に角度 (近接限度角)の2本の直線とで囲まれる領域 (近接可能領域(region of approach))に目標物がいる場合である.目標物の速度の方が大きい場合, 時間制限がなければ常に探索者に会合できるが, 時間制限があれば探索者の前方 の点を中心とする半径 の円内が近接可能領域となる.
[バリヤー哨戒] 海峡を通峡する場合のように目標径路がある幅内を通ることが予測できるとき, 探索者はこの径路をカバーする線上で待ち受け探索ができる. このときの探索法は, 目標径路帯を横断して往復しつつ通過する目標物を探索する往復哨戒 (back-and-forth barrier patrol), 目標速度 と同じ遡上速度を保ちながら径路帯を往復する8の字哨戒 (crossover or bow-tie type barrier patrol), 径路帯の中央で待ち受ける定点哨戒(fixed point barrier patrol), 径路帯上 の一定区域でランダム探索を行うランダム哨戒 (random patrol) 等があり, これらの評価モデルが定式化されている. 以上は1つの目標径路帯に対する哨戒問題であるが, 複数の目標径路への探索者の最適配置問題, ネットワーク状の目標径路網での最適バリヤー問題 [2]等に関しても研究されている.
[探索のマルコフ連鎖モデル] これまで3つの探索形態の定式化モデルを述べ たが, 探索中に目標状態, センサー能力, 環境条件等が変化する場合の探索プロセスをマルコフ連鎖モデルにより定式化した研究もなされており, 出現/消滅形目標物の探索, 先制探知のある探索, 虚探知を含む探索等のモデルが報告されている.


参考文献

[1] B. O. Koopman, Search and Screening, OEG Report No.56, 1946.

[2] R. Hohzaki, K. Iida and M. Teramoto, "Optimal Search for a Moving Target with No Time Information Maximizing the Expected Reward," Journal of the Operations Research Society of Japan, 42(1999), 167-179.