探索理論
【英】：search theory
概要
探索理論は探索者が目標物の効率的な発見を目指す探知探索の理論研究である. このために探索理論では, 目標特性, センサー特性, 探索の場の特性に関する関連科学の知識に基づき探索オペレーションを定式化し, 探索効率の評価モデルを構築して探索要因の効果を解明する. さらに探索効率を最大にする最適条件を求める. 探索理論は,(1)目標分布推定, (2)センサー探知能力の定式化, (3)探索プロセスの特性分析, (4)探索計画の最適化, 等の研究に大別される.
詳説
探索理論 (search theory) は, 探索者 (searcher) が目標物 (target) を効率的に発見するための探索法を明らかにする理論である. 探索という言葉は,「嫁探し」や「プログラムのバグ探し」のように, 曖昧な対象物の探索にも用いられるが, 探索理論では探索の対象は明確に定義された目標物がある場合を扱う. また探索者は目標物を他のものと区別して,「これが目標物である」と確認する手段:センサー (sensor) をもつ. 広義の探索理論は,関数の極値探索の線形探索,グループ検査の2分法探索,探索と目標位置推定からなる所在局限探索,目標状態の観察を目的とする監視,目標分布のあいまいさの減少を図る情報量探索,データ検索法等の研究を含むが, 狭義の探索理論は,通常,探索者による目標物の探知 (detection) を目的とする探知探索 (detection search) に関する理論を指す.
探索理論が「発見の科学」として体系化されたのは, 第2次大戦中の米海軍ASWORG (Antisubmarine Warfare Operations Research Group)による U-boat 探索の作戦研究に始まる.この研究は1946年, Koopman [1] によって書物にまとめられ, またその後の研究の進展をふまえて1980年には改訂版が出版された. この書物はセンサーの探知論 (レーダー,ソナー,目視), 目標物と探索者の遭遇の運動学と探索パターンの評価モデル, 探索努力の最適配分等の理論を詳述したものであり, この書物によって探索理論は体系化され, ＯＲの理論研究分野として認知された. この書物は米海軍の秘密文書であったが, Koopman はその概要を3回に分けて学会誌に発表した [2]. 大戦後のＯＲの爆発的な発展の中では探索理論は, 漸次マイナーな研究分野に衰退するが, それは探索理論の研究が, やや対潜水艦戦の軍事応用に偏り, また問題中心的で中核的な理論モデルがなかったためであると言われる. しかし継続的な努力により, その後の研究は多岐にわたり, 知識の体系は着実に成長してきた. 1970年代以後, 情報化時代を迎えて探索理論は応用面でも新しい進展をみせた. 電子計算機の発達に伴い, 探索理論は意思決定支援システムの情報処理や情勢判断, 探索計画の策定等を支援する理論として, 急速に応用範囲を拡大した. 即ち目標物の情報処理の一環として, 目標存在分布の推定や探索の進行にともなう事後目標分布の計算, 情報に対応した探索計画の評価等のシステムが実用化された.
探索の効率化のための探索理論の結論をひとことで言えば,「目標物を効率的に発見するには, 目標物の見つかりそうな所をうまく探せ.」という常識的な一語に尽きる. しかしそのためには目標物の特性(目標存在分布,行動特性,信号特性等), センサーの特性(信号処理法,探知能力,環境の影響,虚探知の可能性等), 探索の特性(探索の目的,効率性の尺度,探索資源の内容と運用上の制約等)及び探索オペレーションの評価法と最適な探索計画の構成法等の知識が必要である. ゆえに探索問題の研究には, 各種のセンサー工学, 環境の物理学, 信号処理の理論, 眼の生理学, 探知認識の人間工学, 目標行動及び探索の目的と行動全体の知識, 探索システムの運用特性, ＯＲの最適化手法等々の専門分野の学際的なアプローチが必要である. ここでの探索理論の役割は,関連諸科学による目標特性,センサー特性,探索の特性の知識にもとづき,探索オペレーションを定式化して探索の効率を定量的に評価する理論モデルを構築し, 探索要因の効果を解明することである. 更にその要因のいくつかを制御して, 探索効率を最大にするシステム要因や探索システムの運用法の最適な条件を求めることである. そのための探索理論の研究は次の4つのテーマに大別される. 即ち(1) 目標分布の推定問題, (2) 探索センサーの探索能力の定量化問題, (3) 探索プロセスの特性分析の理論モデル, (4) 探索計画の最適化問題, の研究である.
探索はそれ自体で完結する行動ではなく, 目標発見後の主行動が目的であり, 探索はその情報収集活動として位置付けられる. ゆえに「何のために,いかなる方法で,どんな精度で探すか」は探索システムに対する外的条件として与えられるとみるのが探索理論の立場である. そこから探索効率の尺度と探索行動の枠組みが設定される. また通常, 探索を動機づける粗い目標情報が事前に存在し, その精密化のために探索が行われるが, 効率的探索にはその粗い目標情報の活用が重要である. 事前の目標情報をいかに評価し探索計画に反映させるかを分析するのが, 探索理論の第1のテーマ:目標存在分布の推定問題である.
一方, 探索の成否は第一義的にセンサー能力に左右されるので, 探索計画の立案にはセンサーの探知能力の把握が重要となる. これが探索理論の第2のテーマ:センサー探知能力の定量化問題である. 上述の2つの知識にもとづいて,効率的な探索法の理論的な分析が始められる.
探索理論の第3のテーマは, 探索要因と探索効率の関係を解明する探索プロセスの特性分析問題である. この研究のねらいは探索の細部の条件(目標存在分布,移動法則,センサー能力,環境特性,探索手順等)が与えられたとき, 探索の評価モデルを定式化し探索プロセスの特性を定量的に評価する手段を確立することである. それは探索のミクロ・モデルの研究ということができる.
探索理論の第4のテーマは,「探索すべきか否か, どこをどれだけ探すか, どのような順序で探すか, いつまで探すか,」といった探索の全般計画の最適性に関するマクロ・モデルの研究である. 特に探索者の一方的な探索問題を探索努力の最適配分問題と言い, 上述の探索計画の諸元に関する最適性の条件を導出し, 最適な探索計画の設計指針を明らかにする. この種の研究は, 静止目標問題, 移動目標問題, 虚探知のある探索問題, 寿命のある(死亡型,消滅型)目標問題, 先制探知問題, 探索経路制約問題, 探索停止問題等があり, 数理計画問題や変分法問題に定式化され最適解が求められる. 一方, 探索者が探し, 目標物が隠れたり逃げたり, 場合によっては見つかるように行動したりといった双方的な意思決定のある探索としては, 探索ゲームと呼ばれる研究分野において, 潜伏探索ゲーム, 逃避探索ゲーム, 待ち伏せゲーム等が研究されている. また, 友好的な複数の探索者を扱うランデブー探索と呼ばれる問題の研究も近年盛んである.
さて, 探索理論を概観する以下の章では, 上述した第1のテーマから第3のテーマを解説し, さらに近年の研究成果の蓄積が著しい第4のテーマとして静止目標物及び移動目標物に対する最適探索, 探索ゲーム及びランデブー探索を取り上げ, 最後に探索理論の現実の応用例を紹介する.
[1] B. O. Koopman, Search and Screening, OEG Report No.56, 1946. 2nd ed., Pergamon Press, 1980.
[2] B. O. Koopman, "The Theory of Search I," Operations Research, 4 (1956), 324-346. "The Theory of Search II," 4 (1956), 503-536. "The Theory of Search III," 5 (1957), 613-626.
- たんさくりろんのページへのリンク
