Mobil robotların 3 boyutlu yol bulması için pekiştirmeli öğrenme ve metasezgisel algoritmalar
Reinforcement learning and metaheuristic algorithms for three-dimensional path planning of mobile robots
Yazar: ROYAL ALIYEV
Danışman: DR. ÖĞR. ÜYESİ ADEM ÖZYAVAŞ
İstanbul Aydın Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2021
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Hareket edebilen robotların zaman geçtikçe geliştirilmesiyle bu robotların kendi başlarına hareket etmelerini sağlayacak olan algoritmalara olan ihtiyaç da artmıştır. Bu algoritmaların ana hedefi hareket edebilen robotlar için 3 Boyutlu Yol Bulma Problemini çözmektir. Bu algoritmalar sayesinde robotlar bir noktada diğerine sadece kendi aktüatörlerini kullanarak güvenli bir şekilde gidebiliyorlar. Şimdiye kadar birkaç farklı yöntem bu problemi çözmek için ortaya atılmıştır. Çoğu deterministtik yöntem bu problemi çözebilmiştir ama bunu yaparken çok da tatminkar olmaya sonuçlar vermiştir. Bazı çalışmalardaysa bu problem NP-Zor bir problem olarak ele alınmıştır ve bu kategoriye dahil olan diğer optimizasyon problemleri gibi bu problem de Metasezgisel algoritmalar kullanılarak çözülmeye çalışılmıştır. Bu yaklaşım sayesinde daha önce bahsedilen deterministtik yöntemlere kıyasla çok daha iyi sonuçlar ortaya çıkmıştır. Buna bakmayarak Metasezgisel algoritmaların kendilerinin de bazı eksiklikleri ve dezavantajları vardır. En önemli olanıysa bu algoritmaların bazen lokal minimumlarda takılıp kalmasıdır. Yapılan bu çalışmada optimizasyon problemlerini çözmek için 8 farklı algoritma önerilmiştir. Bu algoritmaların 4'ü klasik Metasezgisel algoritmalarıdır bunlar sırasıyla Balina Optimizasyon Algoritması, Gri Kurt Optimizasyon algoritması, Artımlı Gri Kurt Optimizasyon algoritması ve son olarak da Genişletilmiş Gri Kurt Optimizasyon algoritmasıdır. Çalışmada önerilmiş olan diğer 4 algoritmadaysa bu Metasezgisel algoritmaların Pekiştirmeli Öğrenme algoritmaları kullanılarak geliştirilmiş olan hibrit versiyonlarıdır. Bu algoritmalar sırasıyla Pekiştirmeli Öğrenme tabanlı Balina Optimizasyon Algoritması, Pekiştirmeli Öğrenme tabanlı Gri Kurt Optimizasyon algoritması, Pekiştirmeli Öğrenme tabanlı Artımlı Gri Kurt Optimizasyon algoritması ve son olarak da Pekiştirmeli Öğrenme tabanlı Genişletilmiş Gri Kurt Optimizasyon algoritması olarak isimlendirilmiştir. Önerilen bu yeni hibrit algoritmalarında olan mekanizmalar sayesinde algoritmaların zaman ve alan karmaşıklığı çok fazla artmadan arama ve saldırma aşamaları arasındaki denge sağlanabilmektedir ve bu mekanizmalar Pekiştirmeli Öğrenme algoritması kullanılarak geliştirilmiştir. Çalışmada bu optimizasyon algoritmalarıyla beraber 2 yeni yol bulma algoritması geliştirilmiştir. Bu algoritmalar sayesindeyse 3 Boyutlu Yol Bulma problemi optimizasyon algoritmalarına kolayca uyarlanabilmektedir. Bir diğer önerilmiş olan mekanizma sayesindeyse hareket edebilen robotlar en zorlu alanlarda bile en zorlu engellerden kolayca kaçabilmektedirler. Çıkan sonuçlara göre klasik Metasezgisel algoritmalarıyla kıyaslandığı zaman yeni hibrit algoritmalar daha iyi çalışmaktadırlar. Metasezgisel algoritmalarsa daha basit yapılarıyla ve daha az sayıdaki işlemleriyle daha hızlı çalışırlar.

Anahtar Kelimeler: Pekiştirmeli Öğrenme, Metasezgisel Algoritmalar, Hibrit Pekiştirmeli Öğrenme tabanlı Metasezgisel Algoritmalar, Üç Boyutlu Yol Bulma, İnsansız Hava Araçları

Abstract:
As the implementation areas of mobile robots increase demand for algorithms to control robots autonomously raised up. The purpose of these algorithms is Three-dimensional Path Planning which can take robots from one point to another safely using their own actuators. Till now several methods have been proposed for this problem. But most of the classic deterministic Path Planning algorithms just gave satisfactory quality results. Some works considered this problem as NP-Hard problem and tried to solve it like other optimization problems using metaheuristic algorithms. This approach to the problem obviously produced much better results than previous methods. But there are still some drawbacks of metaheuristic methods such as getting stuck in the local minima. In this work 8 different algorithms have been proposed to solve the optimization problems including the Three-dimensional Path Planning problem. Four of those algorithms are classical Metaheuristic algorithms, these algorithms are Whale Optimization Algorithm, Gray Wolf Optimizer algorithm, Incremental Wolf Optimizer algorithm and last one Expanded Wolf Optimizer algorithm. And, other 4 algorithms which have been proposed in this work are the hybrid version of these Metaheuristic algorithms with Reinforcement Learning. These hybrid algorithms called respectively Reinforcement Learning based Whale Optimization Algorithm, Reinforcement Learning based Gray Wolf Optimizer algorithm, Reinforcement Learning based Incremental Wolf Optimizer algorithm and Reinforcement Learning based Expanded Wolf Optimizer algorithm. These newly proposed hybrid algorithms have the mechanisms to balance exploration and exploitation phases of Metaheuristic algorithms and the mechanisms use Reinforcement Learning without considerably increasing time and space complexity. Beside the Optimization algorithms 2 new algorithms are proposed in this work to adapt the Path Planning problem to the Optimization algorithms and one mechanism that helps the mobile robots to avoid the obstacles even in the most complex environments. Due to the results new hybrid algorithm performs better than the conventional metaheuristic algorithms in different ways of formulating fitness values but classic Metaheuristic algorithms work faster according to the simpler mechanism and less amount of the operations.

Keywords: Reinforcement Learning, Metaheuristic Algorithms, Hybrid Reinforcement Learning based Metaheuristic Algorithms, Three-dimensional Path Planning, Unmanned Aerial Vehicles