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

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

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.