sibadiНаучный рецензируемый журнал "Вестник СибАДИ"The Russian Automobile and Highway Industry Journal2071-72962658-5626The Siberian State Automobile and Highway University10.26518/2071-7296-2017-6(58)-148-154sibadi-523Research ArticleИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕINFORMATICS, COMPUTER ENGINEERING AND MANAGEMENTМОДИФИКАЦИЯ АЛГОРИТМА RRT ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ТРАЕКТОРИИ ДВИЖЕНИЯ АВТОМОБИЛЯ ПРИ ОБЪЕЗДЕ ПРЕПЯТСТВИЙTHE MODIFICATION OF THE RRT ALGORITHM FOR THE OPTIMAL TRAJECTORY DETERMINING OF THE MOTION VEHICLE WITH THE OBSTACLES AVOIDANCEАхметзяновИ. З.AkhmetzyanovI. Z.

кандидат технических наук, доцент, Scopus Author ID: 22936807300,  ResearcherID: O-5233-2015, доцент кафедры «Системный анализ и информатика» ФГАОУ ВО «Казанский (Приволжский) федеральный университет»

423822, г. Наб. Челны, пр. Мира, 16а

Главный специалист службы главного конструктора инновационных  автомобилей, Научно-технический центр ПАО «КАМАЗ»

423800, г. Набережные Челны, Транспортный проезд, 70

Candidate of Engineering Sciences, docent, Scopus Author  ID: 22936807300, ResearcherID: O-5233-2015; assistant  professor of the System Analysis and Informatics chair

423822, Mira pr. 16а, Nabereznye Chelny, Russian Federation

senior specialist of the Chief Designer for Innovative  Products unit, the Scientific and Technical Center

423800, Transportnyj proezd, 70, Nabereznye Chelny,  Russian Federation

insurzg@gmail.comИоновМ. А.IonovM. A.

магистрант кафедры «Системный анализ и информатика» ФГАОУ ВО  «Казанский (Приволжский) федеральный университет»

423822, г. Наб. Челны, пр. Мира, 16а

Инженер-конструктор службы главного конструктора инновационных  автомобилей, Научно-технический центр ПАО «КАМАЗ»

423800, г. Набережные Челны, Транспортный проезд, 70

master student, System Analysis and Informatics chair

423822, Mira pr. 16а, Nabereznye Chelny, Russian Federation

maks-ion@inbox.ruКарабцевВ. С.KarabcevV. S.

кандидат технических наук, Scopus Author ID: 6506844842, ResearcherID: J- 6195-2016. Руководитель службы конструкторских и научно-исследовательских работ, Научно-технический центр ПАО «КАМАЗ»

423800, г. Набережные Челны, Транспортный проезд, 70

Доцент кафедры «Системный анализ и информатика» ФГАОУ ВО «Казанский  (Приволжский) федеральный университет»

423822, г. Наб. Челны, пр. Мира, 16а

Candidate of Engineering Sciences, Scopus Author ID:  6506844842, ResearcherID: J-6195-2016; Head of design and research works unit, the Scientific and Technical Center 

423800, Transportnyj proezd, 70, Nabereznye Chelny, Russian Federation)

assistant professor of the System Analysis and Informaticschair

423822, Mira pr. 16а, Nabereznye Chelny, Russian Federation

Vladimir.Karabtsev@kamaz.ruФГАОУ ВО «Казанский (Приволжский) федеральный университет» Научно-технический центр ПАО «КАМАЗ»РоссияKazan (Volga) Federal University KAMAZ PTCRussian FederationФГАОУ ВО «Казанский (Приволжский) федеральный университет» Научно-технический центр ПАО «КАМАЗ»РоссияKazan (Volga) Federal UniversityRussian FederationФГАОУ ВО «Казанский (Приволжский) федеральный университет» Научно-технический центр ПАО «КАМАЗ»РоссияKAMAZ PTC Kazan (Volga) Federal UniversityRussian Federation20171501201806(58)148154Copyright © Ахметзянов И.З., Ионов М.А., Карабцев В.С., 20182018Ахметзянов И.З., Ионов М.А., Карабцев В.С.Akhmetzyanov I.Z., Ionov M.A., Karabcev V.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibadi.org/jour/article/view/523

Данная статья посвящена актуальной проблеме планирования траектории движения беспилотного транспортного средства. Представлены результаты разработки, программной реализации и исследования алгоритма построения квазиоптимальной  траектории движения беспилотного транспортного средства в известном окружении. В  качестве основы был использован стандартный алгоритм RRT для построения пути между  двумя точками. Для повышения эффективности в базовый алгоритм были введены  следующие модификации: ориентирование на точку финиша, удаление промежуточных  вершин, учёт кинематических ограничений при поворотах. Ориентирование на точку  финиша позволяет с некоторой вероятностью проверить возможность прямого соединения  последней точки, найденной алгоритмом RRT, с точкой финиша. Это значительно сокращает  время поиска траектории, так как в базовом алгоритме RRT поиск точки осуществляется до  тех пор, пока случайно сгенерированная точка не окажется в окрестности финиша. Удаление промежуточных вершин осуществляется для участков, на которых можно спрямить траекторию за счет удаления промежуточных вершин без пересечения препятствий. Реализован учёт кинематических ограничений на минимальный радиус поворота  транспортного средства на основе кривых Дубинса. В результате всех указанных  модификаций алгоритма его быстродействие возросло примерно на 30% по результатам компьютерного моделирования.

The problem of planning the motion path of an unmanned vehicle is presented in the article. The results of development and the software  implementation, and the research of the algorithm for constructing quasi- optimal trajectory of an unmanned vehicle in a known environment are  shown. The RRT standard algorithm as the basis for the path construction  between two points is used in the article. To improve the efficiency, the basic  algorithm of the following modifications such as the orientation to the finish  point, the removal of intermediate vertices are introduced. The orientation to the finish point allows to check the possibility of the direct connection to the last point which could be found by the RRT algorithm. The orientation also  reduces the trajectory searching, because the basic RRT algorithm searches  the point until a randomly generated point appears in the vicinity of the  finish line. The deleting process of the intermediate vertices is carried out for such route sections where the trajectory could be straighten by the  intermediate vertices’ removing without crossing the obstacles. The  consideration of the kinematic constraints on the minimum turning radius of  the vehicle, which is based on the Dubins curves is implemented in the  article. As a result of all these algorithm modifications, its performance has  been increased about 30% according to the computer simulation results.

алгоритмыбеспилотные автомобилипланирование движенияпоиск путиробототехникакривые ДубинсаRRTalgorithmsautonomous vehiclesmotion planningroute searchroboticsDubins curvesRRTReferencesPolden 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.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.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.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.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.T. Kunz and M. Stilman, Kinodynamic RRTs with fixed time step and best-input extension are not probabilistically complete. Algorithmic Foundations of Robotics XI. Springer, 2015, pp. 233–244, Springer.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.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.LaValle S.M. Planning algorithms. Cambridge University Press. University of Illinois, p. 786.LaValle S.M. Planning algorithms. Cambridge University Press. University of Illinois, p. 786.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.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.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.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.Пыхтин П.С., Камаев В.А., Крыжановский А.И., Никляев И.Ю., Пыхтин П.С. Планирование траектории движения мобильного робота с использованием градиента функции исследования областей пространства конфигураций // Кибернетика и программирование. 2014. № 1. С. 48-60.Pyhtin P.S., Kamaev V.A., Kryzhanovskij A.I., Nikljaev I.Ju., Pyhtin P.S. Planirovanie traektorii dvizhenija mobil’nogo robota s ispol’zovaniem gradienta funkcii issledova-nija oblastej prostranstva konfiguracij [space [Planning the trajectory of mobile robot using a gradient function studies areas configuration space]. Kibernetika i programmirovanie, 2014, no 1.pp 48-60.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.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.LaValle S.M., Kuffner J.J. Randomized Kinodynamic Planning. IEEE International Conference on Robotics and Automation, 1999, vol. 1, pp. 473-479.LaValle S.M., Kuffner J.J. Randomized Kinodynamic Planning. IEEE International Conference on Robotics and Automation, 1999, vol. 1, pp. 473-479.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.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.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.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.Рэндал У. Биард, Тимоти У. МакЛэйн. Малые беспилотные летательные аппараты: теория и практика. Москва: ТЕХНОСФЕРА, 2015. – 312 c.Rjendal U. B., Timoti U.M. Malye bespilotnye letatel’nye apparaty: teorija i praktika [Small Unmanned Aerial Vehicles: Theory and Practice]. Moskva: TEHNOSFERA, 2015, 312 p.Minas AC, Urrutia S. Discrete Optimization Methods to Determine Trajectories for Dubins’ Vehicles. Electronic Notes in Discrete Mathematics, 2010, vol. 36, pp. 17–24.Minas AC, Urrutia S. Discrete Optimization Methods to Determine Trajectories for Dubins’ Vehicles. Electronic Notes in Discrete Mathematics, 2010, vol. 36, pp. 17–24.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.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.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.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.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.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.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.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.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.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.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.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.

The authors declare that there are no conflicts of interest present.