Path planning algorithm development for unmanned aerial and ground vehicles
İnsansız hava ve kara araçlarında yol planlama algoritması geliştirme
- Tez No: 916226
- Danışmanlar: PROF. DR. O.SETA BOGOSYAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Kontrol ve Otomasyon Mühendisliği Bilim Dalı
- Sayfa Sayısı: 79
Özet
Robotların kullanım alanları günden güne hızlanarak artmaktadır, başlıca bu alanlar otonom araçlar, mobil robotlar, robotik kollar, depolama robotları, yemek yapan robotlar, çeşitli ev temizlik robotlarıdır. Özellikle otonom elektrikli araçlar günümüzün vazgeçilmez bir parçası olma konusunda çok yüksek bir potansiye sahiptir. Bu şekilde artan ihtiyaçdan dolayı çeşitli teknik konularda daha optimal ve gürbüz teknik algoritmalara ihtiyaç duyulmaktadır. Bu ihtiyaçları karşılamak üzere teknik çalışmaların yoğunlaştığı konuları 5 grup altında toplayabiliriz, bunları pozisyonlama, haritalama, yol planlama, yol takibi, dinamik ve statik engellerden kaçınma olarak sıralayabiliriz. Kısa olarak genel tanımları açıklarsak, ilk olarak pozisyonlama, çeşitli sensör verisi ile robotun değişken çere koşullarında kendi konumunu kestirmesi olarak tanımlanabilir. Haritalama çevredeki nesnelerin algılanması ve bu nesnelerin araç hareketi boyunca yerlerinin hafızada tutulması sonucu oluşturulan matris yapısıdır. Bu haritalar iki veya üç boyutlu olabilir ve global harita ve local harita olarak da gruplanabilir. Diğer başlık ise yol planlamadır ve haritada üzerinde tanımlı başlangıç ve hedef noktası arasında güvenli bir rota oluşturulması amacıyla elde edilen konumlar kümesi olarak tanımlanır. Diğer başık olan yol takibi ise başlangıç ve hedef konumlarını içeren rotanın olabilecek minimum hata ile takip edilmesi için gerekli kontrol sinyallerinin üretilmesini sağlar. Son olarak dinamik ve statik engellerden kaçınma algoritmaları bir robotun hareketi boyunca çarpabileceği engellerin önceden kestirilip rota güncellenmesi olarak tanımlanabilir. Yol planlama konusunu detaylandırırsak, bir robot, araç veya diğer otomatikleştirilmiş sistemin engellerden kaçınarak ve minimum dönüş yarıçapı, maksimum hız ve maksimum hızlanma gibi kısıtlamalara uyarak mevcut konumundan istenen bir varış noktasına hareket etmesi için uygun ve en uygun yolu belirleme sürecidir. Yol planlama algoritmaları tipik olarak, engellerin varlığı ve arazinin düzeni dahil olmak üzere robotun çalıştığı ortamı dikkate alır. Robotun maksimum hızı ve dönüş yarıçapı gibi yeteneklerini de dikkate alabilirler. Yol planlama, otonom araçlar, mobil robotlar ve insansız hava araçları dahil olmak üzere robotik ve otomasyondaki birçok uygulamanın önemli bir bileşenidir. Yol planlamasının amacı, robotun veya aracın çevresinde güvenli, verimli ve güvenilir bir şekilde gezinmesini sağlamaktır. Teknik çalışmaların çok fazlaca yapıldığı alanlar arasında yol planlama temel tez konusu olarak seçilmiştir. Bu kapsamda yol planlama algoritmaları temelde 3 kategori altında toplanabilir, bunlar geometrik temelli algoritmalar, ağaç tarama yöntemi algoritmları, makine öğrenmesi ve yapay zeka algoritmaları ve örnek alma temelli algoritmalardır. Bu algoritma gruplarının avantajları ve dezavantajları kendi içerisinde ayrışmaktadır. Bu tez çalışmasında örnek alma temelli algoritmalar üzerinde çalışma yapılmıştır. Örnek alma temelli algoritmaların en temeli olan RRT algoritması ilk olarak incelendi. Algoritma bir harita üzerinde rastgele nokta seçimi ve bu noktalar arasında en yakın olanlarının birbirine bağlanması şeklinde iki süreçten oluşmaktadır. Bu algoritma herhangi bir maaliyet optimizasyonu yapmadan noktaları birbirine bağladığı için elde edilen sonuç optimallikten çok uzak olmaktadır, fakat çok hızlı bir yol sonucu vermektedir. RRT ağaç yapısının optimizizasyonu konusunda ağaç yapısının tekrardan oluşturulması algoritması RRT* adlı yöntem ile öne sürülmüştür. Bu öne sürülen yöntemde iki önemli başlık ön plana çıkmaktadır. Bunlardan ilki her düğümün bir maaliyet değerinin olması, diğeri ise ağaç yapısının tekrardan minimum maaliyet hesabı ile güncellenmesidir. Bu iki özellik sayesinde çok daha kısa sürede çok daha optimal bir yol bulunması sağlanmıştır. RRT* algoritmasının en büyük dezavantajı haritanın bütün olası düğümlerini incelemesidir. Bu dezavantajı ortadan kaldırmak için informed RRT* algoritması öne sürülmüştür. Bu algoritmada bütün harita yerine sadece belirli bir elipse alanı incelenmektedir. Bu oluşturulan elipsin odak noktaları harekete başlangıç ve hareketin bitiş noktaları olarak tanımlanmaktadır ve bulunan yolun uzunluğu ise elipse üzerindeki bir noktanın iki odak noktasına olan uzaklıkların toplamı olarak tanımlanmaktadır. Böylelikle elde edilen elipse başlangıç ve bitiş noktalarını kesin olarak kapsamaktadır. İterasyon devam ederken bulunan yol uzunluğu giderek azalacağından elipsin büyüklüğü giderek azalmaktadır. Özellikle başlangıç ve hedef noktası arasında engel yok ise elde edilen yol düz bir çizgeye yakın elde edilebilmektedir. İnformed RRT* algoritması aslında ilgilenen alanlar üzerinde elips şeklinde olası yol optimizasyonu yapıldığında sonuca çok daha hızlı ulaşılabildiğini göstermiştir. Fakat bu algoritmanın yetersiz kaldığı yer ise oluşturulan ellipsin yüksek eksantirisitiye sahip olması sonucu elips alanın anlamını yitirmesidir ve bütün haritayı kaplamasıdır. Bunun sebebi iki odak noktası uzaklığının görece elde edilen yol uzunluğuna göre çok kısa olmasıdır. Elde edilen elipse bütün haritayı kapsadığı zaman elips içerisinden seçilecek rastgele bir noktanın RRT* algoritmasında olduğu gibi rastgele nokta seçimi aynı özelliği taşımaktadır. İnformed RRT* algoritmasının eksik kaldığı konu yüksek eksantirisitili elipse sahip haritalardır. Bu haritalarda informed RRT* tam olarak RRT* ile aynı yapıya sahip olmaktadır. Bu alandaki eksikliği kapatmak üzere örneklem temelli algoritmalar üzerinde yeni yaklaşımlar denendi. Bu tez çalışmasında önerilen yöntem n-sliced informed RR* olarak adlandırıldı. Algoritma ilk yol bulunanana kadar RRT* ve informed RRT* ile aynı algoritmaya sahiptir. Başlangıç ve hedef nokta arasındaki ilk yol bulunduktan sonra yol n adet dilime bölünmektedir. Sonrasında bu bölümler bir odak noktası zincir tablosu oluşturularak optimize edilecek segment seçimi yapılmıştır. Bu algoritma bir RRT varyantı olduğu için segment seçimi rastgele olarak yapılmaktadır. Segmentler ardışıl alanların kombinasyonu olarak seçilmiştir. informed RRT* algoritması önerdiğimiz n parametresinin 1 değeri alması sonucu sağlanmaktadır. n parametresinin optimizasyonu konusunda dikkat edilmesi gereken nokta yerel minimum değerine takılmamak için çok büyük bir n parametresi seçilmemesidir. Optimal bir n değerinde boş bir harita da dahi yüksek performans elde edilmiştir. Harita büyüklüğü ve engel sayısı arttıkça önerdiğimiz n-sliced informed RRT* algoritması fark edilir derecede elde edilen yol uzunluğunda ve yol bulma süresinde azalma sağlanmıştır. Simülasyon çalışmaları PyGame ortamında Python programlama dili yardımıyla yürütülmüştür. Simülasyon süresinde karşılaştırılacak veriler *.txt uzantılı bir dosyaya, ekran görüntüleri ise periyodik olarak *.png uzantılı dosya olarak kayıt edilmiştir ve Matlab ortamında elde edilen sonuçların çizimleri yapılmıştır. Algoritma içerisindeki noktaların rastgele seçimi yapıldığından dolayı sonuçların anlamlı bir şekilde karşılaştırılması için aynı haritalar aynı parametre seti ile en az sekiz defa çalıştırılmıştır. Önerdiğimiz yöntemin kısa sürede aynı maaliyet değerine sahip yolu bulduğu gözlemlenmiştir.
Özet (Çeviri)
The usage areas of robots are increasing day by day, mainly mobile robots, robotic arms, storage robots, robots that cook food. With this increase, more optimal and robust robots are needed in various technical subjects. We can group these needs as follows: localization, mapping, path planning, trajectory tracking, dynamic and static obstacle avoidance. If we briefly explain the general definitions, firstly, localization can be defined as the robot's estimation of its own position in variable environmental conditions with various sensor data. Map is created as a result of detecting the objects in the environment and keeping the places of these objects in memory during the vehicle movement. The other topic is road planning and it is defined as the set of locations obtained in order to travel a safe route between the starting and goal point. The other topic is the path tracking which provides control signals to be followed in order to follow the route with the minimum possible error. Finally, dynamic and static obstacle avoidance can be defined as predicting the obstacles that a robot may collide with during its movement and updating the route to be . Among the above-mentioned areas, road planning was chosen as the main thesis topic. In this context, path planning algorithms can basically be grouped under 3 categories, these are geometric based algorithms, tree search algorithms, machine learning algorithms and sampling based algorithms. The advantages and disadvantages of these algorithm groups are differentiated within themselves. In this thesis study, sampling based algorithms were studied. The RRT algorithm, which is the most basic of sampling based algorithms, was first examined. This algorithm ensures that the points are connected to each other without any cost optimization. Afterwards, the RRT* algorithm was proposed and this algorithm provides an optimal combination of points by cost optimization and is called rewiring tree. But the biggest disadvantage of this algorithm is that it examines all possible points of the map. Informed RRT* algorithm actually showed that the result can be reached much faster when possible path optimization is made in the form of ellipses on the areas of interest. However, where this algorithm is insufficient is that the ellipse created has a high eccentricity, so the ellipse area loses its meaning and covers the whole map. Then, the method we propose, the road is divided into n slices. These slices are randomly optimized with the help of the rewiring tree, which is a feature of the RRT* algorithm. Thus, even on roads with high eccentricity, it can reach the optimal result in a shorter time. Various maps were determined in the simulation and a consistent comparison was made by keeping the simulation parameters constant. As a result, a high rate of success has been achieved.
Benzer Tezler
- Bir insansız hava aracının modellenmesi ve derin pekiştirmeli öğrenme tabanlı otonom kontrolü
Modeling of an unmanned aerial vehicle and autonomous control based on deep reinforcement learning
BURAK TAŞ
Yüksek Lisans
Türkçe
2023
Savunma ve Savunma TeknolojileriFırat ÜniversitesiSavunma Teknolojileri Ana Bilim Dalı
PROF. DR. AYŞEGÜL UÇAR
- A practical implementation of navigation and obstacle avoidance for quadcopters
Dört pervaneli helikopterler için bir engelden kaçınma ve seyrüsefer uygulaması
ONUR YILDIRIM
Yüksek Lisans
İngilizce
2022
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. OVSANNA SETA ESTRADA
- Otonom araçların yön güdümünde PAF tabanlı EZKH yönteminin geliştirilmesi
PFF based SLAM method development for autonomous vehicles' navigation
EROL DUYMAZ
Doktora
Türkçe
2018
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. HAKAN TEMELTAŞ
- Uydu verileri ile İstanbul Boğazı ve Haliç'de su kirliliğinin makro düzeyde belirlenmesi
Intrepretation at macro level as pollution of water resources of remotely sensed data of Bosphorus and golden horn estuary by an unsupervised and supervised classification method
H.GONCA COŞKUN
- İstanbul Çatalca bölgesinde uzaktan algılama yöntemleri ile metropoliten analizi
Başlık çevirisi yok
F.ZEHRA ALKAN