われがわログ

最適化アルゴリズムとかプログラミングについて書きたい

捜索理論勉強メモ

Optimization

完全に自分の勉強メモ。 静止目標に対する捜索活動の最適化についてまとめた。 参考書は下記の2つ。

コロナ社から出ている本の方が入門向けだが、省かれている部分もある。ただ、不完全定距離センサーの横探知確率や、同センサーの区域捜索に関する議論はコロナ社の方が詳しかった。

捜索理論における確率モデル (シリーズ 情報科学における確率モデル 3)

捜索理論における確率モデル (シリーズ 情報科学における確率モデル 3)

全般的にはこっち↓の方が詳しい。両方参照しつつ読み進めると理解の助けになる。

捜索理論 3訂版―捜索オペレーションの数理

捜索理論 3訂版―捜索オペレーションの数理

捜索センサのモデリング

瞬間的な探知能力のモデリング

不完全定距離発見法則

一定距離 R_{0} \in \mathbb{R}^{+}以下では一定確率で探知できるというモデリング。

g(r(t)) =\begin{cases} g_0, & \text{for} \quad r(t) \leq R_0 \\ 0, & \text{otherwise} \end{cases} \\ b(r(t)) = \begin{cases} b_0, & \text{for} \quad r(t) \leq R_0\\ 0, & \text{otherwise} \end{cases}
  • g: \mathbb{R} → \mathbb{R}_0^+は、離散スキャンセンサ（アクティブソナー等）の1回の「べっ見」に対する目標探知確率（べっ見探知確率）
  • b: \mathbb{R} → \mathbb{R}_0^+は、連続スキャンセンサ（目視・パッシブソナー等）の単位時間当たりの目標探知確率
  • r(t) \in \mathbb{R}_0^+はセンサからの距離

なお、 b(r(t))=\inftyのとき、微小時間\Delta tに対してb(r) \Delta t = 1となって探知確率が1となる

逆三乗発見法則

単位時間当たりの目標探知率b: \mathbb{R}\rightarrow \mathbb{R}_{0}^{+} が、 センサからの距離r(t) \in \mathbb{\text{R}}^{+} の三乗に反比例するという連続スキャンセンサ向けのモデリングであり、広く用いられている。

b\left( {r\left( t \right)} \right) = \left( \frac{k}{r\left( t \right)} \right)^{3}
  • k \in \mathbb{R}^+は定数

目視による海上の捜索では立体角をもとに

b(r(t)) = \frac{\alpha A' h}{( {r^{2}( t ) + h^{2}} )^{\frac{3}{2}}} \approx \frac{\alpha A'h}{r^{3}\left( t \right)} = \left( \frac{k}{r( t )} \right)^{3}

とモデリングされる。最後の式変形では k^ 3 = \alpha A'h とおいた。

  • \alpha \in \mathbb{R}^+は定数
  • A'は物体の面積（XY平面への射影面積）
  • hは飛行高度 ( h \ll r(t)を仮定)

目標の相対移動に対する探知能力のモデリング

以下では、センサを直交座標系の原点に固定し、目標が相対運動している場合を考える。 センサと目標との相対距離が時間の関数 r: \mathbb{R}_ 0 ^ + \to \mathbb{R} _ 0 ^ +で変化する場合には、探知確率 p(t) \in [0,1]は

p(t) = 1 - \exp\left( {- F\left( r \right)} \right)

である。ここで、探知ポテンシャルF(r) \in \mathbb{R} _ 0 ^ + は次のように与えられる。

F(r) = \begin{cases} \sum_{i=1}^n \{ -\log (1-g(r(t_i))) \} & \text{離散スキャンセンサの場合}\\ \int_0^t b(r(\tau)) d\tau & \text{連続スキャンセンサの場合} \end{cases}
  • t_{i}( {i = 1,2, \cdots,n})はべっ見を行う時刻

無限直線状を等速運動する目標で、センサとの最接近距離が xの目標の探知確率は横距離探知確率PL(x) \in [0,1]と呼ばれている。ただし、べっ見探知確率や横距離探知確率はセンサの探知能力の指標としては複雑であり、 実務では、次式で定義される有効探索幅 W \in \mathbb{\text{R}} ^ {+}が用いられている。

W = \int _ {-\infty} ^ {\infty} PL ( x) dx

この式は、横距離探知確率 PL\left( x \right)を持つセンサを、幅 W内で目標に行き会えば確率1で目標を探知し、その外では決して探知しないとする完全定距離センサに近似していることを表している。

不完全定距離センサ

\begin{aligned} PL(x) &= \begin{cases} 1-\exp \left(-\dfrac{b_0 \sqrt{R _ 0^2-x^2}}{u}\right) & \text{for} \quad |x| \leq R_0\\ 0 & \text{otherwise} \end{cases} \\ W &= 2R _ 0 \left[ 1 - \int _ 0 ^1 \exp (-2Z \sqrt{1- y ^ 2 })dy \right] \end{aligned}

ここで

Z = \begin{cases} -\dfrac{R_0 \log (1-g_0)}{ut_0} & \text{離散スキャンセンサの場合} \\ \dfrac{b_0R_0}{u} & \text{連続スキャンセンサの場合} \end{cases}

であり、uは相対速度の絶対値である。

逆三乗センサ

\begin{aligned} PL(x) &= 1- \exp \left(- \dfrac{2k^3}{ux^2}\right)\\ W&= 2 \sqrt{\dfrac{2\pi k^3}{u}} \end{aligned}

なお、 有効捜索幅 Wの経験的な値（商船の見張りから見た有効捜索幅など）は、国際航空海上捜索救難マニュアルに掲載されている。

平行捜索の探知確率

面積Aの地域を、掃引幅Sの平行経路で捜索するときの探知確率 P\left( S \right)を求める。 Sは捜索時間 T \in \mathbb{R}で面積Aを捜索し終わるように設定されるので、 S = \frac{A}{uT}の関係がある。

不完全定距離センサ

まず、 p _ 0 = PL (0)とおき、 2ip_0S \leq W \lt (2i+1) p _ 0 あるいは、 (2i+1)p_0S \leq W \lt (2i+1) p_0S を満たす i \in \mathbb{\text{N}}_{0}（一つしか存在しない）を求める。 この iを用いて、探知確率 P\left( S \right)は次のように書ける。

P(S) = \begin{cases} 1-(1-p_0)^{2i}\left\{ 1+p_0 \left(2i- \dfrac{W}{p_0S}\right) \right\} & 2ip_0S \leq W < (2i+1) p_0\\ 1-(1-p_0)^{2i+1}\left\{ 1+p_0 \left(2i+1- \dfrac{W}{p_0S} \right) \right\} & (2i+1)p_0S \leq W < (2i+1) p_0S \end{cases}

逆三乗センサ

P(s) \approx \sqrt{1 - \exp \left\{ - \left( \frac{W}{S} \right)^{2} \right\}}

最適化問題としての定式化

「捜索資源（捜索努力）」の配分問題を解き、最適な捜索計画を求める。 ただし、捜索者の運動の連続性や捜索経路は考慮しづらいため、ここでは考慮しない。

目標探知確率を最大にする最適努力配分

仮定

  1. 目標空間は Q個の離散地域（セル）から成り、セルのインデックス集合を \mathcal{Q}とおく。
  2. 捜索計画全体（捜索資源の配分）は \Phi = [\phi_1, \phi_2, \cdots \phi _ Q ] ^T \in \mathbb{R} _ 0^{+Q}なる連続量で表される。
  3. 1つの静止目標が Q個の地域のいずれかに存在し、各地域の目標存在確率 p_{i} \in \left\lbrack {0,1} \right\rbrack\left( {i \in \mathcal{\text{Q}}} \right)は捜索者が推定可能である。
  4. 捜索者が使用できる総捜索コストは C \in \mathbb{R}（例えば、捜索に要する金額や、捜索者の被るリスク）であり、また、 Cを目標地域へ分配する場合、任意の大きさに分割可能である。
  5. 捜索資源を1単位だけ地点 iに投入したときのコストは c _ i \in \mathbb{R} _ 0 ^ + である。
  6. 地域 iに目標が存在し、その地域に資源 \phi _ i \in \mathbb{R} _ 0 ^ + が投入された場合、目標の発見確率は関数 f _ i ( \phi _ i )で表され、次の性質を持つ。 f _ i(0) = 0, \quad f(\infty)\leq 1, \quad 0 \lt f'(\psi _ i) \lt \infty, \quad f''(\psi_i) \lt 0。 例えば、逆三乗センサを用いて平行捜索する場合の f _ i ( \phi _ i )は f _ i ( \phi _ i ) = \sqrt{1 - \exp \left\{ - \left( \frac{W \phi _ i}{S} \right)^{2} \right\}} である（これだと f(0)で微分不可なので、理論的には好まれない？）。また、ランダム捜索する場合（センサの種別は問わず）は f _ i \left( {\phi_{i}} \right) = 1 - \exp\left( - \frac{W \phi _ i}{S} \right) である。
  7. 捜索者は総捜索コスト Cの制約下で、目標探知確率を最大とする捜索を計画する。

以上の前提の下、最適捜索のための資源配分問題は次の通り定式化される。

\min_{\Phi} \quad \sum_{i \in \mathcal{Q}} p _ i f _ i (\phi _ i) \quad \text{subject to} \quad \sum_{i \in \mathcal{Q}} c _ i \phi _ i \leq C, \quad \phi _ i \geq 0 \quad \text{for all} \quad i \in \mathcal{Q}