Динамический поиск в выпуклых областях и его визуализация

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

Первые публикации по теории поиска стали появляться после Второй мировой войны в результате исследований как отечественных, так и зарубежных военных специалистов, таких как Б: О. Купман [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.