탐색 이론은 움직이는 표적 뿐만 아니라 정지해 있는 표적을 찾으려 할 때도 요긴하게 활용되는 분야 입니다. 이번 글에서 Central America 선박 탐지 사례른 살펴보고 탐색 이론에서 그 유형은 어떻게 분류되는지 설명드리도록 하겠습니다.
탐색 이론을 바탕으로 침몰한 Central America를 찾아내다.
Central America는 1857년 9월 12일 캘리포니아에서 뉴욕으로 이동 중 허리케인에 의해 침몰한 선박입니다. 이 사고로 425명이 숨지고 많은 금화가 함께 소실되었다고 합니다. 1985년에 이르러 이 선박을 찾아내기 위한 작업이 시작되는데, 선박 침몰 위치가 정확하지 않아 후보지역을 대상으로 광범위한 탐색 경로 설정을 계획하게 됩니다.
Stone이 광범위한 해양에 대한 탐지 확률 지도를 그리게 되고 이를 근거로 탐색을 시작, 결국 해당 선박을 찾아내게 됩니다. 탐색 이론의 태동은 유보트에 효과적으로 대응하기 위한 것이었지만, 이후 다양한 분야에서 활용되며 그 진가를 증명해 내고 있는 것입니다.
물론 최근 기술이 발전에 발전을 거듭해서 SONAR(음파탐지기)를 이용하면 해저의 모습을 영상으로 전시해 주기도 하는 모습이라 침몰 선박을 찾아내는 것이 더 용이해졌을지도 모릅니다. 탐색 이론에서 표적의 유형을 구분할 때 정지 표적과 이동 표적으로 구분하는데, 정지 표적을 효율적으로 탐색하기 위해 탐색 경로를 설정하는 것과 음파탐지기를 효율적으로 운영하는 것 사이에서 어떤 것을 선택하는 것이 유리한 것인지 의문이 생기기도 합니다.
물론, 두 가지 모두를 조화롭게 활용하는 것이 가장 큰 이득을 줄 것이라는 데 의심할 여지는 없습니다.
탐색 이론의 구분 - 환경과 표적, 목표에 따라 다양하게 분류
탐색 이론에서 연구의 방법(유형)은 환경, 표적, 목적에 따라 분류됩니다. 환경에서는 모델의 공간과 시간을 연속형으로 볼 것인지 이산형으로 볼 것인지를 먼저 구분합니다. 예를 들어 탐색이 일어나는 공간을 격자로 나누고 1틱(TIck)의 시간이 지나면 하나의 격자를 이동하는 것으로 설계하면 이산형이며, 그러한 구분 없이 속도, 시간에 따라 이동 거리를 실시간으로 구현하면 연속형이 됩니다.
환경의 구분에서 탐색자가 하나인지 복수인지에 따라서도 구분할 수 있습니다. 일반적으로 탐색자가 2개체 이상이면 계산 복잡도는 증가하게 됩니다.
표적의 형태에 따라서도 구분이 되는데 정지되어 있는 표적과 이동하는 표적, 탐색자의 탐색 경로의 영향을 받지 않을 경우(One-sided)와 영향을 받을 경우(Search game)로 나뉩니다.
일반적으로 탐색 경로를 계획할 때 탐지 확률을 최대치로 갖는 경로를 선택할 것인지 소요 시간을 최소화하는 경로를 선택할 것인지 두 가지 목적 중 하나를 선택하여 모델을 구상합니다. 저는 확률을 기반으로 공부를 해 왔기 때문에 탐지 확률을 최대로 갖는 경로를 선택하는 문제를 연구했습니다.
탐색 이론에서 위의 유형에 따른 연구들이 지속되어 왔고 멋진 결과들도 있습니다. 하지만, 제가 느끼기에 아직도 풀어나가야 할 숙제가 많다는 것을 느끼게 됩니다. 탐지 확률을 최대로 하는 경로를 설정하여 실제로 탐색을 하더라도 표적이 그 경로 상에 없을 수 있다는 불확실성, 탐지하지 못하고 지나칠 불확실성 등 불확실성이 존재하기 때문입니다.
그럼에도 탐지 확률을 최대로 하는 경로를 선택하는 것이 가장 유리하다는 결론을 얻기 위한 과정이 필요한 것 같습니다. AI의 발전과 함께 시뮬레이션이라는 강력한 도구가 있기 때문에 충분히 연구해 볼 만한 가치 있는 분야라고 생각합니다.