Safe Path Planning Under Uncertainty
Author
Pedersen, Emil Ingemann
Term
4. term
Education
Publication year
2020
Submitted on
2020-06-02
Pages
59
Abstract
Dette speciale undersøger, hvordan man planlægger en rute for en UAV (ubemandet luftfartøj eller drone), når der findes områder, som dronen bør holde afstand til, fordi de er forbundet med risiko. Først gives et overblik over eksisterende metoder og opsætninger fra litteraturen, der bruges til at løse lignende planlægningsproblemer. Herefter præsenteres en problemformulering, hvor der tages højde for usikkerhed omkring de områder, der skal undgås. Denne usikkerhed beskrives som forskellige scenarier, som ruteplanlægningen skal være robust over for. Området, dronen skal passere, modelleres som en gridbaseret graf (et rudenet, hvor felter er forbundet). På den måde kan der findes en rute, der minimerer den samlede risiko, ved hjælp af dynamisk programmering med ressourcebegrænsning – en trinvis beregningsmetode, der finder den bedste løsning under givne begrænsninger. Algoritmen tilpasses, så den samtidig kan tage højde for flere scenarier og dermed levere en robust rute, der fungerer på tværs af mulige situationer. Til sidst evalueres tilgangen med en sensitivitetsanalyse, der undersøger, hvor følsomme resultaterne er over for ændringer i antagelser og parametre.
This thesis examines how to plan a route for a UAV (unmanned aerial vehicle, or drone) when there are areas it should avoid because they pose risk. It begins with an overview of existing methods and setups used in the literature to address similar planning problems. It then formulates the problem and describes how to handle uncertainty about the areas to avoid by defining multiple scenarios that the route must account for. The region the drone must traverse is modeled as a grid-based graph (a grid where cells are connected). This makes it possible to find a route that minimizes overall risk using dynamic programming with resource constraint—a stepwise computational method that identifies the best solution under given constraints. The algorithm is adapted to consider multiple scenarios and to produce a robust route that performs well across possible situations. Finally, the approach is evaluated with a sensitivity analysis to examine how the results change when assumptions and parameters are varied.
[This abstract was generated with the help of AI]
Documents