Cooperative collision avoidance for unmanned aerial vehicles

Date
2020-03
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: This thesis presents the design, implementation, and verification of a cooperative collision avoidance algorithms for unmanned aerial vehicles (UAVs) in multi-aircraft conflict scenarios. Two types of collision avoidance algorithms are developed and verified in simulation: a rules-based algorithm and a cooperative path planning based algorithm. The rules-based collision avoidance algorithm is modelled after the tactical Traffic Collision Avoidance System (TCAS) that is used on commercial passenger airliners. To enable multi-aircraft collision avoidance, two methods for combining the pairwise rulesbased collision avoidance actions are proposed, namely Resolution Action Superposition (RAS) and pairwise Closest-Intruder-First (CIF). The path planning based collision avoidance algorithm grows a search tree of admissible conflict resolution paths, and searches the tree to find the conflict-free path with the lowest cost. To enable cooperative collision avoidance, all aircraft communicate their current positions and intended flight paths to all other aircraft. A token allocation strategy is used so that the individual aircraft plan their new collision avoidance paths sequentially according to a predetermined priority order. The rules-based and path planning based collision avoidance algorithms were implemented and verified in simulation. A simulation environment was created to test both the rules-based and path planning based collision avoidance algorithms. Set-piece conflict avoidance scenarios were performed to produce illustrative results. The simulations illustrated that both rules-based and path planning based collision avoidance can resolve both pairwise and multi-aircraft conflicts. Furthermore, Monte Carlo simulations were performed to produce statistical results and evaluate the performance of both algorithms in random conflict scenarios. The simulation results show that both the rules-based and path planning based solutions are able to successfully resolve collision scenarios involving multiple unmanned aerial vehicles. The rules-bases solution requires less computational effort but does not optimise the collision avoidance plans. The path planning based solution requires much more computational effort, but provides optimal solutions that minimises the deviation from the original flights, and minimises the control effort of the avoidance actions.
AFRIKAANSE OPSOMMING: Hierdie tesis beskryf die ontwerp, implementasie, en verifikasie van samewerkende botsingvermyding algoritmes vir onbemande vliegtuie (UAVs) in multi-vliegtuig konflik scenarios. Twee tipes botsingvermyding algoritmes word ontwikkel en getoets in simulasie: ’n reëls-gebaseerde algoritme en ’n padbeplanning-gebaseerde algoritme. Die reëls-gebaseerde algoritme word gemodelleer na die taktiese Traffic Collision Avoidance System (TCAS) wat gebruik word op kommersiële passasiersvliegtuie. Om multivliegtuig botsingvermyding te bewerkstellig, word twee metodes voorgestel om die paarsgewyse reëls-gebaseerde botsingvermyding aksies te kombineer, naamlik Resolusie Aksie Superposisie (RAS) en Naaste-Indringer-Eerste (NIE). Die padbeplanning-gebaseerde botsingvermyding algoritme groei ’n soektogboom van toelaatbare botsingvermyding paaie, en deursoek dan die boom om die botsingvrye pad met die laagste koste te vind. Om samewerkende botsingvermyding te bewerkstellig, kommunikeer al die vliegtuie hulle huidige posisies en beplande vlugpaaie aan al die ander vliegtuie. ’n Token allokering strategie word gebruik sodat individuele vliegtuie hulle nuwe botsingvermyding paai sekwensieël beplan volgens ’n voorafbepaalde prioriteit volgorde. Die reëls-gebaseerde en padbeplanning-gebaseerde botsingvermyding algoritmes is geïmplimenteer en getoets in simulasie. ’n Simulasie omgewing is geskep om beide die reëlsgebaseerde en padbeplanning-gebaseerde algoritmes te toets. Vooropgestelde botsingvermyding scenarios is uitgevoer om illustratiewe resultate te verkry. Die simulasies illustreer dat beide die revls-gebaseerde en padbeplanning-gebaseerde algoritmes in staat is beide paarsgewyse en multi-vliegtuig konflikte op te los. Monte Carlo simulasies is uitgevoer om statistiese resultate te lewer om die vermoë van beide algoritmes in lukrake konflik scenarios te evalueer. Die Monte Carlo simulasies wys dat beide die reëls-gebaseerde en padbeplanning-gebaseerde benaderings suksesvol lukrake multi-vliegtuig konflikte kan oplos. Die reëls-gebaseerde benadering vereis minder verwerkingskrag, maar optimiseer nie die botsinvermyding paaie nie. Die padbeplanning-gebaseerde benadering vereis meer verwerkingskrag, maar verskaf optimale oplossings wat die afwyking van die vliegtuie van hulle oorspronklike vlugplanne minimeer, en ook die beheerenergie van die vermydingsaksies minimeer.
Description
Thesis (MEng)--Stellenbosch University, 2020.
Keywords
Traffic Collision Avoidance System, Drone aircraft -- Collision avoidance, Unmanned aerial vehicles (UAV) -- Safety measures, UCTD
Citation