استفاده از الگوریتم‌های غزال کوهستان و کپک مخاطی برای حل مسئله برنامه‌ریزی مسیر

شاهزاده فاضلی, سیدابوالفضل; طیبی, ندا; برخورداری فیروزآبادی, سعیده; موسوی, اسراء

استفاده از الگوریتم‌های غزال کوهستان و کپک مخاطی برای حل مسئله برنامه‌ریزی مسیر

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

نویسندگان

¹ دانشیار،دانشگاه یزد،یزد، ایران

² کارشناسی ارشد ،دانشگاه یزد،یزد، ایران

³ دانشجوی دکتری ،دانشگاه یزد،یزد، ایران

چکیده

یکی از بخش‌های مهم رباتیک برنامهریزی مسیر است، به‌طوری‌که مطالعه مسیر ربات یکی از موضوعات بسیار مهم تلقی میشود. ربات متحرک باید از موقعیت شروع به سمت موقعیت هدف حرکت کند، درحالی‌که در یک محیط حاوی موانع از موانع موجود اجتناب کند. مسیر باید بر اساس برخی از معیارها مانند کوتاهی طول مسیر، همواری مسیر و امنیت مسیر بهینه باشد. در این مطالعه، هدف اصلی حل مسئله برنامه‌ریزی مسیر برای یک ربات به‌صورت شبکه، ایستا و شناخته شده است که معیارهای کوتاه‌ترین فاصله، امنیت مسیر و همواری مسیر را برآورده میسازد. مسئله برنامه‌ریزی مسیر یک مسئله NP-کامل میباشد و برای این مسئله روشها و الگوریتم‌های مختلفی پیشنهاد شده است که شامل روشهای دقیق و فراابتکاری است. برای حل این مسئله با محاسباتی کمتر از الگوریتمهای فراابتکاری میتوان استفاده کرد که در این مطالعه از الگوریتم ژنتیک، الگوریتم غزال کوهستان و الگوریتم کپک مخاطی استفاده شده است. در پیاده‌سازی‌ها علاوه بر استفاده از عملگرهای خود الگوریتمها از سه عملگر ساده‌سازی، بازبینی و جایگزینی استفاده شده است و همچنین یک تابع ارزیابی جدید و برای تولید جمعیت اولیه سه عملگر ترمیم گره، ترمیم پاره‌خط و بهبود گره برای ایجاد مسیرهای تاحدامکان شدنی ارائه شده است. نتایج نشان میدهند که این الگوریتمها دارای کارایی بالایی هستند و همچنین از پیچیدگی محاسباتی کمتری برای حل این مسئله برخوردارند.

کلیدواژه‌ها

20.1001.1.26762935.1402.14.4.1.7

موضوعات

کامپیوتر - محاسبات نرم و هوش مصنوعی

عنوان مقاله [English]

Using Mountain Gazelle and Slime Mould Algorithms to Solve the Path Planning Problem

نویسندگان [English]

Seyed Abolfazl Shahzadeh Fazeli ¹
Neda Tayebi ²
Saeideh Barkhordari Firozabadi ³
Esra Mosavi ³

¹ Associate Professor, Yazd University, Yazd, Iran

² Master's degree, Yazd University, Yazd, Iran

³ PhD Student, Yazd University, Yazd, Iran

چکیده [English]

Path planning is one of the important parts of robotics, so studying the path of the robot is considered one of the most important subjects. The mobile robot must move from the start position to the goal position, while avoiding obstacles in an obstacle environment. The route should be optimal based on some criteria such as shortness of the path, smoothness of the path and security of the path. In this study, the main goal is to solve the path planning problem for a robot in the form of a discrete, static and known, which meet the criteria of shortest distance, path security and path smoothness. Path planning problem is a NP-complete problem and various methods and algorithms have been proposed, which include exact and meta-heuristic algorithms. Meta-heuristic algorithms can be used to solve this problem with less computational load. In this study genetic algorithm, mountain gazelle algorithm, and Slime mould algorithm are used. In implementations, in addition to the operators of the algorithms themselves, three simplification, revision and replacement operators have been used, as well as a new evaluation function has been presented and after generating the initial population of three operators node repair, line segment repair and node improvement to create paths up to feasible path has been used. The results show that these algorithms have high efficiency and also have less computational complexity to solve this problem

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

Meta-heuristic Algorithms
Path Planning
Genetic Algorithm
Mountain Gazelle Optimizer
Slime Mould Algorithm

مراجع

[1] Canny, J.; Reif, J. “New lower bound techniques for robot motion planning problems”; Int. J. Found. Comput. Sci. 28th Annual Symp. on, 1987, 49–60. DOI: 10.1109/SFCS.1987.42

[2] Nearchou, A. C. “Path planning of a mobile robot using genetic heuristics”; Cambridge University Press, 1998, 16, 575–588. DOI: 10.1017/S0263574798000289

[3] Hussein, A.; Mostafa, H.; Badrel-din, M.; Sultan, O.; Khamis, A.; “Metaheuristic optimization approach to mobile robot path planning”; Int. Conf. on, 2012, 1–6. DOI: 10.1109/ICEngTechnol.2012.6396150

[4] Choset, H.; Lynch, K.; Hutchinson, S.; Kantor, G.; Burgard, W.; Kavraki, L.; Thrun, S. “Principles of robot motion: Theory, algorithms, and implementation errata”; 2007, 1–150.

[5] Berg, M. d.; Cheong, O.; Kreveld, M.v.; Overmars, M. “Computational geometry: algorithms and applications”; Springer-Verlag TELOS, 2008. DOI: 10.1007/978-3-540-77974-2

[6] Latombe, J.-C. “Robot motion planning”; Springer Science & Business Media, 2012, 124. DOI: 10.1007/978-1-4615-4022-9

[7] LaValle, S. M. “Planning algorithms”; Cambridge university press, 2006.

[8] Van, J. P.; Berg, D. “Path planning in dynamic environments”; PhD thesis, Utrecht University, 2007.

[9] Liao, W. “Genetic Algorithm based robot path planning”; In Intelligent Computation Technology and Automation, Int. Conf. on, 2008, 1, 56–59. DOI: 10.1109/ICICTA.2008.216

[10] Leena, N.; Saju, K. “A survey on path planning techniques for autonomous mobile robots”; IOSR J. of Mechanical and Civil Eng. 2014, 8, 76–79.

[11] Victerpaul, P.; Saravanan, D.; Janakiraman, S.; Pradeep, J. “Path planning of autonomous mobile robots: A survey and comparison”; Journal of Advanced Research in Dynamical and Control Systems, 2017, 9, 1535–1565.

[12] Svestka, P.; Latombe, J.; Overmars Kavraki, L. “Probabilistic roadmaps for path planning in high-dimensional configuration spaces”; IEEE T. Robotics Autom. 1996, 12, 566–580. DOI: 10.1109/70.508439

[13] LaValle, S. M. “Rapidly-exploring random trees: A new tool for path planning. 1998”, 1998.

[14] Ismail, A.; Sheta, A.; Al-Weshah, M. “A mobile robot path planning using genetic algorithm in static environment”; Journal of Computer Science, 2008, 4, 341–344.

[15] Buckley, S. J. “Fast motion planning for multiple moving robots”; IEEE Int. Conf. Robot. Autom. 1989, 322–326.

[16] Ni, J., Wang, K., Huang, H., Wu, L. and Luo, C., 2016, August. Robot path planning based on an improved genetic algorithm with variable length chromosome. In 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD) (pp. 145-149). IEEE.

[17] Abdollahzadeh, B.; Gharehchopogh, F. S.; Khodadadi, N.; Mirjalili, S. “Mountain gazelle optimizer: a new nature-inspired metaheuristic algorithm for global optimization problems”; Adv. Eng. Softw. 2022, 174, 103282. DOI :10.1016/j.advengsoft.2022.103282

[18] Seini, T., Yussif, A.S. and Katali, I.M. Enhancing Mountain Gazelle Optimizer (MGO) with an Improved F-Parameter for Global Optimization. Int. Res. J. Eng. Technol, 2023, 10(6), pp.921-930.

[19] Sarangi, P. and Mohapatra, P.,. Evolved opposition-based mountain gazelle optimizer to solve optimization problems. Journal of King Saud University-Computer and Information Sciences, 2023, 35(10), p.101812.

[20] Houssein, E. H.; Mahdy, M. A.; Shebl, D.; Manzoor, A.; Sarkar, R.; Mohamed, W.M. “An effcient slime mould algorithm for solving multi-objective optimization problems”; Expert Syst.- Appl. 2021, 187, 115870.DOI: 10.1016/j.eswa.2021.115870