СУЧАСНІ МЕТОДИ І АЛГОРИТМИ ПЛАНУВАННЯ ШЛЯХУ ДЛЯ АВТОНОМНИХ МОБІЛЬНИХ РОБОТІВ, ЇХ ЦІЛЬОВІ ФУНКЦІЇ
DOI:
https://doi.org/10.58254/viti.6.2024.02.24Ключові слова:
алгоритми, дослідження, автономний робот, методи, планування шляху, ЦФ, оптимізаціяАнотація
Сучасна ситуація в світі алгоритмів дослідження планування шляху автономними роботами показує, що
існує велика кількість алгоритмів та їх модифікацій, які вимагають від дослідників та інженерів автономної
робототехніки тонкого розуміння фундаментальних аспектів їх функціонування. Загальною метою
дослідження є проведення аналізу існуючих алгоритмів, методів та їх модифікацій з точки зору складової
математичного апарата, а саме їх цільових функцій.
В дослідженні розглянуто 38 сучасних алгоритмів і методів планування шляху автономними роботами.
Розглянута важливість і критичність розуміння цільової функції для галузі робототехніки. Наведені приклади,
що ілюструють важливість цього аспекту. В процесі дослідження алгоритми представлені в виді
формалізованих узагальнених математичних формул з урахуванням можливих мінімізації/максимізації,
їх вдосконалень і покращень.
До кожного розглянутого алгоритму і методу наданий висновок стосовно його цільової функції.
У дослідженні окремо виділено методи "Динамічних ігор" та розглянуто застосування
фундаментального "Методу розв’язуючих функцій А. О. Чикрія" для планування шляху.
В загальних висновках, надана інформація переваг та важливості розуміння математичного апарата
алгоритмів пошуку шляху автономними роботами задля вирішення наукових завдань. Узагальнені результати
зведені до єдиної порівняльної таблиці, що надає формалізовану основну функцію алгоритмів, розкриває основну
ідею, переваги/недоліки, сферу застосування і приклад використання. Порівняльна таблиця представлена
в формі узагальненого допоміжного довідкового елемента дослідження
Посилання
- Бернацький А. П. Основи робототехніки військового призначення / А. П. Бернацький. Київ: видав.
ЛІРА-К, 2024. 498 с.
2. Ладієва Л. Р. Методи оптимізації та пошуку оптимальних рішень. Електронне мережне навчальне
видання / У. Л. Р.Ладієва. Київ: КПІ ім. Ігоря Сікорського, 2023. 73 с.
3. Shi Wei Li. Verification and Analysis of Two-dimensional Path Planning Objective Function Optimization
Based on Classical Particle Swarm Optimization Algorithm / 2021 4th International Conference on Intelligent Robotics
and Control Engineering (IRCE), 18-20 September 2021. URL: https://doi.org/10.1109/IRCE53649.2021.9570874.
4. Sidhu. Performance Evaluation of Pathfinding Algorithms [Electronic resource] / Sidhu, H. Kaur // Scholarship
at UWindsor. 2020. Mode of access: https://scholar.uwindsor.ca/etd/8178.
5. Samridh Garg; Bhanu Devi Shortest Path Finding using Modified Dijkstra’s algorithm with Adaptive Penalty
Function/ 2023 14th International Conference on Computing Communication and Networking Technologies (ICCCNT).
06-08 July 2023. Mode of access: https://doi.org/10.1109/ICCCNT56998.2023.10308130.
6. Stephan Weiser, Hans Wulf, Jörn Ihlemann Application of a deepest-path algorithm to study the objective
function landscape during fitting for the Yeoh and Ogden model / PAMM Proc. Appl. Math. Mech. 2021. Mode of access:
https://doi.org/10.1002/pamm.202100086.
7. Матвійчук Р. Д., Данільчук О. М. Порівняння найвідоміших алгоритмів пошуку / Вісник студентського
наукового товариства ДонНУ ім. Василя Стуса, 2022. С. 230–234.
8. Проценко А. А., Іванов В. Г. Класичні методи планування шляху для мобільних роботів / Системи
управління навігації та зв’язку. 3(55) June 2019. С. 143–151. URL: https://doi.org/10.26906/SUNZ.2019.3.143.
9. Pankaj K. Agarwal, Esther Ezra, Micha Sharir Vertical Decomposition in 3D and 4D with Applications to Line
Nearest-Neighbor Searching in 3D / arXiv:2311.01597v1 [cs.CG] 2 Nov 2023. Mode of access:
https://doi.org/10.48550/arXiv.2311.01597.
10. Sleumer, Nora; Tschichold-Gürmann, Nadine Exact cell decomposition of arrangements used for path planning
in robotics/Technical Report / ETH Zurich, Department of Computer Science 329. 1999. Mode of access:
https://doi.org/10.3929/ethz-a-006653440.
11. Choset H. Coverage Path Planning: The Boustrophedon Cellular Decomposition / H. Choset, P.Pignon Field
and Service Robotics Springer-Verlag London Limited 1998 pp 203–209. Mode of access: https://doi.org/10.1007/978-
1-4471-1273-0_32.
12. Bott, Raoul. Morse Theory Indomitable / Bott, Raoul., - Publications Mathématiques de l’IHÉS. 68: 1988.,
pp. 99–114. Mode of access: DOI:10.1007/bf02698544.
13. Dłotko P. Computing homology and persistent homology using iterated Morse decomposition / P. Dłotko,
H. Wagne: arXiv:1210.1429v2 [math.AT] 25 Oct 2012. Mode of access: https://doi.org/10.48550/arXiv.1210.1429.
14. Rasolzadah K. Morse Theory and Handle Decomposition / K. Rasolzadah. Department of Mathematics
Uppsala University, Februari 2018.
15. R. Bahnemann, Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman
Problem / R. Bahnemann, N. Lawrance arXiv:1907.09224v1 [cs.RO] 22 Jul 2019. URL: https://doi.org/10.1007/978-981-
15-9460-1_20.
16. Laumond, J.-P. (Ed.) Robot Motion Planning and Control. London: Spring-Verlag Limited. 1998.
17. Chenghui Cai, Silvia Ferrari Information-Driven Sensor Path Planning by Approximate Cell Decomposition /
IEEE transactions on systems, man, and cybernetics, vol. 39, No. 3, June 2009. URL:
https://doi.org/10.1109/TSMCB.2008.2008561.
18. Chenghui Cai, Silvia Ferrari Information-driven sensor path planning and the treasure hunt problem /
Dissertation Duke University 2008. 112 p.
19. Ramon Gonzalez; Marius Kloetzer; Cristian Mahulea Comparative study of trajectories resulted from cell
decomposition path planning approaches / 2017 21st International Conference on System Theory, Control and Computing
(ICSTCC). URL: https://doi.org/10.1109/ICSTCC.2017.8107010.
20. Prabhakar Reddy G.V.S., Hubert J. Montas, Hanan Samet, Adel Shirmohammadi Quadtree-Based Triangular
Mesh Generation for Finite Element Analysis of Heterogeneous Spatial Data / 2001 ASAE Annual International Meeting
Sacramento, California, USA, July 30-August 1, 2001. 25 p.
21. Huiwei Wang; Yaqian Huang; Huaqing Li Quadtree-Based Adaptive Spatial Decomposition for Range Queries
Under Local Differential Privacy / IEEE Transactions on Emerging Topics in Computing (Volume: 11, Issue: 4, Oct.-
Dec. 2023). pp 1045-1056. URL: https://doi.org/10.1109/TETC.2023.3317393.
22. José Lima The K-Framed Quadtrees Approach for Path Planning Through a Known Environment / ROBOT
2017: Third Iberian Robotics Conference. 2017.
23. Zhou Yijun, Xi Jiadong, Xi Jiadong, Luo Chen A Fast Bi-Directional A* Algorithm Based on Quad-Tree
Decomposition and Hierarchical Map / Preparation of Papers for IEEE Access (February 2017). URL:
http://dx.doi.org/10.1109/ACCESS.2021.3094854.
24. Ana Rodrigues, Pedro Costa, José Lima The K-Framed Quadtrees Approach for Path Planning Through
a Known Environment / November 2018 Advances in Intelligent Systems and Computing 2018. URL:
http://dx.doi.org/10.1007/978-3-319-70833-1_5.
25. Ana Rodrigues, Pedro Costa, José Lima The K-framed quadtrees approach for path planning through a known
environment / Advances in Intelligent Systems and Computing Search for Book Publications. 2018., pp 49–59. URL:
http://doi.org/10.1007/978-3-319-70833-1_5.
26. J. W. Burns; N. S. Subotic; D. Pandelis Adaptive decomposition in electromagnetics / IEEE Antennas and
Propagation Society International Symposium. 1997. URL: https://doi.org/10.1109/APS.1997.631726.
27. Xiaomei Zhang, Xiangyu Yun, Zhe Wang, Mohan Li, Jinming Hu, Chengmin Wang, Cunfeng Wei An
adaptive decomposition algorithm for quantitative spectral CT imaging / X-RAY Spectrometry Vol.53, Iss.4., August
2024., pp. 282–293. URL: https://doi.org/10.1002/xrs.3365.
28. Tao Liu, Zhijun Luo, Jiahong Huang, Shaoze Yan, A Comparative Study of Four Kinds of Adaptive
Decomposition Algorithms and Their Applications / PMC PubMed Central 2018 Jul; 18(7): 2120. URL:
https://doi.org/10.3390 s18072120.
29. Sabudin E. N, Omar. R and Che Ku Melor C. Potential Field Methods And Their Inherent Approaches For
Path Planning / ARPN Journal of Engineering and Applied Sciences Vol. 11, No. 18, Sept. 2016., pp. 10801-10805.
30. Jan Rosell, Pedro Iñiguez Path planning using Harmonic Functions and Probabilistic Cell Decomposition /
IEEE Xplore, Conference: Robotics and Automation, ICRA 2005. URL:
http://dx.doi.org/10.1109/ROBOT.2005.1570375.
31. Emmanuel f Mazer, Juan-Manuel Ahuactzin, Pierre Bessiere The Ariadne’s Clew Algorithm / Journal of
Artificial Intelligence Research. May 1998., pp. 295–316. URL: http://dx.doi.org/10.1613/jair.468.
32. J. M. Ahuactzin, P. Bessiere, E. Mazer The Ariadne’s Clew Algorithm / Journal of Artificial Intelligence
Research 1998. pp. 295–316. URL: https://doi.org/10.48550/arXiv.1105.5440.
33. David Hsu, Jean-claude Latombe, Rajeev Motwani Path Planning in Expansive Configuration Spaces /
International Journal of Computational Geometry & Applications 09(04n05) March 1997. URL:
http://dx.doi.org/10.1142/S0218195999000285.
34. Arushi Khokhar Probabilistic Roadmap (PRM) for Path Planning in Robotics / Medium., Feb 12, 2021.
35. Lijun Qiao, Xiao Luo, Qingsheng Luo An Optimized Probabilistic Roadmap Algorithm for Path Planning of
Mobile Robots in Complex Environments with Narrow Channels / Sensors 2022, 22(22), 8983. URL:
https://doi.org/10.3390/s22228983.
36. S. Carpin Algorithmic Motion Planning: The Randomized Approach/ General Theory of Information Transfer
and Combinatorics. 2006. pp. 740–768.
37. Jinbao Chen, Yimin Zhou; Jin Gong; Yu Deng An Improved Probabilistic Roadmap Algorithm with Potential
Field Function for Path Planning of Quadrotor / 2019 Chinese Control Conference (CCC). July 2019. URL:
https://doi.org/10.23919/ChiCC.2019.8865585.
38. Nancy M. Amato, Yan Wu Randomized roadmap method for path and manipulation planning / IEEE
International Conference on Robotics and Automation vol. 1., May 1996. pp. 113–120. URL:
http://dx.doi.org/10.1109/ROBOT.1996.503582.
39. Robert Bohlin, Lidia E. Kavraki Path Planning Using Lazy / IEEE International Conference on Robotics &
Automation, San Francisco, CA., April 2000. pp. 521–528. URL: https://doi.org/10.1109/ROBOT.2000.844107.
40. Jory Denny; Kensen Shi; Nancy M. Amato Lazy Toggle PRM: A single-query approach to motion planning /
2013 IEEE International Conference on Robotics and Automation., Karlsruhe, Germany. 2013. URL:
https://doi.org/10.1109/ICRA.2013.6630904.
41. Boor, V., Overmars, M.H., Van Der Stappen, A.F.: The Gaussian sampling strategyfor probabilistic roadmap
planners. In: RSS. vol. 2, pp. 1018–1023. IEEE (1999). URL: https://doi.org/10.1109/ROBOT.1999.772447.
42. Steven M. LaValle, Michael S. Branicky On the Relationship Between Classical Grid Search and Probabilistic
Roadmaps / The International Journal of Robotics Research Vol.23, Iss. 7-8 2004. URL:
https://doi.org/10.1177/0278364904045481.
43. Huageng Zhong, Ming Cong, Minghao Wang, Yu Du, Dong Liu HB-RRT:A path planning algorithm for
mobile robots using Halton sequence-based rapidly-exploring random tree / Engineering Applications of Artificial
Intelligence., Vol. 133, Part E., July 2024. URL: https://doi.org/10.1016/j.engappai.2024.108362.
44. Anthony Stentz The D* Algorithm for Real-Time Planning of Optimal Traverses / The Robotics Institute
Carnegie Mellon University Pittsburgh, Pennsylvania 15213, September 1994.
45. Firas A. Raheema, Umniah I. Hameed Path Planning Algorithm using D* Heuristic Method Based on PSO in
Dynamic Environment / American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS)
(2018) Volume 49, No 1, pp. 257–271.
46. Dibyendu Biswas D*, D* Lite & LPA* / Medium Jun 27, 2021.
47. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik, Schultes, Dorothea Wagner
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm / Experimental Algorithms
(WEA 2008). pp.303–318.
48. Akash Lai, Shaz Qadeer A program transformation for faster goal-directed search / 2014 Formal Methods in
Computer-Aided Design (FMCAD) October 2014. URL: https://doi.org/10.1109/FMCAD.2014.6987607.
49. Akash Lal, Shaz Qadeer A Program Transformation for Faster Goal-Directed Search / FMCAD ‘14:
Proceedings of the 14th Conference on Formal Methods in Computer-Aided Design 2014, pp. 147–154.
50. Pang C. Chen, Y. Hwang SANDROS: a motion planner with performance proportional to task difficulty/ IEEE
Transactions on Robotics and Automation (Vol: 14, Iss. 3, June 1998) pp. 390–403. URL:
https://doi.org/10.1109/70.678449.
51. Iswanto, Alfian Ma’arif, Oyas Wahyunggoro, Adha Imam Cahyadi Artificial Potential Field Algorithm
Implementation for Quadrotor Path Planning / (IJACSA) International Journal of Advanced Computer Science and
Applications, Vol. 10, No. 8, 2019. URL: https://dx.doi.org/10.14569/IJACSA.2019.0100876.
52. Eryi Zhang Path planning algorithm based on Improved Artificial Potential Field method / Applied and
Computational Engineering September 2023. pp. 167–174. URL: http://dx.doi.org/10.54254/2755-2721/10/20230170.
53. Wenrui Wang, Mingchao Zhu, Zhenbang Xu An improved artificial potential field method of trajectory
planning and obstacle avoidance for redundant manipulators / International Journal of Advanced Robotic Systems,
September 2018. URL: https://doi.org/10.1177/1729881418799562.
54. Hu Hongyu, Zhang Chi, Sheng Yuhuan, Zhou Bin, Gao Fei An Improved Artificial Potential Field Model
Considering Vehicle Velocity for Autonomous Driving / IFAC-PapersOnLine Vol. 51, Iss. 31., 2018. pp. 863–867. URL:
https://doi.org/10.1016/j.ifacol.2018.10.095.
55. Kaddour Messaoudi, Noureddine Chaib A survey of UAV-based data collection: Challenges, solutions and
future perspectives / Journal of Network and Computer Applications Vol. 216, July 2023. URL:
https://doi.org/10.1016/j.jnca.2023.103670.
56. Lijuan Xie, Huanwen Chen, Guangrong Xie Artificial Potential Field Based Path Planning for Mobile Robots
Using Virtual Water-Flow Method / Advanced Intelligent Computing Theories and Applications. With Aspects of
Contemporary Intelligent Computing Techniques (ICIC 2007). Pp. 588–595. URL: http://dx.doi.org/10.1007/978-3-540-
74282-1_66.
57. Jixue Mo, Gao Changqing, Fei Liu, Qingkai Yang A Modified Artificial Potential Field Method Based on
Subgoal Points for Mobile Robot / ICIRA2023-The 16th international conference on intelligent robotics and applications.,
July 2023. URL: http://dx.doi.org/10.1007/978-981-99-6483-3_26.
58. Hong Liu; Weiwei Wan; Hongbin Zha A dynamic subgoal path planner for unpredictable environments / 2010
IEEE International Conference on Robotics and Automation., Anchorage, AK, USA., May 2010. URL:
https://doi.org/10.1109/ROBOT.2010.5509324.
59. David J. Grymin, Charles B. Neas, Mazen Farhood A hierarchical approach for primitive-based motion
planning and control of autonomous vehicles / Robotics and Autonomous Systems., Vol. 62, Iss. 2, Feb. 2014,
pp. 214–228. URL: https://doi.org/10.1016/j.robot.2013.10.003.
60. Hanlin Chen, Xizhe Zang, Yubin Liu, Xuehe Zhang, Jie Zhao A Hierarchical Motion Planning Method for
Mobile Manipulator / Sensors 2023, 23(15), 6952. URL: https://doi.org/10.3390/s23156952.
61. Yao Qi, Binbing He, Rendong Wang, Le Wang, Youchun Xu Hierarchical Motion Planning for Autonomous
Vehicles in Unstructured Dynamic Environments / IEEE Robotics and Automation Letters ( Volume: 8, Issue: 2, February
2023). pp. 496–503. URL: https://doi.org/10.1109/LRA.2022.3228159.
62. Amitava Chatterjee, Anjan Rakshit, N. Nirmal Singh Vision-Based Mobile Robot Navigation Using Subgoals/
Vision Based Autonomous Robot Navigation., vol. 44, issue 4, May 2011. pp. 620–641.
63. Nirmal Singh, Avishek Chatterjee, Amitava Chatterjee, Anjan Rakshit A two-layered subgoal based mobile
robot navigation algorithm with vision system and IR sensors / May Measurement 44(4) 2011. pp. 620–641. URL:
http://dx.doi.org/10.1016/j.measurement.2010.12.002.
64. LaValle, Steven M. Rapidly-exploring random trees: A new tool for path planning / Technical Report
(TR 98–11). Computer Science Department, Iowa State University. October 1998.
65. J. J. Kuffner; S. M. LaValle RRT-connect: An efficient approach to single-query path planning / Millennium
Conference. IEEE International Conference on Robotics and Automation. April 2000.
https://doi.org/10.1109/ROBOT.2000.844730
66. Fan Yang, Xi Fang, Fei Gao, Xianjin Zhou, Hao Li, Hongbin Jin, Yu Song Obstacle Avoidance Path Planning
for UAV Based on Improved RRT Algorithm / Discrete Dynamics in Nature and Society, Iss. 1., 2022. URL:
https://doi.org/10.1155/2022/4544499.
67. Xiong Yin, Wentao Dong, Xiaoming Wang, Yongxiang Yu, Daojin Yao Route planning of mobile robot based
on improved RRT star and TEB algorithm / Scientific reports 8942. 2024. URL: https://doi.org/10.1038/s41598-024-
59413-9.
68. Xinyu Tang, Jyh-Ming Lien, Nancy Amato OBRRT: Obstacle-Based RRT/ IEEE International Conference on
Robotics and Automation. 2006. pp. 895–900. URL: http://dx.doi.org/10.1109/ROBOT.2006.1641823.
69. Xin Cheng, Jingmei Zhou, Zhou Zhou, Xiangmo Zhao An improved RRT-Connect path planning algorithm
of robotic arm for automatic sampling of exhaust emission detection in Industry 4.0 / Journal of Industrial Information
Integration Vol. 33., June 2023. URL: https://doi.org/10.1016/j.jii.2023.100436.
70. J. J. Kuffner and S. M. LaValle RRT-Connect path solving/ CRA. Millennium Conference. IEEE International
Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065). URL:
https://doi.org/10.1109/ROBOT.2000.844730.
71. Rui Zhang, He Guo, Darius Andriukaitis, Yongbo Li Intelligent path planning by an improved RRT algorithm
with dual grid map / Alexandria Engineering Journal Vol. 88., February 2024, pp. 91–104. URL:
https://doi.org/10.1016/j.aej.2023.12.044.
72. Jun Ding,Yinxuan Zhou, Xia Huang An improved RRT* algorithm for robot path planning based on path
expansion heuristic sampling / Journal of Computational Science Vol. 67, March 2023. URL:
https://doi.org/10.1016/j.jocs.2022.101937.
73. James J. Kuffner, Jr. Steven M. LaValle RRT-Connect: An Efficient Approach to Single-Query Path Planning /
In Proc. 2000 IEEE Int’l Conf. on Robotics and Automation (ICRA 2000) pp. 995–1001. URL:
http://dx.doi.org/10.1109/ROBOT.2000.844730.
74. Zhe Huang, Hongyu Chen, John Pohovey, Katherine Driggs-Campbe Neural Informed RRT*: Learning-based
Path Planning with Point Cloud State Representations under Admissible Ellipsoidal Constraints / arXiv:2309.14595v2
[cs.RO] 07 Mar 2024. URL: http://dx.doi.org/10.1109/ICRA57147.2024.10611099.
75. Бернацький А. П. Вдосконалений метод планування шляху автономного наземного робота
з використанням алгоритму MBD-RRT*FFT / Системи і технології зв’язку, інформатизації та кібербезпеки.
Випуск № 5, 2024. URL: https://doi.org/10.58254/viti.5.2024.03.37.
76. Anita Garhwal, Partha Pratim A Survey on Dynamic Spectrum Access Techniques for Cognitive Radio /
International Journal of NextGeneration Networks (IJNGN). Vol. 3, No. 4, 2012. URL:
http://dx.doi.org/10.5121/ijngn.2011.3402.
77. P. Taylor, L. Jonker, Evolutionary stable strategies and game dynamics /Mathematical Biosciences 40 (1–2)
(1978). pp.145–156.
78. Чикрій А. О. Вимірні багатозначні відображення та їх селектори в динамічних іграх переслідування /
А. А. Чикрій, І. С. Раппопорт // Пробл. упр. та інформатики. № 1-2. 2006. С. 60–70.
79. Shaobo Zhang, Qinxiang Xia, Mingxing Chen, Sizhu Cheng Multi-Objective Optimal Trajectory Planning for
Robotic Arms Using Deep Reinforcement Learning / Sensors 2023, 23(13), 5974. URL:
https://doi.org/10.3390/s23135974.
80. Masoud Fetanat; Sajjad Haghzad; Saeed Bagheri Shouraki Optimization of dynamic mobile robot path
planning based on evolutionary methods / AI & Robotics (IRANOPEN). 2015. URL:
https://doi.org/10.1109/RIOS.2015.7270743.
81. Альбус Дж. Аналітичний метод вирішення ігрового завдання про "М’яку посадку" для рухомих
об’єктів / Дж. Альбус, А. Мейстел, А. О. Чикрій, А. А. Білоусов, А. І. Козлов // Кібернетика та систем. аналіз.
№ 1. 2001. С. 97–115
82. Чикрій А. О Квазилінійні конфліктно керовані процеси зі змінною структурою / А. А. Чикрій,
І. І. Матичин // Пробл. упр. та інформатики. № 6. 1998. С. 31–41.
83. Чикрій А. О. Квазилінійні позиційні інтегральні ігри зближення / А. О. Чикрій, Г. Ц. Чикрій,
К. Ю. Волянський // Пробл. упр. та інформатики. № 6. 2001. С. 5–28.
84. Chikrii, A. Conflict-Controlled Processes / Springer Science &Business Media. 2013.
85. Барановська Л. В., Гирявець Д. М., Барановська Г. Г. Візуалізація групової гри переслідування на
площині / Conference: Information Technologies and Security (ITS-2020). 2021