Publication: Hyper-heuristics for online path planning of unmanned aerial vehicles
Abstract
İNSANSIZ HAVA ARAÇLARININ ÇEVRİMİÇİ GÜZERGÂH PLANLAMASI İÇİN ÜST SEZGİSEL YÖNTEMLER İnsansız Hava Aracı (İHA) üzerinde bir pilot bulundurmayan uzaktan veya otonom olarak kontrol edilebilen bir hava aracıdır. Keşif, gözetleme, hedef edinme ve savaş alanı istihbarat operasyonları gibi askeri görevler İHA kullanım alanının önemli bir kısmını oluşturmaktadır. Bunlara ek olarak araştırma, harita oluşturma, arama ve kurtarma, trafik gözetleme, orman yangınlarının belirlenmesi, zirai yönetim ve bunun gibi ticari ve bilimsel İHA uygulamaları da gittikçe önem kazanmaktadır. Bir insan müdahalesi olmadan uçuşu kontrol edebilme kabiliyeti olarak tanımlanan otonomi hava araçları için önemli bir özelliktir. Bilinmeyen bir çevrede otomatik güzergâh planlama İHA ya yönelik zorlu sorunlardan bir tanesidir. İHA için en uygun uçuş rotasının kararlaştırılması bir takım kısıtlamaların ve çeşitli amaçlara erişmek için bazı hedeflerin yerine getirilmesini farklı çevre koşulları göz önünde bulundurularak gerektirmektedir. Üst sezgisel teknikler verilen bir alt seviye sezgisel yöntem kümesinden seçim yapma işlemini otomatikleştiren problemden bağımsız öte sezgisel yöntemlerdir. Farklı alanlardaki birleşimsel iyileştirme problemlerine başarılı bir şekilde uygulanabilmektedirler. Bu çalışmada bilinmeyen ortamlardaki İHA seferlerine yönelik üç boyutlu çevrimiçi güzergâh planlama sistemi geliştirmek için üst sezgisel bir yaklaşım sunuyoruz. Arazi ile ilgili bilgi araç üzerindeki sensörler yardımıyla elde edilmekte ve alt rota planlaması belirli bir saha içerisinde gerçekleştirilmektedir. Bu işlem başlangıç ve hedef konumlarını birleştiren nihai rota oluşturulana kadar sürdürülür. Her bir bölgedeki İHA rotası dinamik kontrol noktaları kümesi ile meydana getirilen B-Spline eğrileri ile tanımlanmaktadır. Farklı özellikler taşıyan araziler üzerinde uygulanan deneysel çalışmamız çevrimiçi İHA rota planlama problemi için üst sezgisel yöntemlerin kullanımını onaylamaktadır. Bizim Yaklaşımımız çözüm kalitesi ve üretilen tatbik edilebilir çözüm sayısı yönünden ilgili çalışmaya önemli ölçüde üstün gelmiştir.
HYPER-HEURISTICS FOR ONLINE PATH PLANNING OF UNMANNED AERIAL VEHICLES An Unmanned Aerial Vehicle (UAV) is an autonomously or remotely controlled aircraft without an onboard pilot. Military tasks such as reconnaissance, surveillance, target acquisition and several battlefield intelligence operations constitute the major usage area for UAVs. There are also commercial and scientific applications of UAVs including research, map building, traffic surveillance, forest fire detection and agriculture management. Automatic path planning in an unknown environment is one of the challenging problems for unmanned aerial vehicles. Determining the optimal flight path for a UAV requires satisfying several constraints and targets to achieve various objectives by considering different environmental conditions. Hyper-heuristic techniques are problem independent meta-heuristics that automate the process of selecting a set of low-level heuristics in order to solve the given problem. They are successfully applied on combinatorial optimization problems of various domains. In this study, we present hyper-heuristic based techniques to develop 3-D online path planning for UAV navigation in an unknown environment. The information about the terrain is gathered by on-board sensors, and subpath planning is carried out within a certain range. This operation is repeated until the final path which connects the initial and target position is generated. The trajectory of a UAV at each region is represented with B-spline curves, which is constructed by a set of dynamic control points. Experimental study performed on terrains with different characteristics validates the usage of our hyper-heuristic based solutions for online UAV path planning problem. Our approach significantly outperforms related work with respect to quality of solutions and the number of feasible solutions produced.
HYPER-HEURISTICS FOR ONLINE PATH PLANNING OF UNMANNED AERIAL VEHICLES An Unmanned Aerial Vehicle (UAV) is an autonomously or remotely controlled aircraft without an onboard pilot. Military tasks such as reconnaissance, surveillance, target acquisition and several battlefield intelligence operations constitute the major usage area for UAVs. There are also commercial and scientific applications of UAVs including research, map building, traffic surveillance, forest fire detection and agriculture management. Automatic path planning in an unknown environment is one of the challenging problems for unmanned aerial vehicles. Determining the optimal flight path for a UAV requires satisfying several constraints and targets to achieve various objectives by considering different environmental conditions. Hyper-heuristic techniques are problem independent meta-heuristics that automate the process of selecting a set of low-level heuristics in order to solve the given problem. They are successfully applied on combinatorial optimization problems of various domains. In this study, we present hyper-heuristic based techniques to develop 3-D online path planning for UAV navigation in an unknown environment. The information about the terrain is gathered by on-board sensors, and subpath planning is carried out within a certain range. This operation is repeated until the final path which connects the initial and target position is generated. The trajectory of a UAV at each region is represented with B-spline curves, which is constructed by a set of dynamic control points. Experimental study performed on terrains with different characteristics validates the usage of our hyper-heuristic based solutions for online UAV path planning problem. Our approach significantly outperforms related work with respect to quality of solutions and the number of feasible solutions produced.