• 1990 (Vol.4)
  • 1989 (Vol.3)
  • 1988 (Vol.2)
  • 1987 (Vol.1)

Local path finding in autonomous car state lattice based on multi-criteria optimization

© 2021 I. Y. Kornev, V. I. Kibalov, O. S. Shipitko

Institute for Information Transmission Problems RAS 127051 Moscow, Bol’shoy Karetnyy Pereulok 19, Russia
27015 Moscow, Vyatskaya street 27, Russia

Received 19 Nov 2020

In this work algorithm of local path planning for the ground autonomous vehicle with car-type non-holonomic kinematics is proposed. The constructed path is represented by a path in a graph of possible maneuvers that minimizes predefined quality measures. The maneuvers graph is constructed by coping along the global path of precalculated in curvilinear coordinate system maneuvers' templates which are kinematically feasible. The use of a pre-calculated template speeds up runtime algorithm execution. The weight of each graph edge is a weighted sum of several criteria. The search algorithm minimizes maneuvring while keeping the maximum possible distance from obstacles. The obstacles can be dynamically detected as well as extract from static occupancy grid map. The path search in the weighted graph is executed with Dijkstra’s algorithm. The proposed planning algorithm was tested on generated road scenes. Each scene is a static road situation with obstacles in which a safe path has to be found. The safe local path was found in which scenes where it was feasible. The generated local paths are on average just 1.3% longer than the predefined shortest global path, which does not account for obstacles.

Key words: path planning, local path planning, state lattice, multi-objective optimization, collision avoidance, autonomous vehicle, nonholonomic kinematics

DOI: 10.31857/S0235009221020062

Cite: Kornev I. Y., Kibalov V. I., Shipitko O. S. Algoritm lokalnogo planirovaniya puti avtonomnogo transportnogo sredstva na osnove mnogokriterialnoi optimizatsii traektorii v prostranstvennoi reshetke sostoyanii [Local path finding in autonomous car state lattice based on multi-criteria optimization]. Sensornye sistemy [Sensory systems]. 2021. V. 35(2). P. 164–174 (in Russian). doi: 10.31857/S0235009221020062


  • Kunina I.A., Panfilova E.I., Povolotskiy M.A. Detektirovanie peshehodnyh perehodov na izobrazhenijah dorogi na osnove metoda dinamicheskogo vyravnivanija vremennyh rjadov [Zebra-crossing detection on road images using dynamic time warping]. Trudy Instituta sistemnogo analiza Rossiiskoi akademii nauk. 2018. V. 68 (1). P. 23–31. (In Russian). https://doi.org/10.14357/20790279180503
  • Lobanov M.G., Sholomov D.L. Ob uskorenii arhitektury svertochnoj nejronnoj seti na baze ResNet v zadache raspoznavanija ob#ektov dorozhnoj sceny [On the Acceleration of the Convolutional Neural Network Architecture Based on Resnet in the Task of Road Scene Objects Recognition]. Informatsionnye tekhnologii i vychislitel’nye sistemy. 2019. V. 69 (3) P. 57–65. (in Russian). https://doi.org/10.14357/20718632190305
  • Gonzalez D., Pérez J., Milanes V., Nashashibi F. A review of motion planning techniques for automated vehicles. IEEE. 2015. V. 17. № 4. P. 1135–1145. https://doi.org/10.1109/TITS.2015.2498841
  • Kuwata Y., Fiore G.A., Teo J., Frazzoli E., How J.P. Motion planning for urban driving using rrt. IEEE. 2008. P. 1681–1686. https://doi.org/10.1109/IROS.2008.4651075
  • Pivtoraiko M., Kelly A. Efficient constrained path planning via search in state lattices. Internat. Sympos. Artific. Intell., Robot. Automat. Space. 2005. P. 1–7.
  • Pothan S., Nandagopal J. L., Selvaraj G. Path planning using state lattice for autonomous vehicle. IEEE. 2017. P. 1–5. https://doi.org/10.1109/TAPENERGY.2017.8397363
  • Rösmann C., Feiten W., Wösch T., Hoffmann F., Bertram T. Trajectory modification considering dynamic constraints of autonomous robots. VDE. 2012. P. 1–6.
  • Shvets E.A., Shepelev D.A., Nikolaev D.P. Occupancy grid mapping with the use of a forward sonar model by gradient descent. J. Communicat. Technol. Electron. 2016. V. 61. № 12. P. 1474–1480. https://doi.org/10.1134/S106422691612024X
  • Takahashi A., Hongo T., Ninomiya Y., Sugimoto G. Local path planning and motion control for agv in positioning. IEEE. 1989. P. 392–397. https://doi.org/10.1109/IROS.1989.637936
  • Thrun S., Montemerlo M., Dahlkamp H., Stavens D., Aron A., Diebel J., Lau K. Stanley: The robot that won the darpa grand challenge. J. Field Robotics. 2006. V. 23. № 9. P. 661–692. https://doi.org/10.1002/rob.20147
  • Vishal K., Arvind C.S., Mishra R., Gundimeda V. Traffic light recognition for autonomous vehicles by admixing the traditional ML and DL. Intern. Soc. Opt. Photon. 2019. V. 110. C. 110410H. https://doi.org/10.1117/12.2523105
  • Werling M., Ziegler J., Kammel S., Thrun S. Optimal trajectory generation for dynamic street scenarios in a frenet frame. IEEE. 2010. P. 987–993. https://doi.org/10.1109/ROBOT.2010.5509799
  • Ziegler J., Bender P., Dang T., Stiller C. Trajectory planning for bertha a local, continuous method. IEEE. 2014. P. 450–457. https://doi.org/10.1109/IVS.2014.6856581
  • Ziegler J., Stiller C. Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios. IEEE. 2009. P. 1879–1884. https://doi.org/10.1109/IROS.2009.5354448