Введение
1. Анализ методов и алгоритмов планирования траектории 11
1.1 Предметная область 11
1.2 Задача планирования как задача поиска пути на графе 17
1.3 Методы поиска пути на графе 20
1.3.1 Поиск пути на графе как расчет g -3Ha4euuu 20
1.3.2 Эвристические алгоритмы поиска пути 25
1.3.3 Обзор работ, посвященных алгоритмам поиска пути на графе для задачи планирования траектории 31
1.3.4 Выводы 36
1.4 Методы построения графов для решения задачи планирования траектории 37
1.4.1 Методы построения графов видимости 37
1.4.2 Методы построения разбиения Вороного 42
1.4.3 Методы извлечения графовых моделей непосредственно из цифровой карты местности
1.4.4 Выводы 48
1.5. Выводы 50
2. Метрические топологические графы и их применение в задачах планирования траектории 51
2.1. Основные определения 51
2.2 Метрики на МТ-графах 56
2.2.1 Метрика кратчайшего пути 56
2.2.2 Диагональная метрика
2.3 эвристический поиск пути на мт-графах 60
2.4 проблема локального минимума 65
2.5 Выводы 69
3. Иерархический подход к задаче поиска пути на МТ графе 70
3.1 Множество кратчайших путей на мт-графе 70
3.1.1 Операция поворота и взаимное расположение клеток МТ-графа 70
3.1.2 Структура множества кратчайших путей полностью проходимого МТ-графа 76
3.1.3 Нуль-траектории на МТ-графе 89
3.2 Простейшие иерархические алгоритмы поиска пути на мт-графе 92
3.2.1 Основные определения и утверждения 92
3.2.2 Простейшие реализации иерархического подхода к поиску пути на МТ-графе 96
3.3 Алгоритм HGA 99
3.3.1. Препятствия на МТ-графе 99
3.3.2 Стратегия выделения опорных клеток алгоритма HGA 108
3.3.3 Базовая реализация алгоритма HGA 109
3.3.4 Теоретические свойства базовой реализации алгоритма HGA 116
3.3.5 Эвристическая реализация алгоритма HGА 130
3.4. Выводы 140
4. Экспериментальное обоснование эффективности алгоритманса 142
4.1 Программно-аппаратный комплекс для проведения экспериментов 142
4.1.1 Аппаратный комплекс 142
4.1.2 Программный комплекс 142
4.2 Первая серия экспериментов 145
4.3. Вторая серия экспериментов 157
4.4. Третья серия экспериментов 161
4.5. Выводы 165
Заключение 166
Список литературы 168
