Tek ve çok amaçlı robot yol planlama problemi için hibrit bir optimizasyon yöntemi

Abstract

Yol planlama robotik alanında popüler bir konudur. Akıllı bir robotun başlangıç noktasından hedef noktasına engellere çarpmadan kendi kendine hareket edebilme yeteneğine sahip olması gerekmektedir. Bu tez çalışmasında bir mobil robotun yol planlaması için iki yöntem önerilmiştir. Önerilen yöntemler İyileştirilmiş Genetik Algoritma (İGA) ve Dijkstra Algoritması ile Genetik Algoritmayı birlikte içeren bir Hibrit Genetik Algoritma’dır (HGA). İGA’da, standart genetik algoritma operatörlerinin kullanımında RYPP’nin yapısı gereği bazı değişiklikler yapılmıştır. Ayrıca önerilen HGA’da, İGA aracılığıyla muhtemel çözümler aranırken, Dijkstra Algoritması ile de yerel arama yoğunlaştırılmaktadır. Önerilen algoritmalar hücrelere ayrılmış bir çevrede robotun sekiz yönlü hareketine izin vermektedir. Yöntemler uygulanırken RYPP’nin iki türü dikkate alınmıştır: Tek Amaçlı RYPP (TARYPP) ve Çok Amaçlı RYPP (RYPP). TARYPP ile rota uzunluğu en küçüklenmeye çalışılırken, ÇARYPP’de mesafe, düzgünlük ve güvenlik amaçları optimize edilmiştir. Dijkstra ve Bellman-Ford Algoritmaları, 0-1 Tam sayılı Doğrusal Programlama Modeli, İGA ve HGA kullanılarak TARYPP için çözümlere ulaşılmıştır. Ayrıca ÇARYPP için de İGA ve HGA kullanılmıştır. Farklı boyutlardaki problemler için sonuçlar elde edilmiş ve bu sonuçlar karşılaştırılmıştır. Sonuçlar, İGA ve HGA’nın kısa zamanda diğer kesin çözüm yöntemleri kadar iyi çözümler ürettiğini ve HGA’nın da İGA’dan iterasyon ve hesaplama süresi bakımından daha iyi çözümler verdiğini göstermektedir.

Path planning is a popular issue in mobile robotics. An intelligent robot must be able to move by itself from a start location to a target location without collision with obstacles. This thesis proposes two methods to solve the problem of path planning for a mobile robot in a static environment with obstacles. The proposed algorithms are an Improved Genetic Algorithm (IGA) and a Hybrid Genetic algorithm (HGA) which includes Genetic and Dijkstra algorithms together. In use of IGA, some changes are made in standard genetic algorithm’s operators because of structure of robot path planning problem (RPPP). Additionally, proposed HGA provides diversification while searching possible solutions with IGA, but Dijkstra algorithm makes more and more intensification in local area. The proposed algorithms allows eight-neighbor movements in a grid environment. When applying methods; two types of RPPP are considered: Single Objective and Multi-Objective RPPP (SORPPP and MORPPP). While minimizing total path distance is intended in SORPP, distance, smootness and security objectives are optimized in MORPPP. SORPPP is solved by using Dijkstra and Bellman-Ford algorithms, 0-1 Integer Linear Programing Model, IGA and HGA. Additionally, IGA and HGA are used for MORPPP. Results are obtained for different dimensions of problems and reported with comparisons. Results indicate that IGA and HGA provide solutions as well as other exact solution methods in a short time for large dimensional problems and HGA gives better solutions than IGA in terms of iteration number and computation time both SORPPP and MORPPP.