Kinodynamic planning for a fixed-wing aircraft in dynamic, cluttered environments : a local planning method using implicitly-defined motion primitives
Date
2013-03
Authors
Cowley, Edwe Gerrit
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: In order to navigate dynamic, cluttered environments safely, fully autonomous Unmanned
Aerial Vehicles (UAVs) are required to plan conflict-free trajectories between two states
in position-time space efficiently and reliably. Kinodynamic planning for vehicles with
non-holonomic dynamic constraints is an NP-hard problem which is usually addressed
using sampling-based, probabilistically complete motion planning algorithms. These algorithms
are often applied in conjunction with a finite set of simple geometric motion
primitives which encapsulate the dynamic constraints of the vehicle. This ensures that
composite trajectories generated by the planning algorithm adhere to the vehicle dynamics.
For many vehicles, accurate tracking of position-based trajectories is a non-trivial
problem which demands complicated control techniques with high energy requirements.
In an effort to reduce control complexity and thus also energy consumption, a generic
Local Planning Method (LPM), able to plan trajectories based on implicitly-defined motion
primitives, is developed in this project. This allows the planning algorithm to construct
trajectories which are based on simulated results of vehicle motion under the
control of a rudimentary auto-pilot, as opposed to a more complicated position-tracking
system. The LPM abstracts motion primitives in such a way that it may theoretically be
made applicable to various vehicles and control systems through simple substitution of
the motion primitive set.
The LPM, which is based on a variation of the Levenberg-Marquardt Algorithm (LMA),
is integrated into a well-known Probabilistic Roadmap (PRM) kinodynamic planning algorithm
which is known to work well in dynamic and cluttered environments. The complete
motion planning algorithm is tested thoroughly in various simulated environments,
using a vehicle model and controllers which have been previously verified against a real
UAV during practical flight tests.
AFRIKAANSE OPSOMMING: Ten einde dinamiese, voorwerpryke omgewings veilig te navigeer, word daar vereis dat volledig-outonome onbemande lugvoertuie konflikvrye trajekte tussen twee posisie-tydtoestande doeltreffend en betroubaar kan beplan. Kinodinamiese beplanning is ’n NPmoeilike probleem wat gewoonlik deur middel van probabilisties-volledige beplanningsalgoritmes aangespreek word . Hierdie algoritmes word dikwels in kombinasie met ’n eindige stel eenvoudige geometriese maneuvers, wat die dinamiese beperkings van die voertuig omvat, ingespan. Sodanig word daar verseker dat trajekte wat deur die beplaningsalgoritme saamgestel is aan die dinamiese beperkings van die voertuig voldoen. Vir baie voertuie, is die akkurate volging van posisie-gebaseerde trajekte ’n nie-triviale probleem wat die gebruik van ingewikkelde, energie-intensiewe beheertegnieke vereis. In ’n poging om beheer-kompleksiteit, en dus energie-verbruik, te verminder, word ’n generiese plaaslike-beplanner voorgestel. Hierdie algoritme stel die groter kinodinamiese beplanner in staat daartoe om trajekte saam te stel wat op empiriese waarnemings van voertuig-trajekte gebaseer is. ’n Eenvoudige beheerstelsel kan dus gebruik word, in teenstelling met die meer ingewikkelde padvolgingsbeheerders wat benodig word om eenvoudige geometriese trajekte akkuraat te volg. Die plaaslike-beplanner abstraeer maneuvers in so ’n mate dat dit teoreties op verskeie voertuie en beheerstelsels van toepassing gemaak kan word deur eenvoudig die maneuver-stel te vervang. Die plaaslike-beplanner, wat afgelei is van die Levenberg-Marquardt-Algoritme (LMA), word in ’n welbekende “Probabilistic Roadmap” (PRM) kinodinamiese-beplanningsalgoritme geïntegreer. Dit word algemeen aanvaar dat die PRM effektief werk in dinamiese, voorwerpryke omgewings. Die volledige beplanningsalgoritme word deeglik in verskeie, gesimuleerde omgewings getoets op ’n voertuig-model en -beheerders wat voorheen vir akkuraatheid teenoor ’n werklike voertuig gekontroleer is tydens praktiese vlugtoetse.
AFRIKAANSE OPSOMMING: Ten einde dinamiese, voorwerpryke omgewings veilig te navigeer, word daar vereis dat volledig-outonome onbemande lugvoertuie konflikvrye trajekte tussen twee posisie-tydtoestande doeltreffend en betroubaar kan beplan. Kinodinamiese beplanning is ’n NPmoeilike probleem wat gewoonlik deur middel van probabilisties-volledige beplanningsalgoritmes aangespreek word . Hierdie algoritmes word dikwels in kombinasie met ’n eindige stel eenvoudige geometriese maneuvers, wat die dinamiese beperkings van die voertuig omvat, ingespan. Sodanig word daar verseker dat trajekte wat deur die beplaningsalgoritme saamgestel is aan die dinamiese beperkings van die voertuig voldoen. Vir baie voertuie, is die akkurate volging van posisie-gebaseerde trajekte ’n nie-triviale probleem wat die gebruik van ingewikkelde, energie-intensiewe beheertegnieke vereis. In ’n poging om beheer-kompleksiteit, en dus energie-verbruik, te verminder, word ’n generiese plaaslike-beplanner voorgestel. Hierdie algoritme stel die groter kinodinamiese beplanner in staat daartoe om trajekte saam te stel wat op empiriese waarnemings van voertuig-trajekte gebaseer is. ’n Eenvoudige beheerstelsel kan dus gebruik word, in teenstelling met die meer ingewikkelde padvolgingsbeheerders wat benodig word om eenvoudige geometriese trajekte akkuraat te volg. Die plaaslike-beplanner abstraeer maneuvers in so ’n mate dat dit teoreties op verskeie voertuie en beheerstelsels van toepassing gemaak kan word deur eenvoudig die maneuver-stel te vervang. Die plaaslike-beplanner, wat afgelei is van die Levenberg-Marquardt-Algoritme (LMA), word in ’n welbekende “Probabilistic Roadmap” (PRM) kinodinamiese-beplanningsalgoritme geïntegreer. Dit word algemeen aanvaar dat die PRM effektief werk in dinamiese, voorwerpryke omgewings. Die volledige beplanningsalgoritme word deeglik in verskeie, gesimuleerde omgewings getoets op ’n voertuig-model en -beheerders wat voorheen vir akkuraatheid teenoor ’n werklike voertuig gekontroleer is tydens praktiese vlugtoetse.
Description
Thesis (MScEng)--Stellenbosch University, 2013.
Keywords
Motion planning, Conflict avoidance, Autonomous vehicles, Sampling-based algorithms, Dissertations -- Electronic engineering, Theses -- Electronic engineering, Drone aircraft