Введение к работе
Актуальность темы. Поисковые ситуации, встречающиеся на практике, жьма разнообразны. Это и разведка полезных ископаемых, и отыскание нсис-равностей в аппаратуре, и поиск оптимальных управленческих решений, и, аконец, поиск объектов в различных средах, рассматриваемый в предлага-мой работе. Все они имеют по крайней мере одну характерную черту — их онечной целью является получение определенной информации. Сам процесс олучения требуемой информации и называют поиском.
Первые публикации по теории поиска стали появляться после Второй ми-овой войны в результате исследований как отечественных, так и зарубеж-ых военных специалистов, таких как Б.О. Купман, В. А. Абчук, В.Г. Суздаль. [значально эти исследования производились преимущественно для военных елей, но впоследствии выяснилось, что методы этих работ могут с успехом рименяться при решении других проблем. В настоящее время еще нельзя го-орить о том, что общая теория поиска разработана. Скорее имеется большое оличество разнообразных задач, которые можно отнести к поисковым. Инте-есные результаты получены Д.П.Кимом, Ф.Л. Черноусько, Л.А. Петросяном, L.IO. Гарнаевым, Н.А. Зенкевичем, О. Хеллманом и др.
Для поиска характерно отсутствие текущей информации об искомом объ-кте. Таким образом, поиск можно трактовать как управление сближением бъектов при наличии априорной и отсутствии текущей информации. Это от-мчает его от преследования, в котором текущая информация присутствует. 1гры преследования, как правило, могут быть рассмотрены "в малом" и опи-:аны дифференциальными уравнениями. Поэтому их называют также диффе-)енциалъными играми. Фундаментальный вклад в развитие теории диффе-«нциальных игр внесли Р. Айзеке, Л.С. Понтрягин, Н.Н. Красовский и др.
В диссертационной работе рассматривается следующая математическая мо-^ь конфликтной ситуации поиска.
В поиске принимают участие два управляемых объекта — ищущий (объект І) и уклоняющийся (объект В), обладающие простым движением. То есть, щнамические свойства объектов описываются уравнениями
х = и, у = V
і начальными условиями
х(0) = х0, 2/(0) = уо,
где х, у — n-мерные фазовые векторы объектов, и, v — их скорости, точкой обозначены производные по времени t. Векторы и и v суть управления, подчиненные противоборствующим сторонам — ищущему и уклоняющемуся соответственно, которые могут выбирать их так, чтобы удовлетворялись следующие ограничения: а) функции u(t) и v(t) кусочно непрерывны при t > О, б) при всех t > О выполнены условия
К*)|| = а, |К011
отражающие ограничения на управления объектов, а и /3 — положительные постоянные, /3 < а, в) положения объектов при t > 0 удовлетворяют включениям
x(t) Є П, y(t) Є fi,
где ft — некоторая область, ft с R". Область ft называют поисковой областью. Управления v,(t), v(t), удовлетворяющие наложенным условиям а)-в), назовем допустимыми.
Поиск прекращается в момент обнаружения уклоняющегося ищущим, которое происходит при сближении объектов на расстояние, не превосходящее положительной постоянной I, то есть при выполнении условия
\\Х-У\\<1.
Необходимо найти начальный вектор Хо Є ft, число Т > 0 и допустимое управление u(t) ищущего на отрезке [О, Г], для которых при любом начальном векторе уа Є ft и любом допустимом управлении v(t) уклоняющегося на отрезке [О, Т] гарантируется обнаружение уклоняющегося в некоторый момент времени т Є [0,Т].
Предполагается, что обоим конфликтующим объектам известны уравнения движения, ограничения на фазовые векторы и управления, условие обнаружения, постоянные а, /3 и /, а также поисковая область ft. Ищущий должен выбирать свое управление программным способом, опираясь только на знание этой информации, и не имея информации ни об управлении v(t) уклоняющегося ни о его начальном или текущем фазовом состоянии. Уклоняющийся, напротив, может выбирать свое начальное положение и управление, зная начальное положение ищущего и его управление во все будущие моменты времени.
В последнее время для решения задач гарантированного поиска Е.В. Ши-кин, СМ. Губайдуллин и А.Г. Чхартишвили предложили геометрический под-
од, состоящий в использовании при построении поисковой траектории вспо-огательных информационных множеств, вообще говоря, изменяющихся во ремени. Эти множества возникают при анализе возможных траекторий ухло-ения и, как правило, являются запретными для уклоняющегося в том смыс-е, что он не может в них находиться в силу условий задачи (в противном гсучае он был бы обнаружен ранее). Простейшими из информационных мно-сеств являются шар (круг) обнаружения и следящая область. Особую роль грает полная остаточная область — максимальное запретное для уклоняюще-ося множество и область неопределенности — совокупность точек, в которых клоняющийся объект может находиться в данный момент времени. Траекто-ию ищущего строят таким образом, чтобы полная остаточная область, увенчиваясь, в какой-то момент времени заполнила всю поисковую область 1. С спользованием геометрического метода решены задачи поиска на некоторых амкнутых поверхностях, в частности, на поверхности цилиндра и на торе. )тметим, что геометрические методы для решения задачи уклонения исполь-овались в работах М.Н. Иванова и Е.П. Маслова, задачи поиска — в работах к.А. Меликяна, В.А. Залгаллера.
Ф.Л. Черноусько рассмотрена задача динамического поиска в приведенной остановке для плоских и трехмерных выпуклых поисковых областей. Стра-егия ищущего, гарантирующая обнаружение за- конечное время, в плоской ыпуклой области построена при условии /3[а < 1/D, где D — ширина вы-уклой области (минимальная ширина полосы, содержащей данную область). Іоказано, что при выполнении более слабого условия
Щ(?)Ч-
тратегия ищущего, гарантирующая обнаружение, существует. Построенная расктория зависит от параметра, относительно которого известно лишь, что я должен быть достаточно близок к 0. Для цилиндрической поисковой облас-и с площадью основания 5 проведенное построение приводит к достаточным словиям осуществимости гарантированного поиска лишь при /2 <: S.
Способы гарантированного поиска, получаемые при решении таких задач, ообще говоря, оптимальными не являются. Условия на параметры задачи, га-іантирующие завершение поиска, обычно являются лишь достаточными. Не-оторые необходимые условия разрешимости задач поиска найдены П.М. Ла-«ным. Однако говорить о близости необходимых и достаточных условий друг ругу пока рано.
В диссертационной работе найдены достаточные условия разрешимости задачи динамического поиска в плоских и трехмерных выпуклых областях и соответствующие стратегии ищущего, гарантирующие обнаружение уклоняющегося. Для решения задачи используются методы геометрического моделирования и компьютерной визуализации.
Отметим, что использование геометрических методов предполагает работу скорее с траекториями объектов, а не с их управлениями. Управления объектов в случае простого движения можно получить, продифференцировав векторную функцию, описывающую траекторию объекта. Поэтому в предлагаемой работе задача формулируется также и в недифференциальной форме, в качестве ответа получается траектория объекта.
Информационные множества — основная составляющая геометрического подхода к решению задачи поиска — позволяют наглядно представить информацию, которой обладает ищущий о местоположении искомого. Найти их аналитически во многих случая непросто. Поэтому актуальным вопросом является визуализация поискового процесса, то есть использование средств вычислительной техники для вычисления и отображения на каком-либо графическом устройстве информационных множеств задачи поиска. Ее целью является наглядное представление хода поискового процесса, изменения уровня информированности ищущего о местоположении уклоняющегося.
Визуализация поиска может быть использована несколькими способами.
Во-первых, для подтверждения теоретического результата. Для заданной области и значения параметров задачи поиска (а, /3 и /) строится поисковая траектория, полученная аналитически, и полная остаточная область вычисляется последовательно, с некоторым шагом по времени. В момент окончаниї движения полная остаточная область заполняет всю поисковую область.
Во-вторых, для проверки, является ли траектория, выбранная из каких-либо неформальных соображений, поисковой. При окончании движения ищущего по этой траектории проверяется, является ли область неопределенное^ пустым множеством, или нет. В первом случае выбранная траектория является поисковой, во втором — нет.
В-третьих, для интерактивного построения траектории, когда пользоватеш продолжает траекторию в зависимости от того, что он наблюдает на экране При этом компьютер выполняет рутинные операции (вычисление информа ционных множеств), а исследователь на основе неформального анализа пред ставленной информации выбирает дальнейшее поведение ищущего объекта.
К настоящему времени удалось построить оценки области неопределенности и полной остаточной области с некоторым шагом по времени при помощи рекуррентных формул. Примеры таких формул можно найти в работах П.М.Ларина и С.Б.Березина. Эти формулы используют теоретико-множественные операции, такие как пересечение, вычитание и r-расширение. Тем самым, чтобы вычислять эти области при помощи компьютера, необходима модель множеств, позволяющая реализовать эти операции алгоритмически. Алгоритмическая реализация теоретико-множественных операций рассматривалась ранее В.А. Дебеловым, A.M. Мацокиным и С.А. Упольниковым. Однако, рассмотренный в этих работах класс множеств, ограниченных кривыми Безье, не замкнут относительно операции r-расширения. СБ. Березин рассматривает более простой класс множеств, граница которых состоит из конечного числа отрезков. В этом классе результат r-расширения множества также может быть вычислен лишь приближенно.
Цель работы. Получение достаточных условий разрешимости задачи динамического поиска в плоских и трехмерных выпуклых областях, построение соответствующих поисковых траекторий; построение класса множеств, замкнутого относительно теоретико-множественных операций, включая г-расши-рение; описание структуры данных, представляющей любое множество из этого класса; построение численных методов для вычисления результатов указанных операций.
Метод исследования. Для обоснования результатов, полученных в работе, используется специальный геометрический метод — метод следящих областей, методы выпуклого анализа, математического анализа и геометрии.
Научная новизна. В диссертации содержатся следующие новые р&зуль-таты:
-
Построена поисковая траектория в прямоугольнике при условии (*) на параметры задачи.
-
Сформулирована вспомогательная по отношению к задаче поиска задача патрулирования; посгросны траектории патрулирования круга.
-
С использованием траекторий патрулирования круга найдены достаточные условия разрешимости задачи поиска в прямом круговом цилиндре и построены соответствующие поисковые траектории.
-
Исследована задача поиска в произвольной выпуклой области. Найдены достаточные условия разрешимости задачи в плоских и трехмерных выпуклых областях, построены соответствующие траектории.
-
Построена компьютерная модель плоских множеств; найдены алгоритмы вычисления результатов операций пересечения, вычитания и г-расши-рения множеств, необходимые для вычисления оценок информационных множеств задачи поиска.
Теоретическая и практическая ценность. Наряду с решением задачи поиска в плоских и трехмерных выпуклых областях (в частности, в прямоугольнике и цилиндре), обоснованы методы, которые можно применить при решении других задач поиска. Такими методами являются способ построения поисковой траектории при помощи траектории патрулирования и метод проектирования поисковых траекторий.
Разработанные алгоритмы реализации теоретико-множественных операций могут быть применены при моделировании множеств, возникающих в других задачах, не имеющих непосредственного отношения к задачам динамического поиска.
Апробация работы. Результаты работы докладывались на Международной конференции студентов и аспирантов "Ломоносов" (Москва, 1997 г.); на семинаре "Задачи динамического поиска" под руководством профессора Е.В. Шикииа (факультет ВМиК МГУ); на семинаре "Прямые и обратные задачи теории управления" под руководством профессора Н.Л. Григоренко и профессора М.С Никольского (факультет ВМиК МГУ); на семинаре "Геометрия в целом" под руководством профессора И.Х. Сабитова, доцента Э.Р. Ро-зендорна и профессора Е.В. Шикина (мехмат МГУ); на семинаре отдела "Математические модели конфликтных ситуаций" под руководством профессора А.Ф. Кононенко (Вычислительный центр РАН).
Публикации. Основные результаты диссертации опубликованы в работах [1-6].
Структура и объем работы. Диссертация состоит из введения и дву* глав. Объем работы — 120 машинописных страниц, список литературы содержит 44 наименования.
