Исследование методов и разработка алгоритмов автоматического планирования траектории на плоскости

• Автор: Яковлев, Константин Сергеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 184 с. : ил.

Оглавление
ВВЕДЕНИЕ и

АКТУАЛЬНОСТЬ ТЕМЫ.

Цели и задачи исследования

Методы исследования.

Научная новизна работы и результаты, выносимые на защиту

Практическая значимость работы

Апробация работы

Публикации.

Структура и объем работы

Основное содержание работы

1. АНАЛИЗ МЕТОДОВ И АЛГОРИТМОВ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ.
1.1 Предметная область.
. 1.2 Задача планирования как задача поиска пути на графе
1.3 Методы поиска пути на графе
1.3.1 Поиск пути па графе как расчет значений
1.3.2 Эвристические алгоритмы поиска пути.
1.3.3 Обзор работ, посвященных алгоритмам поиска пути на графе для задачи планирования траектории
1.3.4 Выводы.
1.4 МЕТОД,I ПОСТРОЕНИЯ ГРАФОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ
1.4.1 Методы построения графов видимости.
1.4.2 Методы построения разбиения Вороного.
1.4.3 Методы извлечения графовых моделей непосредственно из цифровой карты местности .
1.4.4 Выводы.
1.5. Выводы
2. МЕТРИЧЕСКИЕ ТОПОЛОГИЧЕСКИЕ ГРАФЫ И ИХ ПРИМЕНЕНИЕ В ЗАДАЧАХ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ
2.1. Основные определения
2.2 Метрики на МТграфах.
2.2.1 Метрика кратчайшего пути.
2.2.2 Диагональная метрика.
2.3 Эвристический поиск пути на МТграфах
2.4 Проблема локального минимума.
2.5 Выводы.
3. ИЕРАРХИЧЕСКИЙ ПОДХОД К ЗАДАЧЕ ПОИСКА ПУТИ НА МТГРАФЕ
3.1 Множество кратчайших путей на МТграфе.
3.1.1 Операция поворота и взаимное расположение клеток МТграфа
3.1.2 Структура множества кратчайших путей полностью проходимого МТграфа
3.1.3 Нультраектории на МТграфе
3.2 Простейшие иерархические алгоритмы поиска пути на МТграфе.
3.2.1 Основные определения и утверждения.
3.2.2 Простейшие реализации иерархического подхода к поиску пути на МТграфе.
3.3 Алгоритм НЮА
3.3.1 Препятствия на МТграфе.
3.3.2 Стратегия выделения опорных клеток алгоритма 1ЮА .
3.3.3 Базовая реализация алгоритма НС А
3.3.4 Теоретические свойства базовой реализации алгоритма НСА
3.3.5 Эвристическая реализация алгоритма НСА
3.4. ВЫВОДЫ
4. ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА НСА.
4.1 Программноаппаратный комплекс для проведения экспериментов
4.1.1 Аппаратный комплекс
4.1.2 Программный комплекс.
4.2 Первая серия экспериментов.
4.3. Вторая серия экспериментов
4.4. Третья серия экспериментов
4.5. Выводы
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


Тогда задача планированиятраектории» состоит в-построении: кривой в пространстве, соединяющей точку, соответствующую1 текущему положению БТС, с точкой соответствующей- целевому положению БТС. Другими словами задача планирования траектории БТС - есть задача построения кривой на плоскости или в трехмерном пространстве. Эвклидово пространство - наиболее «естественная» формальная модель, которая может быть использована для постановки, задачи планирования траектории БТС. Использование этой модели позволяет говорить об окружающей среде БТС просто как о «пространстве»; а об-элементах этого- пространства, как о «точках». Эти? С учетом того, что некоторые точки- пространства^ могут соответствовать непроходимым для БТС областям окружающей среды, определение задачи планирования траектории БТС можно скорректировать следующим образом. Кривая, соответствующая траектории, должна содержать только точки, соответствующие проходимым областям окружающей БТС среды. Или - более кратко - траектория должна быть проходимой. Решение задачи планирования траектории может быть получено как в явном, так и в неявном виде. В первом случае решение представляет собой последовательность точек, во втором — алгоритм, пригодный к исполнению системой управления БТС, для следования по искомой траектории. В качестве критерия оптимальности могут выступать как доменонезависимые факторы, такие как длина траектории, или ее гладкость, так и факторы специфичные для решения задачи управления конкретным БТС - построение такой траектории, которая минимизирует энергетические затраты БТС и т. Окружающая среда может быть, как статической, так и динамической. С формальной точки зрения динамическая среда может быть описана в виде пространства, проходимость каждой точки которого меняется во времени. Среда может быть как полностью, так и частично наблюдаемой для БТС. Последнее обозначает, что информация о проходимости некоторого множества точек пространства априори недоступна. Геометрия непроходимых областей пространства. Множества смежных непроходимых точек пространства образуют непроходимые области - многоугольники (если речь и- планировании траектории на плоскости) и многогранники. Геометрические свойства этих фигур, например - выпуклость, могут быть положены в основу классификации задач планирования траектории. БТС, принято выделять два типа задач планирования траектории, исходя из свойств окружающей среды, в которой функционирует БТС: открытая и закрытая задачи планирования траектории. Когда речь идет о закрытой задачи планирования траектории, то подразумевается, что БТС осуществляет свою деятельность внутри некоторого объекта (лабиринта, здания, комнаты и т. Рис. Закрытая задача планирования траектории. Когда речь идет об открытой задачи планирования траектории, то подразумевается, что БТС перемещается по открытой местности, «снаружи» зданий, строений, препятствий и т. То есть, фактически, речь идет о том, что большая часть пространства является проходимой областью, содержащей «вкрапления» непроходимых областей, соответствующих «препятствиям» -см. Рис. Открытая задача планирования траектории. Исходные данные для построения решения задачи планирования траектории. Когда задача планирования траектории рассматривается в контексте разработки СУ БТС, то важным является вопрос - какой информацией обладает СУ БТС (в частности модуль планирования) для ее решения. Так задача планирования может решаться, исходя только из показаний различных датчиков БТС (реактивное планирование), или же наоборот - исходя из априорных знаний об окружающей среде (делиберативное планирование). В качестве средств хранения подобных знаний обычно выступает цифровая карта местности (ЦКМ), которая постоянно хранится в оперативной памяти вычислителя БТС. На практике обычно распространен смешанный подход, когда ЦКМ обновляется исходя из показаний датчиков в режиме реального времени, а планирование траектории осуществляется по обновленной ЦКМ. Важно заметить, что ЦКМ являются дискретными моделями окружающей среды. Так в двумерном случае (при навигации БТС на/в плоскости) ЦКМ обычно представляют из себя матрицу элементам которой соответствуют проходимые и непроходимые области пространства.