Zoning under Environmental Uncertainty: With Applications for Autonomous Vehicle Routing
Translated title
Zoning under Environmental Uncertainty
Authors
Rosenkrands, Kasper ; Pedersen, Casper Bak
Term
4. term
Education
Publication year
2022
Pages
45
Abstract
Efterhånden som skovbrande bliver større, vokser behovet for at overvåge og begrænse deres spredning effektivt. Ubemandede luftfartøjer (UAV'er) egner sig til optisk (kamera-baseret) overvågning, fordi de kan flyve længe og operere i farlige områder. Når flere UAV'er bruges samtidigt, stiger risikoen for konflikter mellem flyene. Normalt kan det løses med indbyrdes kommunikation, men det er ofte upraktisk eller umuligt. Denne afhandling undersøger derfor zonering: at opdele luftrummet i zoner, så hver UAV får navigationsfrihed i sin egen zone uden at skulle kommunikere for at undgå konflikter. Problemet formuleres som en totrins stokastisk lineær programmering, en matematisk planlægningsmodel i to faser, der tager højde for usikre forhold. Først fastlægges zonerne, og derefter planlægges flyvningerne inden for zonerne. Afhandlingen afprøver to zoneringsmetoder inspireret af eksisterende litteratur samt en ny, rute-baseret klyngemetode foreslået af forfatterne. Metoderne evalueres ved at generere ruter inden for de skabte zoner og sammenligne deres samlede rutescorer. Deres anvendelighed i dynamiske miljøer undersøges også ved at måle, hvor ofte ruter kan opdateres optimalt uden at overskride zonegrænser. Endelig sammenlignes zonebaserede løsninger med traditionel ruteplanlægning uden zoner for at vurdere eventuelle ydelsestab på grund af zonebegrænsninger.
As wildfires grow larger, there is a stronger need to monitor and contain their spread effectively. Unmanned aerial vehicles (UAVs) are well suited for optical (camera-based) monitoring because they support long missions and can operate in hazardous areas. Using more UAVs increases the risk of conflicts between aircraft. Communication can help avoid conflicts, but in many situations it is impractical or impossible. This thesis therefore explores zoning: dividing the airspace into zones so each UAV has navigational freedom within its own area without needing to communicate. The problem is formulated as a two-stage stochastic linear programming model—a two-step mathematical planning approach that accounts for uncertainty. In the first stage, zones are defined; in the second, flights are planned within those zones. The study tests two zoning methods inspired by prior literature and introduces a new routing-based clustering method proposed by the authors. The methods are evaluated by generating routes within the resulting zones and comparing their cumulative route scores. Their suitability for dynamic environments is further assessed by examining how often routes can be re-optimized while respecting zone boundaries. Finally, the zone-based approaches are compared with a traditional routing approach without zones to gauge any performance loss caused by zone restrictions.
[This summary has been rewritten with the help of AI based on the project's original abstract]
Keywords
Documents