ИССЛЕДОВАНИЕ МЕТОДОВ ПЛАНИРОВАНИЯ ДВИЖЕНИЯ В ДВУМЕРНЫХ КАРТОГРАФИРОВАННЫХ СРЕДАХ

  • М. Ю. Медведев НИИ робототехники и процессов управления Южного федерального университета
  • В.Х. Пшихопов Южный федеральный университет
  • Д.О. Бросалин Южный федеральный университет
  • Б. В. Гуренко Южный федеральный университет
  • М.А. Васильева Южный федеральный университет
  • Хамдан Низар Южный федеральный университет
Ключевые слова: Планирование движения, двумерная среда, метод случайных деревьев, оптимизация алгоритмов планирования, сравнительный анализ

Аннотация

Исследуются задача планирования движения в двумерных картографированных сре-
дах. Проводится обзор и анализ известных алгоритмов планирования, базирующихся на
диаграммах Вороного, вероятностной дорожной карте, быстро растущих случайных де-
ревьев, алгоритмах Дейкстры, А*, D* и их модификациях, искусственных потенциальных
полях и интеллектуальных эвристиках. На основе проведенного анализа делается вывод о
том, что классические методы в динамических средах требуют значительных затрат по
времени расчетов и объему используемой памяти. Делается вывод об актуальности разра-
ботки алгоритмов, повышающих эффективность известных методов планирования.
В этой связи данная статья посвящена разработке модифицированного алгоритма быст-
ро растущих случайных деревьев и исследованию его эффективности по сравнению с из-
вестными методами. В статье представлен модифицированный алгоритм быстро рас-
тущих случайных деревьев, отличающийся тем, что при проверке наличия пути в новый
потенциальный узел графа проверяется путь в некоторую область возле указанного узла.
Это позволяет снизить количество узлов в строящемся дереве. Разработанный алгоритм
вначале сравнивается с традиционным алгоритмом быстрорастущих случайных деревьев.
Сравнение производится по времени расчета траектории, объему требуемой памяти, дли-
не пути и проценту ситуаций, в которых успешно найдена траектория в целевую точку.
Далее осуществляется сравнение разработанного алгоритма с алгоритмами планирования
других классов. При исследовании используются репрезентативные выборки численных
экспериментов и различные среды, отличающиеся плотностью расположения препятст-
вий и наличием лабиринтов. Также проводится исследование алгоритмов планирования с
использованием результатов экспериментов на наземном колесном роботе. По результа-
там численных и реальных экспериментов делаются выводы о преимуществах и недос-
татках разработанного алгоритма планирования движения и о целесообразности его при-
менения в различных средах.

Литература

1. Gayduk A.R. Primenenie prostranstva sostoyaniya k issledovaniyu sistem avtomaticheskogo
upravleniya [Application of the state space to the study of automatic control systems]. Taganrog:
TRTI, 1979, 100 p.
2. LaValle S. Planning Algorithms. Cambridge University Press, 2006, 842 p.
3. Lozano-Perez T. Spatial planning: A configuration space approach, IEEE Transactions on
Computers, 1983, Vol. 32 (2), pp. 108-120.
4. Kazakov K.A., Semenov V.A. Obzor sovremennykh metodov planirovaniya puti [Review of
modern methods of path planning], Tr. ISP RAN [Proceedings of ISP RAS], 2016, Vol. 28 (4),
pp. 241-294.
5. 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.
6. Stentz A. Optimal and efficient path planning for partially known environments, In Intelligent
Unmanned Ground Vehicles. Springer, Boston, MA, USA, 1997, pp. 203-220.
7. Wang Q., Hao Y., Chen F. Deepening the IDA* algorithm for knowledge graph reasoning
through neural network architecture, Neurocomputing, 2021, Vol. 429, pp. 101-109.
8. Zhou R., Hansen E.A. Memory-Bounded {A*} Graph Search, The Florida AI Research Society
Conference – FLAIRS, 2002, pp. 203-209.
9. Holte R., Perez M., Zimmer R., MacDonald A. Hierarchical A*: Searching abstraction hierarchies
efficiently, Proceedings of the thirteenth national conference on Artificial intelligence,
1996, Vol. 1, pp. 530-535.
10. Liu B., Xiao X., Stone P. A Lifelong Learning Approach to Mobile Robot Navigation, In IEEE
Robotics and Automation Letters, 2021, Vol. 6 (2), pp. 1090-1096.
11. Chen B.Y., Chen X.-W., Chen H.-P., Lam W.H.K. Efficient algorithm for finding k shortest
paths based on re-optimization technique, Transportation Research Part E: Logistics and
Transportation Review, 2020, Vol. 133. Article number 101819.
12. Zhang X., Wylie B., Oscar C., Moore C.A. Time-Optimal and Collision-Free Path Planning for
Dual-Manipulator 3D Printer, IEEE Transactions on Systems, Man, and Cybernetics: Systems,
2020, pp. 2389-2396.
13. 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. Available at: https://doi.org/10.15622/ia.21.3.1.
14. Khatib O. Real-Time Obstacles Avoidance for Manipulators and Mobile Robots, International
Journal of Robotics Research, 1986, Vol. 5 (2), pp. 90-98.
15. Platonov A.K., Karpov I.I., Kiril'chenko A.A. Metod potentsialov v zadache prokladki trassy
[The method of potentials in the task of laying a route], Preprint Instituta prikladnoy
matematiki AN SSSR [Preprint of the Institute of Applied Mathematics of the USSR Academy
of Sciences]. Moscow: 1974, 27 p.
16. Pshikhopov V.Kh. (Ed.), Beloglazov D., Finaev V., Guzik V.,Kosenko E., Krukhmalev V.,
Medvedev M., Pereverzev A., Pyavchenko A., Saprykin R., Shapovalov I., Soloviev V. Path
Planning for Vehicles Operating in Uncertain 2D Environments. Elsevier, Butterworth-
Heinemann, 2017, 312 p. ISBN: 9780128123058.
17. Filimonov A.B., Filimonov N.B. Voprosy upravleniya dvizheniem mobil'nykh robotov
metodom potentsial'nogo navedeniya [Questions of controlling the movement of mobile robots
by the method of potential guidance], Mekhatronika, avtomatizatsiya, upravlenie [Mechatronics,
automation, control], 2019, Vol. 20 (11), pp. 677-685.
18. Woods A.C., La H.M. A Novel Potential Field Controller for Use on Aerial Robots, IEEE
Transactions on Systems, Man, and Cybernetics: Systems, 2019, Vol. 49 (4), pp. 665-676.
19. Koren Y., Borenstein J. Potential field methods and their inherent limitations for mobile robot navigation,
International Conference on Robotics and Automation, 1991, Vol. 2, pp. 1398-1404.
20. Pshikhopov V.Kh., Medvedev M.Yu. Gruppovoe upravlenie dvizheniem mobil'nykh robotov v
neopredelennoy srede s ispol'zovaniem neustoychivykh rezhimov [Group control of the
movement of mobile robots in an uncertain environment using unstable modes], Tr. ISP RAN
[Proceedings of ISP RAS], 2018, Issue 60, pp. 39-63.
21. Malone N., Chiang H.-T., Lesser K., Oishi M., Tapia L. Hybrid Dynamic Moving Obstacle
Avoidance Using a Stochastic Reachable Set-Based Potential Field, IEEE Transactions on Robotics,
2017, Vol. 33 (5), pp. 1124-1138.
22. Friudenberg P. Koziol S. Mobile Robot Rendezvous Using Potential Fields combined With
Parallel Navigation, IEEE Access, 2018, Vol. 6, pp. 16948-16957.
23. Fedele G., D’Alfonso L., Chiaravalloti F., D’Aquila G. Obstacles Avoidance Based on Switching
Potential Functions, Journal of Intelligent and Robotic Systems: Theory and Applications,
2018, Vol. 90 (3-4), pp. 387-405.
24. Gayduk A.R., Mart'yanov O.V., Medvedev M.Yu., Pshikhopov V.Kh., khamdan N., Farkhud A.
Neyrosetevaya sistema upravleniya gruppoy robotov v neopredelennoy dvumernoy srede
[Neural network control system for a group of robots in an indefinite two-dimensional environment]
Mekhatronika, avtomatizatsiya, upravlenie [Mechatronics, automation, control],
2020, Vol. 21 (8), pp. 470-479.
25. Medvedev M., Pshikhopov V. Path Planning of Mobile Robot Group Based on Neural Networks,
Lecture Notes in Artificial Intelligence, 2020, pp. 51-62.
26. Wang Y., Cheng L., Hou Z.-G., Yu J., Tan M. Optimal Formation of Multirobot Systems Based
on a Recurrent Neural Network, IEEE Transactions on Neural Networks and Learning Systems,
2016, Vol. 27 (2), pp. 322-333.
27. Güzel M., Ajabshir V., Nattharith P., Gezer E., Can S. A Novel Framework for Multi-Agent
Systems Using a Decentralized Strategy, Robotica, 2019, Vol. 37 (4), pp. 691-707. DOI:
10.1017/S0263574718001261.
28. De Berg M., Cheong O., Van Kreveld M., Overmars M. Computational Geometry: Algorithms
and Applications. 3rd ed. Springer-Verlag, 2008, 386 p.
29. Guibas L.J., Knuth D.E., Sharir M. Randomized incremental construction of Delaunay and
Voronoi diagrams, Algorithmica, 1992, Vol. 7 (1), pp. 381-413.
30. LaValle S.M., Kuffner J.J. Rapidly-exploring random trees: Progress and prospects, Workshop
on the Algorithmic Foundations of Robotics, 2000, pp. 293-308.
31. Kedem K., Sharir M. An efficient motion planning algorithm for a convex rigid polygonal object in
2-dimentional polygonal space, Discrete Computational Geometry, 1990, Vol. 5 (1), pp. 43-75.
32. Lee W., Choi G.-H., Kim T.-W. Visibility graph-based path-planning algorithm with quadtree
representation, Applied Ocean Research, 2021, Vol. 117.
33. Finkel R., Bentley J.L. Quad Trees: A Data Structure for Retrieval on Composite Keys, Acta
Informatica, 1974, Vol. 4 (1), pp. 1-9. DOI: 10.1007/BF00288933.
34. Pradhan S., Mandava R.K., Vundavilli P.R. Development of path planning algorithm for biped robot
using combined multi-point RRT and visibility graph, International Journal of Information Technology,
2021, Vol. 13, pp. 1513-1519. Available at: https://doi.org/10.1007/s41870-021-00696-w.
35. Beloglazov D.A., Guzik V.F., Kosenko E.Yu., Krukhmalev V.A., Medvedev M.Yu., Pereverzev
V.A., Pshikhopov V.Kh., P'yavchenko A.O., Saprykin R.V., Solov'ev V.V., Finaev V.I.,
Chernukhin Yu.V., Shapovalov I.O. Intellektual'noe planirovanie traektoriy podvizhnykh
ob"ektov v sredakh s prepyatstviyami [Intelligent planning of trajectories of moving objects in
environments with obstacles], ed. by V.Kh. Pshikhopova. Moscow: Fizmatlit, 2014, 300 p.
ISBN 978-5-9221-1595-7.
36. Bhattacharya P., Gavrilova M.L. Roadmap-Based Path Planning - Using the Voronoi Diagram
for a Clearance-Based Shortest Path, IEEE Robotics & Automation Magazine, 2008, Vol. 15
(2), pp. 58-66. DOI: 10.1109/MRA.2008.921540.
37. Al-Dahhan M.R.H., Schmidt K.W. Voronoi Boundary Visibility for Efficient Path Planning,
IEEE Access, 2020, Vol. 8, pp. 134764-134781. DOI: 10.1109/ACCESS.2020.3010819.
38. Magid E., Lavrenov R., Svinin M., Khasianov, A. Combining Voronoi Graph and Spline-Based
Approaches for a Mobile Robot Path Planning. In: Gusikhin O., Madani K. (eds.), Informatics
in Control, Automation and Robotics. ICINCO 2017. Lecture Notes in Electrical Engineering,
Vol 495. Springer, Cham, 2020. Available at: https://doi.org/10.1007/978-3-030-11292-9_24.
39. Kavraki L.E., Svestka P., Latombe J.C., Overmars M.H. Probabilistic roadmaps for path planning
in high-dimensional configuration spaces, IEEE transactions on Robotics and Automation,
1996, Vol. 12 (4), pp. 566-580. DOI: 10.1109/70.508439.
40. Kamil A.R.M., Shithil S.M., Ismail Z.H., Mahmud M.S.A., Faudzi A.A.M. Path Planning Based
on Inflated Medial Axis and Probabilistic Roadmap for Duct Environment, Lecture Notes in
Electrical Engineering, Vol. 834. Springer, Singapore, 2022. Available at:
https://doi.org/10.1007/978-981-16-8484-5_42.
41. Chen G., Luo N., Liu D., Zhao Z., Liang Ch. Path planning for manipulators based on an improved
probabilistic roadmap method, Robotics and Computer-Integrated Manufacturing,
2021, Vol. 72.
42. Rantanen M.T., Juhola M. Speeding up probabilistic roadmap planners with locality-sensitive
hashing, Robotica, 2015, Vol. 33 (7), pp. 1491-1506.
43. Buaba R., Homaifar A., Gebril M., Kihn E. Satellite Image Retrieval Application Using Locality
Sensitive Hashing in L2-Space, Proceedings of IEEE Aerospace Conference, Big Sky,
MT, USA, 2011, pp. 1-7.
44. Kala R. Increased Visibility Sampling for Probabilistic Roadmaps. IEEE International Conference
on Simulation, Modeling, and Programming for Autonomous Robots, Brisbane,
AUSTRALIA. 2018, pp. 87-92.
45. Chakravorty S., Kumar S. Generalized Sampling-Based Motion Planners, IEEE Transactions
on Systems, Man, and Cybernetics. Part B: Cybernetics, 2011, Vol. 41 (3).
46. Qureshi A., Ayaz Y. Potential functions based sampling heuristic for optimal path planning,
Autonomous Robot, 2016, Vol. 40, pp. 1079-1093.
47. Cheng G.-R., Ma M.-C., Tan L.-G., Song S.-M. Gaussian estimation for non-linear stochastic uncertain
systems with time-correlated additive noises and packet dropout compensations, IET Control
Theory Appl., 2022, Vol. 16, pp. 600-614. Available at: https://doi.org/10.1049/cth2.12252.
48. Wang X., Li X., Guan Y., Song J., Wang R. Bidirectional Potential Guided RRT* for Motion
Planning, IEEE Acsess, 2019, Vol. 7, pp. 95046-95057.
49. Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning, The International
Journal of Robotics Research, 2011, Vol. 30 (7), pp. 846-894.
50. Chen L., Shan Y., Tian W., Li B., Cao D. A Fast and Efficient Double-Tree RRT -Like Sampling-
Based Planner Applying on Mobile Robotic Systems, IEEE/ASME Transactions on
Mechatronics, 2018, Vol. 23 (6), pp. 2568-2578.
51. Wang J., Meng M.Q.-H., Khatib O. EB-RRT: Optimal Motion Planning for Mobile Robots,
IEEE Transactions on Automation Science and Engineering, 2020, Vol. 17 (4), pp. 2063-2073.
52. Janos J., Vonasek V., Penicka R. Multi-Goal Path Planning Using Multiple Random Trees,
IEEE Robotics and Automation Letter, 2021, Vol. 6 (2), pp. 4201-4208.
53. Devaurs D., Siméon T., Cortés J. A multi-tree extension of the transition-based RRT: Application
to ordering-and-pathfinding problems in continuous cost spaces, In Proc. IEEE/RSJ Int.
Conf. Intell. Robots Syst., 2014, pp. 2991-2996.
54. Vonásek V., Pˇeniˇcka R. Space-filling forest for multi-goal path planning, In Proc. 24th IEEE
Int. Conf. Emerg. Technol. Factory Automat., 2019, pp. 1587-1590.
55. Jeong I.-B., Lee S.-J., Kim J.-H. Quick-RRT*: Triangular inequality-based implementation of
RRT* with improved initial solution and convergence rate, Expert Systems with Applications,
2019, Vol. 123, pp. 82-90.
56. Yang K. Anytime synchronized-biased-greedy rapidly-exploring random tree path planning in
two dimensional complex environments, International Journal of Control, Autom. Syst., 2011,
Vol. 9, No. 4, pp. 750.
57. Wang J., Chi W., Shao M., Meng M. Q.-H. Finding a high-quality initial solution for the RRTs
algorithms in 2D environments, Robotica, 2019, Vol. 37, No. 10, pp. 1677-1694.
58. Medvedev M., Pshikhopov V., Gurenko B., Hamdan N. Path planning method for mobile robot
with maneuver restrictions, Proc. of the International Conference on Electrical, Computer,
Communications and Mechatronics Engineering (ICECCME) 7-8 October 2021, Mauritius.
10.1109/ICECCME52200.2021.9591090.
59. Medvedev M.Yu., Kostyukov V.A., Pshikhopov V.Kh. Optimizatsiya dvizheniya mobil'nogo
robota na ploskosti v pole konechnogo chisla istochnikov-repellerov [Optimization of the
movement of a mobile robot on a plane in the field of a finite number of repeller sources],
Tr. ISP RAN [Proceedings of ISP RAS], 2020, Vol. 19 (1), pp. 43-78.
60. Kostjukov V., Medvedev M., Pshikhopov V. Method for Optimizing of Mobile Robot Trajectory
in Repeller Sources Field, Informatics and Automation, 2021, Vol. 20 (3), pp. 690-726.
61. Pshikhopov V.Kh., Medvedev M.Yu., Gayduk A.R., Neydorf R.A., Belyaev V.E., Fedorenko
R.V., Kostyukov V.A., Krukhmalev V.A. Sistema pozitsionno-traektornogo upravleniya
robotizirovannoy vozdukhoplavatel'noy platformoy: matematicheskaya model' [Positional trajectory
control system of a robotic aeronautical platform: mathematical model], Mekhatronika,
avtomatizatsiya, upravlenie [Mechatronics, automation, control], 2013, No. 6, pp. 14-21.
62. Pshikhopov, V., Medvedev, M. Multi-Loop Adaptive Control of Mobile Objects in Solving Trajectory
Tracking Tasks, Automation and Remote Control, 2020, Vol. 81 (11), pp. 2078-2093.
Available at: https://doi.org/10.1134/S0005117920110090.
63. Pshikhopov V.Kh., Medvedev M.Yu. Sravnitel'nyy analiz tsentralizovannogo i
detsentralizovannogo algoritmov dvizheniya stroem BLA mul'tikopternogo tipa [Comparative
analysis of centralized and decentralized algorithms for the movement of a multicopter-type
UAV system], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2022, No. 1 (225), pp. 121-139.
64. Pshikhopov V.Kh., Medvedev M.Yu., Gaiduk A.R., Fedorenko R.V., Krukhmalev V.A., Gurenko
B.V. Position-Trajectory Control System for Unmanned Robotic Airship, IFAC Proceedings Volumes
(IFAC-PapersOnline). The 19th World Congress the International Federation of Automatic
Control. Cape Town, South Africa. August 24-29, 2014, pp. 8953-8958.
65. Pshikhopov V.Kh., Medvedev M.Yu. Sintez sistem upravleniya podvodnymi apparatami s
nelineynymi kharakteristikami ispolnitel'nykh organov [Synthesis of control systems for underwater
vehicles with nonlinear characteristics of executive bodies], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 3 (116), pp. 147-156.
Опубликован
2022-08-09
Выпуск
Раздел
РАЗДЕЛ II. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ