《移動目標物の最適探索》

出典: ORWiki

【いどうもくひょうぶつのさいてきたんさく (optimal search for a moving target) 】

　自分の意志ではなく，一定のルールに従って存在位置が時間的に変化する目標物を移動目標物(moving target) といい，本項ではそういう目標物の探索を扱う．静止目標物の探索においては，目的関数が決定変数ごとに分離された和の形をとることが多く，解析が比較的容易となり，研究は基本モデルによる一般論から特殊モデルの解析へと，どちらかと言えば演繹的方向に進んだ．それに対し移動目標物探索問題では，目的関数が分離されていないため，解析は格段と困難になり，研究も遅れて始まり，単純・具体的なモデル解析の集積から一般理論の確立へと帰納的方向に進んだ．今日では移動目標物探索においても最適性に関する必要十分条件が確立され，静止目標物探索も含めて見晴らしの良い統一的視点をもつこととなった．ただその複雑さの故に必要十分条件から解析的に最適政策を導出することができず，逐次近似法としての政策改良法が提案されている．それは他の期の努力配分を固定した一期だけの努力再配分を各期について行い，その改善操作を要求精度を満たすまで繰り返すというものである．この結果今では計算機を用いて格段に多くの問題が解けるようになった．ただこれらのアルゴリズムは有限回の操作で終了する必要から，空間・時間がともに離散かつ有限個でなければならない．


　指数型探知関数の場合の移動目標物に対する基本探索モデルは次の通りである．探索空間はn \, 個の小領域より成り，探索期間としてT \, 期間を考える．目標物の運動は探索者の行動とは独立であり，有限個の移動経路(moving path) が考えられるものとする．移動経路は\omega= (\omega_1 ,\cdots, \omega_T )\, で表される. \omega_i\,は第i \, 期に目標物が存在する小領域である．移動経路の集合を\Omega\, とし，移動経路が\omega\, である確率をp(\omega)\, とする．第i \,期に投入可能な探索努力量はm(i) \,で，これは任意に細分可能とする．探索政策は\phi =\left\{ \phi (k,i) \mid k=1,\cdots,n; i=1,\cdots,T \right\} \, で表される．\phi (k, i)\,は第i \, 期に小領域k \, へ投入される努力量である．第i \, 期に目標物が小領域k \, に存在するとの条件のもとで，その期に努力量z \, を小領域k \, に投入して発見する確率を1- \exp\left[-\lambda(k,i)z \right]\, とする．ここに\lambda(k,i)\, は所与の正定数で，第i \, 期の小領域k \, における瞬間発見率(instantaneous detection rate) である．問題はT \, 期間での発見確率 を最大にすることである．定式化すると，制約条件

\begin{array}{ll} \sum_{k=1}^{n} \phi(k,i) \leq m(i),~i=1,\cdots, T \\ \phi(k,i) \geq 0, ~k=1,\cdots, n;~i=1,\cdots, T \end{array} \,

のもとで、汎関数

P[\phi]= \sum_{\omega \in \Omega} p(\omega) \left[ 1- \exp ( - \sum_{i=1}^{T} \lambda(\omega_i,i) \phi(\omega_i,i) ) \right] \,

を最大にする\phi\, を求めることである．Brown[1] によれば，政策\phi^{*}\, が最適であるための必要十分条件は，整数\mu_1,\cdots, \mu_T \,　が存在して

\left[ \frac{\partial P[\phi]}{\partial \phi(k,i)} \right]_{\phi=\phi^*}~ \left\{ {= \atop \leq} \right\} \mu_1 ~~~ if ~~ \phi^*(k,i) \left\{ {> \atop =} \right\} 0 ~~~( k=1,\cdots,n;~i=1,\cdots, T)

が成立することである．これは静止目標物探索におけるde Guenin ルールと同種のNeyman-Pearson lemma 型の条件式である．Brown はさらに，最適配分\phi^{*}\,の第i \, 期における配分\phi^{*}(\cdot,i)\, は，第i \, 期以外の全ての期を\phi^{*}\, に従って探索して発見できないとの条件のもとでの，目標物の第i \, 期における存在分布を事前分布とする静止目標物探索の最適政策になっていることを示した．これは発見確率最大化問題に関しては，移動目標物に対する最適探索が静止目標物に対する最適探索の多重構造になっていることを示すものである．Brown はこのことより一期ごとの努力再配分を繰り返していく政策改良法を提案している．Stromquist and Stone[8] は，一般探知関数の場合を含む，より一般的な汎関数最大化問題において，最適性の必要十分条件を得ているが，これは静止目標物探索を含めて，統一的視点を与えるものである．


　発見確率最大化以外の探索基準についても，いくつかの研究がある．Stone and Kadane[6] は，移動目標物に対する所在探索(whereabouts search) の最適政策を求めることは，有限個の発見確率最大化問題を解くことに帰することを示した．Washburn[10] は，各期まで発見できない時こうむる損失を導入して期待損失最小化問題を考え，FAB(forward and backward) アルゴリズムと呼ばれる近似解法を提案しているが，このモデルには(1) 発見確率最大化，(2) 所在探索，(3) 生存目標物の発見確率最大化などの問題が含まれている．Tierney and Kadane[9] は，(1) ある特定の場所で発見する確率の最大化，(2) 累積期待利得の最大化，(3)監視問題(surveillance problem：ランダムに出現する目標物の出現から発見までの期待時間の最小化) などを含む一般モデルを考察し，マルコフ戦略と呼ばれる政策が最適であるための必要十分条件を示し，近似解法を提案している．


　初期の研究で，具体的な移動目標物探索問題に初めて明解な解を与え，その後の研究に大きな刺激を与えたのがPollock[5] である．二つの小領域の間をマルコフ連鎖に従って移動している目標物に対し，期待探索回数最小化問題および有限回探索による発見率最大化問題を考察している．このPollock モデルを連続時間で考え，微分方程式モデルとして扱ったのがDobbie[2] である．


　移動目標物探索では，探索しないで目標物が発見し易い場所へ移動してくるのを「待つ」ことも意味がある．「待つ」費用が小さい時に，「待つ」ことの効果を示したのがNakai[4] である．


　未知パラメータ(たとえば目標物の初期位置や速度など) の値が決れば，目標物の移動経路が一意に確定するとき，この運動は条件付確定型(conditionary deterministic) であるというが，Stone and Richardson[7] は，このような場合の発見確率最大化問題を解いている．ところで探索空間，探索努力量が共に連続の場合には，最適努力配分は密度関数として求められるが，広く薄く引き延ばされた配分を，厳密に実行することは通常困難である．そこでLukka[3] は条件付確定型移動目標物探索において，探索者の政策として実際の探索経路(search path) を採用し，経路上に投入された探索努力の遠方にいる目標物の発見に与える影響を考慮して，発見確率最大化問題を解いている．以上のモデル以外にもさまざまな問題が考察されている．

参考文献

[1] S. S. Brown, “Optimal Search for a Moving Target in Discrete Time and Space,” Operations Reserch, 28 (1980), 1275-1289.

[2] J. M. Dobbie, “A Two-Cell Model of Search for a Moving Target,” Operations Research, 22 (1974), 79-92.

[3] M. Lukka, “On the Optimal Searching Tracks for a Moving Target,” SIAM Journal of Applied Mathematics, 32 (1977), 126-132.

[4] T. Nakai, “A Search Model for a Moving Target in Which the Decision Wait Is Permitted,” Mathematica Japonica, 25 (1980), 597-605.

[5] S. M. Pollock, “A Simple Model of Search for a Moving Target,” Operations Research, 18 (1970), 883-903.

[6] L. D. Stone and J. B. Kadane, “Optimal Whereabouts Search for a Moving Target,” Operations Research, 29 (1981), 1154-1166.

[7] L. D. Stone and H. R. Richardson, “Search for Target with Conditionally Deterministic Motion,” SIAM Journal of Applied Mathematics, 27 (1974), 239-255.

[8] W. S. Stromquist and L. D. Stone, “Constrained Optimization of Functionals with Search Theory Applications,” Mathematics of Operations Research, 6 (1981), 518-529.

[9] L. Tierney and J. B. Kadane, “Surveillance Search for a Moving Target,” Operations Research, 31 (1983), 720-738.

[10] A. R. Washburn, “Search for a Moving Target：The FAB Algorithm,” Operations Research, 31 (1983), 739-751.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E7%A7%BB%E5%8B%95%E7%9B%AE%E6%A8%99%E7%89%A9%E3%81%AE%E6%9C%80%E9%81%A9%E6%8E%A2%E7%B4%A2%E3%80%8B" より作成