The task of planning the unmanned vehicle trajectory in a dynamically changing environment

Introduction. The paper presents a solution to the problem of an unmanned vehicle (UV) trajectory planning in modern road conditions with a dynamically changing environment. The algorithm of the solution was based on the method of rapidly-exploring random trees (RRT), which consisted in generating tree vertices with the help of applying the law of equiprobability and finding the optimal trajectory. The optimal length criterion was the minimum length. The purpose of the study was: to solve the problem of increasing the speed trajectory algorithm when planning UV motion to make it effective in a dynamically changing environment; to compare the qualitative assessment of the synthesized algorithm with known algorithms. Methodology and research methods. The applied methods of mathematical modeling and the graph theory main notions were used. Scientific novelty and results. A distinctive feature of the proposed algorithm was that the search space was defined as a road map model. It has been proposed to set the roadway in the form of a trafic lane which was bounded by two lines - a sequential set of lines and the arcs of circles. For the convenience of solving the trajectory search problem, the UV was customary modelled as a circle of a fixed radius. The concept of the search space transforming and passable zones changing was presented, taking into account the vehicle model. The law of tree vertices generation was applied permitting to effectively explore the search space. A method of forming a set of trajectories prototypes as tree vertices sequences was proposed. A formula scheme for constructing the prototype primary trajectory was given, and a criterion for the admissibility of the trajectory was also presented. Practical significance. The proposed algorithm can significantly increase the speed searching of the desired trajectory.

RRT, unmanned vehicle, trajectory planning, mathematical model of a road map, search space, Dubins path (trajectory), RRT, vehicle size consideration

1. Иванов А.М., Шадрин С.С., Карпухин К.Е. Интеллектуальное транспортное средство. Адаптация подсистемы определения взаимного положения движущихся транспортных средств // Известия МГТУ «МАМИ». - 2013. - № 2 (16), т. 1. - С. 57-62.

2. -й Международный автомобильный научный форум «Интеллектуальные транспортные системы повышения энергоэффективности и безопасности движения» // Журнал автомобильных инженеров. - 2016. - № 5. - С. 6-7.

3. Батищев Ю.А., Дудник В.В., Гуринов А.С., Копкин А.С. Архитектура и возможности системы пространственной ориентации беспилотных и сверхлёгких летательных аппаратов на чувствительных элементах нового поколения // Вестник Донского государственного технического университета. - 2010. -№ 2, т. 10. - С. 229-233.

4. Яковлев К.С., Макаров Д.А., Баскин Е.С. Метод автоматического планирования траектории беспилотного летательного аппарата в условиях ограничений на динамику полёта // Искусственный интеллект и принятие решений. - 2014. - № 4. - C. 3-17.

5. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische mathematik. - 1959. - Vol. 1. -No. 1. - P. 269-271.

6. Рэднал У. Биард, Тимоти У. МакЛэйн. Малые беспилотные летательные аппараты: теория и практика. - М: Техносфера, 2015. - 312 с.

7. Андрейчук А.А., Яковлев К.С. Планирование траектории на плоскости с учётом размера агента (мобильного робота, беспилотного транспортного средства) / Четвёртый Всероссийский научно-практический семинар «Беспилотные транспортные средства с элементами искусственного интеллекта». - Казань: Центр инновационных технологий, 2017. - С. 107-117.

8. Choset H., Lynch K.M., Hutchinson S., Kantor G., Burgard W., Kavraki L.E. , Thrun S. Principles of Robot Motion: Theory, Algorithms, and Implementations. -Cambridge: MIT Press, 2005. - 149 p.

9. 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. - No. 79. - P. 497-516.

10. Jarrod M. Snider Automatic Steering Methods for Autonomous Automobile Path Tracking. - Pittsburgh: Carnegie Mellon University, 2009. - 71 p.