АЛГОРИТМ ПЛАНИРОВАНИЯ ПУТИ В ДВУХМЕРНОЙ СРЕДЕ С ПОЛИГОНАЛЬНЫМИ ПРЕПЯТСТВИЯМИ НА КЛАССЕ КУСОЧНО-ЛОМАНЫХ ТРАЕКТОРИЙ
Аннотация
Актуальной проблемой, возникающей при разработке алгоритмов автоматического
планирования пути, является рост вычислительных затрат при увеличении сложности
среды функционирования. Не лишены этого недостатка графовые методы планирования, в
частности, метод диаграмм видимости. Он позволяет сформировать в качестве узлов
графа вершины полигональных границ каждого препятствия, а ребрами графа являются
все те отрезки, соединяющие эти вершины, которые не имеют пересечений с препятст-
виями. При увеличении количества препятствий возрастает сложность такого графа,
причем этот рост очень быстрый. Поэтому наиболее важной задачей становятся приемы
сокращения сложности графа видимости. В данной статье предлагается гибридный алго-
ритм, строящийся на методе диаграмм видимости и семействе Bug-алгоритмов.
Bug-алгоритм относится к классу локальных, поскольку каждый раз имеет дело с огибани-
ем одного препятствия, появляющегося на пути следования робота, и этот алгоритм не
может предсказать заранее, какое следующее препятствие придется обходить. Предла-
гаемый в данной статье метод планирования траектории движения сочетает графовый
алгоритм с Bug-алгоритмами, что позволяет построить специальный граф с узлами в виде
характерных точек препятствий. При этом Bug-алгоритм является шагом итерационного
процесса оптимизации на графе, позволяющего за конечное число шагов прийти к опти-
мальному решению на классе кусочно-ломаных кривых. Предлагаемый метод решает зада-
чу глобального поиска пути на классе кусочно-линейных траекторий с полигональными
препятствиями; а в отличие от классического методов диаграмм прямой видимости, су-
щественно снижает размерность графа за счет специального выбора ограниченного коли-
чества характерных точек соответствующих препятствий. В статье проводится разра-
ботка и теоретическое обоснование предлагаемого метода. Приводятся расчетные соот-
ношения алгоритма, обосновывается оптимальность получаемой траектории. Аналити-
ческие соотношения подтверждаются результатами численного моделирования в различ-
ных средах, заполненных полигональными препятствиями. При этом эффективность пред-
лагаемых алгоритмов подтверждается на примерах среды, заполненной препятствиями
до 70–80%. Показано, что для прокладывания пути на сценах лабиринтного типа с одним
распространенным видом препятствий рассматриваемый алгоритм на 10% превосходит
оптимальный алгоритм Дейкстры.
Литература
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.
