Графический подход к исследованию и решению задач динамического поиска

• Автор: Березин, Сергей Борисович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 131 с. : ил

Содержание
Введение

Глава 1. Аппроксимации информационных множеств

1.1 Основные определения

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

2 Круги обнаружения

3 Область неопределенности

4 Остаточная область

5 Общая упреждающая область .

6 Общая следящая область.

1.2 Аппроксимация информационных множеств.

1 Аппроксимация области неопределенности.
2 Построение вспомогательных множеств
3 Аппроксимация общей остаточной области.
4 Аппроксимация общей упреждающей области .
5 Свойства аппроксимаций информационных множеств .
Глава 2. Алгоритмическая реализация
2.1 Теоретикомножественные операции на плоскости.
1 Способы компьютерного представления множеств.
2 Класс представимых на компьютере множеств
3 Структуры данных для представления границ множеств .
4 Решение вспомогательных задач
5 Вычисление характеристической функции
6 Реализация теоретикомножественных операций
7 Операция грасширешш множества.
8 Регуляризованная аппроксимация грасширения
9 Упрощение границы множества
2.2 Теоремы вложения для информационных множеств
1 Свойства регуляризованных операций.
2 Регуляризованная аппроксимация области
неопределенности.
3 Регуляризованные аппроксимации остаточной и
упреждающей областей.
Глава 3. Методы решения поисковых задач
3.1 Визуализация процесса поиска
3.2 Расчет достаточных ресурсов.
1 Расчет минимального радиуса круга обнаружения
2 Расчет минимальной скорости .
3.3 Поиск в монотонном многоугольнике
1 Патрулирование горизонтального сечения
монотонного многоугольника.
2 Вытеснение уклоняющегося объекта.
3 Достаточные условия для поиска в монотонном
многоугольнике.
4 Алгоритм построения поисковой траектории.
5 Сравнение с другими методами.
3.4 Поиск в кольце
1 Поиск в кольце.
2 Изменение направления вытеснения в многоугольнике .
3 Поиск в многоугольной области .
4 Оптимизация поиска.
5 Дальнейшее развитие
Литература


Обзор результатов, полученных при геометрическом подходе к решению поисковых задач, и список литературы даны в работе [2|. Геометрический подход был использован и при решении задачи поиска одним ищущим объектом на некоторых классах замкнутых поверхностей 0] и в двух- и трехмерных выпуклых областях (, ]. Вопрос о необходимых условиях осуществимости поиска, также как вопрос о построении оптимальных траекторий, пока остаются открытыми. В работе П. М. Ларина (] получены необходимые условия для некоторых постановок задач поиска, но пока они далеки от достаточных. Информационные множества для случая нескольких ищущих объектов рассматривались лишь в небольшом числе работ (см. Также мало изучен вопрос поиска в невыпуклых областях. Это связано с тем, что при увеличении количества ищущих объектов или при усложнении структуры области поиска трудности при построении информационных множеств значительно возрастают. В таких случаях аналитические методы построения информационных множеств перестают быть эффективным и разумно воспользоваться вычислительными и графическими возможностями современных компьютеров. Ясно, что построенные на компьютере аппроксимации информационных множеств имеют практическую ценность лишь в том случае, когда они сохраняют основные свойства аппроксимируемых множеств. В частности, аппроксимация области неопределенности должна содержать реальную область неопределенности. Только тогда можно утверждать, что вне построенной аппроксимации уклоняющегося объекта нет, и делать обоснованные суждения на основе результатов расчетов. Поэтому задача построения аппроксимаций информационных множеств на компьютере естественным образом разделяется на две части: построение формул, позволяющих за конечное число шагов строить аппроксимации, обладающие нужными свойствами, и разработка алгоритма вычисления по этим формулам, сохраняющего свойства моделируемых множеств. Рекуррентные формулы для аппроксимаций информационных множеств с обоснованием их свойств рассматриваются, например, в работах П. М. Ларина [, ]. В диссертационной работе приведены и обоснованы рекуррентные формулы для области неопределенности, остаточной и упреждающей областей на заданных временных промежутках в задаче поиска с участием нескольких ищущих объектов. Вопросам разбиения плоскости кривыми Безье и алгоритмической реализации операций над множествами на плоскости посвящены работы В. А. Дебелова, А. М. Мацокина и С. А. Упольникова [-]. В этих работах классические теоретико-множественные операции заменяются на регуляризованные или логические, широко применяемые в системах геометрического моделирования и автоматического проектирования. Применение регуляризованных операций позволяет избежать появления множеств, границы которых будут включать разрезы или изолированные точки и отрезки прямых. Однако класс множеств, рассмотренный в этих работах, не замкнут относительно г-расширения множества. Другая схема алгоритмической реализации операций над множествами, предложенная A. A. Скворцовым [], допускает применение классических теоретико-множественных операций и является замкнутой относительно операции r-расширения множества. К сожалению, в перечисленных выше работах вопросу влияния погрешности компьютерного представления действительных чисел [-] на результаты вычислений уделено недостаточное внимание. Как показывает практика, ошибки округления, неизбежно возникающие при работе с действительными числами, могут приводить к неточным результатам и даже к нарушению логической структуры данных, например, к нарушению структуры границы множества. В работе () рассмотрен один из методов борьбы с ошибками округления и приведен обширный список литературы, посвященной этому вопросу. Целью диссертационной работы является построение и обоснование алгоритмов, позволяющих строить на компьютере аппроксимации информационных множеств, сохраняющие основные свойства аппроксимируемых множеств. Предложенный численный метод применяется для построения поисковых траекторий и определения минимальных достаточных ресурсов в задачах динамического поиска в невыпуклых областях для нескольких ищущих объектов.