3-D offline path planning for ummanned aerial vehicles by using metaheuristics


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara Üniversitesi, Turkey

Approval Date: 2008

Thesis Language: English

Student: Işıl Hasırcıoğlu

Abstract:

İNSANSIZ HAVA TAŞITLARINA YÖNELİK OLARAK EVRİMSEL ALGORİTMALAR YARDIMI İLE OFFLINE GÜZERGAH PLANLAMA İnsansız hava araçları, uzaktan kontrol edilen veya önceden programlanmış uçuş planlarına göre otomatik olarak hareket eden uçaklardır. İnsansız hava araçları; hava keşifleri, deniz ve dağlardaki arama kurtarma çalışmaları, hava fotoğrafçılığı ve haritacılığı, yangın tespiti ve trafik kontrolü gibi çeşitli amaçlar için kullanılmaktadır. İnsansız hava araçlarının otomatik çalışmalarını sağlayabilmek için uzun süre insan desteği olmadan çalışma özelliği sağlayacak kontrol sistemleri geliştirilmesi gerekmektedir. Engellere çarpmadan en uygun yolu izleyecek yollar üreten yol planlayıcıları, insansız hava araçlarına otomatik çalışma özelliği kazandırabilmektedirler. Uçuş planının optimize edilmesi, değişken ortam koşullarının ve hava şartlarının göz önüne alınması gerektiği çok amaçlı bir problemdir. Bu projede üç boyutlu ortamlarda otomatik olarak hareket eden insansız hava araçları için bir offline (sabit ortam ve kısıtlarda) yol planlayıcısı geliştirdik. Geliştirilen yol planlayıcısı; arazi yüzeyine çarpmayan, belli bir görüş mesafesinde izin verilen minimum dönme açısından büyük açılarla, kısıtlanan minimum ve maksimum yükseklikler arasında belirtilen tehlikeli bölgeden uzak bir seyir izleyen en kısa yolu bulmayı hedeflemektedir. Bu yol planlayıcısını geliştirmek için farklı problemler için kullanılan metasezgisel (metaheuristic) yöntemler (Genetik Algoritmalar, Parçacık Sürü Eniyileme ve HyperHeuristics) kullandık. Farklı arazi tipleri için gerçekleştirdiğimiz deneyler neticesinde, Genetik Algoritmaların çoğu arazi için diğer yöntemlerden daha iyi sonuçlar verdiğini gördük. Bununla birlikte HyperHeuristics yönteminin zor arazi tiplerinin çoğunda diğer yöntemlerden daha iyi sonuçlar verdiğini gözlemledik. Parçacık Sürü Eniyileme yönteminin ise diğer yöntemlerle karşılaştırıldığında iyi sonuçlar vermezken mimimum çalışma zamanına sahip olduğu gözlendi. ABSTRACT 3-D OFFLINE PATH PLANNING FOR UNMANNED AERIAL VEHICLES BY USING METAHEURISTICS Unmanned Aerial Vehicle (UAV) is an aircraft which is remotely controlled or can fly autonomously according to the pre-programmed flight plans. UAVs are used for many missions including weather reconnaissance, search and rescue assisting operations in sea and mountains, aerial photographing and mapping, fire detection, traffic control. Autonomous operation of UAVs requires the development of control systems that can work without human support for long time periods. The path planners which generate collison-free and optimized paths are needed to give autonomous operation capability to the UAVs. The optimization of the flight path is a multi-objective problem dealing with variable terrain features as well as dynamic environment conditions. In this study, we develop an offline path planning framework for unmanned aerial vehicle navigation in 3-D environments. Our framework targets to find the shortest path and / or a flight envelope in a given line of sight by avoiding terrain collisions, traveling on a path which provides within the restricted minimum and maximum distances to the terrain, traveling far from the specified threat zones, and maneuvering with an angle greater than allowable minimum curvature radius. We present various metaheuristic techniques (Genetic Algorithms, Particle Swarm Optimization and Hyper-Heuristics) in order to construct the paths for UAV navigation. Based on the comparative study on terrains with various characteristics, it was observed that our GA-based method outperforms the other two heuristics with respect to quality of solutions (given in total cost of a constructed path including the penalties of all constraints) for most of the terrains examined. On the other hand, Hyper-Heuristics outperforms other methods for more than half of the hard terrains. Although, the PSO method does not perform well when compared with the other techniques, it requires the minimum running time among them to generate a feasible path.