AN ALGORITHM FOR PATH PLANNING IN A TWO-DIMENSIONAL ENVIRONMENT WITH POLYGONAL OBSTACLES ON A CLASS OF PIECEWISE POLYLINE TRAJECTORIES
Abstract
An urgent problem of developing algorithms for automatic path planning is the increase in
computational costs with an increase in the complexity of the operating environment. Graphic
planning methods, in particular the method of visibility diagrams, are not without this drawback.
As the number of obstacles increases, the complexity of a visibility graph increases, and this
growth is very fast. Therefore, techniques for reducing the complexity of the visibility graph become
the most important task. This article proposes a hybrid algorithm based on the method of
visibility diagrams and Bug algorithms. The method of path planning proposed in this article
combines a graph algorithm with Bug algorithms, which allows you to build a special graph with
nodes in the form of characteristic obstacle points. In this case, the Bug algorithm is a step in the
iterative optimization process on the graph, which allows for a finite number of steps to come to
an optimal solution on a class of piecewise polyline curves. The proposed method solves the problem
of global path search. Unlike the classical methods of line-of-sight diagrams, it significantly
reduces the dimension of the graph due to a special selection of a limited number of characteristic
points of the corresponding obstacles. The article develops and theoretically substantiates the
proposed method. The calculated relations of the algorithm are given. The optimality of the obtained
trajectory is justified. The analytical relations are confirmed by the results of numerical
modeling in various environments filled with polygonal obstacles. It is shown that in order to pave
the way for maze-type scenes with one common type of obstacles, the algorithm under consideration
is 10% superior to the optimal Dijkstra algorithm.
References
International Conference on Intelligent Robots and Systems. Sendai, Japan, 2004, Vol. 3,
pp. 2813-2818.
2. Janet J.A., Luo R.C., Kay M.G. The essential visibility graph: An approach to global motion
planning for autonomous mobile robots, IEEE International Conference on Robotics and Automation.
Nagoya, Japan, 1995, Vol. 2, pp. 1958-1963.
3. Habib M.K., Asama H. Efficient method to generate collision free paths for an autonomous
mobile robot based on new free space structuring approach, IEEE-RSJ International Conference
on Intelligent Robots and Systems. Osaka, Japan, 1991, Vol. 2, pp. 563-567.
4. Wallgrun J.O. Voronoi graph matching for robot localization and mapping, Transactions on
computational science. Springer. 2010, pp. 76-108.
5. LaValle S.M., Kuffner J. Randomized kinodynamic planning, Int. Journal of Robotics Research,
2001, Vol. 20 (5), pp. 378-400.
6. Pshikhopov V.Kh., Medvedev M.Yu., Brosalin D.O., Vasil'eva M.A., Gurenko B.V., Khamdan
Nizar. Issledovanie metodov planirovaniya dvizheniya v dvumernykh kartografirovannykh
sredakh [Study of path planning methods in two-dimensional mapped environments], Izvestiya
YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2022, No. 3 (227),
pp. 170-192.
7. Pshikhopov V.Kh., Medvedev M.Yu., Kostyukov V.A., Khusseyn F., Kadim A. Algoritmy
planirovaniya traektoriy v dvumernoy srede s prepyatstviyami [Algorithms for trajectory planning
in a two-dimensional environment with obstacles], Informatika i avtomatizatsiya
[Informatics and Automation], 2022, Vol. 21 (3), pp. 459-492.
8. Sukharev A.G. Ob optimal'nykh strategiyakh poiska ekstremuma [About optimal strategies for
finding the extremum], Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki [Journal of
Computational Mathematics and Mathematical Physics], 1971, Vol. 11 (4), pp. 910-924.
9. Hornung A., Wurm K.M., Bennewitz M., Stachniss C., Burgard W. OctoMap: An efficient
probabilistic 3D mapping framework based on octrees, Autonomous Robots, 2013, Vol. 34 (3),
pp. 189-206.
10. Janson L., Ichter B., Pavone M. Deterministic sampling-based motion planning: Optimality,
complexity, and performance, International Journal of Robotics Research, 2018, Vol. 37 (1),
pp. 46-61.
11. Hart P.E., Nilsson N.J., Raphael B.A. Formal Basis for the Heuristic Determination of Minimum
Cost Paths, IEEE Transactions on Systems Science and Cybernetics, 1968, Vol. 2,
pp. 100-107.
12. Stentz A. Optimal and efficient path planning for partially known environments, In Intelligent
Unmanned Ground Vehicles. Springer, Boston, MA, USA, 1997, pp. 203-220.
13. Koenig S., Likhachev M., Furcy D. Lifelong Planning A*, Artificial Intelligence, 2004,
Vol. 155 (1-2), pp. 93-146.
14. Kazakov K.A., Semenov V.A. Obzor sovremennykh metodov planirovaniya dvizheniya [Overview
of modern traffic planning methods], Tr. ISP RAN [Proceedings of ISP RAS], 2016,
Vol. 28 (4), pp. 241-294.
15. Ng J., Braunl T. Performance comparison of bug navigation algorithms, Journal of Intelligent
and Robotic Systems, 2007, Vol. 50 (1), pp. 73-84.
16. Lumelsky V., Stepanov A. Dynamic path planning for a mobile automaton with limited information
on the environment, IEEE Transactions on Automatic Control, 1986, Vol. 31 (11),
pp. 1058-1063.
17. Yufka A., Parlaktuna O. Performance comparison of the BUG’s algorithms for mobile robots,
Proc. of International Symposium on Innovations in Intelligent Systems and Applications.
Trabzon, Turkey, 2009, pp. 416-421.
18. Kostyukov V.A., Medvedev M.Yu., Pshikhopov V.Kh. Planirovanie dvizheniya nazemnykh
robotov v srede s prepyatstviyami: algoritmy postroeniya traektoriy v gruppe pri zadannom
shablone [Planning the movement of ground robots in an environment with obstacles: algorithms
for constructing trajectories in a group with a given formation], Mekhatronika,
avtomatizatsiya, upravlenie [Mechatronics, Automation, Control], 2023, Vol. 24, No. 1,
pp. 33-45.
19. Kostyukov V.A., Medvedev M.Yu., Pshikhopov V.Kh. Algoritmy planirovaniya sglazhennykh
individual'nykh traektoriy dvizheniya nazemnykh robotov [Algorithms for planning smoothed
individual trajectories of ground robots], Mekhatronika, avtomatizatsiya, upravlenie [Mechatronics,
Automation, Control], 2022, Vol. 23 (11), pp. 585-595.
20. Kostjukov V. Pshikhopov V., Medvedev M. Optimization of mobile robot movement on a plane
with finite number of repeller sources, SPIIRAS Proceedings, 2020, Vol. 19 (1), pp. 43-78.
21. Zabarankin M., Uryasev S., Pardalos P. Optimal Risk Path Algorithms, Cooperative Control
and Optimizaton. Dordrecht: Kluwer Acad., 2002, pp. 271-303.
