Послать статью по эл. почте 
МОДИФИКАЦИЯ АЛГОРИТМА RRT ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ТРАЕКТОРИИ ДВИЖЕНИЯ АВТОМОБИЛЯ ПРИ ОБЪЕЗДЕ ПРЕПЯТСТВИЙ
https://doi.org/10.26518/2071-7296-2017-6(58)-148-154
Аннотация
Данная статья посвящена актуальной проблеме планирования траектории движения беспилотного транспортного средства. Представлены результаты разработки, программной реализации и исследования алгоритма построения квазиоптимальной траектории движения беспилотного транспортного средства в известном окружении. В качестве основы был использован стандартный алгоритм RRT для построения пути между двумя точками. Для повышения эффективности в базовый алгоритм были введены следующие модификации: ориентирование на точку финиша, удаление промежуточных вершин, учёт кинематических ограничений при поворотах. Ориентирование на точку финиша позволяет с некоторой вероятностью проверить возможность прямого соединения последней точки, найденной алгоритмом RRT, с точкой финиша. Это значительно сокращает время поиска траектории, так как в базовом алгоритме RRT поиск точки осуществляется до тех пор, пока случайно сгенерированная точка не окажется в окрестности финиша. Удаление промежуточных вершин осуществляется для участков, на которых можно спрямить траекторию за счет удаления промежуточных вершин без пересечения препятствий. Реализован учёт кинематических ограничений на минимальный радиус поворота транспортного средства на основе кривых Дубинса. В результате всех указанных модификаций алгоритма его быстродействие возросло примерно на 30% по результатам компьютерного моделирования.
Ключ. слова
Об авторах
И. З. АхметзяновРоссия
кандидат технических наук, доцент, Scopus Author ID: 22936807300, ResearcherID: O-5233-2015, доцент кафедры «Системный анализ и информатика» ФГАОУ ВО «Казанский (Приволжский) федеральный университет»
423822, г. Наб. Челны, пр. Мира, 16а
Главный специалист службы главного конструктора инновационных автомобилей, Научно-технический центр ПАО «КАМАЗ»
423800, г. Набережные Челны, Транспортный проезд, 70
М. А. Ионов
Россия
магистрант кафедры «Системный анализ и информатика» ФГАОУ ВО «Казанский (Приволжский) федеральный университет»
423822, г. Наб. Челны, пр. Мира, 16а
Инженер-конструктор службы главного конструктора инновационных автомобилей, Научно-технический центр ПАО «КАМАЗ»
423800, г. Набережные Челны, Транспортный проезд, 70
В. С. Карабцев
Россия
кандидат технических наук, Scopus Author ID: 6506844842, ResearcherID: J- 6195-2016. Руководитель службы конструкторских и научно-исследовательских работ, Научно-технический центр ПАО «КАМАЗ»
423800, г. Набережные Челны, Транспортный проезд, 70
Доцент кафедры «Системный анализ и информатика» ФГАОУ ВО «Казанский (Приволжский) федеральный университет»
423822, г. Наб. Челны, пр. Мира, 16а
Список литературы
1. 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, vol. 10, pp. 1–8.
2. Guang Yang and V. Kapila, Optimal path planning for unmanned air vehicles with kinematic and tactical constraints. Proceedings of the 41st IEEE Conference on Decision and Control, 2002, vol. 2, pp. 1301–1306.
3. T. Kunz and M. Stilman, Kinodynamic RRTs with fixed time step and best-input extension are not probabilistically complete. Algorithmic Foundations of Robotics XI, pp. 233– 244, Springer, 2015.
4. D. Hsu, R. Kindel, J.-C. Latombe, and S. Rock, Randomized kinodynamic motion planning with moving obstacles. The International Journal of Robotics Research, vol. 21, pp. 233–255, 2002.
5. LaValle S.M. Planning algorithms. Cambridge University Press. University of Illinois, p. 786.
6. Dolgov D., Thrun S., Montemerlo M., Diebel J. Path Planning for Autonomous Vehicles in Unknown Semistructured Environments. The International Journal of Robotics Research, 2010, 29, pp. 485–501.
7. Lindemann S. R. and LaValle S. M. Incrementally reducing dispersion by increasing Voronoi bias in RRTs. Proceedings IEEE International Conference on Robotics and Automation, 2004, vol. 4, pp. 3251–3257.
8. Пыхтин П.С., Камаев В.А., Крыжановский А.И., Никляев И.Ю., Пыхтин П.С. Планирование траектории движения мобильного робота с использованием градиента функции исследования областей пространства конфигураций // Кибернетика и программирование. 2014. № 1. С. 48-60.
9. 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, vol. 4, issue 2, pp. 100-107.
10. LaValle S.M., Kuffner J.J. Randomized Kinodynamic Planning. IEEE International Conference on Robotics and Automation, 1999, vol. 1, pp. 473-479.
11. 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, pp. 338–353.
12. Boor V., Overmars M.H., Stappen A.F. The Gaussian sampling strategy for probabilistic roadmap planners. IEEE International Conference on Robotics and Automation, 1999, vol. 1, pp. 473–479.
13. Рэндал У. Биард, Тимоти У. МакЛэйн. Малые беспилотные летательные аппараты: теория и практика. Москва: ТЕХНОСФЕРА, 2015. – 312 c.
14. Minas AC, Urrutia S. Discrete Optimization Methods to Determine Trajectories for Dubins’ Vehicles. Electronic Notes in Discrete Mathematics, 2010, vol. 36, pp. 17–24.
15. 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, 1957, vol. 79, No. 3.
16. 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, pp. 2379–2384.
17. K. Savla, E. Frazzoli and F. Bullo. Traveling Salesperson Problems for the Dubins Vehicle. IEEE Transactions on Automatic Control, vol. 53, No. 6, Jul. 2008, pp. 1378-1390.
18. Wang D., F. Qi. Trajectory Planning for a Four-Wheel-Steering Vehicle, Proceedings of the 2001 IEEE International Conference on Robotics & Automation, 2001, pp. 3320–3325.
19. Hota S, Ghose D. A. Modified Dubins Method for Optimal Path Planning of a Miniature Air Vehicle Converging to a Straight Line Path. Proceedings of the 2009 conference on American Control Conference, 2009, pp. 2397–2402.
20. 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, 1957, 79, pp. 497–516.
Дополнительные файлы
Для цитирования: Ахметзянов И.З., Ионов М.А., Карабцев В.С. МОДИФИКАЦИЯ АЛГОРИТМА RRT ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ТРАЕКТОРИИ ДВИЖЕНИЯ АВТОМОБИЛЯ ПРИ ОБЪЕЗДЕ ПРЕПЯТСТВИЙ. Научный рецензируемый журнал "Вестник СибАДИ". 2017;(6(58)):148-154. https://doi.org/10.26518/2071-7296-2017-6(58)-148-154
For citation: Akhmetzyanov I.Z., Ionov M.A., Karabcev V.S. THE MODIFICATION OF THE RRT ALGORITHM FOR THE OPTIMAL TRAJECTORY DETERMINING OF THE MOTION VEHICLE WITH THE OBSTACLES AVOIDANCE. The Russian Automobile and Highway Industry Journal. 2017;(6(58)):148-154. (In Russ.) https://doi.org/10.26518/2071-7296-2017-6(58)-148-154
Обратные ссылки
- Обратные ссылки не определены.
