배경

1968년에 미국 해군의 잠수함 스코피온호이 소식을 거쳤습니다. 이때의 수색에 사용된 것이 베이즈 추정을 이용한 베이즈 수색(Bayesian Search)입니다. 비행기나 그 블랙박스 등의 수색에도 사용됩니다.

변수 정의

먼저 수색 영역을 셀로 정의합니다. 여기에서는 간이적으로 20x20의 에리어로 합니다. 이것에 항로나 최종 보고된 위치 등의 정보로부터, 그 셀마다의 추량의 발견 확률을, 사전 확률로서 이하와 같이 확립 분포로 표현합니다. 제 경우에는 정규 분포로 표현했습니다. 빨간색 X는 실종된 수색 대상입니다.



이제 다음과 같이 변수를 정의합니다.


변수 이름
의미


$i$
셀의 인덱스. 위에서 나타낸 수색 대상의 경우 $i=(16,10)$로 표현한다.

$Y_i$
i에 수색 대상이 있는지 여부의 진정한 가치. 있는 경우 1. 없는 경우 0.

$\pi_i$
위의 추측의 사전 확률. $P_r(Y_i=1)$

$Z_i$
i를 수색한 결론. 발견되면 1. 없는 경우 0. Yi=1인 경우에 발견되지 않았던 경우도 0.

$p_i$
i에 수색 대상이 있었을 경우의 발견 확률. $P_r(Z_i=1|Y_i=1)$. 이 예에서는 어느 셀도 일률적으로 0.1로 한다. 실제로는 해저까지의 깊이 등으로 셀마다 변경된다.


$p_i$를 정의하고 있는 바와 같이, 이 추정의 포인트는 거기에 수색 대상이 있었다고 해도, 수색반의 능력 부족등에 의해 발견되지 않는 경우를 고려하고 있는 것입니다.　　
자, 실제 수색으로 넘어갑시다.

검색 알고리즘

$\pi_i$가 최대가 되는 인덱스 $i$가 나타내는 셀을 수색 셀로 한다.

셀 $i$에서 검색 대상이 발견되면 종료. 찾을 수 없으면 다음과 같이 $\pi$를 업데이트하세요.
$\pi_i\leftarrow\frac{(1-p_i)\pi_i}{1-p_i\pi_i} $
i 이외의 셀 j의 경우 :
$\pi_j\leftarrow\frac{\pi_j}{1-p_i\pi_i}$

내 구현의 경우, $\pi$가 점점 포화되어 파탄했기 때문에, 셀 전체를 합계해 1.0이 되도록 정규화했습니다.

1부터 반복.

사전 확률 갱신의 모습

1000 스텝을 5 스텝 날림으로 그립니다. 파란 점이 그 단계에서 검색 대상으로 한 셀입니다. 빨간색 X를 검색해도 처리를 마치지 않은 이유는 $p_i$가 0.1이기 때문입니다. 10회에 1회에 수색 성공의 판정이 됩니다.


발견되었는지 여부는별로 중요하지 않으므로 끝까지 표시하지 않습니다. 시간이 있을 때 전체 탐색과의 퍼포먼스 비교를 해 봅니다.

고찰

인간이
　「대체 여기 편에 있을 것」
라고 하는 추측 정보를 사용해, 그 근처에서 어딘지 모르게 순서대로 수색하는 경우도,
"저기, 이상하구나. 이렇게 추측에서 벗어나 있는 장소에 있는 것은 없어.
또 그 근처에서 찾을까」
라고 하는 상태에, 에리어를 전수색하는 것이 아니라, 어느 정도 수색 끝나면 또 예측 지점으로부터 수색을 스타트한다고 하는 움직임이 된다고 생각합니다.
그래서 위의 GIF 이미지에서,
베이즈 수색은 그것을 더 낭비 없이 합리적으로 하는 방법이라고 생각했습니다.

위의 GIF 결과를 보면, 수색점이 셀의 위치적으로 아치라 코치라를 접하고 있으므로, 실제로 수색하는 경우는
　셀내의 검색시간 >> 셀간의 이동시간
그렇지 않으면 발견까지의 시간이 낭비로 길어지네요.

코드

아래로 올렸습니다.

참고문헌