Otonom mobil robotlar için A* ve olasılıksal yol haritası tabanlı hibrit yol planlama algoritması tasarımı ve analizi
A* and probabilistic roadmap based hybrid path planning algorithm design and analysis for autonomous mobile robots
Yazar: BARIŞ UZUN
Danışman: PROF. DR. MÜSLÜM CENGİZ TAPLAMACIOĞLU ; DOÇ. DR. HALUK GÖZDE
Gazi Üniversitesi / Fen Bilimleri Enstitüsü / Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2022
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering
Dizin: Algoritmalar = Algorithms ; Endüstriyel robotlar = Industrial robots ; Yol planlama = Path planning

Özet:
Son yıllarda gelişen teknolojiler ile robot teknolojilerinde büyük ilerlemeler kaydedilmiştir. Gelişen robot teknolojileri insan hayatının her alanında görülmektedir. Robotlar geliştikçe otonom yani kendi kendine hareket edebilecek, kendi kararlarını kendi verebilecek hale gelmiştir. Otonom teknolojisinin en önemli uygulamalarından biri en kısa rota hesaplama algoritmalarıdır. Bu tez çalışmasında robot teknolojilerinden bahsedilmiş ve en kısa rota hesaplama algoritmaları analiz edilmiştir. Öncelikle rota hesaplama algoritmaları sınıflandırılmaları ile gösterilmiş ve ilgili algoritmalar özet şeklinde açıklanmıştır. Tezin ana konusu olan A* ve PRM algoritmaları detaylıca açıklanmıştır. A* algoritması pratik uygulamalarda verimli ve stabil çalışan bir algoritmadır. Harita üzerindeki en kısa rotayı mutlaka bulur fakat harita boyutu büyüdükçe rota hesaplama süresi üstel bir şekilde artmaktadır. Bu sebeple mevcut bu tez çalışmasında PRM algoritması kullanılarak A* algoritmasının bu dezavantajının ortadan kaldırılması hedeflenmiştir. Ayrıca tez çalışmasında PRM algoritması detaylı olarak analiz edilmiş ve PRM algoritması ile A* algoritmasının birlikte çalışacağı hibrit bir algoritma geliştirilmiştir. Literatürdeki diğer çalışmalardan farklı olarak yeni oluşturulan algoritmanın verimliliğinin test edilmesi için 10 farklı haritada 2 algoritma rota oluşturma süresi, rota uzunluğu vb. gibi parametreler açısından karşılaştırılmıştır. Bu haritalarda literatür çalışmaları dikkate alınarak farklı zorluklarda performanslarının testlerinin gerçekleştirilmesi için farklı boyutlarda ve farklı engel yoğunluğunda analizler gerçekleştirilmiştir. Çalışmanın devamında test sonuçları incelenmiş ve algoritmaların avantajları ve dezavantajları görülmüştür. Ayrıca bu dezavantajların çözümü için yeni öneriler sunulmuştur.

Abstract:
With the developing technologies in recent years, great progress has been made in robot technologies. Developing robot technologies are seen in all areas of human life. As robots develop, they have become autonomous which they can move on their own and make their own decisions. One of the most important applications of autonomous technology is the shortest route calculation algorithms. In this thesis, robot technologies are mentioned, and the shortest route calculation algorithms are analyzed. Firstly, route calculation algorithms are shown with their classification and related algorithms are explained in summary form. A* and PRM algorithms, which are the main subject of the thesis, are explained in detail. The A* algorithm is an efficient and stable algorithm in practical applications. It definitely finds the shortest route on the map, but as the map size increases, the route calculation time increases exponentially. For this reason, it is aimed to eliminate this disadvantage of the A* algorithm by using the PRM algorithm in this thesis study. In addition, the PRM algorithm was analyzed in detail and a hybrid algorithm was developed in which the PRM algorithm and A* algorithm would work together in the thesis study. Unlike other studies in the literature, in order to test the efficiency of the newly created algorithm, 2 algorithms on 10 different maps compared in terms of parameters such as route creation time, route length, etc. Considering the literature studies on these maps, analyzes of different sizes and different obstacle densities were carried out in order to test their performance at different difficulties. In the continuation of the study, the test results were examined, and the advantages and disadvantages of the algorithms were seen. In addition, new suggestions are presented for the solution of these disadvantages.