Bayesovská teorie vyhledávání - Bayesian search theory

Bayesian theory theory is the application of Bayesian statistics to the search for lost objects. Bylo několikrát použito k nalezení ztracených námořních plavidel, například USS Scorpion , a hrálo klíčovou roli při obnově letových zapisovačů po katastrofě Air France Flight 447 z roku 2009. Bylo také použito při pokusech o najděte pozůstatky letu 370 společnosti Malaysia Airlines .

Postup

Obvyklý postup je následující:

  1. Formulujte co nejvíce rozumných hypotéz o tom, co se s objektem mohlo stát.
  2. Pro každou hypotézu vytvořte funkci hustoty pravděpodobnosti pro umístění objektu.
  3. Vytvořte funkci, která dá pravděpodobnost skutečného nalezení objektu v místě X, když tam budete hledat, pokud se skutečně nachází v místě X. Při hledání oceánu je to obvykle funkce hloubky vody - v mělké vodě je šance na nalezení objektu dobrá, pokud hledání je na správném místě. V hluboké vodě jsou šance sníženy.
  4. Kombinujte výše uvedené informace souvisle a vytvořte celkovou mapu hustoty pravděpodobnosti. (Obvykle to jednoduše znamená znásobení obou funkcí dohromady.) To dává pravděpodobnost nalezení objektu pohledem na místo X pro všechna možná místa X. (To lze vizualizovat jako obrysovou mapu pravděpodobnosti.)
  5. Vytvořte vyhledávací cestu, která začíná v bodě s nejvyšší pravděpodobností a „skenuje“ oblasti s vysokou pravděpodobností, pak střední pravděpodobnosti a nakonec oblasti s nízkou pravděpodobností.
  6. Průběžně během hledání revidujte všechny pravděpodobnosti. Například pokud hypotézy pro umístění X naznačují pravděpodobný rozpad objektu a hledání v místě X nepřineslo žádné fragmenty, pak je pravděpodobnost, že je objekt někde kolem, výrazně snížena (i když ne obvykle na nulu), zatímco pravděpodobnosti jeho bytí na jiných místech je odpovídajícím způsobem zvýšeno. Proces revize se provádí použitím Bayesovy věty .

Jinými slovy, nejprve prohledejte, kde bude s největší pravděpodobností nalezeno, potom prohledávejte, kde je méně pravděpodobné, pak prohledávejte, kde je pravděpodobnost ještě menší (ale stále možná kvůli omezením paliva, dojezdu, vodních proudů atd.), dokud nezůstane nedostatečná naděje na nalezení objektu za přijatelnou cenu.

Výhodou Bayesovské metody je, že všechny dostupné informace jsou používány koherentně (tj. Způsobem „nepropustným“) a metoda automaticky vytváří odhady nákladů pro danou pravděpodobnost úspěchu. To znamená, že ještě před začátkem vyhledávání lze hypoteticky říci: „Existuje 65% šance, že ji najdete při 5denním vyhledávání. Pravděpodobnost vzroste na 90% po 10denním vyhledávání a 97% po 15 dní “nebo podobné prohlášení. Ekonomickou životaschopnost vyhledávání lze tedy odhadnout před přidělením zdrojů k vyhledávání.

Kromě USS Scorpion patří mezi další plavidla umístěná podle Bayesovské teorie hledání i MV  Derbyshire , největší britské plavidlo, jaké kdy na moři přišlo, a SS  Střední Amerika . Osvědčilo se také při hledání ztracené vodíkové bomby po havárii Palomares B-52 ve Španělsku z roku 1966 a zotavení havarovaného letu Air France 447 v Atlantském oceánu .

Bayesovská teorie hledání je začleněna do softwaru pro plánování misí CASP (Computer Assisted Search Program), který používá Pobřežní stráž Spojených států k pátrání a záchraně . Tento program byl později upraven pro vyhledávání ve vnitrozemí přidáním faktorů terénu a pokrytí půdy pro použití letectvem Spojených států a civilní leteckou hlídkou .

Matematika

Předpokládejme, čtverce mřížky má pravděpodobnost p , že obsahují vrak a že pravděpodobnost úspěšné detekci vrak, je-li tam je q . Pokud je prohledáno náměstí a není nalezen žádný vrak, pak je podle Bayesovy věty revidovaná pravděpodobnost vraku na náměstí dána vztahem

Pro každý druhý čtverec mřížky, pokud je jeho předchozí pravděpodobnost r , je jeho zadní pravděpodobnost dána vztahem

USS Scorpion

V květnu 1968 se americké námořnictvo je jaderné ponorky USS Scorpion (SSN-589) se nepodařilo dospět podle očekávání u svého domovského přístavu v Norfolku ve Virginii . Velitelé amerického námořnictva si byli téměř jisti, že loď byla ztracena na východním pobřeží , ale při rozsáhlém průzkumu se nepodařilo objevit pozůstatky Štíra .

Poté odborník na hlubinné námořnictvo John P. Craven navrhl, že Scorpion potopil jinde. Craven uspořádal pátrání jihozápadně od Azor na základě kontroverzní přibližné triangulace pomocí hydrofonů . Byla mu přidělena pouze jedna loď, Mizar , a poradil si s firmou poradenských matematiků, aby maximalizoval své zdroje. Byla přijata Bayesovská metodika vyhledávání. Zkušení velitelé ponorek byli dotazováni, aby vytvořili hypotézy o tom, co mohlo způsobit ztrátu Scorpiona .

Mořská oblast byla rozdělena na čtverce mřížky a každému čtverci byla přidělena pravděpodobnost pod každou z hypotéz, aby byla získána řada pravděpodobnostních mřížek, jedna pro každou hypotézu. Ty pak byly sečteny, aby se vytvořila celková pravděpodobnostní mřížka. Pravděpodobnost spojená s každým čtvercem byla pak pravděpodobnost, že vrak byl na tomto čtverci. Byla vytvořena druhá mřížka s pravděpodobnostmi, které představovaly pravděpodobnost úspěšného nalezení vraku, pokud by měl být prohledán ten čtverec a vrak tam skutečně měl být. Toto byla známá funkce hloubky vody. Výsledkem kombinace této mřížky s předchozí mřížkou je mřížka, která dává pravděpodobnost nalezení vraku v každém čtverci mřížky moře, pokud by měla být prohledána.

Na konci října 1968 našla oceánografická výzkumná loď námořnictva Mizar části mořského dna trupu Scorpionu , asi 740 km jihozápadně od Azor , pod více než 3000 m (9 800 ft) z vody. To bylo poté, co námořnictvo uvolnilo zvukové pásky ze svého podmořského poslechového systému „ SOSUS “, který obsahoval zvuky zničení Scorpiona . Vyšetřovací soud byl následně znovu svolán a na místo byla vyslána další plavidla, včetně batyskafu Trieste II , která sbírala mnoho obrázků a dalších údajů.

Ačkoli Craven získal velkou zásluhu na lokalizaci trosek Scorpiona , Gordon Hamilton, odborník na akustiku, který propagoval použití hydroakustiky k určení umístění stříkání raket Polaris, pomohl definovat kompaktní „vyhledávací pole“, kde byl vrak nakonec nalezen. Hamilton zřídil poslechovou stanici na Kanárských ostrovech, která získala jasný signál o tom, co někteří vědci věří, že hluk tlakového trupu lodi exploduje, když prochází rozdrcenou hloubkou . Vědec z Naval Research Laboratory jménem Chester „Buck“ Buchanan pomocí vlečených kamerových saní svého vlastního designu na palubě Mizara konečně lokalizoval Scorpiona . Tažené kamerové sáně, které vyrobil JL „Jac“ Hamm z divize Engineering Services Laboratory Naval Research Laboratory, jsou umístěny v Národním muzeu námořnictva Spojených států . Buchanan pomocí této techniky lokalizoval zničený trup Thresheru v roce 1964.

Optimální rozdělení úsilí při hledání

Klasická kniha na toto téma Theory of Optimal Search ( Operations Research Society of America , 1975), kterou napsal Lawrence D. Stone, získala v roce 1975 Lanchesterovu cenu od American Operations Research Society.

Hledání v polích

Předpokládejme, že stacionární objekt je skryt v jednom z n polí (umístění). Pro každé umístění existují tři známé parametry: cena jediného vyhledávání, pravděpodobnost nalezení objektu jediným hledáním, pokud tam objekt je, a pravděpodobnost , že se tam objekt nachází. Hledající hledá objekt. Znají apriorní pravděpodobnosti na začátku a po každém (neúspěšném) pokusu je aktualizují podle Bayesova zákona. Problém nalezení objektu s minimálními očekávanými náklady je klasický problém vyřešený Davidem Blackwellem . Optimální politika je překvapivě snadno popsatelná: v každé fázi se podívejte na místo, které maximalizuje . Toto je vlastně speciální případ indexu Gittins .

Viz také

Reference

  • Stone, Lawrence D. , Theory of Optimal Search , publikovaná společností 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 / In-Search-of-Air-France-Flight-447
  • Iida, Koji., Studies on the Optimal Search Plan , Vol. 70, Lecture Notes in Statistics, Springer-Verlag, 1992.
  • De Groot, Morris H., Optimální statistická rozhodnutí , Wiley Classics Library, 2004.
  • Richardson, Henry R; a Stone, Lawrence D. Operační analýza během podvodního hledání Scorpiona . Naval Research Logistics Quarterly , červen 1971, roč. 18, Number 2. Office of Naval Research.
  • Stone, Lawrence D. Hledání SS Střední Amerika : Matematický lov pokladů. Technická zpráva, Metron Inc. Reston, Virginie.
  • Koopman, BO Search and Screening , Operations Research Evaluation Group Report 56, Center for Naval Analyses, Alexandria, Virginia. 1946.
  • Richardson, Henry R; a Discenza, JH Pobřežní stráž Spojených států počítačově podporovaný systém plánování vyhledávání (CASP). Naval Research Logistics Quarterly . Sv. 27 číslo 4. str. 659–680. 1980.
  • Ross, Sheldon M. , An Introduction to Stochastic Dynamic Programming , Academic Press. 1983.