Teoria przeszukiwania bayesowskiego

Teoria wyszukiwania bayesowskiego to zastosowanie statystyki bayesowskiej do poszukiwania zagubionych obiektów. Był kilkakrotnie używany do odnajdywania zaginionych statków morskich, na przykład USS Scorpion , i odegrał kluczową rolę w odzyskaniu rejestratorów lotu w katastrofie Air France Flight 447 w 2009 roku. Był również używany przy próbach zlokalizowania szczątki samolotu Malaysia Airlines Flight 370 .

Procedura

Zwykła procedura jest następująca:

Sformułuj jak najwięcej rozsądnych hipotez na temat tego, co mogło się stać z obiektem.
Dla każdej hipotezy skonstruuj funkcję gęstości prawdopodobieństwa dla lokalizacji obiektu.
Skonstruuj funkcję dającą prawdopodobieństwo znalezienia obiektu w lokalizacji X podczas wyszukiwania tam, jeśli rzeczywiście znajduje się on w lokalizacji X. W przypadku wyszukiwania oceanu jest to zwykle funkcja głębokości wody — w płytkiej wodzie szanse na znalezienie obiektu są duże, jeśli wyszukiwanie jest we właściwym miejscu. W głębokiej wodzie szanse są zmniejszone.
Połącz powyższe informacje w spójny sposób, aby stworzyć ogólną mapę gęstości prawdopodobieństwa. (Zwykle oznacza to po prostu pomnożenie dwóch funkcji razem). Daje to prawdopodobieństwo znalezienia obiektu, patrząc w miejscu X, dla wszystkich możliwych miejsc X. (Można to zwizualizować jako konturową mapę prawdopodobieństwa ) .
Skonstruuj ścieżkę wyszukiwania, która rozpoczyna się w punkcie o najwyższym prawdopodobieństwie i „przeszukuje” obszary o wysokim prawdopodobieństwie, następnie pośrednie prawdopodobieństwa, a na końcu obszary o niskim prawdopodobieństwie.
Sprawdzaj wszystkie prawdopodobieństwa w sposób ciągły podczas wyszukiwania. Na przykład, jeśli hipotezy dla lokalizacji X zakładają prawdopodobną dezintegrację obiektu, a poszukiwania w lokalizacji X nie przyniosły żadnych fragmentów, to prawdopodobieństwo, że obiekt znajduje się gdzieś w pobliżu, jest znacznie zmniejszone (choć zwykle nie do zera), podczas gdy prawdopodobieństwo jego przebywania w innych miejscach jest odpowiednio zwiększony. Proces rewizji odbywa się poprzez zastosowanie twierdzenia Bayesa .

Innymi słowy, najpierw szukaj tam, gdzie najprawdopodobniej zostanie znaleziony, następnie szukaj tam, gdzie znalezienie go jest mniej prawdopodobne, a następnie szukaj tam, gdzie prawdopodobieństwo jest jeszcze mniejsze (ale nadal możliwe ze względu na ograniczenia paliwa, zasięgu, prądów wodnych itp.), dopóki nie pozostanie niewystarczająca nadzieja na zlokalizowanie obiektu po akceptowalnych kosztach.

Zaletą metody bayesowskiej jest to, że wszystkie dostępne informacje są wykorzystywane spójnie (tj. w sposób „nieprzeciekający”), a metoda automatycznie generuje szacunki kosztów dla danego prawdopodobieństwa sukcesu. Oznacza to, że jeszcze przed rozpoczęciem wyszukiwania można hipotetycznie powiedzieć, że „istnieje 65% szans na znalezienie go w ciągu 5-dniowego wyszukiwania. Prawdopodobieństwo to wzrośnie do 90% po 10-dniowym wyszukiwaniu i 97% po 15 dni” lub podobne oświadczenie. W ten sposób opłacalność ekonomiczną poszukiwań można oszacować przed zaangażowaniem zasobów w poszukiwania.

Oprócz USS Scorpion , inne statki zlokalizowane według teorii wyszukiwania bayesowskiego to MV Derbyshire , największy brytyjski statek, jaki kiedykolwiek zaginął na morzu, oraz SS Central America . Okazał się również skuteczny w poszukiwaniu zaginionej bomby wodorowej po katastrofie Palomares B-52 w Hiszpanii w 1966 r. Oraz w odzyskaniu na Oceanie Atlantyckim rozbitego samolotu Air France Flight 447 .

Teoria wyszukiwania Bayesa jest włączona do oprogramowania do planowania misji CASP (Computer Assisted Search Program) używanego przez Straż Przybrzeżną Stanów Zjednoczonych do poszukiwań i ratownictwa . Program ten został później dostosowany do poszukiwań w głębi lądu poprzez dodanie współczynników terenu i pokrycia terenu do użytku przez Siły Powietrzne Stanów Zjednoczonych i Cywilny Patrol Lotniczy .

Matematyka

Załóżmy, że kwadrat siatki ma prawdopodobieństwo p , że zawiera wrak i że prawdopodobieństwo pomyślnego wykrycia wraku, jeśli tam jest, wynosi q . Jeśli kwadrat zostanie przeszukany i nie zostanie znaleziony żaden wrak, to zgodnie z twierdzeniem Bayesa skorygowane prawdopodobieństwo przebywania wraku na placu jest określone wzorem

{\ Displaystyle p' = {\ Frac {p (1-q)} {(1-p) + p (1-q)}} = p {\ Frac {1-q} {1-pq} <p .}

Dla każdego innego kwadratu siatki, jeśli jego wcześniejsze prawdopodobieństwo wynosi r , jego późniejsze prawdopodobieństwo jest określone przez

{\ displaystyle r' = r {\ frac {1} {1-pq}}> r.}

USS Skorpion

W maju 1968 roku atomowy okręt podwodny Marynarki Wojennej USA USS Scorpion (SSN-589) nie dotarł zgodnie z oczekiwaniami do jej macierzystego portu w Norfolk w Wirginii . Dowódcy Marynarki Wojennej Stanów Zjednoczonych byli prawie pewni, że statek zaginął u wybrzeży wschodniego wybrzeża , ale szeroko zakrojone poszukiwania nie przyniosły rezultatu w postaci szczątków Scorpiona .

Następnie ekspert Marynarki Wojennej, John P. Craven , zasugerował, że Scorpion zatonął gdzie indziej. Craven zorganizował poszukiwania na południowy zachód od Azorów w oparciu o kontrowersyjną przybliżoną triangulację hydrofonów . Przydzielono mu tylko jeden statek, Mizar , i zasięgnął porady Metron Inc., firmy konsultantów matematyków, aby zmaksymalizować swoje zasoby. Przyjęto metodologię wyszukiwania bayesowskiego. Przeprowadzono wywiady z doświadczonymi dowódcami łodzi podwodnych, aby postawić hipotezy dotyczące tego, co mogło spowodować utratę Scorpiona .

Obszar morski podzielono na kwadraty siatki i przypisano prawdopodobieństwo do każdego kwadratu, w ramach każdej z hipotez, aby uzyskać pewną liczbę siatek prawdopodobieństwa, po jednej dla każdej hipotezy. Zostały one następnie dodane razem, aby utworzyć ogólną siatkę prawdopodobieństwa. Prawdopodobieństwo związane z każdym kwadratem było wówczas prawdopodobieństwem, że wrak znajdował się w tym kwadracie. Skonstruowano drugą siatkę z prawdopodobieństwami reprezentującymi prawdopodobieństwo pomyślnego znalezienia wraku, gdyby ten kwadrat miał zostać przeszukany, a wrak rzeczywiście się tam znajdował. Była to znana funkcja głębokości wody. Wynikiem połączenia tej siatki z poprzednią siatką jest siatka, która daje prawdopodobieństwo znalezienia wraku w każdym kwadracie siatki morza w przypadku jego przeszukiwania.

Pod koniec października 1968 roku oceanograficzny statek badawczy Marynarki Wojennej Mizar zlokalizował sekcje kadłuba Scorpiona na dnie morskim, około 740 km (400 mil morskich; 460 mil) na południowy zachód od Azorów , poniżej ponad 3000 m (9800 stóp) Z wody. Było to po tym, jak Marynarka Wojenna wydała taśmy dźwiękowe z podwodnego systemu nasłuchowego „ SOSUS ”, które zawierały odgłosy zniszczenia Scorpiona . Sąd śledczy został następnie zwołany ponownie i inne statki, w tym batyskaf Trieste II , zostały wysłane na miejsce zdarzenia, zbierając wiele zdjęć i innych danych.

Chociaż Craven otrzymał duże uznanie za zlokalizowanie wraku Scorpiona , Gordon Hamilton, ekspert od akustyki, który był pionierem w wykorzystaniu hydroakustyki do określania miejsc rozpryskiwania się pocisków Polaris, odegrał kluczową rolę w zdefiniowaniu kompaktowego „pola wyszukiwania”, w którym ostatecznie znaleziono wrak. Hamilton założył stację nasłuchową na Wyspach Kanaryjskich, która uzyskała wyraźny sygnał tego, co niektórzy naukowcy uważają za hałas implodacji kadłuba ciśnieniowego statku, gdy pokonywał głębokość zmiażdżenia . Naukowiec z Laboratorium Badawczego Marynarki Wojennej , Chester „Buck” Buchanan, używając holowanej sanki z kamerą własnego projektu na pokładzie Mizara , w końcu zlokalizował Scorpiona . Holowany wózek z kamerą, który został wyprodukowany przez JL „Jac” Hamm z Naval Research Laboratory's Engineering Services Division, znajduje się w Muzeum Narodowym Marynarki Wojennej Stanów Zjednoczonych . Buchanan zlokalizował wrak kadłuba Threshera w 1964 roku przy użyciu tej techniki.

Optymalny rozkład wysiłku związanego z wyszukiwaniem

Klasyczna książka na ten temat The Theory of Optimal Search ( Operations Research Society of America , 1975) autorstwa Lawrence'a D. Stone'a z Metron Inc. zdobyła w 1975 roku nagrodę Lanchester przyznawaną przez American Operations Research Society.

Wyszukiwanie w skrzynkach

Załóżmy, że nieruchomy przedmiot jest ukryty w jednym z n pudełek (lokalizacji). Dla każdej lokalizacji $trzy$ znane parametry: koszt $znalezienia$ wyszukiwania, prawdopodobieństwo $\ displaystyle a_ {i}$ przez a ja $,$ jeśli obiekt tam jest, i prawdopodobieństwo, tam jest. Poszukiwacz szuka przedmiotu. Znają prawdopodobieństwa a priori na początku i aktualizują je zgodnie z prawem Bayesa po każdej (nieudanej) próbie. Problem znalezienia obiektu przy minimalnym oczekiwanym koszcie jest klasycznym problemem rozwiązanym przez Davida Blackwella . Co zaskakujące, optymalna polityka jest łatwa do opisania: na każdym etapie patrz na lokalizację, która maksymalizuje $}}$ } W rzeczywistości jest to szczególny przypadek indeksu Gittinsa .

Zobacz też

Wnioskowanie bayesowskie – Metoda wnioskowania statystycznego
Gra w wyszukiwanie – gra dwuosobowa o sumie zerowej

Stone, Lawrence D., The Theory of Optimal Search , opublikowane przez Operations Research Society of America , 1975
Stone, Lawrence D., In Search of Air France Flight 447. Institute of Operations Research and the Management Sciences, 2011. https://www.informs.org/ORMS-Today/Public-Articles/August-Volume-38-Number -4/W-poszukiwaniu-lotu-francji-447
Iida, Koji., Studia nad optymalnym planem wyszukiwania , tom. 70, Notatki do wykładów ze statystyki, Springer-Verlag, 1992.
De Groot, Morris H., Optymalne decyzje statystyczne , Wiley Classics Library, 2004.
Richardson, Henry R.; and Stone, Lawrence D. Operations Analysis podczas podwodnych poszukiwań Scorpiona . Naval Research Logistics Quarterly , czerwiec 1971, tom. 18, Numer 2. Biuro Badań Marynarki Wojennej.
Stone, Lawrence D. Poszukiwanie Ameryki Środkowej SS : matematyczne poszukiwanie skarbów. Raport techniczny, Metron Inc. Reston, Wirginia.
Koopman, BO Search and Screening , Operations Research Evaluation Group Report 56, Center for Naval Analyses, Alexandria, Virginia. 1946.
Richardson, Henry R.; and Discenza, JH Wspomagany komputerowo system planowania poszukiwań (CASP) Straży Przybrzeżnej Stanów Zjednoczonych. Kwartalnik Logistyki Badań Marynarki Wojennej . Tom. 27 nr 4. s. 659–680. 1980.
Ross, Sheldon M., Wprowadzenie do stochastycznego programowania dynamicznego , Academic Press. 1983.