Motion planning algorithms for autonomous navigation for a rotary-wing UAV
Date
2013-03
Authors
Beyers, Coenraad Johannes
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: This project concerns motion planning for a rotary wing UAV, where vehicle controllers are
already in place, and map data is readily available to a collision detection module. In broad
terms, the goal of the motion planning algorithm is to provide a safe (i.e. obstacle free)
flight path between an initial- and goal waypoint. This project looks at two specific motion
planning algorithms, the Rapidly Exploring Random Tree (or RRT*), and the Probabilistic
Roadmap Method (or PRM).
The primary focus of this project is learning how these algorithms behave in specific environments
and an in depth analysis is done on their differences. A secondary focus is the
execution of planned paths via a Simulink simulation and lastly, this project also looks at
the effect of path replanning.
The work done in this project enables a rotary wing UAV to autonomously navigate an
uncertain, dynamic and cluttered environment. The work also provides insight into the
choice of an algorithm for a given environment: knowing which algorithm performs better
can save valuable processing time and will make the entire system more responsive.
AFRIKAANSE OPSOMMING: ’n Tipiese vliegstuuroutomaat is daartoe in staat om ’n onbemande lugvaartvoertuig (UAV) so te stuur dat ’n stel gedefinieerde punte gevolg word. Die punte moet egter vooraf beplan word, en indien enige verandering nodig is (bv. as gevolg van veranderinge in die omgewing) is dit nodig dat ’n menslike operateur betrokke moet raak. Vir voertuie om ten volle outonoom te kan navigeer, moet die voertuig in staat wees om te kan reageer op veranderende situasies. Vir hierdie doel word kinodinamiese beplanningsalgoritmes en konflikdeteksiemetodes gebruik. Hierdie projek behels kinodinamiese beplanningsalgoritmes vir ’n onbemande helikopter, waar die beheerders vir die voertuig reeds in plek is, en omgewingsdata beskikbaar is vir ’n konflikdeteksie-module. In breë terme is die doel van die kinodinamiese beplanningsalgoritme om ’n veilige (d.w.s ’n konflikvrye) vlugpad tussen ’n begin- en eindpunt te vind. Hierdie projek kyk na twee spesifieke kinodinamiese beplanningsalgoritmes, die “Rapidly exploring Random Tree*” (of RRT*), en die “Probabilistic Roadmap Method” (of PRM). Die primêre fokus van hierdie projek is om die gedrag van hierdie algoritmes in spesifieke omgewings te analiseer en ’n volledige analise te doen op hul verskille. ’n Sekondêre fokus is die uitvoering van ’n beplande vlugpad d.m.v ’n Simulink-simulasie, en laastens kyk hierdie projek ook na die effek van padherbeplanning. Die werk wat gedoen is in hierdie projek stel ’n onbemande helikopter in staat om outonoom te navigeer in ’n onsekere, dinamiese en besige omgewing. Die werk bied ook insig in die keuse van ’n algoritme vir ’n gegewe omgewing: om te weet watter algoritme beter uitvoertye het kan waardevolle verwerkingstyd bespaar, en verseker dat die hele stelsel vinniger kan reageer.
AFRIKAANSE OPSOMMING: ’n Tipiese vliegstuuroutomaat is daartoe in staat om ’n onbemande lugvaartvoertuig (UAV) so te stuur dat ’n stel gedefinieerde punte gevolg word. Die punte moet egter vooraf beplan word, en indien enige verandering nodig is (bv. as gevolg van veranderinge in die omgewing) is dit nodig dat ’n menslike operateur betrokke moet raak. Vir voertuie om ten volle outonoom te kan navigeer, moet die voertuig in staat wees om te kan reageer op veranderende situasies. Vir hierdie doel word kinodinamiese beplanningsalgoritmes en konflikdeteksiemetodes gebruik. Hierdie projek behels kinodinamiese beplanningsalgoritmes vir ’n onbemande helikopter, waar die beheerders vir die voertuig reeds in plek is, en omgewingsdata beskikbaar is vir ’n konflikdeteksie-module. In breë terme is die doel van die kinodinamiese beplanningsalgoritme om ’n veilige (d.w.s ’n konflikvrye) vlugpad tussen ’n begin- en eindpunt te vind. Hierdie projek kyk na twee spesifieke kinodinamiese beplanningsalgoritmes, die “Rapidly exploring Random Tree*” (of RRT*), en die “Probabilistic Roadmap Method” (of PRM). Die primêre fokus van hierdie projek is om die gedrag van hierdie algoritmes in spesifieke omgewings te analiseer en ’n volledige analise te doen op hul verskille. ’n Sekondêre fokus is die uitvoering van ’n beplande vlugpad d.m.v ’n Simulink-simulasie, en laastens kyk hierdie projek ook na die effek van padherbeplanning. Die werk wat gedoen is in hierdie projek stel ’n onbemande helikopter in staat om outonoom te navigeer in ’n onsekere, dinamiese en besige omgewing. Die werk bied ook insig in die keuse van ’n algoritme vir ’n gegewe omgewing: om te weet watter algoritme beter uitvoertye het kan waardevolle verwerkingstyd bespaar, en verseker dat die hele stelsel vinniger kan reageer.
Description
Thesis (MScEng)--Stellenbosch University, 2013.
Keywords
Motion planning algorithms, Autonomous navigation, Rotary-wing UAV, Unmanned aerial vehicle, Dissertations -- Electronic engineering, Theses -- Electronic engineering, Drone aircraft