Введение к работе
Актуальность темы. Теория поиска занимается формализацией ясного на интуитивно-бытовом уровне понятия 4поиск» и разработкой соответствующих математических моделей. Приложения этой теории весьма разнообразны: поиск статических объектов (полезных ископаемых, неисправностей), динамических объектов (небесных тел, пропавших людей, электронных сигналов) и т. п. Теория поиска — молодая математическая дисциплина. Первые исследования по поиску были проведены во время Второй мировой войны для военных приложений. Основоположником теории поиска считается американский ученый Б. О. Купман, работавший во время войны в группе по исследованию операций Военно-морского флота США.
В работах Купмана, а также в более поздних работах таких исследователей, как Р. Айзеке, Д. П. Ким, Л. А. Петросян, Н. А. Зенкевич, А. Ю. Гар-наев, О. Хеллман, Ш. Тал и др. прослеживается общий подход, связанный с активным применением в моделировании поискового процесса теории вероятностей. Основным критерием успешности поиска выступает, как правило, вероятность обнаружения, а типичной поисковой задачей является максимизация этой вероятности. Использование теории вероятностей хорошо подходит для описания таких характерных явлений, сопутствующих поисковому процессу, как несовершенство прибора-детектора, не обеспечивающего обнаружения в 100% случаев, или недостаток информации о возможном местоположении разыскиваемого объекта, или повторяемость поисковой ситуации и задача обеспечения успешного поиска в определенной доле повторений. Подобное ^вероятностное» моделирование подходит для значительного числа приложений, однако не исчерпывает их всех.
Альтернативой вероятностному поиску является гарантированный поиск, модель которого и рассматривается в диссертации. Элементы гарантированного поиска встречаются уже у Купмана и Айзекса, но пристальное внимание исследователей он привлек лишь в сравнительно недавнее время.
Рассматриваемая в диссертации модель гарантированного поиска состоит в следующем. Точечные участники поискового процесса, ищущий S и уклоняющийся Н, перемещаются по траекториям S(t) и H(t) соответственно. На эти траектории налагаются следующие ограничения:
|S(ta)-S(ti)|<|ia-ti|, (1)
| РОС НАЦИОНАЛЬНА» і
З I БИБЛИОТЕКА I
! ygsga
\Н{Ь)-ЩЬ)\*ю\Ь-и\, (2)
О < w < 1 (и> = const). (3)
Уклоняющийся считается обнаруженным, если в некоторый момент t* выполняется неравенство
|5(0-Я(ОКг, (4)
причем радиус обнаружения г является ненулевым (и фиксированным),
г > О (г — const). (5)
Последние два условия говорят о том, что с ищущим связан круг обнаружения радиуса г.
Ищущий и уклоняющийся перемещаются в пределах поискового множества Q0, в качестве которого в диссертации рассматриваются в основном евклидова плоскость и ее подмножества. Перед ищущим ставится определенная поисковая задача, например патрулирование некоторого подмножества Q С Qo- Ключевая предпосылка модели гарантированного поиска состоит в том, что эта поисковая задача должна быть решена ищущим при помощи единственной траектории, не зависящей от действий уклоняющегося, при том лишь условии, что траектория уклоняющегося содержится во множестве ТІ — множестве траекторий-нарушителей. То есть, поставленная задача имеет решение, если
3 S*(t): V//(t) Є U 3f = f{H): \S'{t*) - H(t*)\ < r. (6)
Конкретный вид множества ТІ зависит от поставленной перед ищущим задачи. Если решается задача патрулирования подмножества Q С Qo, то Ті состоит из всех траекторий вида (2), проходящих через Q.
В отличие от вероятностного поиска, где обеспечивается некоторый средний результат при условии многократного повторения ситуации, здесь должно быть гарантировано успешное обнаружение для каждого конкретного случая независимо от действий уклоняющегося. Это может быть важно, например, когда поисковая ситуация уникальна и реализуется всего один раз или когда критическим является исход каждого повторения ситуации, а не некий средний параметр.
То, что одной-единственной траекторией-решением S*{t) обнаружение гарантируется для любой траектории уклоняющегося, можно перефразировать
следующим образом: ищущий никак не корректирует свои действия в зависимости от движения уклоняющегося. Напротив, уклоняющийся может использовать какую угодно информацию об ищущем (включая положение и скорость ищущего в текущий и даже будущие моменты времени) и как угодно корректировать свое поведение, пытаться противодействовать обнаружению, но это ему все равно не поможет. Это можно суммировать следующим образом: в модели гарантированного поиска ищущий является полностью неинформированным о действиях уклоняющегося, а уклоняющийся — полностью информированным о действиях ищущего.
Гарантированному поиску можно дать и следующую интерпретацию: в поисковом процессе участвует не один, а несколько уклоняющихся, возможно, бесконечное их число. Можно даже считать, что в каждой точке имеется по уклоняющемуся. Тем не менее ищущий одной траекторией-решением должен обнаружить их всех.
В начале 1990-х для решения задач гарантированного поиска Е. В. Шикин, С. М. Губайдуллин и А. Г. Чхартишвили предложили наглядно-геометрический метод, основанный на использовании переменных информационных множеств. Применяя данный метод, упомянутые исследователи, а также А. А. Скворцов, С. Б. Березин и др. получили целый ряд интересных результатов. Постановки, рассмотренные в их работах, весьма разнообразны, при этом общее направление работ можно охарактеризовать как построение конкретных поисковых траекторий для определенных классов поисковых множеств. В этих работах формулировались достаточные условия разрешимости задач гарантированного поиска, при этом обоснованием достаточных условий выступали построенные траектории.
В отдельных (тривиальных и близких к ним) случаях удавалось сформулировать необходимые и достаточные условия, однако для содержательных задач этого сделано пока не было. На фоне упомянутых результатов бросается в глаза отсутствие работ по отысканию общих содержательных необходимых условий разрешимости, чему и посвящена диссертация. Необходимые условия разрешимости задач гарантированного поиска позволят, например,
отсеивать заведомо неразрешимые задачи;
сравнивать разрывы между необходимыми и имеющимися достаточными условиями.
в) г)
Ряс. 1
Однако, что более важно, необходимые условия связаны с действиями уклоняющегося. Здесь прослеживается прямая аналогия с упомянутой выше связью между достаточными условиями и действиями ищущего. Действительно, пусть выполнены достаточные условия разрешимости. Это означает, что существует траектория S*(t), гарантирующая обнаружение независимо от траектории уклоняющегося (рис. 1а). При этом действия уклоняющегося остаются в тени. Поэтому отыскание достаточных условий сосредоточивает наше внимание на действиях ищущего и сродни «игре» на его стороне. В случае, когда достаточные условия не выполнены, а необходимые — выполнены, мы ничего не можем сказать об исходе поиска (рис. 16). Пусть теперь необходимые условия не выполнены (рис. 1 в, г). Мы можем выразить этот факт через отрицание утверждения (б):
VS ЗН(5) Є Н : Vt |S(t) - ff(t)| > г. (7)
Как видно, здесь фигурирует функция H(S), сопоставляющая каждой траектории ищущего S траекторию Н уклонения от 5. На рис. 1в показана некоторая траектория ищущего Si и соответствующая траектория уклонения H(S\)l а на рис. 1 г — другая траектория ищущего 5Л и траектория укпоне-
ния от нее H(S2). Поскольку уклонение возможно от любой траектории, в тени остаются действия ищущего, а акцент переходит на действия уклоняющегося. Таким образом, отыскание необходимых условий сродни «игре» за уклоняющегося.
Цель работы: получение содержательных необходимых условий разрешимости задач гарантированного поиска. При этом необходимые условия должны быть достаточно общими, т. е. применимыми к широкому классу задач.
Основные результаты.
Наглядно-геометрический метод, ранее применяемый в основном для получения достаточных условий разрешимости, адаптирован для отыскания необходимых условий. Тем самым подтверждена эффективность данного метода и его потенциал.
Получены содержательные необходимые условия разрешимости широкого класса задач гарантированного поиска. Указан алгоритм построения траектории уклонения от произвольной траектории ищущего в случае невыполнения данных условий.
Полученные условия применены к некоторым конкретным поисковым множествам и проведено сравнение с достаточными условиями разрешимости, полученными ранее другими исследователями. Нарис. 2 приведен пример подобного сравнения для поиска на единичной сфере. Сравнение производится для значений параметров w и г. Область Л является областью выполнения достаточных условий, полученных А. Г. Чхарти-швили и Е. В. Шикиным. Область С является областью невыполнения необходимых условий, полученных в диссертации. Для области В вопрос остается открытым.
Построена дискретная модель поискового процесса. При том, что эта модель в основном использовалась как средство доказательства, указано на ее самостоятельную ценность, в особенности в качестве средства моделирования и визуализации поискового процесса на ЭВМ.
Введена и подробно исследована вспомогательная конструкция, использованная в формулировках необходимых условий разрешимости некоторых классов задач — функция периметра плоских множеств. В этом кон-
0.5
0.5 1
Рис.2
тексте особо рассмотрен класс плоских выпуклых множеств- Для выпуклых многоугольников указан алгоритм построения функции периметра. Доказана теорема о сходимости функции периметра последовательности многоугольников, аппроксимирующей произвольное выпуклое множество, к функции периметра этого множества. Упомянутый алгоритм реализован в виде компьютерной программы, прилагающейся к диссертации.
Проведены полноценные обобщения на трехмерный случай, случай нескольких ищущих и случай поиска на сфере, подтверждающие широкую применимость использованного метода.
Методы исследования. Основным методом исследования является наглядно-геометрический подход, основанный на представлении информации, накапливаемой в процессе поиска, в виде переменных информационных множеств. Использованы также методы математического анализа, вариационного исчисления и геометрии.
Научная новизна. Впервые сформулированы общие необходимые условия разрешимости задач гарантированного поиска.
Теоретическая и практическая ценность. Адаптация наглядно-геометрического метода к получению необходимых условий подтверждает теоретический потенциал данного метода. С его использованием в диссертации получены результаты для поиска в плоских и трехмерных областях, поиска несколькими ищущими и поиска на сфере. Однако применимость данного метода вовсе не исчерпывается рассмотренными поисковыми ситуациями; тем самым открывается возможность для исследований новых постановок задач и задач в других поисковых множествах.
Необходимые условия разрешимости позволяют оценивать разрывы с достаточными условиями, отсеивать заведомо неразрешимые задачи поиска, а также алгоритмически строить траектории уклонения.
Апробация работы. Результаты работы докладывались на семинаре «Задачи динамического поиска» под руководством профессора Е. В. Шикина (факультет ВМиК МГУ), семинаре кафедры оптимального управления под руководством профессоров Н. Л. Григоренко и М. С. Никольского (факультет ВМиК МГУ), семинаре «Геометрия в целом» под руководством профессора И. X. Сабитова, старшего научного сотрудника Э. Р. Розендорна и профессора Е. В. Шикина (мехмат МГУ).
Публикации. Основные результаты диссертации опубликованы в работах [1-5].
Структура и объем диссертации. Диссертация состоит из вводной главы, двух основных глав и приложения. Общий объем диссертации — 129 страниц. Список литературы включает 38 наименований. В диссертации содержатся 42 иллюстрации. К диссертации прилагается компакт-диск с программным обеспечением.
