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

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

Работа №	46027
Тип работы	Магистерская диссертация
Предмет	информатика
Объем работы	83
Год сдачи	2018
Стоимость	5740 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	324

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

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

Содержание

ВВЕДЕНИЕ 6
1 ОБЗОР СОВРЕМЕННЫХ ПОДХОДОВ И РЕШЕНИЙ В ОБЛАСТИ ПЛАНИРОВАНИЯ ПУТИ
АВТОНОМНЫХ ТРАНСПОРТНЫХ СРЕДСТВ 8
1.1 АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМЫ АВТОНОМНОГО УПРАВЛЕНИЯ АВТОМОБИЛЯМИ 8
1.2 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ АВТОНОМНЫХ АВТОМОБИЛЕЙ 9
1.3 МОДЕЛЬ ДИНАМИКИ ДВИЖЕНИЯ ТРАНСПОРТНОГО СРЕДСТВА 13
1.4 ОПТИМАЛЬНАЯ ТРАЕКТОРИЯ 17
1.5 МЕТОДЫ И АЛГОРИТМЫ НАВИГАЦИИ РОБОТОВ 19
1.6 УЧЕТ ОГРАНИЧЕНИЙ ДВИЖЕНИЯ АВТОМОБИЛЯ 31
1.7 СУЩЕСТВУЮЩИЕ РЕШЕНИЯ 35
2 ОПТИМИЗАЦИЯ ЛОКАЛЬНЫХ ТРАЕКТОРИЙ ОБЪЕЗДА ПРЕПЯТСТВИЙ 39
2. 1 ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ 39
2.2 АЛГОРИТМ ОПТИМИЗАЦИИ 42
2.3 ЗАДАЧА ПРЕДСТАВЛЕНИЯ ГИПЕРГРАФА 45
2.4 ОПТИМИЗАЦИЯ ГИПЕРГРАФА 47
2.5 ОПТИМИЗАЦИЯ ШТРАФНОЙ ФУНКЦИЙ 49
3 ИНТЕГРАЦИЯ АЛГОРИТМА 53
3.1 ВЫБОР СРЕДЫ РАЗРАБОТКИ И ТЕСТИРОВАНИЯ 53
3.2 НАСТРОЙКА РОБОТА И ПАКЕТОВ 57
3.3 ПОСТРОЕНИЕ КОНТУРА РОБОТА 61
3.4 ИНТЕГРАЦИЯ С ROS NAVIGATION 63
4 ПРОВЕДЕНИЕ ТЕСТОВЫХ ИСПЫТАНИЙ 65
4.1 ИНТЕРФЕЙСЫ 65
4.2 ПРОВЕРКА РАБОТЫ АЛГОРИТМА ПРИ РАЗЛИЧНЫХ ВЕСОВЫХ ЗНАЧЕНИЯХ КРИТЕРИЕВ 68
4.3 ПРОВЕДЕНИЕ ИСПЫТАНИЯ В СРЕДЕ СИМУЛЯЦИИ STAGE 71
ЗАКЛЮЧЕНИЕ 78
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 80

Введение

В настоящее время ведется множество разработок в сфере автомобилестроения с целью создания полностью роботизированных автомобилей. Уже сегодня существуют автомобили, которые могут передвигаться по дороге самостоятельно, но в
критических ситуациях все же необходимо вмешательство человека.
Автономные транспортные средства весьма полезны для общества, так как в
перспективе их использование позволит снизить количество дорожно-транспортных
происшествий, снизить затраты на грузоперевозки товаров, уменьшить количество
пробок на дорогах, а также они позволят быть независимыми многим людям, которые не могут управлять транспортными средствами из-за возраста или ограничений
здоровья.
Автономия транспортного средства на дороге требует надежной системы
навигации. Одной из важных частей навигации является система планирования
движения. Алгоритмы планирования движения должны создавать траекторию движения транспортного средства в режиме реального времени, используя информацию, предоставленную системой восприятия о текущем состоянии автомобиля, состоянии дороги впереди и местоположения других транспортных средств и объектов
на дороге.
Важным требованием к планировщику является скорость предоставления данных об изменениях на дороге. Это является сложной задачей для генерации траектории движения, так как в дорожных ситуациях необходима быстрая реакция системы
во избежание аварийных ситуаций.
Так же не менее важным требованием является оптимальность формируемых
траекторий. Учет оптимальности формируемых траекторий позволит роботам быть
эффективнее по сравнению с человеком, а именно тратить меньше времени на прохождение пути.
Планирование движения охватывает множество областей, например, человеческая походка, создание динамических траекторий для летательных аппаратов, вождение наземных транспортных средств по пересеченной местности. Для решения
этих разрозненных задач используется широкий спектр методов. Поэтому необхо7
димо сузить нашу сферу задач до планирования движения автономных транспортных средств на дороге.
Для построения оптимальных траекторий движения автономного транспортного средства необходимо реализовать алгоритм оптимизации траектории объезда
препятствий, возникающих перед автономным транспортным средством. Поэтому
целью данной работы является разработка программного модуля планирования локальных траекторий для определения оптимальных траекторий движения автономного транспортного средства, обеспечивающих безопасный объезд препятствий при
движении на дороге.
Для достижения данной цели необходимо решить ряд задач:
1) анализ математической модели движения транспортного средства;
2) анализ существующих методов построения траекторий;
3) разработка на основе существующих подходов и программная реализация алгоритма для получения оптимальных локальных траекторий
4) тестирование разработанного программного модуля.
Для решения поставленных задач были привлечены классические методы глобальной оптимизации и теории графов. Проверка работоспособности алгоритмов и
оценка точности осуществлялись путем проведения компьютерных экспериментов.
Научная новизна данной работы заключается в том, что был предложен эффективный способ многокритериальной оптимизации локальных траекторий движения автономных транспортных средств.
Данная работа имеет практическую ценность для разработки автономных
транспортных средств. Так как в ходе данной работы разработан программный модуль, реализующий алгоритмы навигации автомобиля и предназначенное для использования на бортовом вычислителе. Программный модуль был реализован в среде ROS, что существенно упрощает внедрение полученного алгоритма в систему автономного транспортного средства

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

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

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

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

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

Заключение

В данной работе было произведено исследование предметной области поиска
траекторий движения робота. После проведения анализа существующих алгоритмов
поиска траекторий, был выбран и модифицирован алгоритм для произведения оптимизации полученных траекторий. Полученный алгоритм имеет высокое быстродействие и качество получаемых траекторий.
Получаемые траектории с помощью обычных алгоритмов планирования траекторий являются неоптимизированными, вследствие чего движение по данным
траекториям влечет за собой лишние энергозатраты.
Благодаря полученному алгоритму оптимизации траекторий можно сократить
энергозатраты при движении автомобиля, время на их прохождение, а также повысить безопасность.
Описанные алгоритмы были реализованы на языке программирования C++.
Во время работы программы пользователь может осуществлять изменение параметров автомобиля и оптимизации траекторий, полученные параметры пользователь
может сохранять в файл для дальнейшего использования. Также пользователь может
располагать автономное транспортное средство в любой точке рабочей области,
кроме мест расположения препятствий, так же располагается и конечная точка траектории. После того, как определена целевая точка для автомобиля запускается алгоритмы построения глобальной и локальной траектории движения. Карта препятствий загружается в виде изображения, что позволяет реализовывать карты любой
сложности
Скорость поиска траекторий зависит от количества препятствий вокруг робота, формы робота и от аппаратного обеспечения.
Был проведен ряд испытаний разработанного программного модуля, проведен
анализ полученных в ходе испытаний результатов. Результаты показали, что для качественного построения траекторий необходимо более мощное аппаратное обеспечение, так как от этого зависит максимальная скорость движения робота. Иначе говоря, АТС часто останавливается для пересчета новых траекторий в сложных участках.79
Данная работа имеет практическую ценность для разработки автономных
транспортных средств. Так как в ходе данной работы разработан программный модуль, реализующий алгоритмы навигации автомобиля и предназначенное для использования на бортовом вычислителе. Программный модуль был реализован в среде ROS, что существенно упрощает внедрение полученных алгоритмов в систему
автономного транспортного средства.
Результаты полученные в ходе тестирования показывают, что алгоритм имеет
неплохую производительность. Медленное вычисление связано со слабыми характеристиками компьютера. При использовании алгоритмов в реальном автомобиле
необходим вычислитель, характеристики которого в разы превышают характеристики компьютера, на котором проводились тесты. Это связано с тем что в реальном
автомобиле используется большее количество датчиков и вследствие чего необходимо обрабатывать гораздо большее количество данных.

Литература

Нгуен Т. Н. Бортовая информационно-измерительная и управляющая
система беспилотного автомобиля для циклических тестовых заездов: дис. ... канд.
техн. наук. Рязанский гос. радиотехнический университет, Рязань, 2014.
2 Lee Gomes. Hidden Obstacle for Google’s Self-Driving Cars // MIT Technology
Review, 2014. URL: https://www.technologyreview.com/s/530276/hidden-obstacles-forgoogles-self-driving-cars/ (дата обращения: 05.06.2018)
3 Интеллектуальный мобильный робот [Электронный ресурс] / - Евстигнеев
Д.В. - Режим доступа: www/ URL: http://robot-rad.narod.ru/index.html/ (дата
обращения: 05.06.2018)
4 Andreasson J., Moller A., Otter M. Modeling of a racing car with Modelicas
MultiBody library. // In Peter Fritzson, editor, Proceedings of the Modelica'2000
Workshop. The Modelica Association and Lund University, Oct., 2000.
5 Bunte T., Sahin A., Bajcinca N. Inversion of vehicle steering dynamics with
Modelica/Dymola. // Proc. of 4th International Modelica Conference, Hamburg, March,
2005. – pp. 319–328.
6 Heller S., Bunte T. Modelica vehicle dynamics library: Implementation of
driving maneuvers and a controller for active car steering. // Proc. of 3rd International
Modelica Conference, Linkoping, Nov., 2003. – pp. 19–28.
7 Meijaard J.P., Schwab A.L. Linearized equations for an extended bicycle model.
Proceedings of III European Conference on Computational Mechanics, Solids, Structures
and Coupled Problems in Engineering. Lisbon, June 5–9, 2006. – 18 p.
8 LeBlanc D., Johnson G., Venhovens P., Gerber G., DeSonia R., Ervin R., Lin
C., Ulsoy A., Pilutti T. CAPC: A Road-Departure Prevention System. // IEEE Control
Systems Magazine, Vol. 16, No. 6, 1996. – pp. 61-71.
9 Grau C. A parametric study of the lateral dynamics of a nonlinear four-wheel
road-vehicle model. Ph.D., Engineering: Mechanical Engineering, University of
Cincinnati, 2003. - 141 p.
10 Новожилов И.В., Павлов И.С. Приближенная математическая модель
колесного экипажа. // Изв. РАН. МТТ. 1997. №2. С. 196–204.81
11 Olson B.J. Nonlinear dynamics of longitudinal ground vehicle traction. M.S.
Thesis defense, Michigan State University, 2001. – 53 p.
12 Olson B.J., Shaw S.W., Stepan G. Nonlinear dynamics of longitudinal vehicle
traction. // Proc. of th 9-th Mini-Conference on Vehicle System Dynamics, Identifications
and Anomalies, Budapest, 2004. – pp. 537-545.
13 Wang and Qi. Trajectory Planning for a Four-Wheel-Steering Vehicle, 2001.
14 LaValle S.M. Planning algorithms / Cambridge University Press. – University of
Illinois. – 2006. – 786 p.
15 ARNL Path Planning and Navigation. // Mobile Robots Research and Academic
Customer Support. URL:
http://robots.mobilerobots.com/wiki/ARNL_Path_Planning_and_Navigation (дата
обращения: 05.06.2018).
16 CARMEN Robot Navigation Toolkit. URL: http://carmen.sourceforge.net/ (дата
обращения: 05.06.2018)
17 ROS.org | Powering the world's robots [Электронный ресурс]. URL:
http://www.ros.org/ (дата обращения: 05.06.2018).
18 Likhachev, M. Any-time Dynamic A*: An Anytime, Replanning Algorithm / M.
Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun // Proceedings of the
International Conference on Automated Planning and Scheduling (ICAPS). 2005. P. 262–
271.
19 Dijkstra E.W. A note on two problems in connexion with graphs // Numerische
Mathematik. – 1959. – №1. – P. 269-271.
20 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.
21 Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality
of A* // Journal of the ACM. — 1985. — Т. 32, № 3. — С. 505 — 536.
22 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.82
23 Koenig S., Likhachev M. D* Lite // AAAI/IAAI. – 2004. – V. 25. – №2. – P.
99–112
24 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.
25 Voronoi G. Nouvelles applications des paramètres continus à la théorie des
formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs //
Journal für die reine und angewandte Mathematik. – 1908. – V. 134. – P. 198-287
26 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.
27 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
28 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.
29 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.
30 Пыхтин П.С., Камаев В.А., Крыжановский А.И., Никляев И.Ю., Пыхтин
П.С. — Планирование траектории движения мобильного робота с использованием
градиента функции исследования областей пространства конфигураций //
Кибернетика и программирование. – 2014. – № 1. – С. 48 - 60. DOI: 10.7256/2306-
4196.2014.1.9828 URL: http://e-notabene.ru/kp/article_9828.html (дата обращения:
05.06.2018)
31 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 195783
32 Farin G., Sapidis N. Automatic Fairing Algorithm for B-Spline Curves //
Computer-Aided Design. — 1990. — Vol. 22. — P. 121—129.
33 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.
34 Пестерев Л.В., Гилимьянов Р.Ф. Планирование пути для колесного робота
// Проблемы вычислений в распределенной среде: распределенные приложения,
коммуникационные системы, математические модели и оптимизация / Труды ИСА
РАН. - Москва, 2006. - Т. 25. — С. 204-211.
35 Позняк Э. Г., Шикин Е. В. Дифференциальная геометрия./ Э. Г. Позняк, Е.
В. Шикин. - М.: УРСС, 2003.
36 R. K¨ummerle et al., ”g2o: A general framework for graph optimization”, in
Proc. of the IEEE Intl. Conf. on Robotics and Automation (ICRA), Shanghai, China, May
2011.
37 P. R. Amestoy, T. A. Davis, and I. S. Duff, ”Algorithm 837: Amd, an
approximate minimum degree ordering algorithm.”, in ACM Trans. Math. Softw. vol. 30,
pp. 381-388, September 2004.
38 Y. Chen et al., ”Algorithm 887: Cholmod, supernodal sparse cholesky
factorization and update/downdate”, in ACM Trans. Math. Softw. vol. 35, pp: 22:1-22:14,
October 2008.
39 C. Rösmann, F. Hoffmann and T. Bertram: Planning of Multiple Robot
Trajectories in Distinctive Topologies, Proc. IEEE European Conference on Mobile
Robots, UK, Lincoln, Sept. 2015