Navigating Urban Skies: A Novel Path Planning Approach for Systems of Drones

Abstract

Ubemannede luftfartøy (“unmanned aerial vehicles”, UAV) har mulighet til å endre samfunnets syn på tilgjengelighet. I løpet av det siste tiåret har UAVer, også kjent som droner, fått større og større interesse fra både institusjonelle og kommersielle aktører. Den lavere delen av luftrommet i urbane områder er underutnyttet, og UAVer kan benytte nettopp denne delen av luftrommet. Samtidig sørger UAVer for større fleksibilitet i transport av pakker og passasjerer sammenlignet med mer tradisjonelle transportmidler. UAVer kan dermed utvide tilgjengeligheten til ulike essensielle og ikke-essensielle varer og tjenester for folk flest.

Det er ikke usannsynlig at UAVer vil håndtere en betydelig del av pakke- og passasjertransporten innen en rekke ulike sektorer de kommende årene. For at denne overgangen skal bli vellykket må flyruten til hver UAV være godt planlagt, og påvirkningen flyrutene har på samfunnet må hensyntas. Formålet med denne masteroppgaven er derfor å foreslå en ruteplanleggingsmodell som genererer sosialt akseptable systemflygeplaner for et sett med UAVer i et urbant miljø.

Denne masteroppgaven studerer fler-UAV ruteplanleggingsproblemet (“multi-UAV path planning”, MUAVPP) i et statisk, tredimensjonalt, urbant miljø. Problemet er modellert som et ikke-lineært, fler-objektiv, blandet heltallsproblem som balanserer fire objektiver; flygetid, risiko, visuell forurensing og støyforurensing. Alle objektivene skal minimeres. En hybrid evolusjonær algoritme som kombinerer non-dominated sorting algorithm III (NSGA-III) med ant colony optimization (ACO) brukes for å løse problemet.

Flere hull i eksisterende litteratur adresseres i denne masteroppgaven. Mest fremtredende er den manglende inkluderingen av visuell forurensing og støyforurensing, som begge er svært sentrale faktorer for sosial aksept. I tillegg modellerer denne masteroppgaven både luft- og bakkerisikoen tilknyttet UAVer, hvilket ikke ble funnet i den undersøkte litteraturen. Den foreslåtte modellen tillater også variasjon av ulike karakteristikker ved UAVer og deres operasjoner mellom ulike deler av UAVenes reiser. Fra et mer overordnet perspektiv, er bruken av en evolusjonær algoritme til å løse et fler-objektiv, fler-UAV ruteplanleggingsproblem i et tredimensjonalt, urbant miljø en ny tilnærming.

Ved å anvende den hybride evolusjonære algoritmen på MUAVPP problemet, ser vi lovende resultater. Algoritmen finner et utvalg systemflygeplaner som gjør gode avveininger mellom de fire objektivene for et sett med testinstanser som benytter Stavanger som en casestudie. Algoritmen jobber med en stor mengde systemflygeplaner underveis i kjøringen, og velger ut fem differensierte systemflygeplaner som returneres. Løsningsmetoden sørger dermed for at beslutningstakeren får et håndterbart antall systemflygeplaner å velge mellom, og sikrer samtidig at graden av samfunnspåvirkning kan kontrolleres. Resultatene gir altså en klar indikasjon på at det er mulig å hensynta sosial aksept i ruteplanleggingen for UAVer i urbane miljøer. Den foreslåtte modellen har imidlertid lang kjøretid, og fremtidig forskning bør derfor fokusere på effektivitetsfremmende tiltak hvis modellen skal brukes i den virkelige verden.

Unmanned aerial vehicles (UAVs) have the potential to transform society’s perception of accessibility. During the last decade, UAVs, also known as drones, have accumulated considerable interest from both institutional and commercial actors. UAVs are able to exploit the underutilized low-altitude urban airspace and provide increased flexibility in parcel and passenger transport compared to more traditional means of transportation. UAVs can hence broaden the general population’s access to various essential and non-essential goods and services.

It is not unlikely that UAVs will handle a significant share of parcel and passenger transport within a wide range of sectors in the coming years. To make this transition successful, the flight paths taken by each UAV must be well planned and the social impact of the paths must be accounted for. Thus, this thesis proposes a path planning model to generate socially acceptable system flight plans for a set of UAVs in an urban environment.

This thesis studies the multi-UAV path planning (MUAVPP) problem in a static, three dimensional, urban environment. The problem is modeled as a multi-objective mixed integer nonlinear program that balances four objectives which are all to be minimized; flight time, risk, visual pollution and noise pollution. A hybrid evolutionary algorithm (HEA) that combines the non-dominated sorting genetic algorithm III (NSGA-III) with ant colony optimization (ACO) is proposed to solve the MUAVPP problem.

Several gaps in existing literature are addressed in this thesis. Most prominent is the current lack of incorporating visual and noise pollution, which are both critical for social acceptability. Furthermore, this thesis models air risk, in addition to ground risk, which is also absent in the reviewed literature. In addition, the proposed model allows various UAV and operational characteristics to vary between different parts of the UAVs’ voyages. Taking a holistic view, the use of an evolutionary algorithm to solve a multi-objective, multi-UAV path planning problem in a three dimensional urban environment, is a novel proposition.

By applying the HEA to the static MUAVPP problem, we see promising results. Using the Norwegian city of Stavanger as a case study, the HEA finds a set of system flight plans that successfully trades off the four objectives for the designed test instances. The HEA works with a large set of system flight plans during its runtime, and selects five diverse system flight plans to return. The solution method thus ensures a manageable number of options for a decision maker to choose from, while simultaneously allowing the degree of social impact to be controlled. The results thus make it clear that it is possible to incorporate social acceptability when performing UAV path planning in urban environments. The proposed model suffers from extensive runtimes however, and future research should focus on efficiency enhancements if the model is to be used in the real world.