Zoning under Environmental Uncertainty: With Applications for Autonomous Vehicle Routing

Rosenkrands, Kasper ; Pedersen, Casper Bak

4. term

Mathematics-Economics, Master

2022

2022-06-02

45 pages

With the increasing size of wildfires (National Interagency Fire Center [21]) a need for effec- tive ways of monitoring and containing the fires spread has emerged. The use of un- manned aerial vehicles (UAVs) for optical mon- itoring of a spreading wildfire is appropriate due to e.g., the longevity of missions and the hazardous environment. With the increasing size of fires more UAVs are needed to effectively monitor an area, lead- ing to more potential conflicts between UAVs, thereby requiring the need for communication if a UAV were to deviate from its planned route. However there are many situations where communication between UAVs is not practical or even impossible. This project there- fore explores zoning methods that will allow each agent to have navigational freedom while not needing to communicate in order to avoid conflicts. This problem is formulated as a 2-stage stochastic linear programming problem, that reflects the zoning and flight stage, where the environmental uncertainty during flight should be considered when constructing zones. This is solved using two zoning methods, in- spired by the literature (Khemakhem et al. [18]) as well as a novel routing-based cluster- ing method proposed by the authors. These are then compared using cumulative route scores for routes generated in the resulting zones. Their applicability for dynamic environments is further tested by considering how often each of the zoning solutions routes can be optimally updated while respecting zone boundaries. Lastly, the aforementioned zoning methods are compared with a traditional routing approach, in order to gauge performance degradation due to zone restriction

Autonomous vehicles ; clustering ; zoning ; vehicle routing problem ; graph theory

Download
View record in AAU Student Projects