Please use this identifier to cite or link to this item: https://hdl.handle.net/11499/1079
Title: Tek ve çok amaçlı robot yol planlama problemi için hibrit bir optimizasyon yöntemi
Other Titles: A Hybrid optimization method for single and multi objective robot path planning problem
Authors: Boğar, Eşref
Advisors: Selami Beyhan
Keywords: Mobil Robotlar
Yol Planlama
İyileştirilmiş Genetik Algoritma
Dijkstra Algoritması
Bellman-Ford Algoritması
Engelli Çevre
Hibrit Genetik Algoritma
Mobile Robots
Path Planning
Improved Genetic Algorithm
Dijkstra Algorithm
Bellman-Ford Algorithm
Environment With Obstacles
Hybrid Genetic Algorithm
Publisher: Pamukkale Üniversitesi Fen Bilimleri Enstitüsü
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.
URI: https://hdl.handle.net/11499/1079
Appears in Collections:Tez Koleksiyonu

Files in This Item:
File Description SizeFormat 
Eşref Boğar.pdf2.48 MBAdobe PDFThumbnail
View/Open
Show full item record



CORE Recommender

Page view(s)

138
checked on Mar 27, 2024

Download(s)

228
checked on Mar 27, 2024

Google ScholarTM

Check





Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.