Otonom araçlar için yol bulma probleminin genetik algoritmalar ve FPGA ile çözümü ve gerçekleştirilmesi
The solution and implementation of path planning problem with genetic algorithms and FPGA for autonomous vehicles
Yazar: ADEM TUNCER
Danışman: DOÇ. DR. MEHMET YILDIRIM
Kocaeli Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik-Bilgisayar Eğitimi Ana Bilim Dalı
Derece: Doktora, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering ; Mühendislik Bilimleri = Engineering Sciences
Dizin: En kısa yol problemi = Shortest path problem ; FPGA = FPGA ; Genetik algoritmalar = Genetic algorithms ; Robot yönlendirme = Robot navigation ; Sezgisel algoritmalar = Heuristic algorithms

Özet:
Bu tez çalışmasında, otonom bir gezgin robot için yol bulma problemi Genetik Algoritmalar (GA) kullanılarak çözüldü. GA ile yol bulma problemine ilişkin yeni bir mutasyon operatörü geliştirildi ve bu yeni mutasyon operatörü ile daha önce literatürde sunulmuş olan farklı mutasyon operatörleri karşılaştırıldı. Karşılaştırmalar sonucunda yeni mutasyon operatörünün daha başarılı performans sergilediği sonucuna varıldı.
GA ile yol bulma algoritması Pioneer 3-DX gezgin robot üzerinde denendi. Robot ile haberleşmede Matlab programı kullanıldı. Görüntü almak amacıyla, laboratuvar tavanına bir kamera yerleştirilerek lokalizasyon gerçekleştirildi, robotun ortamdaki engelleri ve kendi konumunu belirleyebilmesi sağlandı. Böylece, lokalizasyon ve yol bulma işlemleri bütünleşik bir sistem olarak gerçek laboratuvar ortamında denendi.
Bir bilgisayar üzerinde çalıştırılan GA, daha sonra Sahada Programlanabilir Kapı Dizisi (Field Programmable Gate Array, FPGA) üzerinde donanımsal olarak gerçekleştirildi. GA önce yarı yazılımsal yarı donanımsal bir şekilde hibrit olarak daha sonra tamamı donanımsal olarak tasarlandı. Hibrit yapıdaki GA?nın, sadece amaç fonksiyon hesaplayan bölümü donanımsal Intellectual Property Core (IP çekirdek) ile, diğer operatörleri de Microblaze adı verilen yazılımsal işlemci üzerinde çalışacak şekilde tasarlandı ve performans katkısı incelendi. Daha sonra da, sistem tamamen IP çekirdek ile donanımsal olarak gerçekleştirildi ve performans katkısı incelendi.
Kameradan görüntü alıp işleyerek harita oluşturan, GA ile yol bulan, robot ile haberleşen, robotun GA ile bulunan bir yol bilgisine göre veya kullanıcı tarafından belirlenen bir yol koordinatlarına göre ilerleyebilmesini sağlayan Matlab-GUI tabanlı bir arayüz yazıldı.
Tez çalışması kapsamında sistemin tamamı gerçek bir laboratuvar ortamında uygulandı, böylece çalışmanın sadece benzetim ortamında kalmayıp, gerçek dünyada uygulanabilirliği gösterildi.

Abstract:
In this thesis, the problem of the path planning for an autonomous mobile robot was resolved by using Genetic Algorithms. A new mutation operator was developed to address the problem of path planning by GA. This mutation operator was compared with various other mutation operators documented in research literature. In light of the comparisons, it was found that the new mutation operator showed superior performance than the other operators. 
Path planning with GA was tested on the Pioneer 3-DX mobile robot. Matlab was used to communicate with the robot. On the part of localization, a camera was installed on the ceiling of the laboratory to receive images and to assist the robot with the ability to determine its own location and the obstacles in the environment. This way, procedures of localization and path planning were tested in the real lab environment. 
First run on a computer, GA was later performed in hardware on the Field Programmable Gate Array (FPGA). First, GA was designed as a hybrid fashion, in which a section was designed in software and the other sections were designed in hardware. Then, it was designed as entirely in hardware. In the hybrid design, only the component, that is calculating the objective function, was designed with hardware, namely IP (intellectual property) core. The rest of the operators were designed in software to work on the Microblaze processor, which is a soft-processor.  Performance contribution was evaluated by comparing with the fully software design. Subsequently, the system was designed entirely in hardware with an IP core and performance contribution was evaluated.
A Matlab-GUI based interface was written for fetching images from the camera and processing them to form a map, path planning with GA, communicating with the robot, moving the robot according to the path found by the GA or the path, coordinates of which  are provided by the user.
Within the frame of the dissertation study, the entire system was performed in a real lab environment, so as to demonstrate that the study is applicable in the real world, besides being simulated.