STUDY OF PATH PLANNING METHODS IN TWO-DIMENSIONAL MAPPED ENVIRONMENTS
Keywords:
Motion planning, two-dimensional environment, random tree method, optimization of planning algorithms, comparative analysis
Abstract
The article studies the problem of motion planning in two-dimensional mapped environments.
The review and analysis of known planning algorithms based on Voronoi diagrams, probabilistic
road maps, rapidly growing random trees, Dijkstra algorithms, A*, D* and their modifications, artificial
potential fields and intelligent heuristics are carried out. Based on the analysis, it is concluded
that classical methods in dynamic environments require significant costs in terms of calculation time
and the amount of memory used. The conclusion is made about the relevance of the development of
algorithms that increase the efficiency of known planning methods. In this regard, this article is devoted
to the development of a modified algorithm of rapidly growing random trees and the study of its
effectiveness in comparison with known methods. The article presents a modified algorithm for rapidly
growing random trees, characterized in that when checking for a path to a new potential node of
the tree, the path to some area near the specified node is checked. This reduces the number of nodes
in the tree under construction. The developed algorithm is first compared with the traditional algorithm
of fast-growing random trees. The comparison is made by the trajectory calculation time, the
amount of memory required, the path length and the percentage of situations in which the trajectory
to the target point was successfully found. Next, the developed algorithm is compared with the planning
algorithms of other classes. The study uses representative samples of numerical experiments and
various environments that differ in the density of obstacles and the presence of mazes. A study of
planning algorithms using the results of experiments on a ground-based wheeled robot is also being
conducted. Based on the results of numerical and real experiments, conclusions are drawn about the
advantages and disadvantages of the developed algorithm of motion planning and the feasibility of its
application in various environments.
References
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.
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.
Published
2022-08-09
Issue
Section
SECTION II. INFORMATION PROCESSING ALGORITHMS
