автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Динамический поиск в выпуклых областях и его визуализация

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. М. В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И

КИБЕРНЕТИКИ Г Г ¿г ОД

5 О ш

На правах рукописи УДК 517.97

СКВОРЦОВ Алексей Александрович

ДИНАМИЧЕСКИЙ ПОИСК В ВЫПУКЛЫХ ОБЛАСТЯХ И ЕГО ВИЗУАЛИЗАЦИЯ

05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2000

Работа выполнена на факультете вычислительной математики и кибернетик! Московского государственною университета им. М.В.Ломоносова.

Научный руководитель:

доктор физико-математических наук, профессор Е.В. Шикин

Официальные оппоненты: доктор физико-математических наук,

профессор Н.Л. Григоренко

кандидат физико-математических наук, старший научный сотрудник В. А. Галактионов

Ведущая организация: Вычислительный центр РАН

Защита диссертации состоится " 0$ " (^{СоХр^ 2000 г. в на заседании Диссертационного совета К.053.05.87 в Московском государственном университете им. М.В.Ломоносова по адресу: 119899, Москва, Воробьевы горы, МГУ, 2-й учебный корпус, факультет вычислительной математик! и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан

" 03» /-сол^рЗ-

. 2000 г.

Ученый секретарь диссертационного совета, доцент

В.М. Говоре

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Поисковые ситуации, встречающиеся на практике, зсьма разнообразны. Это и разведка полезных ископаемых, и отыскание неис-равностей в аппаратуре, и поиск оптимальных управленческих решений, и, аконец, поиск объектов в различных средах, рассматриваемый в предлагавши работе. Все они имеют по крайней мере одну характерную черту — их онечной целью является получение определенной •информации. Сам процесс олучения требуемой информации и называют поиском.

Первые публикации по теории поиска стали появляться после Второй ми-овой войны в результате исследований как отечественных, так и зарубеж-ых военных специалистов, таких как Б.О. Купман, В. А. Абчук, В.Г. Суздаль, [значально эти исследования производились преимущественно для военных елей, но впоследствии выяснилось, что методы этих работ могут с успехом рименяться при решении других проблем. В настоящее время еще нельзя го-орить о том, что общая теория поиска разработана. Скорее имеется большое оличество разнообразных задач, которые можно отнести к поисковым. Инте-есные результаты получены Д.П.Кимом, Ф.Л. Черноусько, JI.A. Петросяном, L.IO. Гарнаевым, H.A. Зенкевичем, О. Хеллманом и др.

Для поиска характерно отсутствие текущей информации об искомом объ-кте. Таким образом, поиск можно трактовать как управление сближением бъектов при наличии априорной и отсутствии текущей информации. Это от-мчает его от преследования, в котором текущая информация присутствует. 1гры преследования, как правило, могут быть рассмотрены "в малом" и опи-:аны дифференциальными уравнениями. Поэтому их называют также диффе-)енциальными играми. Фундаментальный вклад в развитие теории диффе-»енциальных игр внесли Р. Айзеке, JI.C. Понтрягин, H.H. Красовский и др.

В диссертационной работе рассматривается следующая математическая мо-\ель конфликтной ситуации поиска.

В поиске принимают участие два управляемых объекта — ищущий (объект 4) и уклоняющийся (объект В), обладающие простым движением. То есть, щнамические свойства объектов описываются уравнениями

X = и, у = V

i начальными условиями

х(0) = х0, 2/(0) = уо,

где х, у — n-мерные фазовые векторы объектов, и, v — их скорости, точкой обозначены производные по времени t. Векторы и я v суть управления, подчиненные противоборствующим сторонам — ищущему и уклоняющемуся соответственно, которые могут выбирать их так, чтобы удовлетворялись следующие ограничения: а) функции u(t) и v(t) кусочно непрерывны при t > О, б) при всех t > О выполнены условия

Kt)|| = a, IK01I < /3,

отражающие ограничения на управления объектов, а и ¡3 — положительные постоянные, ¡3 < а, в) положения объектов при t > О удовлетворяют включениям

a:(t) 6 fi, 2/(t) G fi,

где fi — некоторая область, fi с R". Область fi называют поисковой областью. Управления u(t), v(t), удовлетворяющие наложенным условиям а)-в), назовем допустимыми.

Поиск прекращается в момент обнаружения уклоняющегося ищущим, которое происходит при сближении объектов на расстояние, не превосходящее положительной постоянной I, то есть при выполнении условия

11®-г/Н<г.

Необходимо найти начальный вектор Хо G fi, число Т > 0 и допустимое управление u(t) ищущего на отрезке [О, Т], для которых при любом начальном векторе уа £ fi и любом допустимом управлении v(t) уклоняющегося на отрезке [О, Т] гарантируется обнаружение уклоняющегося в некоторый момент времени т G [0,Т].

Предполагается, что обоим конфликтующим объектам известны уравнения движения, ограничения на фазовые векторы и управления, условие обнаружения, постоянные а, /3 и I, a также поисковая область fi. Ищущий должен выбирать свое управление программным способом, опираясь только на знание этой информации, и не имея информации ни об управлении v(t) уклоняющегося ни о его начальном или текущем фазовом состоянии. Уклоняющийся, напротив, может выбирать свое начальное положение и управление, зная начальное положение ищущего и его управление во все будущие моменты времени.

В последнее время для решения задач гарантированного поиска Е.В. Ши-кин, С.М. Губайдуллин и А.Г. Чхартишвили предложили геометрический под-

од, состоящий в использовании при построении поисковой траектории вспо-огательных информационных множеств, вообще говоря, изменяющихся во ремени. Эти множества возникают при анализе возможных траекторий укло-ения и, как правило, являются запретными для уклоняющегося в том смыс-е, что он не может в них находиться в силу условий задачи (в противном гсучае он был бы обнаружен ранее). Простейшими из информационных мно-сеств являются шар (круг) обнаружения и следящая область. Особую роль грает полная остаточная область — максимальное запретное для уклоняющейся множество и область неопределенности — совокупность точек, в которых клоняющийся объект может находиться в данный момент времени. Траекто-ию ищущего строят таким образом, чтобы полная остаточная область, увенчиваясь, в какой-то момент времени заполнила всю поисковую область О. С спользованием геометрического метода решены задачи поиска на некоторых амкнутых поверхностях, в частности, на поверхности цилиндра и на торе. )тметим, что геометрические методы для решения задачи уклонения исполь-овались в работах М.Н. Иванова и Е.П. Маслова, задачи поиска — в работах 1.А. Меликяна, В.А. Залгаллера.

Ф.Л. Черноусько рассмотрена задача динамического поиска в приведенной остановке для плоских и трехмерных выпуклых поисковых областей. Стра-егия ищущего, гарантирующая обнаружение за- конечное время, в плоской ыпуклой области построена при условии 13[а < 1/Г), где О — ширина вы-уклой области (минимальная ширина полосы, содержащей данную область). 1оказагш, что при выполнении более слабого условия

тратегия ищущего, гарантирующая обнаружение, существует. Построенная раектория зависит от параметра, относительно которого известно лишь, что я должен быть достаточно близок к 0. Для цилиндрической поисковой облас-и с площадью основания 5 проведенное построение приводит к достаточным словиям осуществимости гарантированного поиска лишь при /2 5.

Способы гарантированного поиска, получаемые при решении таких задач, ообще говоря, оптимальными не являются. Условия на параметры задачи, га->антирующие завершение поиска, обычно являются лишь достаточными. Не-оторые необходимые условия разрешимости задач поиска найдены П.М. Ла-1иным. Однако говорить о близости необходимых и достаточных условий друг ругу пока рано.

2

2

В диссертационной работе найдены достаточные условия разрешимости задачи динамического поиска в плоских и трехмерных выпуклых областях и соответствующие стратегии ищущего, гарантирующие обнаружение уклоняющегося. Для решения задачи используются методы геометрического моделирования и компьютерной визуализации.

Отметим, что использование геометрических методов предполагает работу скорее с траекториями объектов, а не с их управлениями. Управления объектов в случае простого движения можно получить, продифференцировав векторную функцию, описывающую траекторию объекта. Поэтому в предлагаемой работе задача формулируется также и в недифференциальной форме, в качестве ответа получается траектория объекта.

Информационные множества — основная составляющая геометрического подхода к решению задачи поиска — позволяют наглядно представить информацию, которой обладает ищущий о местоположении искомого. Найти их аналитически во многих случая непросто. Поэтому актуальным вопросом является визуализация поискового процесса, то есть использование средств вычислительной техники для вычисления и отображения на каком-либо графическом устройстве информационных множеств задачи поиска. Ее целью является наглядное представление хода поискового процесса, изменения уровня информированности ищущего о местоположении уклоняющегося.

Визуализация поиска может быть использована несколькими способами.

Во-первых, для подтверждения теоретического результата. Для заданной области и значения параметров задачи поиска (а. /3 и I) строится поисковая траектория, полученная аналитически, и полная остаточная область вычисляется последовательно, с некоторым шагом по времени. В момент окончат« движения полная остаточная область заполняет всю поисковую область.

Во-вторых, для проверки, является ли траектория, выбранная из каких-либо неформальных соображений, поисковой. При окончании движения ищущего по этой траектории проверяется, является ли область неопределенное» пустым множеством, или нет. В первом случае выбранная траектория является поисковой, во втором — нет.

В-третьих, для интерактивного построения траектории, когда пользойател! продолжает траекторию в зависимости от того, что он наблюдает на экране При этом компьютер выполняет рутинные операции (вычисление информа ционных множеств), а исследователь на основе неформального анализа пред ставленной информации выбирает дальнейшее поведение ищущего объекта.

К настоящему времени удалось построить оценки области неопределенности и полной остаточной области с некоторым шагом по времени при помощи рекуррентных формул. Примеры таких формул можно найти в работах П.М.Ларина и С.Б.Березина. Эти формулы используют теоретико-множественные операции, такие как пересечение, вычитание и r-расширение. Тем самым, чтобы вычислять эти области при помощи компьютера, необходима модель множеств, позволяющая реализовать эти операции алгоритмически. Алгоритмическая реализация теоретико-множественных операций рассматривалась ранее В.А. Дебеловым, A.M. Мацокиным и С.А. Упольниковым. Однако, рассмотренный в этих работах класс множеств, ограниченных кривыми Безье, не замкнут относительно операции r-расширения. С.Б. Березин рассматривает более простой класс множеств, граница которых состоит из конечного числа отрезков. В этом классе результат г-расширения множества также может быть вычислен лишь приближенно.

Цель работы. Получение достаточных условий разрешимости задачи динамического поиска в плоских и трехмерных выпуклых областях, построение соответствующих поисковых траекторий; построение класса множеств, замкнутого относительно теоретико-множественных операций, включая г-расши-рение; описание структуры данных, представляющей любое множество из этого класса; построение численных методов для вычисления результатов указанных операций.

Метод исследования. Для обоснования результатов, полученных в работе, используется специальный геометрический метод — метод следящих областей, методы выпуклого анализа, математического анализа и геометрии.

Научная новизна. В диссертации содержатся следующие новые результаты:

1. Построена поисковая траектория в прямоугольнике при условии (*) на параметры задачи.

2. Сформулирована вспомогательная по отношению к задаче поиска задача патрулирования; посгросны траектории патрулирования круга.

3. С использованием траекторий патрулирования круга найдены достаточные условия разрешимости задачи поиска в прямом круговом цилиндре и построены соответствующие поисковые траектории.

4. Исследована задача поиска в произвольной выпуклой области. Найдены достаточные условия разрешимости задачи в плоских и трехмерных выпуклых областях, построены соответствующие траектории.

5. Построена компьютерная модель плоских множеств; найдены алгоритмы вычисления результатов операций пересечения, вычитания и г-расши-рения множеств, необходимые для вычисления оценок информационных множеств задачи поиска.

Теоретическая и практическая ценность. Наряду с решением задачи поиска в плоских и трехмерных выпуклых областях (в частности, в прямоугольнике и цилиндре), обоснованы методы, которые можно применить при решении других задач поиска. Такими методами являются способ построения поисковой траектории при помощи траектории патрулирования и метод проектирования поисковых траекторий.

Разработанные алгоритмы реализации теоретико-множественных операций могут быть применены при моделировании множеств, возникающих в других задачах, не имеющих непосредственного отношения к задачам динамического поиска.

Апробация работы. Результаты работы докладывались на Международной конференции студентов и аспирантов "Ломоносов" (Москва, 1997 г.); на семинаре "Задачи динамического поиска" под руководством профессора Е.В. Шикииа (факультет ВМиК МГУ); на семинаре "Прямые и обратные задачи теории управления" под руководством профессора Н.Л. Григоренко и профессора М.С. Никольского (факультет ВМиК МГУ); на семинаре "Геометрия в целом" под руководством профессора И.Х. Сабитова, доцента Э.Р. Ро-зендорна и профессора Е.В. Шикина (мехмат МГУ); на семинаре отдела "Математические модели конфликтных ситуаций" под руководством профессора А.Ф. Кононенко (Вычислительный центр РАН).

Публикации. Основные результаты диссертации опубликованы в работах [1-6].

Структура и объем работы. Диссертация состоит из введения и дву> глав. Объем работы — 120 машинописных страниц, список литературы содержит 44 наименования.

СОДЕРЖАНИЕ РАБОТЫ

Диссертационная работа состоит из введения и двух глав.

Во введении содержится краткий обзор работ и полученных ранее резуль-атов по теме диссертации, описывается содержание и результаты работы.

Первая глава посвящена теоретическому решению задачи поиска в вы-¡уклых областях.

Рассматривается движение двух точечных объектов А (ищущего) и В (ук-юняющегося), обладающих простым движением, в поисковой области О, 2 С К". Особое внимание уделяется наиболее интересным случаям п — 2, 3. Скорость ищущего равна по модулю положительному числу а, модуль скорос-•и уклоняющегося ограничен сверху положительным числом 0, ¡3 < а. Поиск [родолжается до тех пор, пока не произойдет обнаружения, которое происхо-щг в тот момент времени, когда расстояние между объектами не превосходит аданного положительного числа I. До момента обнаружения ищущий не полу-[ает никакой информации о положении и/или скорости уклоняющегося. Ему [звестны только постоянные а, /3 и I, а также поисковая область П. Ищущий ыбирает свое начальное положение удобным для себя образом. Объект В, на-1ротив, знает всю возможную информацию о поведении объекта А, включая :го положение во все будущие моменты времени.

Задача состоит в построении такой траектории объекта А, при движении по :оторой он гарантирует обнаружение объекта В, каким бы допустимым способом тот ни уклонялся. Момент обнаружения, разумеется, зависит от способа клонения, но важно, что обнаружение происходит в течение некоторого коечного времени Т. Время поиска Т является искомой величиной.

Отметим, что при такой постановке задачи ищупщй может выбирать свою раекторию только программным образом.

Существуют разные подходы к решению поисковых задач. В работе ис-юльзуются методы геометрического моделирования и компьютерной визуализации. В разделе 1.2 приводятся необходимые сведения о геометрическом (етоде решения задачи поиска и об информационных множествах, составля-эщих его основу. Рассматриваются шар (круг) обнаружения, остаточная об-[асть, полная остаточная область, область неопределенности, упреждающая бласть и объединение остаточной и упреждающей областей — следящая об-[асть.

В разделе 2.3 в общей форме обсуждается принцип построения поисковой траектории в цилиндрической области П = Ех [О, Я], £2 С К™, путем использования траектории патрулирования ее поперечного сечения £, £ с К™-1.

В подобных областях объекту А целесообразно перемещаться таким образом, чтобы его следящая область в каждый момент времени перекрывала поперечное сечение области в котором он находится. Для удобства мы считаем ось цилиндра направленной вертикально, вдоль оси Охп, а область £ — лежащей в горизонтальной плоскости (или на горизонтальной прямой).

Тогда, если объект А начинает свое движение на одном основании цилиндрической области О., а заканчивает на другом, то в какой-то момент времени объекты непременно окажутся в одной горизонтальной плоскости и, следовательно, объект В попадет в следящую область объекта А, что неизбежнс повлечет за собой его обнаружение.

При указанном способе поиска скорость объекта А имеет две составляющие — вдоль оси цилиндрической области (вертикальная) и вдоль его попе-реченого сечения (горизонтальная). Отношение их модулей дает тангенс угла в наклона траектории объекта А к плоскости поперечного сечения. В ране« решенных задачах этот угол получается из свойств самой следящей области. Например, в случае цилиндрической поверхности из геометрических соображений понятно, что при движении с большим углом следящая область не охватывает поперечного сечения, а при движении с меньшим — имеет области самоналегания. При движении с выбранным углом упреждающая часть следящей области касается остаточной части таким образом, что следящая область замыкается в кольцеобразную область, охватывающую поперечное сечение.

В трехмерном случае построение поисковой траектории разбивается на два этапа. Первый этап состоит в построении траектории патрулирования — замкнутой траектории в поперечном сечении К цилиндрической области 2 х [О, Я при перемещении по которой объект А гарантирует обнаружение объекта Е если последний попадает в какой-то (неизвестный ищущему) момент време ни в это сечение (время движения объекта А по траектории патрулирована не ограничено). Простейший способ построения траектории патрулирования -построение замкнутой кривой, при перемещении по которой следящая обласп в любой момент времени покрывает сечение К.

На втором этапе рассматривается движение объекта А по траектории, вь бираемой так, чтобы ортогональная проекция его текущего положения на по перечное сечение К перемещалась по траектории патрулирования, а ортого

гальная проекция на вертикально расположенную ось цилиндра перемещалась [оступательно в одном направлении. Отношение модуля вертикальной состав-щющей скорости объекта А к модулю горизонтальной дает тангенс угла 0, ко-орый рассматриваемая траектория составляет с плоскостью горизонтального ечения цилиндра К.

Если радиус I шара обнаружения объекта А больше необходимого для пат->улирования, то при достаточно малом угле подъема 0 полученная траектория гвляется поисковой. Проведенные в этом разделе построения строго обосно-1ываются в разделе 1.5 при построении поисковой траектории в цилиндре.

В разделе 1.4 рассмотрена задача поиска в прямоугольнике. Прямоуголь-шк можно представить в виде 5] х [О, Я], где Е — отрезок [О, В], О < Н. Таким >бразом, для построения поисковой траектории указанным методом необходи-яо построить траекторию патрулирования отрезка Е. Траекторией патрули-ювания является движение по некоторой части Р0> этого отрезка и обратно

Если к этой траектории применить второй этап построения поисковой тра-:ктории, получится ломаная определенного класса. В работе рассматривается >тот класс ломаных, найдены условия, при которых такая ломаная являет-•я поисковой траекторией. Показано, что при выполнении условия (*) задача юиска в прямоугольнике разрешима и построена ломаная, являющаяся поис-совой траекторией.

В разделе 1.5 рассматривается задача поиска в прямом круговом цилиндре. Сначала решается задача патрулирования круга К, для которой найдено *ва класса траекторий. Первый класс получается из условия, что следящая класть в любой момент времени покрывает круг К. Таковой является спираг ювидная траектория патрулирования. Второй класс траекторий патрулирова-шя — окружности, центр которых совпадает с центром круга К. Для каждого (ласса найдены достаточные условия на параметры задачи, при которых она разрешима. Эти условия имеют следующий вид:

*де I — радиус шара обнаружения, Я — радиус круга К, а — модуль скорости ищущего, /3 — максимальный модуль скорости уклоняющегося, Л и /г — лонотонно возрастающие функции (указанные в работе явно), г = 1 для спиралевидной траектории, г = 2 для траектории в виде окружности.

др).

Пусть объект А!, имеющий радиус I' шара обнаружения, патрулирует поперечное сечение К цилиндрической области перемещаясь по соответствующей траектории патрулирования со скоростью а. В работе показано, что объект А, имеющий радиус I шара обнаружения (/ > V) может осуществить гарантированный поиск в области П. Поисковая траектория получается в виде винтовой линии, проекция которой на сечение К перемещается по траектории патрулирования, а проекция на ось цилиндра движется поступательно в одном направлении.

Таким образом, достаточные условия разрешимости поисковой задачи в цилиндре имеют вид

при i — 1, 2 (достаточно выполнения хотя бы одного из условий). В качестве V можно взять значение I' = /ï/,(/3/a) < I.

Решение получается описанным выше способом, найдено явное выражение для угла подъема в. Показано, что угол 9 может быть переменным в — B(t), найдены условия на функцию 0(t), при выполнении которых траектория является поисковой.

В разделе 1-6 рассмотрен поиск в выпуклых областях. Доказана

Теорема (о проектировании). Пусть V — некоторая область пространства Rn, x(t) — поисковая траектория в обмети V, П — замкнутая выпуклая область, fî С V. Тогда при движении по траектории z(t) — P(x(t)), где Р(х) — ближайшая к точке х точка области (I, объект А обеспечивает обнаружение объекта Б.

Это становится возможным, поскольку оператор проектирования Р(х) обладает двумя свойствами. Первое из них заключается в том, что расстояние между образами двух точек не превосходит расстояния между самими точками:

Поэтому объект А при перемещении по траектории z(t) не превышает свой ресурс скорости. Второе свойство состоит в следующем. Фиксируем произвольную точку VI из области Тогда расстояние между образом Р(х) любо? точки х и точкой IV не превосходит расстояния между точками х ти:

||P(®x)-P(x2)|| < \\xi-x2\\.

¡|ад - Р(х)\\ < ||w - х\\.

)тсюда непосредственно следует, что все точки шара обнаружения объекта А ри его перемещении по траектории х({), лежащие также в области Л, принад-ежат шару обнаружения объекта А при его перемещении по траектории

Траектория %{{) в,строгом смысле не является поисковой, так как при пере-[ещении объекта А по ней его скорость может быть меньше заданной. Однако, ели кривая, которую описывает векторная функция является кусочно-ладкой, то можно перепараметризовать траекторию гН) таким образом, что-ы объект А перемещался по ней со скоростью а и перепараметризованная раектория будет поисковой.

Если кривая, описываемая векторной функцией ,г(г), не является кусочно-ладкой, ее можно приблизить ломаной -го(й) с любой наперед заданной точ-остью е. При этом ломаная 2г> (£) будет траекторией, обеспечивающей обнаружение при радиусе обнаружения I, если поисковая траектория х({) в области г найдена при условии, что радиус шара обнаружения объекта А равен 1-е. 1осле этого ломаную ло(0 следует перепараметризовать таким образом, чтобы бъект А двигался по ней со скоростью а.

Для решения задачи поиска в плоской (трехмерной) выпуклой области за-лючим ее в прямоуштыгак (цилиндр). Затем, взяв полученную в предыду-[щх разделах поисковую траекторию в прямоугольнике (цилиндре), применима ней вышеописанный алгоритм. Условие (*}, в котором в качестве вели-(ины О берется ширина области (минимальная ширина полосы, содержащей данную выпуклую область), является достаточным для разрешимости задачи юиска в плоской выпуклой области. Аналогично, условие (**), в котором в ачестве величины Я берегся минимальный радиус описанного цилиндра, яв-[яется достаточным для разрешимости задачи поиска в трехмерной выпуклой бласти.

Вторая глава посвящена визуализации поискового процесса.

Основной объем второй главы занимает построение алгоритмов вычисления >езультатов теоретико-множественных операций, необходимых для вычисле-[ия информационных множеств — пересечения, вычитания и г-расширения. Зводится класс плоских множеств, замкнутый относительно этих операций. )тот класс состоит из множеств, границу которых можно представить в ви-<е объединения конечного числа отрезков, дуг окружностей и изолированных «чек. Произвольно взятое множество из этого класса представляется в ш-^ объединения своих почти связных компонент, каждая из которых, в свою »чередь, является пересечением множеств, имеющих линейно связную гра-

ницу (почти связным называется множество, замыкание которого непусто и линейно связно). Множество, имеющее линейно связную границу, описывается циклическим списком отрезков и дуг окружностей, составляющих его границу. Предлагается структура данных, использующая данное разложение для представления любого множества из рассматриваемого класса. Показано, как, оперируя с этой структурой, можно вычислять характеристическую функцию множества, пересечение множеств, дополнение множества, расширение множества и другие теоретико-множественные операции. Построенные алгоритмы используют описанное выше разложение множества.

С использованием этих алгоритмов автором написана демонстрационная программа, визуализирующая процесс поиска в прямоугольнике при перемещении ищущего по поисковой траектории, найденной в работе аналитически.

Автор выражает глубокую благодарность своему научному руководителю профессору Е.В.Шикину за постоянное внимание к работе и поддержку, без которых работа вряд ли была бы написана, а также к.ф.-м.н. А.Г. Чхартишви-ли и другим участникам семинара "Задачи динамического поиска" за многочисленные ценные замечания.

По теме диссертации опубликованы следующие работы:

L] Скворцов A.A. Динамический поиск в плоской выпуклой области. М., Деп. в ВИНИТИ 10 ноября 1995 г., №2985-В95.

2] Скворцов A.A. Динамический поиск в выпуклых областях // Фундаментальная и прикладная математика, 1998, Т.4, Вып.2, С.785-790.

3) Скворцов A.A. Траектория патрулирования в задаче динамического поиска // Тезисы докладов международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов", секция "Вычислительная математика и кибернетика", Москва, 8-10 апреля 1997 г., М., Изд-во Московского университета, 1998, Вьш.2, С.202-203.

1] Скворцов A.A. Траектория патрулирования в задаче динамического поиска. М., Деп. в ВИНИТИ 13 мая 1998 г., М456-В98.

5] Скворцов A.A. Динамический поиск в трехмерных выпуклых областях // Вестник Московского университета. Сер.15. Вычислительная математика и кибернетика, 1999, №3, С. 20-24.

5] Скворцон A.A. Алгоритмическая реализация теоретико-множественных операций на плоскости. М., Деп. в ВИНИТИ 10 июля 2000 г., №1915-ВОО.

Введение

Глава 1. Поиск в выпуклых областях

1.1 Постановка задачи.

1.2 Информационные множества

§1 Шар обнаружения.

§2 Остаточная область

§3 Полная остаточная область.

§4 Упреждающая область.

§5 Следящая область

§6 Область неопределенности.

1.3 Патрулирование

1.4 Поиск в прямоугольнике

§1 Вытеснение уклоняющегося в полосе.

§2 Решение задачи поиска в прямоугольнике.

1.5 Поиск в цилиндре.

§1 Спиралевидная траектория патрулирования.

§2 Траектория патрулирования в виде окружности

§3 Построение поисковой траектории

§4 Поисковая траектория с переменным углом подъема

§5 Решение задачи поиска в цилиндре

1.6 Поиск в выпуклой области

§1 Метод проектирования поисковой траектории

§2 Решение задачи в плоском и трехмерном случаях

Глава 2. Визуализация поискового процесса

2.1 Динамика информационных множеств

2.2 Алгоритмическая реализация операций над множествами

§1 Класс допустимых множеств на плоскости.

§2 Покрытия границы допустимого множества.

§3 Свойства правильных покрытий границы.

§4 Замкнутость класса допустимых множеств относительно теоретико-множественных операций

§5 Канонический вид допустимого множества

§6 Структура данных для представления множеств

§7 Характеристическая функция множества

§8 Специальный случай пересечения множеств.

§9 Пересечение множеств с линейно связной границей

§10 Пересечение почти связного множества и множества с линейно связной границей

§11 Общий случай пересечения множеств

§12 Дополнение допустимого множества

§13 Другие операции над допустимыми множествами

§14 Построение r-расширения множества.

2.3 Визуализация поиска в плоской выпуклой области

Поисковые ситуации, встречающиеся на практике, весьма разнообразны. Это и разведка полезных ископаемых, и отыскание неисправностей в аппаратуре, и поиск оптимальных управленческих решений, и, наконец, поиск объектов в различных средах. Все они имеют по крайней мере одну характерную черту — их конечной целью является получение определенной информации. Сам процесс получения требуемой информации и называют поиском.

Первые публикации по теории поиска стали появляться после Второй мировой войны в результате исследований как отечественных, так и зарубежных военных специалистов, таких как Б:О.Купман [1-3], В.А. Абчук и В.Г. Суздаль [4]. Изначально эти исследования производились преимущественно для военных целей, но впоследствии выяснилось, что методы, предложенные в этих работах, могут с успехом применяться при решении других проблем. В настоящее время еще нельзя говорить о том, что общая теория поиска разработана. Скорее имеется большое количество разнообразных задач, которые можно отнести к поисковым. В монографии Д.П.Кима [15] содержится обзор работ по задачам поиска, имеется обширная библиография.

В данной работе под поиском будем понимать поиск объектов. Как правило, в задачах поиска объектов принимают участие две стороны: ищущая и искомая. Ищущая обследует определенную область пространства, называемую поисковой областью, с целью обнаружения находящихся там искомых объектов или установления факта их отсутствия. Обнаружение происходит при сближении объектов друг к другу на определенное расстояние. Если объекты перемещаются в невыпуклой области, то условием обнаружения может быть попадание в прямую видимость (отрезок, соединяющий объекты, целиком лежит в поисковой области). Условия обнаружения могут зависеть и от случайных факторов (в этом случае может быть задана плотность вероятности обнаружения искомого в зависимости от расстояния между объектами). Ищущий и искомый объекты не обязательно являются точками. Например, при большом количестве ищущих их можно описывать плотностью распределения в поисковой области. В этом случае составной ищущий объект задается некоторой функцией, определенной в поисковой области и зависящей от времени.

Для поиска характерно отсутствие текущей информации об искомом объекте. Тем самым, поиск можно трактовать как управление сближением объектов при наличии априорной и отсутствии текущей информации. Это отличает его от преследования, которое есть управление сближением объектов при наличии текущей информации о преследуемом объекте. Задачу преследования можно рассматривать как логическое продолжение поисковой задачи. В процессе поиска ищущему местонахождение искомого неизвестно. Поиск заканчивается, как только объекты сближаются на определенное расстояние и местоположение искомого становится известно ищущему. Но в этот же момент может начаться игра преследования, поскольку искомый (теперь его можно назвать "преследуемый") находится в пределах зоны действия средств обнаружения ищущего (преследователя) и информация о местоположении преследуемого поступает непрерывно. Игры преследования называют также дифференциальными играми, так как они могут быть описаны дифференциальными уравнениями. Дифференциальные игры рассматривались Р. Айзексом [5], H.H. Красовским [16], Ф.Л. Черноусько [31] и другими авторами.

Поскольку в поисковых задачах текущей информации о местонахождении искомого объекта не поступает, то стратегию ищущего можно задавать только программным способом. В играх преследования, напротив, стратегия ищущего существенным образом зависит от текущего состояния игры. Если в задаче преследования текущая информация поступает только в отдельные моменты времени (возможно, зависящие от выбора ищущего), то на промежутках времени, в течение которых информации не поступает, задача преследования фактически является задачей поиска. В этом случае решение является программным на каждом таком участке, хотя в целом оно зависит от информации об искомом, поступающей в указанные моменты времени.

Из всего многообразия задач поиска можно выделить конфликтные задачи, в которых искомый объект в пределах своих возможностей может противодействать обнаружению (в этом случае будем называть его уклоняющимся). Задачи поиска, не относящиеся к конфликтным, исследовались рядом авторов, в частности, Б.О.Купманом [1-3], О.Хелл-маном [30], Д.П.Кимом [15]. Конфликтные задачи изучались в работах Р. Айзекса [5], Ф.Л. Черноусько [32], Л.А. Петросяна [21, 22], в которых игры поиска рассматриваются как в дискретной, так и в непрерывной постановках, в зависимости от мощности множества возможных положений искомого объекта. Некоторые игры поиска с конечным числом положений ищущего и искомого сводятся к матричным играм.

По характеру движения искомого объекта задачи поиска можно разделить на четыре группы: 1) поиск неподвижного объекта, 2) поиск объекта, движущегося детерминированным образом, 3) поиск объекта, движущегося случайным образом и 4) поиск активно уклоняющегося объекта.

Конфликтные задачи поиска неподвижного объекта рассматривались Р. Айзексом [5], Л.А. Петросяном [21, 22]. Искомый выбирает точку поисковой области, в которой он прячется в начальный момент времени. Ищущий выбирает траекторию движения и движется по ней до момента сближения с искомым до заданного расстояния, стремясь минимизировать время поиска. В чистых стратегиях решения этой игры, как правило, не существует, оптимальная смешанная стратегия искомого заключается в равновероятном выборе точки поисковой области.

Б.О.Купман [3], а затем О.Хеллман [30], рассмотрели задачу оптимального распределения поисковых усилий при поиске неподвижного объекта при условии, что ищущему известна плотность вероятности нахождения искомого объекта в поисковой области. Максимизируемым функционалом является вероятность обнаружения искомого объекта к заданному моменту времени. Исследована динамика условной плотности вероятности нахождения искомого объекта в поисковой области в зависимости от действий ищущего объекта.

Искомый объект может перемещаться некоторым детерминированным образом в зависимости от начального положения и скорости. Задача будет нетривиальной, если эта априорная информация известна ищущему неточно и, возможно, неполно (например, только начальное положение). Решению таких задач посвящена монография Д.П. Кима [15], в которой предполагается, что искомый объект движется прямолинейно и равномерно. Найдены оптимальные стратегии поиска, максимизирующие вероятность обнаружения искомого, при различных предположениях об априорной информации, известной ищущему.

Конфликтная задача поиска искомого объекта, движущегося детерми-нированно, может заключаться в выборе искомым начального положения и направления движения. В работе А.Г. Чхартишвили и Е.В. Шикина [42] рассмотрена задача поиска на плоскости, в которой искомый выбирает свое начальное положение и направление движения, а затем движется прямолинейно и равномерно. Ищущему известен модуль скорости уклоняющегося, но неизвестны ни его начальное положение, ни направление его движения. При превосходстве ищущего над уклоняющимся в скорости построена траектория, при движении по которой ищущий гарантирует обнаружение уклоняющегося, независимо от выбранной последним стратегии уклонения.

В работе О.Хеллмана [30] рассмотрена задача обнаружения искомого объекта, движущегося случайным образом. При этом плотность вероятности нахождения искомого объекта в поисковой области изменяется с течением времени, удовлетворяя некоторому дифференциальному уравнению.

Искомый объект, обладая некоторой информацией о поведении ищущего, может активно уклоняться от обнаружения. Задачи такого типа рассматриваются в работах В.А. Абчука и В.Г.Суздаля [4], Ф.Л.Черно-усько [32], Л.А. Петросяна [21, 22], А.Г. Чхартишвили и Е.В. Шикина [42]. К этому же типу относится и рассматриваемая в данной работе задача динамического поиска. В поиске принимают участие два управляемых объекта — ищущий (объект А) и уклоняющийся (объект В), обладающие простым движением, в некоторой области О,, О, С Кп. Область О, называют поисковой областью. Модуль скорости ищущего постоянен и равен а, модуль скорости уклоняющегося не превосходит ¡5, где а а ¡3 — положительные постоянные, ¡3 < а. Объекты могут выбирать свое начальное положение и направление движения в любой момент времени, а уклоняющийся — еще и величину своей скорости, так чтобы скорости объектов были кусочно-непрерывными функциями времени, а сами объекты не выходили за пределы поисковой области. Поиск прекращается в момент обнаружения уклоняющегося ищущим, которое происходит при сближении объектов на расстояние, не превосходящее положительной постоянной I.

Необходимо найти такую траекторию ищущего, при движении по которой он гарантирует обнаружение уклоняющегося, независимо от траектории последнего. Ищущий должен выбрать свою траекторию программным способом, опираясь только на знание поисковой области О и постоянных а, /3 и I и не имея никакой информации о поведении уклоняющегося. Уклоняющийся, напротив, может выбирать свою траекторию, зная положение ищущего во все будущие моменты времени.

В последнее время для решения задач гарантированного поиска Е.В. Шикин, С.М. Губайдуллин и А.Г. Чхартишвили предложили геометрический подход, состоящий в использовании при построении поисковой траектории вспомогательных информационных множеств, вообще говоря, изменяющихся во времени (см. работы [7-11, 33-43]). Эти множества возникают при анализе возможных траекторий уклонения и, как правило, являются запретными для уклоняющегося в том смысле, что он не может в них находиться в силу условий задачи (в противном случае он был бы обнаружен ранее). Простейшими из информационных множеств являются шар (круг) обнаружения и следящая область. Особую роль играет полная остаточная область — максимальное запретное для уклоняющегося множество и область неопределенности — совокупность точек, в которых уклоняющийся объект может находиться в данный момент времени. Траекторию ищущего строят таким образом, чтобы полная остаточная область, увеличиваясь, в какой-то момент времени заполнила всю поисковую область О. С использованием геометрического метода решены задачи поиска на некоторых замкнутых поверхностях [36], в частности, на поверхности цилиндра и на торе [10].

Ф.Л. Черноусько [32] рассмотрена задача динамического поиска в приведенной постановке для плоских и трехмерных выпуклых поисковых областей. Стратегия ищущего, гарантирующая обнаружение за конечное время, в плоской выпуклой области построена при условии /3/а < 1/В, где И — ширина выпуклой области (минимальная ширина полосы, содержащей данную область). Показано, что при выполнении более слабого условия [(?)' 1 стратегия ищущего, гарантирующая обнаружение, существует. Построенная траектория зависит от параметра, относительно которого известно лишь, что он должен быть достаточно близок к 0. Для цилиндрической поисковой области с площадью основания 5 проведенное построение приводит к достаточным условиям осуществимости гарантированного поиска лишь при I2 < б1.

Способы гарантированного поиска, получаемые при решении таких задач, вообще говоря, оптимальными не являются. Условия на параметры задачи, гарантирующие завершение поиска, обычно являются лишь достаточными. Некоторые необходимые условия разрешимости задач поиска найдены П.М.Лариным [19, 20]. Однако говорить о близости необходимых и достаточных условий пока рано.

В данной работе найдены достаточные условия разрешимости задачи динамического поиска в плоских и трехмерных выпуклых областях и соответствующие стратегии ищущего, гарантирующие обнаружение уклоняющегося. Для решения задачи используются методы геометрического моделирования и компьютерной визуализации.

Информационные множества — основная составляющая геометрического подхода к решению задачи поиска — позволяют наглядно представить информацию, которой обладает ищущий о местоположении искомого. Найти их аналитически во многих случая непросто. Поэтому актуальным вопросом является визуализация поискового процесса, то есть использование средств вычислительной техники для вычисления и отображения на каком-либо графическом устройстве информационных множеств задачи поиска. Ее целью является наглядное представление изменения уровня информированности ищущего о местоположении уклоняющегося.

Визуализация поиска может быть использована несколькими способами: 1) для подтверждения теоретического результата; 2) для проверки, является ли траектория, выбранная из каких-либо неформальных соображений, поисковой; 3) для интерактивного построения траектории, когда компьютер выполняет рутинные операции (вычисление информационных множеств), а исследователь на основе неформального анализа представленной информации выбирает дальнейшее поведение ищущего объекта.

К настоящему времени удалось построить оценки области неопределенности и полной остаточной области с некоторым шагом по времени при помощи рекуррентных формул. Примеры таких формул можно найти в работах П.М.Ларина [19, 20], в работе С.Б.Березина [б]. Эти формулы используют теоретико-множественные операции, такие как пересечение, вычитание и r-расширение. Тем самым, чтобы вычислять эти области при помощи компьютера, необходима модель множеств, позволяющая реализовать эти операции алгоритмически. Алгоритмическая реализация теоретико-множественных операций рассматривалась ранее в работах В.А. Дебелова, A.M. Мацокина и С.А. Упольникова [12-14]. Однако, рассмотренный в этих работах класс множеств, ограниченных кривыми Безье, не замкнут относительно операции r-расширения. В работе С.Б.Березина [6] рассматривается более простой класс множеств, граница которых состоит из конечного числа отрезков. В этом классе результат r-расширения множества также может быть вычислен лишь приближенно.

Целью данной работы является построение поисковых траекторий в выпуклых областях. Особое внимание уделяется плоскому и трехмерному случаям. В плоском случае траектория построена, если параметры задачи удовлетворяют условию (*), в трехмерном случае найдены достаточные условия и поисковая траектория. Траектория в выпуклой области строится в два этапа. Первый этап состоит в построении поисковой траектории в некоторой простой области, объемлющей исходную. Для плоской выпуклой области такой областью является описанный прямоугольник, для трехмерной — описанный цилиндр. Затем поисковая траектория в объемлющей области (прямоугольнике, цилиндре) проектируется на исходную выпуклую поисковую область. Под проектированием понимается действие оператора, ставящего в соответствие каждой точке пространства Rn ближайшую к ней точку выпуклой области.

Поисковая траектория в прямоугольнике ищется среди ломаных определенного класса. При условии, что параметры задачи удовлетворяют соотношению (*), показано, какую именно ломаную из этого класса можно взять в качестве поисковой траектории.

Для решения задачи поиска в цилиндре предложен следующий метод. На первом шаге строится решение задачи патрулирования в поперечном круге К. Траекторией патрулирования является замкнутая кривая, при движении по которой ищущий объект не допускает пересечения уклоняющимся круга К без обнаружения. Поисковая траектория начинается на одном основании цилиндра и заканчивается на другом. Движение объекта А происходит таким образом, что его проекция на круг К перемещается по траектории патрулирования.

Целью работы является также построение алгоритмов вычисления оценок информационных множеств задачи поиска на плоскости для визуализации поискового процесса при помощи средств вычислительной техники.

Вводится класс плоских множеств, замкнутый относительно необходимых для вычисления оценок информационных множеств операций — пересечения, вычитания и г-расширения. Этот класс состоит из множеств, границу которых можно представить в виде объединения конечного числа отрезков, дуг окружностей и изолированных точек. Предлагается структура данных для представления любого множества из рассматриваемого класса. Показано, как, оперируя с этой структурой, можно вычислять характеристическую функцию множества, пересечение множеств, дополнение множества, расширение множества и другие теоретико-множественные операции.

Работа состоит из введения, двух глав и списка литературы. Главы состоят из разделов, некоторые разделы состоят из нескольких параграфов. При необходимости текст иллюстрируется рисунками. Нумерация формул, определений, теорем и утверждений, начинается заново в каждой из глав с указанием номера главы, нумерация рисунков — сквозная во всей диссертации.

1. Koopman В.О. Theory of search: 1. Kinematic bases // Oper. Research, 1956, V.4, №.

2. Koopman B.O. Theory of search: II. Target detection // Oper. Research, 1956, V.4, №5.

3. Koopman B.O. Theory of search: III. The optimum distribution of searching efforts // Oper. Research, 1957, V.5, №5.

4. Абчук В.А., Суздаль В.Г. Поиск объектов. М., 1977.

5. Айзеке Р. Дифференциальные игры. М., Мир, 1967.

6. Березин С.Б. Теоретико-множественные операции в задаче визуализации переменных информационных множеств. М., Деп. в ВИНИТИ 24 января 2000 г., №127-ВОО.

7. Губайдуллин С.М. Анализ одной стратегии в плоской задаче обнаружения. М., Деп. в ВИНИТИ, 1990, Ш750-В90.

8. Губайдуллин С.М. Построение переменной контролируемой области в задаче поиска на плоскости при заданной траектории движения. М., Деп. в ВИНИТИ 3 июля 1990, Ш751-В90.

9. Губайдуллин С.М. Следящая область в задачах поиска. М., Деп. в ВИНИТИ, 1992, №2020-В92.

10. Губайдуллин С.М., Шикин Е.В. Следящие области на цилиндре и на торе // Вестник московского университета. Сер. 15. Вычислительная математика и кибернетика, 1992, №2, С.46-50.

11. Губайдуллин С.М., Чхартишвили А.Г., Шикин Е.В. Геометрические свойства следящей области в задаче поиска // Международная конференция "Лобачевский и современная геометрия", Казань, 18-22 августа 1992 г., Тезисы докладов, 1992, 4.1, С.27-28.

12. Дебелов В.А., Мацокин A.M., Упольников С.А. Разбиение плоскости кривыми Безье // Труды 7-ой международной конференции по компьютерной графике и визуализации Графикон'97 (21-24 мая 1997, Москва), Протвино, 1997, С.67-74.

13. Дебелов В.А., Мацокин A.M., Упольников С.А. Разбиение плоскости и теоретико-множественные операции // Сибирский журнал вычислительной математики / РАН. Сибирское отделение, Новосибирск, 1998, Т.1, т.

14. Дебелов В.А., Мацокин A.M. Алгоритм реализации теоретико-множественных операций // Труды 8-ой международной конференции по компьютерной графике и визуализации Графикон'98 (7-11 сентября 1998, Москва), ВМК МГУ, 1998, С.174-181.

15. Ким Д.П. Методы поиска и преследования подвижных объектов. М., Наука, 1989.

16. Красовский H.H., Субботин А.И. Позиционные дифференциальные игры. М., Наука, 1974.

17. Ларин П.М. Упреждающая область, порождаемая парой ищущих, и ее визуализация. М., Деп. в ВИНИТИ, 1995, №2910-В95.

18. Ларин П.М. Следящая область пары отрезков // Фундаментальная и прикладная математика, 1998, Т.4, Вып.2, С.559-566.

19. Ларин П.М. О невозможности гарантированного поиска в достаточно большой области. М., Деп. в ВИНИТИ 26 мая 1998, №1629-В98.

20. Ларин П.М. О неразрешимости задач гарантированного поиска в достаточно большой области // Вестник Московского университета, Сер.15, Вычислительная математика и кибернетика, 2000, №1, С.44-47.

21. Петросян Л.А., Зенкевич H.A. Оптимальный поиск в условиях конфликта. Л., 1987.

22. Петросян Jl.А., Гарнаев А.Ю. Игры поиска. СПб., Издательство Санкт-Петербургского университета, 1992.

23. Скворцов A.A. Условия разрешимости поисковой задачи ищущий-уклоняющийся на бесконечном цилиндре. М., Деп. в ВИНИТИ 23 июня 1994 г., Ш565-В94.

24. Скворцов A.A. Динамический поиск в плоской выпуклой области. М., Деп. в ВИНИТИ 10 ноября 1995 г., №2985-В95.

25. Скворцов A.A. Динамический поиск в выпуклых областях // Фундаментальная и прикладная математика, 1998, Т.4, Вып.2, С.785-790.

26. Скворцов A.A. Траектория патрулирования в задаче динамического поиска. М., Деп. в ВИНИТИ 13 мая 1998 г., Ш456-В98.

27. Скворцов A.A. Динамический поиск в трехмерных выпуклых областях // Вестник московского университета. Сер.15. Вычислительная математика и кибернетика, 1999, №3, С.20-24.

28. Скворцов A.A. Алгоритмическая реализация теоретико-множественных операций на плоскости. М., Деп. в ВИНИТИ 10 июля 2000 г., Ш915-В00.

29. Хеллман О. Введение в теорию оптимального поиска. М., 1985.

30. Черноусько Ф.Л., Меликян A.A. Игровые задачи управления и поиска. М., 1978.

31. Черноусько Ф.Л. Управляемый поиск подвижного объекта // Прикладная математика и механика, 1980, Т.44, Вып.1, С.3-12.

32. Чхартишвили А.Г, Об одном геометрическом свойстве следящей области в двумерной задаче поиска. М., Деп. в ВИНИТИ 3 января 1991, ДО60-В91.

33. Чхартишвили А.Г. Об одном геометрическом свойстве следящей области в задачах поиска // Вестник Московского университета, Сер.1, Математика. Механика. 1992, №3, С.7-10.

34. Чхартишвили А.Г., Шикин Е.В. Метод следящих областей в задачах поиска // Математический сборник, 1993, Т.184, №10, С.107 134.

35. Чхартишвили А.Г., Шикин Е.В. Динамические задачи поиска и обнаружения на некоторых замкнутых поверхностях // Дифференциальные уравнения, 1993, Т.29, №11, С.1948-1957.

36. Чхартишвили А.Г., Шикин Е.В. Задачи поиска и обнаружения на некоторых поверхностях // Понтрягинские чтения-1У. Весенняя воронежская математическая школа. Тезисы докладов (3-8 мая 1993 г.), Воронеж, 1993, С.205.

37. Чхартишвили А.Г. О феномене тонкой следящей области в задаче динамического поиска. М., Деп. в ВИНИТИ, 1994, Ш445-В94.

38. Чхартишвили А.Г., Шикин Е.В. Об одном геометрическом подходе к решению динамических игр поиска // Дифференциальные уравнения, 1994, Т.ЗО, №6, С.1097-1098.

39. Чхартишвили А.Г., Шикин Е.В. Следящая область в пространстве Лобачевского // Вестник Московского университета. Сер.1. Математика. Механика. 1994, №2, С.36-41.