Robust sampling-based conflict resolution for commercial aircraft in airport environments
Date
2015-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: This thesis presents a robust, sampling-based path planning algorithm for commercial airliners that simultaneously
performs collision avoidance both with intruder aircraft and terrain. The existing resolution systems
implemented on commercial airliners are fast and reliable; however, they do possess certain limitations. This
thesis aims to propose an algorithm that is capable of rectifying some of these limitations. The development
and research required to derive this conflict resolution system is supplied in the document, including a
detailed literature study explaining the selection of the final algorithm. The proposed algorithm applies an
incremental sampling-based technique to determine a safe path quickly and reliably. The algorithm makes
use of a local planning method to ensure that the paths proposed by the system are indeed flyable. Additional
search optimisation techniques are implemented to reduce the computational complexity of the algorithm.
As the number of samples increases, the algorithm strives towards an optimal solution; thereby deriving a
safe, near-optimal path that avoids the predicted conflict region. The development and justification of the
different methods used to adapt the basic algorithm for the application as a confiict resolution system are
described in depth. The final system is simulated using a simplified aircraft model. The simulation results
show that the proposed algorithm is able to successfully resolve various conflict scenarios, including the generic
two aircraft scenario, terrain only scenario, a two aircraft with terrain scenario and a multiple aircraft
and terrain scenario. The developed algorithm is tested in cluttered dynamic environments to ensure that
it is capable of dealing with airport scenarios. A statistical analysis of the simulation results shows that the
algorithm finds an initial resolution path quickly and reliably, while utilising all additional computation time
to strive towards a near-optimal solution.
AFRIKAANSE OPSOMMING: Hierdie tesis bied 'n robuuste, monster-gebaseerde roetebeplanningsalgoritme vir kommersiële vliegtuie aan, wat botsingvermyding met indringervliegtuie en met die terrein gelyktydig uitvoer. Die bestaande konflikvermyding- stelsels wat op kommersiële vliegtuie geïmplementeer word, is vinnig en betroubaar; dit het egter ook sekere tekortkominge. Hierdie tesis is daarop gemik om 'n algoritme voor te stel wat in staat is om sommige van hierdie tekortkominge reg te stel. Die ontwikkeling en navorsing wat nodig was om hierdie konflik-vermyding-algoritme af te lei, word in die dokument voorgelê, insluitende 'n gedetailleerde literatuurstudie wat die keuse van die finale algoritme verduidelik. Die voorgestelde algoritme pas 'n inkrementele, monster-gebaseerde tegniek toe om vinnig en betroubaar 'n veilige roete te bepaal. Die algoritme maak gebruik van 'n lokale beplanningsmetode om te verseker dat die roetes wat die stelsel voorstel inderdaad uitvoerbaar is. Aanvullende soektog-optimeringstegnieke word geïmplementeer om die berekeningskompleksiteit van die algoritme te verlaag. Soos die aantal monsters toeneem, streef die algoritme na 'n optimale oplossing; sodoende herlei dit na 'n veilige, byna-optimale roete wat die voorspelde konflikgebied vermy. Die ontwikkeling en regverdiging van die verskillende metodes wat gebruik is om die basiese algoritme aan te pas vir die toepassing daarvan as 'n konflik-vermyding-stelsels word in diepte beskryf. Die finale stelsel word gesimuleer deur 'n vereenvoudigde vliegtuigmodel te gebruik. Die simulasie resultate dui daarop dat die voorgestelde algoritme verskeie konflikscenario's suksesvol kan oplos, insluitend die generiese tweevliegtuigscenario, die slegs-terreinscenario, die tweevliegtuig-met-terreinscenario en die veelvuldige vliegtuig-enterreinscenario. Die ontwikkelde algoritme is in 'n beisge (cluttered), dinamiese omgewing getoets om te verseker dat dit 'n besige lughawescenario kan hanteer. 'n Statistiese ontleding van die simulasie resultate bewys dat die algoritme vinnig en betroubaar 'n aanvanklike oplossingspad kan vind, addisioneel word die oorblywende berekeningstyd ook gebruik om na 'n byna optimaleoplossing te streef.
AFRIKAANSE OPSOMMING: Hierdie tesis bied 'n robuuste, monster-gebaseerde roetebeplanningsalgoritme vir kommersiële vliegtuie aan, wat botsingvermyding met indringervliegtuie en met die terrein gelyktydig uitvoer. Die bestaande konflikvermyding- stelsels wat op kommersiële vliegtuie geïmplementeer word, is vinnig en betroubaar; dit het egter ook sekere tekortkominge. Hierdie tesis is daarop gemik om 'n algoritme voor te stel wat in staat is om sommige van hierdie tekortkominge reg te stel. Die ontwikkeling en navorsing wat nodig was om hierdie konflik-vermyding-algoritme af te lei, word in die dokument voorgelê, insluitende 'n gedetailleerde literatuurstudie wat die keuse van die finale algoritme verduidelik. Die voorgestelde algoritme pas 'n inkrementele, monster-gebaseerde tegniek toe om vinnig en betroubaar 'n veilige roete te bepaal. Die algoritme maak gebruik van 'n lokale beplanningsmetode om te verseker dat die roetes wat die stelsel voorstel inderdaad uitvoerbaar is. Aanvullende soektog-optimeringstegnieke word geïmplementeer om die berekeningskompleksiteit van die algoritme te verlaag. Soos die aantal monsters toeneem, streef die algoritme na 'n optimale oplossing; sodoende herlei dit na 'n veilige, byna-optimale roete wat die voorspelde konflikgebied vermy. Die ontwikkeling en regverdiging van die verskillende metodes wat gebruik is om die basiese algoritme aan te pas vir die toepassing daarvan as 'n konflik-vermyding-stelsels word in diepte beskryf. Die finale stelsel word gesimuleer deur 'n vereenvoudigde vliegtuigmodel te gebruik. Die simulasie resultate dui daarop dat die voorgestelde algoritme verskeie konflikscenario's suksesvol kan oplos, insluitend die generiese tweevliegtuigscenario, die slegs-terreinscenario, die tweevliegtuig-met-terreinscenario en die veelvuldige vliegtuig-enterreinscenario. Die ontwikkelde algoritme is in 'n beisge (cluttered), dinamiese omgewing getoets om te verseker dat dit 'n besige lughawescenario kan hanteer. 'n Statistiese ontleding van die simulasie resultate bewys dat die algoritme vinnig en betroubaar 'n aanvanklike oplossingspad kan vind, addisioneel word die oorblywende berekeningstyd ook gebruik om na 'n byna optimaleoplossing te streef.
Description
Thesis (MEng)--Stellenbosch University, 2015.
Keywords
Airport environments, Commercial airliners, Sampling-based path planning algorithm, UCTD