جستجو در:
دوره 23، شماره 3 - ( اسفند 1401 )
جلد 23 شماره 3 صفحات 172-161 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Khanmirza E, Haghbeigi M, Farzan M. A New Incremental Search Method for Multi-robot Path Planning. Modares Mechanical Engineering 2023; 23 (3) :161-172
URL: http://mme.modares.ac.ir/article-15-63177-fa.html
URL: http://mme.modares.ac.ir/article-15-63177-fa.html
خان میرزا اسماعیل، حق بیگی مرتضی، فرزان محمد. روش جستجوی تدریجی جدید برای طراحی مسیر سیستم‌های چندرباتی. مهندسی مکانیک مدرس. 1401; 23 (3) :161-172
اسماعیل خان میرزا* 
1، مرتضی حق بیگی2 ، محمد فرزان2
1، مرتضی حق بیگی2 ، محمد فرزان2
1- دانشگاه علم و صنعت ایران ، khanmirza@iust.ac.ir
2- دانشگاه علم و صنعت ایران
2- دانشگاه علم و صنعت ایران
چکیده: (1386 مشاهده)
یکی از این چالش‌های مساله طراحی مسیر چندرباتی، افزایش ابعاد فضای جستجو به صورت نمایی همراه با افزایش تعداد رباتها در محیط عملیات است. بنابراین، به الگوریتم‌هایی نیاز است که دارای کارایی محاسباتی بوده و بتوانند مسیرهای بهینه و بدون برخورد رباتها را در زمان محدود طراحی کنند. در این مقاله یک الگوریتم طراحی مسیر مرکزی برای هدایت رباتها در محیط عملیات مشترک ارائه شده است. این الگوریتم یک روش جستجوی اکتشافی تدریجی است که در آن الگوریتم D* Lite به منظور تطبیق با حالت چندرباتی توسعه داده شده است. هماهنگی در طراحی مسیر برای تمام رباتها بر اساس مفهوم زمان تصرف بوده که در ساختار مدل مفهومی محیط پیاده‌سازی شده است. همچنین، یک تابع مرکزی جهت به‌روزرسانی اطلاعات مدل مفهومی محیط و حرکت تدریجی رباتها توسعه داده شده است. به منظور ارزیابی روش پیشنهادی، دو گروه شبیهسازیهای استاتیک و پویا انجام شده است. در دسته اول، تمرکز بر مطالعه اثر پارامترهای الگوریتم است. نتایج نشان میدهد که الگوریتم پیشنهادی قابلیت طراحی مسیر برای 40 ربات در محیطی با 55 درصد فضای آزاد را دارد و نیز رابطه زمان محساباتی و تعداد رباتها غیر نمایی است. دسته دوم شبیهسازیها در محیط سهبعدی Gazebo انجام شده که به صورت برخط و پویا است. نتایج روش پیشنهادی با روشی بر اساس میدانهای پتانسیل مصنوعی برای تعداد 14 ربات مورد مقایسه قرار گرفته است. نتایج نشان میدهد که با افزایش تعداد رباتها از 9 عدد، زمان انجام عملیات برای روش مبتنی بر میدان پتانسیل افزایش زیادی پیدا کرده و یا غیرممکن میشود.
نوع مقاله: پژوهشی اصیل |
موضوع مقاله:
رباتیک
دریافت: 1401/5/5 | پذیرش: 1401/9/6 | انتشار: 1401/12/10
دریافت: 1401/5/5 | پذیرش: 1401/9/6 | انتشار: 1401/12/10
فهرست منابع
1. 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]
2. 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]
3. 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]
4. 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]
5. 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]
6. 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]
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]
8. 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).
9. Koenig S, Likhachev M. D*lite. In: Eighteenth national conference on Artificial intelligence. USA: American Association for Artificial Intelligence; 2002. p. 476-83.
10. 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]
11. LaValle SM. Planning algorithms. Cambridge university press; 2006. [DOI:10.1017/CBO9780511546877]
12. 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]
13. Wagner G, Choset H. Subdimensional expansion for multirobot path planning. Artificial intelligence. 2015;219:1-24. [DOI:10.1016/j.artint.2014.11.001]
14. Rathi A, Vadali M, others. Dynamic prioritization for conflict-free path planning of multi-robot systems. arXiv preprint arXiv:210101978. 2021;
15. 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]
16. 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]
17. 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]
18. 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]
19. 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
20. 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]
21. 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]
22. 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]
23. 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]
24. 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]
25. Wilde BD, Mors A, Witteveen C. Push and rotate: cooperative multi-agent path planning. In: AAMAS. 2013. [DOI:10.1613/jair.4447]
26. 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]
27. 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]
28. Khorshid MM, Holte RC, Sturtevant NR. A polynomial-time algorithm for non-optimal multi-agent pathfinding. In: Fourth annual symposium on combinatorial search. 2011.
29. 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]
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |