Tez No	İndirme	Tez Künye	Durumu
397130		Çoklu otonom insansız hava araçları için paralel programlama tabanlı yol planlaması / Parallel programming based path planning for multi autonomous unmmaned vehicles Yazar:ÖMER ÇETİN Danışman: DOÇ. DR. GÜRAY YILMAZ Yer Bilgisi: Hava Harp Okulu Komutanlığı / Havacılık ve Uzay Teknolojileri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Yazılım Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Dağıtık bilgisayar sistemi = Distributed computer system ; Paralel bilgisayarlar = Parallel computers ; Çok işlemcili bilgisayarlar = Multiprocessor computers	Onaylandı Doktora Türkçe 2015 384 s.
İnsansız Hava Aracı (İHA) otonom platformları, insanlı benzer sistemlere nazaran daha etkin, ucuz ve emniyetli şekilde istenilen görev hedeflerini sağlayabilmeleri gibi nedenlerden dolayı, sivil ve askeri birçok alanda yaygın olarak kullanılan teknolojiler haline gelmişlerdir. Karmaşık olarak tanımlanan ve farklı tipte faydalı yük verileri (optik, IR vb.) ile icra edilebilecek görevlerin yerine getirilmesi, büyük ölçekli (taktik gibi) İHA sistemlerinin kullanılmasını gerektirmektedir. Ancak büyük ölçekli tek bir platform kullanılması yerine, birden fazla ve nispeten daha küçük ölçekli İHA sisteminin (mini gibi) bir arada iş birliği içinde formasyon uçuşu dahilinde kullanılması gerek maliyet gerekse de görevin başarı olasılığını arttırması gibi bir takım avantajlar sağlamaktadır. Grup halinde bir formasyon dahilinde hareket edebilen otonom İHA sistemlerinin kullanımına olan ihtiyaç, görevin icrası sırasında coğrafi engellerden kooperatif olarak kaçınma ve dar alanlarda birbirleri ile çarpışmayı önleme gibi karmaşık problemleri, dolayısıyla kazanılması gereken ilave otonom yetenekleri ortaya çıkarmaktadır. Bu durum İHA sistemleri için dinamik yol planlaması kapsamında karmaşıklık düzeyi yüksek ve de hassas hareket planlaması ihtiyacını karşılayabilecek yol planlaması gereksinimi doğurur. Platformların birbirleri ile hassas bir konumlandırma dahilinde uyumlu hareket etmeleri ve koordinasyon ihtiyacı, gerçek zamanlı bir yol planlaması gereksinimini ortaya koyan bir diğer durumdur. Bu kapsamda gerçek zamanlı olarak çarpışmayı önleyecek ve dinamik engellerden kooperatif biçimde etkin olarak sakınmaya imkan sağlayacak, aynı zamanda belirlenen formasyon şemasını uçuş süresince mümkün olduğunca muhafaza etmeye çalışacak bir yaklaşım için, otonom yol planlaması ihtiyacı oluşmuştur. Literatürde otonom hareket eden sistemlerin engellerden kaçınma ya da çarpışmayı önleme amaçlı yol planlaması problemlerinde yaygın olarak kullanılan çözüm yöntemlerden birisi yapay potansiyel alan (YPA) tabanlı yaklaşımlardır. Potansiyel alan yaklaşımı, nispeten küçük ölçekli olarak tanımlanmış iki boyutlu alanlar içerisinde ve yavaş hareket eden otonom araçlar için oldukça hızlı hesaplanabilir ve kolay uygulanabilir olması gibi nedenlerden dolayı otonom yol planlaması problemlerine yönelik bir çözüm yöntemi olarak literatürde yerini almıştır. YPA uygulamalarının karekteristik problemleri arasında yer alan yerel minimum problemi gibi sorunların çözümüne yönelik çalışmalar literatürde sıkça görülmektedir. Ender olarak ele alınan bir diğer YPA problemi ise; nispeten geniş alanlarda (özellikle genel yol planlaması ihtiyacı durumunda) ve çok hızlı hareket etme yeteneğine sahip üç boyutlu ortamlar içerisinde yer alan otonom sistemler için YPA'ların dinamik olarak gerçek zamanlı hesaplanmasına yönelik gereksinim duyulan hesaplama gücü ihtiyacının giderilmesi durumudur. YPA içerisindeki çözünürlük derecesi, hareketin hassasiyeti ve yol planlamasının etkinliği açısından önemli bir faktör olup, çözünürlük arttıkça hareketin hassasiyeti artmakta ve dinamik olarak değişen üç boyutlu ortamlar için hesaplama hızına bağlı ihtiyaç duyulan hesaplama gücü ihtiyacı da fazlalaşmaktadır. Ayrıca, takım halindeki kooperatif İHA sistemleri için hareket ortamı ve engel modellemesi üç boyutlu olduğundan, karmaşıklık düzeyi ve işlemci gücü ihtiyacı daha önemli bir problem haline gelmektedir. Bunun yanı sıra YPA kapsamında üç boyutlu olarak engellerin modellemesinde faydalanılacak olan sensor verisi hali hazırda İHA platformlarında kullanılan sensor mimarileri tarafından karşılanamamaktadır. Düşünülen yaklaşımın üç boyutlu alanlar içerisinde etkin olarak kullanılabilmesi amacıyla "Çok Katmanlı YPA" yaklaşımı çalışma kapsamında geliştirilen özgün bir çözüm yöntemi olup, İHA sistemlerinde engellerin tespit edilmesi amacıyla kullanılan sensor mimarilerinden üretilen veriler kullanılarak uygulanabilir bir yaklaşım elde edilmiştir. Formasyon uçuşunun otonom olarak planlanması amacıyla farklı karakterlerdeki (iten, çeken, dönen vb.) temel potansiyel alan yapılarının bir arada kullanılmasına gerek duyulmuştur. Dinamik olarak değişen ve sürekli karakterini güncelleyen alan içerisindeki hareketin etkin olarak hesaplanabilmesi, gerçek zamanda uygulanması zor bir problemdir. Bunun ötesinde ortaya konulan çözümün uygulanabilir bir yaklaşım olması da etkin bir çözüm için gereklidir. Ortaya konulan otonom formasyon uçuşu amaçlı yol planlaması yaklaşımı, farklı karakterlerdeki İHA sistemleri tarafından uygulanabilir çözümler ortaya koymalıdır. Farklı özelliklerdeki temel potansiyel alanları bir araya getiren otonom yol planlaması yaklaşımında, alanlar arasındaki geçişler çalışma kapsamında öncelikle ikili değer üreten (binary) fonksiyonlar ile sağlanmış ancak bu durum alanlar arasında keskin dönüş karakteristiklerine ihtiyaç duyduğundan dolayı farklı tipte İHA sistemleri tarafından uygulanması güç paternler üretecek sonuçlar üretmiştir. Bu nedenle otonom yol planlaması modeli kapsamında ele alınan farklı potansiyel alanların sınırlarının belirlenmesi amacıyla ikili sınır fonksiyonları yerine sigmoid fonksiyonlardan faydalanılmış, böylece alan geçişleri esnasında platformun daha etkin ve uygulanabilir manevralar icra etmesini sağlayabilecek bir yaklaşım modellemesi gerçekleştirilmiştir. Her iki yöntemin başarısı simülasyon ortamında ölçülmüş ve etkinlik, performans açısından karşılaştırılarak sonuçlar üretilmiştir. Üç boyutlu, geniş, yüksek çözünürlüklü ve hızlı olarak değişen dinamik potansiyel alanların hesaplanmasında; hızlı, geniş bellekli ve nispeten yüksek maliyetli merkezi işlemcilere dayalı yaklaşımlar problemin çözümü için yeterli olmamaktadır. Bunun yerine dağıtılmış yapıda çalışabilen esnek ve paralel hesaplama yapılarının kullanılmasının daha etkin sonuçlar üreteceği değerlendirilmiştir. Gerek maliyetleri, gerekse ortaya koydukları hesaplama kapasiteleri açısından son yıllarda yaygın olarak kullanılan paralel hesaplama amaçlı yapılardan birisi grafik işlemci tabanlı çok çekirdekli paralel programlama araçlarıdır. Son yıllarda grafik işlemcilerin paralel ve genel maksatlı olarak programlanabilmeleri sayesinde, öbek yapılı süper bilgisayar altyapılarının çok daha ucuz maliyetler ile gerçekleştirilmeleri sağlanmıştır. Karmaşık ve yüksek hesaplama gücü ihtiyacı duyan, yüksek çözünürlüklü dinamik olarak tanımlanmış YPA çözümleri gibi problemlerin, paralel olarak çözülmesi amacıyla grafik işlemcilerin genel maksatlı paralel programlanması (GPGPU) tabanlı yapılar gerek fiziksel özellikleri gerekse de etkin hesaplama yetenekleri nedeniyle İHA sistemlerinde kullanılabilir ideal platformlar olarak değerlendirilmektedir. Çalışma ile otonom ve hızlı hareket kabiliyetine sahip, ancak kısıtlı manevra yeteneği olan, formasyon düzenindeki kooperatif İHA sistemleri için YPA yaklaşımının eksik kaldığı, dinamik olarak değişen ve önceden özellikleri bilinmeyen üç boyutlu alanlar içerisinde farklı otonom davranışların sergilenmesi esnasında vektörel alanların tekrar hesaplanmasının getirdiği yüksek hesaplama gücü ihtiyacını karşılayacak nitelikte GPGPU tabanlı paralel ve dağıtılmış bir çözüm yöntemi geliştirmek amaçlanmıştır. Çalışma kapsamında geliştirilen GPGPU tabanlı paralel çekirdek kodu sistem kaynaklarını minimum tüketirken, aynı zamanda sistemin maksimum hız ve verim ile çalışmasını sağlayacak gerekli optimizasyonları da içermektedir. Ayrıca, ortaya konulan yaklaşımın hali hazırda kullanılmakta olan İHA sistemleri üzerinde uygulanabilecek şekilde bir mobil donanım desteği vasıtasıyla uygulaması da sınanmıştır. Sonuç olarak, paralel programlama teknikleri uygulanarak problemin çözümünün mobil sistemler için ideal programlama ortamı sağlayan grafik işlemci (GPU) tabanlı yaklaşımlar ile hesaplanması amaçlanmaktadır. Bu konuda literatürde yeterli sayıda araştırmanın yer almadığı gözlemlenmiş ve literatüre katkı sağlanmıştır. Ortaya konulan YPA tabanlı otonom yol planlaması çözüm yaklaşımının, gerçek zamanlı olarak sonuç üretebilmesine imkân sağlayacak nitelikte GPGPU tabanlı tek komut seti çolu veri (Single Instruction, Multiple Data - SIMD) tipinde paralel algoritmalar geliştirilerek uygulanması amaçlanmıştır. Otonom paralel formasyon düzenin sağlanması için geliştirilen yaklaşımın dinamik ve önceden konum ve davranışları bilinmeyen engellerin yer aldığı bir ortamda başarısının ölçülerek problemin karmaşıklık düzeyinin arttırılmasına yönelik çalışmalar gerçekleştirilmiştir. Önceden özellikleri bilinmeyen alan içerisinde yer alan engellerin algılanmasını modelleyen bir yaklaşım geliştirilmiştir. Gerçekleştirilen yol planlama algoritmalarının faklı mobil ve sabit grafik işlemciler üzerinde başarısının ölçülerek algoritmaların donanımlara göre optimize edilmesi çalışmaları gerçekleştirilmiştir. Bu kapsamda mobil ve sabit grafik işlemciler üzerindeki yaklaşımın performansı, geleneksel işlemciler ile gerçekleştirilen seri hesaplama performansı ile karşılaştırmalı olarak ortaya konulmuştur. Paralel hesaplama performansı farklı türde grafik işlemciler üzerinde mobil (Tesla Quadro 1000M, NVIDIA GeForce GTX 670MX) ve iş istasyonu/masaüstü (Tesla K20c, GeForce GTX480) sınanarak performans değerleri üretilmiştir. Elde edilen sistemin hesaplama performansı, klasik olarak programlanmış sıralı hesaplama yaklaşımları ile karşılaştırılmış ve bir takım paralel hesaplamaya yönelik iyileştirmelerin uygulanması ile birlikte K20c grafik işlemcisi ile yaklaşık 17 kat seri hesaplama performansından daha iyi bir hesaplama performansı elde edilmiştir. Ayrıca birden fazla grafik işlemci bir arada kullanılarak, aynı ana makine üzerindeki grafik işlemcilerden faydalanılarak yaklaşık 41 kat performans elde edilmiştir. Ağ ortamı üzerinde yer alan çok sayıda grafik işlemciden bir arada YPA tabanlı hesaplama yapma olanağı sağlayacak yaklaşım ortaya konulmuş ve haberleşme maliyetleri göz ardı edildiğinde yaklaşık 48 kat seri hesaplamaya nazaran performans artışı elde edilmiştir. İHA sistemleri üzerine geliştirilen akademik çalışmaların yoğunluğu, birçok otonom sistem için uygulama geliştirme amaçlı tekniğin, aracın ve yöntemin literatürde kolay ulaşılabilir hale gelmesini sağlamıştır. Yaklaşımın başarısı noktasal yüklü parçacığın hareket modeli tabanlı simülasyonlar ile sınanmıştır. Çok sayıda otonom döner kanatlı quad-rotor platformun otonom şekilde kontrolünün aynı anda sağlanmasının gerçekleştirilmesi ve YPA tabanlı otonom paralel formasyon yaklaşım teorisinin uygulamalı olarak ortaya konulması kapsamında otonom uçuş kontrol sistemi yapısı simülasyon ve gerçek uygulama olarak ortaya konulmuştur. Çalışma kapsamında elde edilen sonuçlar, simülasyon ortamında sınandıktan sonra AR Drone quad-rotor platform sistemleri üzerinde uygulanarak gerçek sistemlerdeki başarımları ölçülmüş ve uygulamadaki problemleri ortaya konularak çözüm geliştirilmiştir. Bu kapsamda tez çalışması ile geliştirilecek olan teorik çalışmaların başarısının uygulamalı olarak ölçülebilmesine imkân tanıyacak şekilde AR-Drone quad-rotor platformların otonom şekilde hareket etmelerine ve kontrol edilebilmelerine imkân tanıyacak şekilde gömülü yazılımlarında bir takım düzenlemelere gidilmiştir. Hareket kontrolünü düzenleyen uçuş bilgisayarı yapısı YPA ile desteklenmiş bir yol planlamasına destek verebilecek şekilde güncellenmiştir. Ayrıca platformun GPS desteği ile dış ortamlarda otonom uçuşunun sağlanabilmesi amacıyla Ardu Mega Pilot kontrol donanımı (APM) ile küresel konumlandırma sistemi (Global Positioning System - GPS) alıcı anteni ve XBee iletişim modülünün entegrasyonu sağlanmıştır. Böylece APM modülü üzerine bağlı olan GPS anteninin edindiği konum bilgilerinin Xbee kablosuz iletişim modülü üzerinden kontrol yazılımının koşturulduğu bilgisayar sistemine aktarımı sağlanmıştır. Farklı senaryolar dahilinde uçuş denemeleri gerçekleştirilerek yaklaşımın başarısı uygulamalı olarak ortaya konulmuştur. Sonuç olarak, çalışma ile otonom uçuş gerçekleştirmeyi amaçlayan çok sayıdaki platformun bir arada formasyon teşkil edecek, birbirleri ve ortam dahilinde yer alan engeller ile çarpışmalarının önlendiği güvenli bir seyrüsefer gerçekleştirmelerine imkan sağlayacak yol planlaması yaklaşımı, grafik işlemciler üzerinde koşturulabilen paralel algoritmalar ortaya konularak gerçeğe en yakın zamanlı sonuçlar üretecek şekilde simülasyon ve uygulamalar ile sınanarak başarıyla özgün şekilde geliştirilmiştir.
The autonomous Unmanned Aerial Vehicles (UAVs) are more efficient than similar manned platforms for the reasons such as to be able to provide cheap and safe solutions, so that technology has become widely used in many areas of civil and military. The missions which are defined as complex and requires different types of payload data together (like optical, IR, etc.), needs to usage of large scale of UAV platforms to fulfillment of the tasks. However using multiple and relatively small-scale UAV platforms (such as mini class) as a combination of cooperation in a formation flight instead of using a large scale single platform (such as tactical class) provides a number of advantages such as reducing operation costs and increasing probability of success of the mission. The need for the use of autonomous UAV systems that can move within a formation in groups, brings out some complex problems like avoiding of geographical barriers in cooperative manner and prevention of collision with each other in narrow areas, furthermore needs additional autonomous capabilities. In this case, it also raises path planning requirements to meet the needs precise motion planning and a high level of complexity within the scope of dynamic path planning for UAV systems. Another case demonstrating the need for a real-time path planning is moving the platforms within a precise positioning and co-ordination with the others in the formation. In this context, autonomous path planning requirements has occurred because of the needs like to avoid collisions in real time and to avoid from the dynamic obstacles as in cooperative manner, but also to determine the formation scheme and to try to maintain it as much as possible during the flight. APF based path planning approaches are one of the widely used methods in the literature to avoid collision with other platforms and to generate obstacles free patterns. Potential field approach has taken its place in literature because of their easily applicable and computable features especially for autonomous platfroms in the small scale and two-dimensional space. Efforts for generation of the solution for the APF based path planning approaches characteristic problems like local minimum problem are seen frequently in the literature. But another problem of APF based path planning (especially in the case of general path planning needs) is satisfaying the real-time computaiton needs especially for large size dynamic and three-dimensional fields. Resolution degree in the APF is and important factor by the means of movement precision and effectiveness in the path planning, it increases the sensivitiy of the movement but it affects the computation speed in negative way and it needs more power especially for three-dimensionan dynamic envoriments. Furthermore the needs of computation power becomes important isuuse for the co-operated uav platoforms in a formation because they are in an envirement that requires three dimensional modelling of obstacles and path planning. In addition, the sensors data which are used for modelling of the obstacles in three-dimensional have not been provided by the sensors on the UAV platforms yet. The sensors have not enough technical specs to produce three dimensional sensor data yet. To model the obstacles in three dimensional with current sensors that are used on UAV platforms, "multi layer APF" approach is designed and serve a unique solution in this work. The basic strucutures of the potential field based path planning (like pushing, pulling, rotating, etc.) are used together in a combination to satisfy the needs of autonomous formation flight path planning. The computation of the movement is a difficult problem in real-time implementation especially for the dynamically changing enviroments that is updating its characteristics by the movements of the platforms in it. Moreover the real-time path planning solution must be feasible, effective and applicable by the platforms. The autonomous formation flight path planning approach must demonstrate practical solutions for the UAV systems in different characteristics. Firstly the basic structures of the potential fields are combined by using binary functions to achieve fast computation results, but these solution generates the paths which are hard to implement especially for different UAVs due to the requirements of the sharp turning manevuars, etc. Therefore, sigmoid functions are used instead of binary functions to limit the basic sub-potential fields while combining them to generated suitable path planning structures. With using sigmoid functions to limit the basic potential fields, more smooth patterns are generated that are suitable for most UAV flight charecteristics. The success and effectiveness of both of these methods have been measured in the simulation environment by comparing the results in terms of performance. In the computation of the three-dimensional, large and rapidly dynamic potential field with high resolution value, high speed large memory based and reletively high cost central processors are not sufficient for solving the real time computation problem. Instead of central processors, the usage of flexible and distributed parallel computing structures are suggested to produce more effective computation performance results. GPU-based multi-core parallel programming tools has become one the widely used parallel computing structures in recent years due to both their low costs as well as demonstrating their parallel computing capacity. In recent years, thanks to parallel and general purpose programming ability on graphic processors, cluster based supercomputer infrastructures are provided with a much cheaper costs. Problems that needs high performance computing power like high resolution, dynamic and complex APF solutions, become able to solve by using parallel GPGPU based structures which are suitable computation frames for UAVs due to especilally their physical properties and efficent calculation capabilities. The aim of this work meets the high speed re-computation requirements of the three-dimensional, large and rapidly dynamic potential field with high resolution value for the cooperative UAVs in a formation scheme with limited manevuar capabilities and high speed by benefiting from GPGPU based parallel and distributed computation approach. GPGPU based parallel kernel algorithm that is developed in this work, while consuming minimal system resources, but also includes optimizations necessary to make it work with maximum speed and efficiency for computation performance. In addition, the approach is tested on mobile hardwares which are accepted as suitable and applicable for the current UAV platforms today. As a result, solution of the problem is applied by using parallel programming techniques on the GPUs that are accepted as ideal mobile and parallel computing enviroments. It is observed that there is not sufficient number of work in the literature about this subject and it is intend to provide support on literature with this work. The proposed APF-based autonomous path planning approach are computed by developing and implementing SIMD type and GPGPU based parallel algorithms to provide real time solutions. The approach developed for establishing the autonomous formation, is tested under more complex conditions by applying in dynamic enviroments including unknown obstacles before flight. An approach is also developed to model for detection of the obstacles in unknown enviroment. The performed path planning algorithms performances are measured on different mobile and on-board graphic processors by applying required optimizations that are specific for GPU processors hardware architectures. In this context, the performance of the approach on the on-board and mobile graphics processors, has tried to put forward in comparison with the serial computing performance achieved by conventional processors. Parallel computing performance values has been generated on mobile (Tesla Quadro 1000M NVIDIA GeForce GTX 670MX) and workstation / desktop (K20c Tesla, GeForce GTX480) graphics processors. The computing performance of the resulting system on K20c graphic processors achieved 17 times better computation performance results against sequentially programmed approach on classical CPUs computation performance. Moreover, by using a combination of multiple graphics processors on the same host machine approximately 41 times better computation performance has been achieved. Also, by using multiple graphic processors on a network with multiple hosts, approximately 48 times better computation performance has been achieved against sequentially programmed approach on classical CPUs computation performance by ignoring communication costs on network. With the high intensity of the academic researches about autonomous systems like UAVs, the technique for application development for many autonomous systems, tool and methods become readily available in the literature. Firstly, the success of the approach is tested with the point mass particle motion model based simulations. Also, autonomous flight control system architecture has been putted forth with simulations and real time applications in the manner of controlling multiple quad-rotor platforms together. The obtained results is evaluated in the simulation studies and then the success of the approach has been evaluated in real time applications by using AR-Drone quadrotor platforms by this work. Theoretical results obtained in this study has been evaluated with real-time applications on AR Drone platforms which become suitable by applying a number of regulations on embedded control software of the drones and developing control software that is allowing control of the multiple platforms together. Motion control of the governing structure of the flight computer has been updated so that it can support a path planning supported by the APF. Also to achieve the location of the platform on the outdoor environment a GPS antenna is integrated on the platform by using Ardu Pilot Mega (APM) flight computer and XBee communication equipment. Thus, the location information of the platform obtained by GPS antenna that is connected to the APM module is transferred via Xbee wireless communication module to the computer system that runs the control software. By implementing flight tests for different scenarios, the success of the approach has been putted forth experimentally. As a result, autonomous path planning needs are satisfied for multiple platforms that aim autonomous flight on a defined formation scheme with safe navigation while prevention of collision with obstacles and other mobile platforms or each other. The path planning approach is successfully implemented as a real time original solution by using parallel suitable algorithms for graphic processors. Also the success of the genuine approach is tested with simulation and practical experiments.