Байесовская теория поиска - Bayesian search theory
Байесовская теория поиска - это применение байесовской статистики к поиску потерянных объектов. Он несколько раз использовался для поиска потерянных морских судов, например, USS Scorpion , и сыграл ключевую роль в восстановлении бортовых самописцев во время катастрофы рейса 447 авиакомпании Air France в 2009 году. Найдите останки рейса 370 Malaysia Airlines .
Процедура
Обычная процедура выглядит следующим образом:
- Сформулируйте как можно больше разумных гипотез о том, что могло случиться с объектом.
- Для каждой гипотезы постройте функцию плотности вероятности местоположения объекта.
- Создайте функцию, дающую вероятность фактического нахождения объекта в местоположении X при поиске там, если он действительно находится в местоположении X. При поиске в океане это обычно является функцией глубины воды - на мелководье шансы найти объект хорошие, если поиск в нужном месте. В глубокой воде шансы снижаются.
- Последовательно объедините приведенную выше информацию для создания общей карты плотности вероятности. (Обычно это просто означает умножение двух функций вместе.) Это дает вероятность найти объект, посмотрев в местоположении X, для всех возможных местоположений X. (Это может быть визуализировано как контурная карта вероятности.)
- Постройте путь поиска, который начинается в точке с наибольшей вероятностью и «сканирует» области с высокой вероятностью, затем промежуточные вероятности и, наконец, области с низкой вероятностью.
- Постоянно проверяйте все вероятности во время поиска. Например, если гипотезы для местоположения X предполагают вероятное разрушение объекта и поиск в местоположении X не дал никаких фрагментов, тогда вероятность того, что объект находится где-то поблизости, значительно снижается (хотя обычно не до нуля), в то время как вероятности его нахождения в других местах соответственно увеличивается. Процесс пересмотра осуществляется с применением теоремы Байеса .
Другими словами, сначала ищите там, где он, скорее всего, будет найден, затем ищите там, где это менее вероятно, затем ищите, где вероятность еще меньше (но все еще возможна из-за ограничений по топливу, дальности, водным потокам и т. до тех пор, пока остается недостаточная надежда на размещение объекта по приемлемой стоимости.
Преимущества байесовского метода заключаются в том, что вся доступная информация используется согласованно (т. Е. "Защищенным от утечек" способом), и метод автоматически производит оценки стоимости для заданной вероятности успеха. То есть, даже до начала поиска, можно гипотетически сказать, что «существует 65% -ный шанс найти его за 5-дневный поиск. Эта вероятность возрастет до 90% после 10-дневного поиска и 97% после 15 дней »или аналогичное заявление. Таким образом, можно оценить экономическую жизнеспособность поиска до выделения ресурсов на поиск.
Помимо USS Scorpion , другие суда , обнаруженные с помощью байесовской теории поиска, включают MV Derbyshire , крупнейшее британское судно, когда-либо потерянное в море, и SS Central America . Он также оказался успешным в поисках потерянной водородной бомбы после крушения Palomares B-52 в Испании в 1966 году и при обнаружении в Атлантическом океане разбившегося рейса 447 Air France .
Теория байесовского поиска включена в программу планирования миссий CASP (Computer Assisted Search Program), используемую Береговой охраной США для поиска и спасания . Позднее эта программа была адаптирована для поиска на суше путем добавления факторов местности и наземного покрова для использования ВВС США и Гражданским воздушным патрулем .
Математика
Предположим, что квадрат сетки с вероятностью p содержит обломки, а вероятность успешного обнаружения обломков равна q . Если в квадрате обыскивают и не обнаруживают обломков, то по теореме Байеса пересмотренная вероятность того, что затонувшее судно находится в квадрате, определяется выражением
Для любого другого квадрата сетки, если его априорная вероятность равна r , его апостериорная вероятность определяется выражением
USS Scorpion
В мае 1968 года ВМС США «с атомной подводной лодки USS Scorpion (SSN-589) не смог прибыть , как ожидается , на своем родном порту Норфолк, штат Вирджиния . Командующие ВМС США были почти уверены, что судно потеряно у Восточного побережья , но тщательные поиски не смогли обнаружить останки Скорпиона .
Затем глубоководный эксперт ВМФ Джон П. Крейвен предположил, что « Скорпион» затонул в другом месте. Крейвен организовал поиск к юго-западу от Азорских островов на основе сомнительной приблизительной триангуляции с помощью гидрофонов . Ему выделили только один корабль, Mizar , и он воспользовался советом фирмы математиков-консультантов, чтобы максимально использовать свои ресурсы. Была принята байесовская методология поиска. Были опрошены опытные командиры подводных лодок, чтобы сформулировать гипотезы о том, что могло стать причиной гибели Скорпиона .
Район моря был разделен на квадраты сетки, и каждому квадрату была присвоена вероятность в соответствии с каждой из гипотез, чтобы получить ряд сеток вероятностей, по одной для каждой гипотезы. Затем они были сложены вместе, чтобы получить общую сетку вероятностей. Вероятность, прикрепленная к каждому квадрату, была тогда вероятностью того, что обломок был в этом квадрате. Вторая сетка была построена с вероятностями, которые представляли вероятность успешного обнаружения обломков, если бы этот квадрат был обыскан и обломки действительно были бы там. Это была известная функция глубины воды. Результатом объединения этой сетки с предыдущей сеткой является сетка, которая дает вероятность найти затонувший корабль в каждом квадрате сетки моря, если его нужно будет обыскать.
В конце октября 1968 года океанографическое исследовательское судно ВМС Mizar обнаружило части корпуса Scorpion на морском дне примерно в 740 км (400 морских миль; 460 миль) к юго-западу от Азорских островов , на глубине более 3000 м (9800 футов). воды. Это было после того, как ВМФ выпустил аудиозаписи из своей подводной системы прослушивания " SOSUS ", которые содержали звуки уничтожения Scorpion . Впоследствии следственный суд был вновь созван, и к месту происшествия были отправлены другие суда, в том числе батискаф « Триест II» , для сбора большого количества фотографий и других данных.
Хотя Крэйвен получил большую заслугу в обнаружении обломков Scorpion , Гордон Гамильтон, эксперт по акустике, который первым применил гидроакустику для определения мест падения ракеты Polaris, сыграл важную роль в определении компактного "окна поиска", в котором в конечном итоге было найдено обломки. Гамильтон установил на Канарских островах станцию прослушивания, которая получила четкий сигнал того, что, по мнению некоторых ученых, было шумом взрыва прочного корпуса судна, когда оно проходило глубину падения . Naval Research Laboratory ученый по имени Честер «Buck» Buchanan, используя буксируемую камеру санки своего собственного дизайна на борте Мицар , наконец , расположенный скорпион . Буксируемые салазки для фотоаппаратов, которые были изготовлены Дж. Л. «Джаком» Хаммом из отдела инженерных служб лаборатории военно-морских исследований, размещены в Национальном музее ВМС США . Бьюкенен обнаружил разрушенный корпус Thresher в 1964 году, используя эту технику.
Оптимальное распределение поисковых усилий
Классическая книга по этой теме «Теория оптимального поиска» ( Американское общество исследования операций , 1975 г.) Лоуренса Д. Стоуна получила в 1975 г. Ланчестерскую премию Американского общества исследования операций.
Поиск в ящиках
Предположим, что неподвижный объект скрыт в одном из n ящиков (локаций). Для каждого местоположения есть три известных параметра: стоимость однократного поиска, вероятность нахождения объекта при однократном поиске, если объект там есть, и вероятность того, что объект находится там. Искатель ищет объект. Они знают априорные вероятности в начале и обновляют их по закону Байеса после каждой (неудачной) попытки. Задача поиска объекта с минимальной ожидаемой стоимостью - классическая задача, которую решает Дэвид Блэквелл . Удивительно, но оптимальную политику описать несложно: на каждом этапе ищите то место, которое максимизирует . На самом деле это частный случай индекса Gittins .
Смотрите также
Рекомендации
- Стоун, Лоуренс Д. , Теория оптимального поиска , опубликованная Американским обществом исследования операций , 1975 г.
- Стоун, Лоуренс Д. , В поисках рейса 447 авиакомпании Air France. Институт исследований операций и управления, 2011 г. https://www.informs.org/ORMS-Today/Public-Articles/August-Volume-38-Number -4 / В поисках-оф-Эйр-Франс-рейс-447
- Иида, Коджи, Исследования по оптимальному плану поиска , Vol. 70, Конспект лекций по статистике, Springer-Verlag, 1992.
- Де Гроот, Моррис Х., Оптимальные статистические решения , Библиотека Wiley Classics, 2004.
- Ричардсон, Генри Р.; и Стоун, Лоуренс Д. Анализ операций во время подводных поисков Скорпиона . Ежеквартально по военно-морской исследовательской логистике , июнь 1971 г., Vol. 18, номер 2. Управление военно-морских исследований.
- Стоун, Лоуренс Д. Поиски СС Центральная Америка : математическая охота за сокровищами. Технический отчет, Metron Inc. Рестон, Вирджиния.
- Купман, Б.О. Поиск и проверка , Отчет группы оценки исследований операций 56, Центр военно-морского анализа, Александрия, Вирджиния. 1946 г.
- Ричардсон, Генри Р.; и Discenza, JH. Компьютерная система планирования поиска береговой охраны США (CASP). Ежеквартально по логистике военно-морских исследований . Vol. 27 номер 4. С. 659–680. 1980 г.
- Росс, Шелдон М. , Введение в стохастическое динамическое программирование , Academic Press. 1983 г.