
Тип работы:	Предмет:	Язык работы:

РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ТРАЕКТОРИИ ОБЪЕЗДА ПРЕПЯТСТВИЙ АВТОМОБИЛЕМ

Работа №	83041
Тип работы	Бакалаврская работа
Предмет	информатика
Объем работы	83
Год сдачи	2016
Стоимость	4880 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	227

Не подходит работа?

Узнай цену на написание

Содержание

ВВЕДЕНИЕ 6
1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ 8
1.1 АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМЫ АВТОНОМНОГО УПРАВЛЕНИЯ АВТОМОБИЛЯМИ 8
1.2 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ АВТОНОМНЫХ АВТОМОБИЛЕЙ 9
1.3 ОПТИМАЛЬНАЯ ТРАЕКТОРИЯ 11
2 АВТОНОМНОЕ ТРАЕКТОРНОЕ УПРАВЛЕНИЕ 14
2.1 МОДЕЛЬ ДИНАМИКИ ДВИЖЕНИЯ ТРАНСПОРТНОГО СРЕДСТВА 14
2.2 АРХИТЕКТУРА ПРОГРАММЫ УПРАВЛЕНИЯ АВТОМОБИЛЕМ 16
2.3 АЛГОРИТМЫ ПОСТРОЕНИЯ ТРАЕКТОРИИ 18
2.4 УЧЕТ ОГРАНИЧЕНИЙ ДВИЖЕНИЯ АВТОМОБИЛЯ 28
2.5 ВЫБОР АЛГОРИТМА ПЛАНИРОВАНИЯ ПУТИ 32
3 РЕАЛИЗАЦИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 34
3.1 ВЫБОР И ОБОСНОВАНИЕ ЯЗЫКА ПРОГРАММИРОВАНИЯ И СРЕДЫ РАЗРАБОТКИ 34
3.2 РАЗРАБОТКА ИНТЕРФЕЙСА ПРОГРАММЫ 34
3.3 РАСПОЛОЖЕНИЕ ПРЕПЯТСТВИЙ 36
3.4 РЕАЛИЗАЦИЯ АЛГОРИТМА RRT 40
3.5 СГЛАЖИВАНИЕ ПУТИ 43
3.6 РЕАЛИЗАЦИЯ АЛГОРИТМА ДУБИНСА 45
3.7 ТЕСТИРОВАНИЕ 49
ЗАКЛЮЧЕНИЕ 55
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 57
ПРИЛОЖЕНИЕ

Введение

Многие годы люди мечтали о создании автомобилей, способных ездить без
вмешательства водителя. В настоящее время ведется множество разработок в сфере
автомобилестроения с целью создания полностью роботизированных автомобилей.
Уже сегодня существуют автомобили, которые могут передвигаться по дороге самостоятельно, но в критических ситуациях все же необходимо вмешательство человека.
Автономные транспортные средства весьма полезны для общества, так как в
перспективе их использование позволит снизить количество дорожно-транспортных
происшествий, снизить затраты в транспортной отрасли, уменьшить количество
пробок на дорогах, а также они позволят быть независимыми многим людям, которые не могут управлять транспортными средствами из-за возраста или ограничений
здоровья.
Автономия транспортного средства на дороге требует надежной системы планирования движения. Система планирования движения создает траекторию движения транспортного средства в течение нескольких секунд, используя информацию,
предоставленную системой восприятия о текущем состоянии автомобиля, состоянии
дороги впереди и местоположения других транспортных средств и объектов на дороге.
Важным условием планировщика является скорость предоставления данных
об изменениях на дороге. Это сложная задача для генерации траектории движения,
так как в сложных дорожных ситуациях необходима быстрая реакция системы, во
избежание аварийных ситуаций.
Планирование движения охватывает множество областей, например, вычисление белковых взаимодействий, человеческая походка, создание динамических траекторий для летательных аппаратов, вождение наземных транспортных средств по
пересеченной местности. Для решения этих разрозненных задач используется широкий спектр методов. Поэтому необходимо сузить нашу сферу задач до планирования
движения автономных транспортных средств на дороге.7
Для построения траекторий в различных дорожных ситуациях необходимо
осуществить алгоритмы для объезда препятствий, возникающих перед автономным
транспортным средством. Поэтому целью данной работы будет разработка программного модуля для построения квазиоптимальной траектории объезда препятствий, обеспечивающий безопасный объезд препятствий произвольной формы.
Для достижения данной цели необходимо решить ряд задач:
 анализ математической модели движения транспортного средства;
 анализ существующих алгоритмов построения траекторий;
 реализация алгоритма построения траектории;
 тестирование программной реализации алгоритма.

Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!

ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ

Курсовые Статьи Диплом Рязань

Заключение

В данной работе было произведено исследование предметной области поиска
траекторий движения робота. После проведения анализа существующих алгоритмов
поиска траекторий, был выбран и реализован алгоритм быстро разворачивающегося
случайного дерева. Использование этого алгоритма позволяет получать траектории
с высокой скоростью.
Траектория, получаемая алгоритмом RRT, в результате оказывалась слишком
извилистой, поэтому, чтобы исправить этот недостаток был разработан алгоритм
для сокращения траекторий. В итоге это позволило значительно уменьшить длину
получаемых траекторий, тем самым приблизить их к оптимальным.
Для того чтобы автомобиль мог двигаться по получаемым траекториям необходимо учитывать кинематические ограничения транспортного средства, которые
зависят от его маневренности и скорости. Для решения этой задачи был проанализирован алгоритм построения кривых Дубинса. Использование кривых Дубинса позволило получить траекторию, состоящую из кусочных дуг. Тем самым это позволило учитывать кинематические ограничения автомобиля, а именно минимальный
радиус поворота автомобиля.
Описанные алгоритмы были реализованы в программе, написанной на языке
MATLAB. Во время работы программы пользователь может осуществлять ввод
препятствий, располагать автомобиль в любой точке рабочей области, кроме мест
расположения препятствий, так же располагается и конечная точка траектории. После того, как построена карта препятствий и установлены начало и конец траектории, можно запустить поиск траектории. Построенную карту препятствий можно
сохранить в файл для дальнейшего его использования. Для создания новой карты
препятствий необходимо совершить сброс, для чего создана специальная клавиша.
При нажатии на нее совершается очистка рабочей области.
Скорость поиска траекторий зависит от загруженности участка препятствиями
и от дистанции между начальной и конечной вершиной.56
Был проведен ряд испытаний разработанной программы, проведен анализ полученных в ходе испытаний результатов и выявлены слабые стороны алгоритма.
Слабыми сторонами программы являются:
1. недостаточное быстродействие программы;
2. не учтена возможность движения автомобиля задом.
Оба этих недостатка решаемы. Для решения проблемы быстродействия необходимо совершить распараллеливание кода, для возможности работы программы с
использованием многоядерных ЦП ЭВМ. Модернизация алгоритма поиска траекторий, может так же позволить сократить время поиска траекторий движения. Для
учета движения автомобиля задом необходимо модифицировать построение кривых
Дубинса.
После адаптации программы для использования в параллельной архитектуре
и добавления учета движения автомобиля задним ходом результатом станет не
только значительное ускорение процесса построения траекторий, но так же это повлияет и на длину получаемых траекторий. Учет возможности движения автомобиля
задом позволит совершать развороты автомобиля на месте, что значительно сократит длину получаемых траекторий.

Литература

1 Нгуен Т. Н. Бортовая информационно-измерительная и управляющая система беспилотного автомобиля для циклических тестовых заездов: дис. ... канд. техн. наук. Рязанский гос. радиотехнический университет, Рязань, 2014.
2 Wang and Qi. Trajectory Planning for a Four-Wheel-Steering Vehicle, 2001.
3 LaValle S.M. Planning algorithms / Cambridge University Press. - University of Illinois. - 2006. - 786 p.
4 Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. - 1959. - №1. - P. 269-271.
5 Hart P.E., Nilsson N.J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // Systems Science and Cybernetics, IEEE Transactions 1968. - V. 4. - issue 2. - P. 100-107.
6 Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. — 1985. — Т. 32, № 3. — С. 505 — 536.
7 Dolgov D., Thrun S., Montemerlo M., Diebel J. Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments // The International Journal of Robotics Research. - 2010. - №29. - P. 485-501.
8 Koenig S., Likhachev M. D* Lite // AAAI/IAAI. - 2004. - V. 25. - №2. - P. 99-112
9 Wilmarth S. A., Amato N. M., Stiller P. F. MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space // IEEE International Conference on Robotics and Automation. - 1999. - P. 1024-1031.
10 Voronoi G. Nouvelles applications des parametres continus a la theorie des formes quadratiques. Deuxieme memoire. Recherches sur les parallelloedres primitifs // Journal fur die reine und angewandte Mathematik. - 1908. - V. 134. - P. 198-287
11 Boor V., Overmars M.H., Stappen A.F. The Gaussian sampling strategy for probabilistic roadmap planners // IEEE International Conference on Robotics and Automation. - 1999. - V. 1. - P. 473-479.
12 Schwarzer F., Saha M., Latombe J.-C. Adaptive Dynamic Collision Checking for Single and Multiple Articulated Robots in Complex Environments // IEEE Transactions on Robotics. - 2005. - P. 338-353
13 Polden J., Pan Z., Larkin N., Van Duin S. Path Planning with a Lazy Significant Edge Algorithm (LSEA) // International Journal of Advanced Robotic Systems. - 2013. - V. 10. - P. 1-8.
14 Lindemann S. R. and LaValle S. M., “Incrementally reducing dispersion by increasing Voronoi bias in RRTs,” in Proceedings IEEE International Conference on Robotics and Automation, 2004.
15 Пыхтин П.С., Камаев В.А., Крыжановский А.И., Никляев И.Ю., Пыхтин П.С. — Планирование траектории движения мобильного робота с использованием градиента функции исследования областей пространства конфигураций // Кибернетика и программирование. - 2014. - № 1. - С. 48 - 60. DOI: 10.7256/2306¬4196.2014.1.9828 URL: http://e-notabene.ru/kp/article_9828.html
16 Dubins L.E. On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents // American Journal of Mathematics 79 (3): 497-516, July 1957
17 Farin G., Sapidis N. Automatic Fairing Algorithm for B-Spline Curves // Computer-Aided Design. — 1990. — Vol. 22. — P. 121—129.
18 Farin G., Sapidis N. Curvature and the Fairness of Curves and Surfaces // IEEE Computer Graphics and Applications. — 1989. — Vol. 9, № 2. — P. 52—57. 2.
19 Пестерев Л.В., Гилимьянов Р.Ф. Планирование пути для колесного робота // Проблемы вычислений в распределенной среде: распределенные приложения, коммуникационные системы, математические модели и оптимизация / Труды ИСА РАН. - Москва, 2006. - Т. 25. — С. 204-211.
20 Позняк Э. Г., Шикин Е. В. Дифференциальная геометрия./ Э. Г. Позняк, Е. В. Шикин. - М.: УРСС, 2003.
21 Кетков Ю. Л., Кетков А. Ю., Шульц М. М. MATLAB 7: программирование, численные методы / Ю. Л. Кетков, А. Ю. Кетков, М. М. Шульц. - СПб.: БХВ- Петербург, 2005. - 752с.: ил.
22 Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа./ Е. С. Половинкин, М. В. Балашов. — М.: ФИЗМАТЛИТ, 2004. — 416 с.
23 Рэндал У. Б., Тимоти У. М. Малые беспилотные летательные аппараты. Теория и практика /При поддержке ОАО «111111 «Радар ммс» перевод с англ. под ред. к.т.н. Г.В. Анцева. - Москва: ТЕХНОСФЕРА, 2014. -312 с.
24 Chitsaz H. and LaValle S. M. Time-optimal Paths for a Dubins Airplane Proceedings of the 46th IEEE Conference on Decision and Control (CDC), 2007