Otonom mobil robotlar için metasezgisel yöntemler kullanılarak yol planlama algoritmasının geliştirilmesi
Development of path planning algorithm using metaheuristic methods for autonomous mobile robots
Yazar: YUNUS TEZEL
Danışman: DR. ÖĞR. ÜYESİ SUAT KARAKAYA
Kocaeli Üniversitesi / Fen Bilimleri Enstitüsü / Mekatronik Mühendisliği Ana Bilim Dalı / Mekatronik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2024
Konu: Mekatronik Mühendisliği = Mechatronics Engineering
Dizin: Hareketli robotlar = Mobile robots ; Metasezgisel algoritmalar = Metaheuristic algorithms

Özet:
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ı, fizik tabanlı, evrimsel tabanlı ve insan tabanlı olmak üzere dört farklı alt kategoriye ayrılır. Bu tez kapsamında global yol planlama için üç farklı metasezgisel algoritma kullanılacaktı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. Bu haritalar robot çalışmaya başlamadan önce robot tarafından bilinen, haritalanmış (mapped) statik engeller içermektedir. Bu haritalar kullanılarak farklı yol planlama problemlerinde algoritmaların nasıl bir sonuç verdiğ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.
Metasezgisel algoritmalar kullanılarak global yol planlama yapıldıktan sonra ortama robot tarafından daha önce bilinmeyen haritalanmamış (unmapped) statik engeller eklenmiştir. Robot bu engellerle karşılaştığında geliştirilen yerel yol planlama algoritmasını çalıştırarak tekrar rotasına dönmektedir. Geliştirilen yerel yol planlama algoritması Parçacık Sürü Optimizasyonu (Particle Swarm Optimization, PSO) temellidir. Robot haritalanmamış bir engelle karşılaştığında geliştirilen pencere yöntemi ile rotasına yeniden bağlanacağı noktayı belirler. Daha sonra PSO algoritması belirli bir bölge içerisine rastgele parçacıklar yerleştirir. Bu parçacıkların maliyet değeri her iterasyonda güncellenir. Robot, algoritma sonunda bulunan en iyi parçacığı kullanarak engelden kaçınır ve rotasına geri döner. Robot rotasında ilerler ve tekrar bir engel ile karşılaşırsa aynı adımları tekrarlayarak hedefine ulaşmaya çalışır.

Abstract:
Path planning for mobile robots is the process of determining the optimal route to reach a specific 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 classified into two categories: population-based and single-solution-based. Population-based algorithms are divided into four different subcategories: swarm-based, physic-based, evolutionary-based and human-based. Within the scope of this thesis, three different metaheuristic algorithms will be used for global path planning. Various grid-based maps with specialized scenarios were created to compare the performance of these metaheuristic algorithms. These maps contain mapped static obstacles that are known before the robot starts operating. The results of algorithms in different path planning problems have been observed using these maps. As a result of the observations, the performances of these algorithms were tested and compared on different maps created.
After performing global path planning using metaheuristic algorithms, unmapped static obstacles that the robot did not know before starting work were added to the environment. When the robot encounters these obstacles, it returns to its route by running the developed local path planning algorithm. The developed local path planning algorithm is based on Particle Swarm Optimization (PSO). When the robot encounters an unmapped obstacle, it determines the point to reconnect to its route with the developed window method. The PSO algorithm then places random particles within a specific region. The cost value of these particles is updated at each iteration. The robot avoids the obstacle using the best particle found at the end of the algorithm and returns to its route. The robot proceeds along its route, and if it encounters another obstacle, it repeats the same steps to reach its destination.