Development of Path Planning Algorithm for Autonomous Mobile Robots using Metaheuristic Methods and Comparison of Their Peformances


Creative Commons License

Tezel Y., Karakaya S.

5th International Engineering Research Symposium, Düzce, Turkey, 7 - 09 March 2024, pp.55-65

  • Publication Type: Conference Paper / Full Text
  • City: Düzce
  • Country: Turkey
  • Page Numbers: pp.55-65
  • Yıldız Technical University Affiliated: Yes

Abstract

In recent years, studies have been carried out on path planning, which plays a critical role in mobile robot

navigation, and metaheuristic algorithms are used to solve this problem. Path planning for mobile robots is

the process of determining the optimal route to reach a speci􀏐ic goal or task without hitting any obstacles.

This process is an optimization problem that aims to ensure that the mobile robot reaches the target point

from a starting point at the least cost. Path planning can be performed using metaheuristic algorithms. Metaheuristic algorithms are classi􀏐ied into two categories: population-based and single-solution-based.

Population-based algorithms are divided into 􀏐ive different subcategories: swarm-based, physic-based,

evolutionary-based, human-based and math-based. Within the scope of this study, three different

metaheuristic algorithms will be used for path planning. There are Simulated Annealing (SA) which is a

single-solution-based algorithm, Genetic Algorithm (GA) which is a population and evolutionary-based

algorithm, and Cuckoo Search (CS) which is a population and swarm-based algorithm. Various grid-based

maps with specialized scenarios were created to compare the performance of these metaheuristic

algorithms. Thus, the kind of results the algorithms produced in different path planning problems was

observed. As a result of the observations, the performances of these algorithms were tested and compared

on the maps that were initially designed.

Keywords: Autonomous Mobile Robots, Metaheuristic Algorithms, Optimization, Path Planning

Son yıllarda mobil robot navigasyonunda kritik bir önem taşıyan yol planlama üzerine çalışmalar

yapılmakta ve bu problemi çözmek için metasezgisel algoritmalar kullanılmaktadır. Mobil robotlar için yol

planlama, belirli bir hedefe veya göreve ulaşmak amacıyla engellere çarpmadan en uygun rotayı belirleme

sürecidir. Bu süreç mobil robotun bir başlangıç noktasından hedef noktaya en az maliyetle ulaşmasını

amaçlayan bir optimizasyon problemidir. Yol planlama, metasezgisel algoritmalar kullanılarak

gerçekleştirilebilir. Metasezgisel algoritmalar popülasyon tabanlı ve tek çözüm tabanlı olmak üzere ikiye

ayrılır. Popülasyon tabanlı algoritmalar kendi içinde sürü tabanlı, 􀏐izik tabanlı, evrimsel tabanlı, insan

tabanlı ve matematik tabanlı olmak üzere beş farklı alt kategoriye ayrılır. Bu çalışma kapsamında yol

planlama için üç farklı metasezgisel algoritma kullanılacaktır. Bu algoritmalar; tek çözüm tabanlı olan

Benzetimli Tavlama (Simulated Annealing, SA), popülasyon ve evrimsel tabanlı algoritma olan Genetik

Algoritma (Genetic Algorithm, GA), popülasyon ve sürü tabanlı olan Guguk Kuşu Arama (Cuckoo Search, CS)

algoritmalarıdır. Bu metasezgisel algoritmaların performanslarının karşılaştırılması için ızgara tabanlı

farklı senaryolar içeren haritalar oluşturulmuştur. Böylece farklı yol planlama problemlerinde

algoritmaların nasıl bir sonuç ürettiği gözlemlenmiştir. Gözlemlerin sonucunda, bu algoritmaların

performansları oluşturulan farklı haritalarda test edilmiş ve karşılaştırmaları yapılmıştır.

Anahtar Kelimeler: Metasezgisel Algoritmalar, Optimizasyon, Otonom Mobil Robotlar, Yol Planlama