مهندسی مکانیک مدرس

مهندسی مکانیک مدرس

روش جستجوی تدریجی جدید برای طراحی مسیر سیستم‌های چندرباتی

نوع مقاله : پژوهشی اصیل

نویسندگان
اسماعیل خان میرزا
مرتضی حق بیگی
محمد فرزان
دانشگاه علم و صنعت ایران
10.52547/mme.23.3.161
چکیده
یکی از این چالش‌های مساله طراحی مسیر چندرباتی، افزایش ابعاد فضای جستجو به صورت نمایی همراه با افزایش تعداد ربات‌ها در محیط عملیات است. بنابراین، به الگوریتم‌هایی نیاز است که دارای کارایی محاسباتی بوده و بتوانند مسیرهای بهینه و بدون برخورد ربات‌ها را در زمان محدود طراحی کنند. در این مقاله یک الگوریتم طراحی مسیر مرکزی برای هدایت ربات‌ها در محیط عملیات مشترک ارائه شده است. این الگوریتم یک روش جستجوی اکتشافی تدریجی است که در آن الگوریتم ‎D* Lite‎ به منظور تطبیق با حالت چندرباتی توسعه داده شده است. هماهنگی در طراحی مسیر برای تمام ربات‌ها بر اساس مفهوم زمان تصرف بوده که در ساختار مدل مفهومی محیط پیاده‌سازی شده است. همچنین، یک تابع مرکزی جهت به‌روزرسانی اطلاعات مدل مفهومی محیط و حرکت تدریجی ربات‌ها توسعه داده شده است. به منظور ارزیابی روش پیشنهادی، دو گروه شبیه­سازی­های استاتیک و پویا انجام شده است. در دسته اول، تمرکز بر مطالعه اثر پارامترهای الگوریتم است. نتایج نشان می­دهد که الگوریتم پیشنهادی قابلیت طراحی مسیر برای 40 ربات در محیطی با 55 درصد فضای آزاد را دارد و نیز رابطه زمان محساباتی و تعداد ربات­ها غیر نمایی است. دسته دوم شبیه­سازی­ها در محیط سه­بعدی Gazebo انجام شده که به صورت برخط و پویا است. نتایج روش پیشنهادی با روشی بر اساس میدان­های پتانسیل مصنوعی برای تعداد 14 ربات مورد مقایسه قرار گرفته است. نتایج نشان می­دهد که با افزایش تعداد ربات­ها از 9 عدد، زمان انجام عملیات برای روش مبتنی بر میدان پتانسیل افزایش زیادی پیدا کرده و یا غیرممکن می­شود.
کلیدواژه‌ها
طراحی مسیر
سیستم‌های چند رباته
جستجوی تدریجی
ربات خودکار

موضوعات

عنوان مقاله English

A New Incremental Search Method for Multi-robot Path Planning

نویسندگان English

Esmaeel Khanmirza
Morteza Haghbeigi
Mohammad Farzan
Iran University of Science and Technology
چکیده English

Multi-robot path planning problem involves some challenges. One of them is the exponential increase in the size of the search space as a result of increasing the number of robots in the operating environment. Therefore, there is a need for algorithms with high computational performance to plan optimal and collision-free paths in a limited time. In this article, a centralized path planning algorithm is presented. The algorithm is a heuristic incremental search, in which the D* Lite algorithm has been adapted for the multi-robot case. The concept of occupancy time has been embedded into the environment model to avoid path interference. A centralized function has been designed to update the environment model and robot data. To evaluate the method, two groups of simulations of static and dynamic types were carried out. The static simulations focused on studying the effect of algorithm parameters, and it was shown that the algorithm can plan paths for up to 40 robots in an environment having 55 percent free space. The dynamic simulations were carried out in Gazebo, a real-time and dynamic physical simulator. The results were compared to a baseline method based on potential fields. The number of robots was increased to 14, and it was demonstrated that for 9 robots and more, the potential field approach either fails or has a rapid increase in computation time, while the proposed method can find feasible solutions in a limited time.

کلیدواژه‌ها English

path planning
multi-robot systems
incremental Search
autonomous mobile robots
Khanmirza E, Haghbeigi M, Nazarahari M, Doostie S. A comparative study of deterministic and probabilistic mobile robot path planning algorithms. In: 2017 5th RSI international conference on robotics and mechatronics (ICRoM). 2017. p. 534-9. [DOI:10.1109/ICRoM.2017.8466197]
Khanmirza E, Haghbeigi M, Nazarahari M, Doostie S. A comparative study of deterministic and probabilistic mobile robot path planning algorithms. In: 2017 5th RSI international conference on robotics and mechatronics (ICRoM). 2017. p. 534-9. [DOI:10.1109/ICRoM.2017.8466197]
Gasparetto A, Boscariol P, Lanzutti A, Vidoni R. Path Planning and Trajectory Planning Algorithms: A General Overview. In: Carbone G, Gomez-Bravo F, editors. Motion and Operation Planning of Robotic Systems: Background and Practical Approaches [Internet]. Cham: Springer International Publishing; 2015 [cited 2021 Oct 25]. p. 3-27. (Mechanisms and Machine Science). Available from: [DOI:10.1007/978-3-319-14705-5_1]
Gasparetto A, Boscariol P, Lanzutti A, Vidoni R. Path Planning and Trajectory Planning Algorithms: A General Overview. In: Carbone G, Gomez-Bravo F, editors. Motion and Operation Planning of Robotic Systems: Background and Practical Approaches [Internet]. Cham: Springer International Publishing; 2015 [cited 2021 Oct 25]. p. 3-27. (Mechanisms and Machine Science). Available from: [DOI:10.1007/978-3-319-14705-5_1]
Hwang YK, Ahuja N, others. A potential field approach to path planning. IEEE transactions on robotics and automation. 1992;8(1):23-32. [DOI:10.1109/70.127236]
Hwang YK, Ahuja N, others. A potential field approach to path planning. IEEE transactions on robotics and automation. 1992;8(1):23-32. [DOI:10.1109/70.127236]
Barraquand J, Langlois B, Latombe JC. Numerical potential field techniques for robot path planning. IEEE transactions on systems, man, and cybernetics. 1992;22(2):224-41. [DOI:10.1109/21.148426]
Barraquand J, Langlois B, Latombe JC. Numerical potential field techniques for robot path planning. IEEE transactions on systems, man, and cybernetics. 1992;22(2):224-41. [DOI:10.1109/21.148426]
Bhattacharya P, Gavrilova ML. Roadmap-based path planning - using the voronoi diagram for a clearance-based shortest path. IEEE Robotics & Automation Magazine. 2008;15(2):58-66. [DOI:10.1109/MRA.2008.921540]
Bhattacharya P, Gavrilova ML. Roadmap-based path planning - using the voronoi diagram for a clearance-based shortest path. IEEE Robotics & Automation Magazine. 2008;15(2):58-66. [DOI:10.1109/MRA.2008.921540]
Barbehenn M. A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices. IEEE Transactions on Computers. 1998 Feb;47(2):263-. [DOI:10.1109/12.663776]
Barbehenn M. A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices. IEEE Transactions on Computers. 1998 Feb;47(2):263-. [DOI:10.1109/12.663776]
Delling D, Sanders P, Schultes D, Wagner D. Engineering Route Planning Algorithms. In: Lerner J, Wagner D, Zweig KA, editors. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation [Internet]. Berlin, Heidelberg: Springer; 2009 [cited 2021 Oct 25]. p. 117-39. (Lecture Notes in Computer Science). Available from: [DOI:10.1007/978-3-642-02094-0_7]
Delling D, Sanders P, Schultes D, Wagner D. Engineering Route Planning Algorithms. In: Lerner J, Wagner D, Zweig KA, editors. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation [Internet]. Berlin, Heidelberg: Springer; 2009 [cited 2021 Oct 25]. p. 117-39. (Lecture Notes in Computer Science). Available from: [DOI:10.1007/978-3-642-02094-0_7]
Koenig S, Likhachev M. Incremental A*. In: Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Cambridge, MA, USA: MIT Press; 2001. p. 1539-46. (NIPS'01).
Koenig S, Likhachev M. Incremental A*. In: Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Cambridge, MA, USA: MIT Press; 2001. p. 1539-46. (NIPS'01).
Koenig S, Likhachev M. D*lite. In: Eighteenth national conference on Artificial intelligence. USA: American Association for Artificial Intelligence; 2002. p. 476-83.
Koenig S, Likhachev M. D*lite. In: Eighteenth national conference on Artificial intelligence. USA: American Association for Artificial Intelligence; 2002. p. 476-83.
Koenig S, Likhachev M. Fast replanning for navigation in unknown terrain. IEEE Transactions on Robotics. 2005 Jun;21(3):354-63. [DOI:10.1109/TRO.2004.838026]
Koenig S, Likhachev M. Fast replanning for navigation in unknown terrain. IEEE Transactions on Robotics. 2005 Jun;21(3):354-63. [DOI:10.1109/TRO.2004.838026]
LaValle SM. Planning algorithms. Cambridge university press; 2006. [DOI:10.1017/CBO9780511546877]
LaValle SM. Planning algorithms. Cambridge university press; 2006. [DOI:10.1017/CBO9780511546877]
Zagradjanin N, Pamucar D, Jovanovic K. Cloud-based multi-robot path planning in complex and crowded environment with multi-criteria decision making using full consistency method. Symmetry. 2019;11(10):1241. [DOI:10.3390/sym11101241]
Zagradjanin N, Pamucar D, Jovanovic K. Cloud-based multi-robot path planning in complex and crowded environment with multi-criteria decision making using full consistency method. Symmetry. 2019;11(10):1241. [DOI:10.3390/sym11101241]
Wagner G, Choset H. Subdimensional expansion for multirobot path planning. Artificial intelligence. 2015;219:1-24. [DOI:10.1016/j.artint.2014.11.001]
Wagner G, Choset H. Subdimensional expansion for multirobot path planning. Artificial intelligence. 2015;219:1-24. [DOI:10.1016/j.artint.2014.11.001]
Rathi A, Vadali M, others. Dynamic prioritization for conflict-free path planning of multi-robot systems. arXiv preprint arXiv:210101978. 2021;
Rathi A, Vadali M, others. Dynamic prioritization for conflict-free path planning of multi-robot systems. arXiv preprint arXiv:210101978. 2021;
Tang B, Xiang K, Pang M, Zhanxia Z. Multi-robot path planning using an improved self-adaptive particle swarm optimization. International Journal of Advanced Robotic Systems. 2020;17(5):1729881420936154. [DOI:10.1177/1729881420936154]
Tang B, Xiang K, Pang M, Zhanxia Z. Multi-robot path planning using an improved self-adaptive particle swarm optimization. International Journal of Advanced Robotic Systems. 2020;17(5):1729881420936154. [DOI:10.1177/1729881420936154]
Matoui F, Boussaid B, Metoui B, Abdelkrim MN. Contribution to the path planning of a multi-robot system: centralized architecture. Intelligent Service Robotics. 2019;13(1):147-58. [DOI:10.1007/s11370-019-00302-w]
Matoui F, Boussaid B, Metoui B, Abdelkrim MN. Contribution to the path planning of a multi-robot system: centralized architecture. Intelligent Service Robotics. 2019;13(1):147-58. [DOI:10.1007/s11370-019-00302-w]
Standley T. Finding Optimal Solutions to Cooperative Pathfinding Problems. Proceedings of the AAAI Conference on Artificial Intelligence. 2010 Jul 3;24(1):173-8. [DOI:10.1609/aaai.v24i1.7564]
Standley T. Finding Optimal Solutions to Cooperative Pathfinding Problems. Proceedings of the AAAI Conference on Artificial Intelligence. 2010 Jul 3;24(1):173-8. [DOI:10.1609/aaai.v24i1.7564]
Felner A, Goldenberg M, Sharon G, Stern R, Beja T, Sturtevant N, et al. Partial-expansion A* with selective node generation. Proceedings of the AAAI Conference on Artificial Intelligence. 2012 Sep;26(1):471-7. [DOI:10.1609/aaai.v26i1.8137]
Felner A, Goldenberg M, Sharon G, Stern R, Beja T, Sturtevant N, et al. Partial-expansion A* with selective node generation. Proceedings of the AAAI Conference on Artificial Intelligence. 2012 Sep;26(1):471-7. [DOI:10.1609/aaai.v26i1.8137]
Yu J, LaValle SM. Planning Optimal Paths for Multiple Robots on Graphs [Internet]. arXiv; 2013 Jan [cited 2022 May 21]. Report No.: arXiv:1204.3830. Available from: http://arxiv.org/abs/1204.3830
Yu J, LaValle SM. Planning Optimal Paths for Multiple Robots on Graphs [Internet]. arXiv; 2013 Jan [cited 2022 May 21]. Report No.: arXiv:1204.3830. Available from: http://arxiv.org/abs/1204.3830
Wagner G, Choset H. M*: A complete multirobot path planning algorithm with performance bounds. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. p. 3260-7. [DOI:10.1109/IROS.2011.6095022]
Wagner G, Choset H. M*: A complete multirobot path planning algorithm with performance bounds. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. p. 3260-7. [DOI:10.1109/IROS.2011.6095022]
Ferner C, Wagner G, Choset H. ODrM* optimal multirobot path planning in low dimensional search spaces. In: 2013 IEEE international conference on robotics and automation. 2013. p. 3854-9. [DOI:10.1109/ICRA.2013.6631119]
Ferner C, Wagner G, Choset H. ODrM* optimal multirobot path planning in low dimensional search spaces. In: 2013 IEEE international conference on robotics and automation. 2013. p. 3854-9. [DOI:10.1109/ICRA.2013.6631119]
Sharon G, Stern R, Goldenberg M, Felner A. The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence. 2013 Feb 1;195:470-95. [DOI:10.1016/j.artint.2012.11.006]
Sharon G, Stern R, Goldenberg M, Felner A. The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence. 2013 Feb 1;195:470-95. [DOI:10.1016/j.artint.2012.11.006]
Sharon G, Stern R, Felner A, Sturtevant NR. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence. 2015 Feb 1;219:40-66. [DOI:10.1016/j.artint.2014.11.006]
Sharon G, Stern R, Felner A, Sturtevant NR. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence. 2015 Feb 1;219:40-66. [DOI:10.1016/j.artint.2014.11.006]
Luna R, Bekris KE. Efficient and complete centralized multi-robot path planning. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. p. 3268-75. [DOI:10.1109/IROS.2011.6095085]
Luna R, Bekris KE. Efficient and complete centralized multi-robot path planning. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. p. 3268-75. [DOI:10.1109/IROS.2011.6095085]
Wilde BD, Mors A, Witteveen C. Push and rotate: cooperative multi-agent path planning. In: AAMAS. 2013. [DOI:10.1613/jair.4447]
Wilde BD, Mors A, Witteveen C. Push and rotate: cooperative multi-agent path planning. In: AAMAS. 2013. [DOI:10.1613/jair.4447]
Regele R, Levi P. Cooperative Multi-Robot Path Planning by Heuristic Priority Adjustment. In: 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2006. p. 5954-9. [DOI:10.1109/IROS.2006.282480]
Regele R, Levi P. Cooperative Multi-Robot Path Planning by Heuristic Priority Adjustment. In: 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2006. p. 5954-9. [DOI:10.1109/IROS.2006.282480]
Maw AA, Tyan M, Nguyen TA, Lee JW. iADA*-RL: Anytime graph-based path planning with deep reinforcement learning for an autonomous UAV. Applied Sciences [Internet]. 2021;11(9). Available from: https://www.mdpi.com/2076-3417/11/9/3948 [DOI:10.3390/app11093948]
Maw AA, Tyan M, Nguyen TA, Lee JW. iADA*-RL: Anytime graph-based path planning with deep reinforcement learning for an autonomous UAV. Applied Sciences [Internet]. 2021;11(9). Available from: https://www.mdpi.com/2076-3417/11/9/3948 [DOI:10.3390/app11093948]
Khorshid MM, Holte RC, Sturtevant NR. A polynomial-time algorithm for non-optimal multi-agent pathfinding. In: Fourth annual symposium on combinatorial search. 2011.
Khorshid MM, Holte RC, Sturtevant NR. A polynomial-time algorithm for non-optimal multi-agent pathfinding. In: Fourth annual symposium on combinatorial search. 2011.
Matoui F, Boussaid B, Abdelkrim MN. Distributed path planning of a multi-robot system based on the neighborhood artificial potential field approach. Simulation. 2019;95(7):637-57. [DOI:10.1177/0037549718785440]
Matoui F, Boussaid B, Abdelkrim MN. Distributed path planning of a multi-robot system based on the neighborhood artificial potential field approach. Simulation. 2019;95(7):637-57. [DOI:10.1177/0037549718785440]
مهندسی مکانیک مدرس
دوره 23، شماره 3
اسفند 1401
صفحه 161-172