Mobil Robotların Yol Planlaması için Harita Ön İşlemeli Yol Bulma Algoritması Geliştirilmesi

Abstract

Mobil robotlar günümüzde bir çok ortamda kullanılmaktadır. Mobil robotların, engellerle dolu olduğu bir ortamda bir başlangıç noktasından bir hedef noktasına çarpışmasız ulaşabilmesi için yol planlama algoritmaları kritik öneme sahiptir. Bu tez çalışmasında araba benzeri kısıtlı manevra yeteneğine sahip araçlarda, aracın kinematik kısıtlarını dikkate alarak güvenli bir yol planlaması gerçekleştiren yeni bir yol planlama algoritması geliştirilmiştir. Geliştirilen yöntem; Hybrid A* algoritması ile jump point search algoritmalarını birleştiren, ön işlemeye dayalı yeni bir yöntem önermektedir. Klasik Hybrid A* algoritması araba benzeri araçlar için aracın takip edebileceği eğrisel yollar planlayabilmektedir. Ancak farklı harita şartlarında Hybrid A* algoritmasının hedef noktayı bulabilme süresi uzayabilmektedir. Özellikle hedefe giden yan yolların bulunduğu haritalar ya da hedefe gidiyormuş gibi görünen ancak çıkmaz bir sokak ile son bulan yollar bulunduran haritalar bu durum için bir örnektir. Hybrid A* algoritmasının bu dezavatajı, geliştirilen yöntemle arama işlemi üç aşamada gerçekleştirilerek çözülmüştür. Aşamalar sırasıyla: Haritada önemli noktaların bulunduğu ön işleme adımı, önemli noktalar kullanılarak hedefe giden geometrik olarak en kısa yolun bulunduğu grafik arama aşaması ve son olarak, grafik araması aşamasında belirlenen önemli noktalar arasında kinematik kısıtlamalara uygun eğrisel yolların planlandığı Hybrid A* tabanlı yol planlama aşamasıdır. Grafik arama aşaması ve Hybrid A* tabanlı yol planlama aşaması, başlangıç ve hedef noktasına göre gerçek zamanlı olarak çalıştırılmaktadır. ROS ortamında, testlerin gerçekleştirileceği iki ortam modellenmiş ve bu modeller Gazebo simülasyon ortamına aktarılmıştır. Bu ortamlar, Karto mapping adı verilen haritalama algoritması kullanılarak haritalandırılmıştır. Oluşturulan haritalar, bir maliyet haritasına dönüştürülerek geliştirilen algoritmasının testleri yapılmıştır. Yapılan simülasyon testlerinde gelitirilen yöntemin hedefe başarı ile Hybrid A* algoritmasından daha hızlı ulaştığı görülmüştür.Mobile robots are used in many places in today's world. Planning algorithms has a vital position for mobile robots to achieve a target point from a starting point without colliding any obstacles. In this thesis; a new path-planning algorithm for vehicles with restricted maneuverability like cars, is developed executing a safe path-planning by considering the kinematic constraints of a vehicle. The new developed method suggests a new one based on preprocessing, combining Hybrid A* and jump point seach algorithms. Classic Hybrid A* can plan curved paths for vehicles like cars can follow. However, the Hybrid A* algorithm's duration reaching the target point can extend in different map conditions. Especially; the maps with side roads directing the endpoint or maps with roads, looking like directing to the endpoint but end with a dead end, present example for the situation. Hybrid A* algorithm' disadvantage has been solved with a new developed method, a search process. Three stages are given respectively as; the preprocessing stage with a map containing important landmarks, the graphic searching stage that contains the geometrically shortest path leading to the target point using important landmarks and finally a path-planning stage among landmarks that is determined during the graphic searching stage based on Hybrid A*, where curvilinear paths are planned in accordance with kinematic constraints. Graphic searching and path-planning stage based on Hybrid A* are operated real time according to the starting and target point. Two models where the tests take place were represented and those models were transferred into Gazebo simulation environment in ROS setting. These settings were mapped with Karto mapping. The created map was turned into a cost map and the algorithm tests were executed. In the simulation tests, it has been observed that the developed method reaches to target point succesfully faster than the Hybrid A* algorithm.