Path planning for wave-powered unmanned surface vehicle based on electronic navigational charts and weather data

Abstract

Denne masteroppgaven gjør rede for utviklingen og implementasjonen av en stifinner for en USV som drives av bølgekraft. USVen, NTNU AutoNaut, er en del av et forskningsprosjekt på NTNU i Trondheim.

Stifinning for AutoNaut ble gjennomført på høstsemesteret i 2021 i form av en prosjektoppgave. Dette prosjektet brukte elektroniske sjøkart med geodatabase-data for å lage ruter AutoNauten kunne følge uten å gå på grunn. En rutenettbasert tilnærming ble valgt, og sjøkartet ble delt opp i noder. Søkealgoritmen A* ble ble brukt for å skape stier som unngikk land og grunner. Denne algoritmen, hjulpet av en euklidisk heuristikk, klarte å produsere en sti fra et startpunkt til et endepunkt på kartet. Systemet fungerte, og produserte waypoints gitt at en gjennomførbar rute eksisterte.

Denne oppgaven utvider på prosjektoppgaven. Mens prosjektoppgaven kun produserte ruter basert på geografi og havdybde, sikter denne masteroppgaven på å også ta hensyn til værdata. Værvarsler ble hentet fra et API utviklet av Meteorologisk Institutt. Dette ble valgt på grunn av både dekningsområde, tilgjengelighet og pris. Seks datapunkter ble hentet inn for denne oppgaven, relatert til vind, bølger og havstrøm, da disse ble ansett for å være mest relevant for ruteplanlegging til havs. Verktøy for innsamling og plotting av værdata ble utviklet for SeaCharts APIet, og disse verktøyene vil kanskje innlemmes i SeaCharts i fremtiden.

En kostnadsfunksjon basert på værdata ble laget med spesielt hensyn på sikkerhet. A*-algoritmen ble modifisert til å inkludere denne kostnadsfunksjonen, og bevegelseskostnader ble vektlagt med hensyn på normal og diagonal bevegelse, såvell som angrepsvinkel og styrke på værkreftene. Kostnadene ble tunet ved hjelp av selvgenerert dummy-data. Resultatene virket lovende, og de resulterende rutene så ut til å vinkle AutoNauten riktig i forhold til værkreftene. Likevel er det nødvendig med ekte sjøtester for å validere systemet tilstrekkelig. Ekte sensordata fra AutoNauten ble ikke hentet inn, både på grunn av tidsbegrensinger og begrenset tilgjengelighet. En gjennomtenkt plan for testing og tuning må gjennomføres for at stifinneren skal virke ordentlig i det ekte havrommet.

Det har også blitt jobbet med å begrense utvalgte faremomenter for AutoNauten. Buffersoner ble generert rundt land og grunner. Disse ble ansett som hindringer av A*-algoritmen, for å begrense sjansene for grunnstøting. En minimum trygg avstand til land ble også funnet.

Videre ble rutene generert av stifinneren utsatt for postprosessering. For å både begrense informasjonsmengden som må sendes til AutoNauten, og i tillegg begrense antallet manuelle inputs nødvendig for å starte et oppdrag, ble algoritmer for å begrense antall waypoints utviklet. To potensielle beskjæringsalgoritmer ble testet, én basert på å hoppe over enkeltpunkter og én basert på rekursiv segmentering av ruten. Sistnevnte ble ansett å være bedre på grunn av bedre skalerbarhet og fleksibilitet.

The work documented in this thesis details the development and implementation of a path planning plan for a wave-powered USV. The USV, known as NTNU AutoNaut, is part of a scientific project hosted by the Norwegian University of Science and Technology.

Previous work related to path planning for the AutoNaut was conducted in the fall semester of 2021 in the form of a project thesis. This work used ENCs with geodatabase data to create paths to avoid grounding of the AutoNaut. A grid-based approach was selected, and the sea chart was divided into distinct nodes. An A* algorithm was implemented to create paths which avoided land and shallows. This algorithm, aided by a euclidean heuristic, would produce way-points from a starting point to a goal point on the map. The system showed promising results, and would produce a list of way-points given the existence of a feasible path.

This thesis expands upon the project thesis. While the project thesis would produce paths solely based on geography and ocean depth, this work aims to take weather data into account when generating paths. Weather forecasts were collected from the Norwegian Meteorological Institute, which was selected for its coverage area, availability and wide selection of data. Forecasts related to wind, waves and current were downloaded, as these forecasts were determined to be the most relevant for path generation. Collection and plotting tools for weather data were created for the SeaCharts API, and these might be integrated into the tool in future work.

A cost function based on the weather data was created with emphasis on safety. The A* algorithm was modified to incorporate this cost function, and movement costs were weighted according to normal and diagonal movement, as well as the angle of attack and magnitude of the weather forces. These costs were then tuned using simulated data. Results appear promising, but the attempts to tune the system were inconclusive. Sensor data from the AutoNaut itself was not gathered due to time constraints and availability. A proper plan for testing and tuning needs to be executed for the path planner to work properly in the real ocean environment.

In addition to the collection of weather forecasts, efforts were made to limit the number of hazardous situations the AutoNaut might find itself in. Buffer zones were created around land and shallows. These were seen as obstacles by the path planner to decrease the chances of grounding. A minimum safe distance to land to allow for operator intervention was also created.

Furthermore, the paths generated by the path planning algorithm underwent some post-processing. In order to both limit the amount of information needed to be sent to the AutoNaut, as well as decrease the amount of manual inputs needed to start a mission, two algorithms for reducing the amount of waypoints were developed. Two potential "path pruning" algorithms were created and tested, one based on pure skipping of waypoints, and one based on recursive segmentation of the path. In the end, the latter was chosen as it scaled better and was more flexible.