《探索モデルと探索の運動学》

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

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

［デイタム探索］　デイタム探索はデイタム点の誤差が大きい場合や,目標物が移動する場合に問題となる. 後者では拡散する目標分布を追跡する探索をとる. 既知のデイタム点から全周に速度 $u\,$ で拡散する目標物を探索者が速度 $v(v>u)\,$ で追跡する径路は極座標表現では, $r=r_{0}exp(\pm \lambda \theta )\,$, (ただし $r_{0}=ut_{0},t_{0}:\,$ 探索開始時間, $\lambda =\xi /{\sqrt {1-\xi ^{2}}},~\xi =u/v\,$, 指数の+符号は反時計方向の探索径路)で表わされる. デイタム点を一周する所要時間 $T=t_{0}[exp(2\pi \lambda )-1]\,$ は速度比 $\xi \,$ が1に近づけば急激に増加する. また初期存在領域が半径 $a\,$の円であり, そこから一様に逃避する目標物を, 有効探索率 $Q\,$ の探索者が目標存在領域の拡大に合わせて探索領域を拡大しつつ時間$[t_{0},t]\,$ の間ランダムに探索するとき, 目標探知確率 $P(t)\,$ は次式となる.

$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\}.\,$

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

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

$P(S)=1-{\frac {1}{S}}\int _{0}^{S}\exp \left(-\sum _{i=-\infty }^{\infty }F(|x-iS|)\right){\mbox{d}}x.\,$

　センサーの発見法則が決まれば 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle F(\cdot)\, } が定まるので 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P(S)\, } が計算される. 定距離発見法則や逆3乗法則の場合の $P(S)\,$ は公式化されている [1].

　ランダム探索において, 目標領域面積 $A\,$, 探索者の有効探索率 $Q\,$, 探索時間 $t\,$, 探索速度 $v\,$, 目標速度 $u\,$ の場合の目標探知確率 $P(t)\,$ は次式となる.

$P(t)=1-\exp \left(-{\frac {Qf(\xi ,n)t}{A}}\right),~~\xi ={\frac {u}{v}},~~n:\,$発見法則の形状係数,

$f(\xi ,n)={\frac {1}{2\pi }}\int _{0}^{2\pi }(\xi ^{2}+1-2\xi \cos \theta )^{(n-2)/\{2(n-1)\}}{\mbox{d}}\theta ,~~n>2.\,$

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

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

$\xi \geq 1~\,$ の場合, $~~g(\alpha )={\frac {1}{2\pi f(\xi ,\infty )}}\left\{\cos ^{-1}(-\cos \alpha /\xi )\cos \alpha +{\sqrt {\xi ^{2}-\cos ^{2}\alpha }}\right\},\,$

$\xi <1~\,$ の場合, $~~g(\alpha )=~\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ \ \,$

$q_{ij}=\left\{{\begin{array}{l}\\\\\\\\\\\\\\\end{array}}\right.\,$	$\textstyle {\frac {\cos \alpha }{2f(\xi ,\infty )}},~~~-\cos ^{-1}\xi \leq \alpha \leq \cos ^{-1}\xi ~~\,$のとき,
	$\textstyle {\frac {1}{2\pi f(\xi ,\infty )}}\left\{\cos ^{-1}(-\cos \alpha /\xi )\cos \alpha +{\sqrt {\xi ^{2}-\cos ^{2}\alpha }}\right\},\,$
	$\qquad -\cos ^{-1}(-\xi )\leq \alpha \leq -\cos ^{-1}\xi ~~\,$又は$~~\cos ^{-1}\xi \leq \alpha \leq \cos ^{-1}(-\xi )~~\,$のとき,
	$0,~~~\alpha <-\cos ^{-1}(-\xi )~~\,$又は$~~\alpha >\cos ^{-1}(-\xi )~~\,$のとき

探索者の針路を$0\,$度とし方位 $[-\alpha ,\alpha ]\,$間で の遭遇確率は $\textstyle G(\alpha )=\int _{-\alpha }^{\alpha }g(x){\mbox{d}}x\,$ であり, $\xi =0\,$の静止目標物の場合は 50% が探索者の針路を挾む約 $\pm 30\,$ 度の範囲で遭遇する.
　時間制限 $T\,$ 内で速度 $v\,$の探索者に小さな速度 $u\,$の目標物がが会合できるのは, 探索者から前方に距離 $vT\,$の点を中心とする半径 $uT\,$の円と探索者の進路から左右に角度$\theta =\pm \sin ^{-1}(u/v),v>u\,$ (近接限度角)の2本の直線とで囲まれる領域 (近接可能領域(region of approach))に目標物がいる場合である.目標物の速度の方が大きい場合, 時間制限がなければ常に探索者に会合できるが, 時間制限があれば探索者の前方 $vT\,$ の点を中心とする半径 $uT\,$ の円内が近接可能領域となる.
［バリヤー哨戒］ 海峡を通峡する場合のように目標径路がある幅内を通ることが予測できるとき, 探索者はこの径路をカバーする線上で待ち受け探索ができる. このときの探索法は, 目標径路帯を横断して往復しつつ通過する目標物を探索する往復哨戒 (back-and-forth barrier patrol), 目標速度 $u\,$ と同じ遡上速度を保ちながら径路帯を往復する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.