En NSGA-II Basert Optimal Baneplanlegger for Autonom Dokking av Fjernstyrte Undervannsfartøy

Abstract

I denne avhandlingen presenteres en optimal baneplanlegger for fjernstyrte undervannsfartøy basert på den genetiske algoritmen NSGA-II. Avhandlingen er gjort på bakgrunn av en forskningshypotese som sier at baneplalegging er et viktig forskningsområde med tanke på å oppnå vedvarende autonomi i undervannsoperasjoner, og videre at det vil være fordelaktig å implementere en baneplanlegger basert på NSGA-II i kontrollsystemet til fjernstyrte undervannsfartøy. Defineringen av denne forskningshypotesen er basert på en omfattende litteraturstudie som er ment å gi en oversikt over ulike optimeringsteknikker brukt innenfor baneplanlegging.

Den overordnede motivasjonen bak denne oppgaven er å øke graden av autonomi i operasjoner med fjernstyrte undervannsfartøy. Dette er på bakgrunn av at høyere grad av autonomi vil føre til lavere kostnader, økt effektivitet og nøyaktighet, samt opprettholde sikkerheten i slike operasjoner. Mindre avhengighet av menneskelig innblanding vil føre til reduserte kostnader. En avansert kontrollarkitektur, som inkluderer en baneplanlegger, vil føre til økt effektivitet og nøyaktighet. Og ikke minst, tilfredsstillende ytelse av det integrete systemet vil ivareta sikkerheten.

Banelppanleggeren er utviklet og implementert i kontrollsystemet til det fjernstyrte undervannsfartøyet Minerva 2, slik at fartøyet er i stand til å utføre autonomome dokkingoperatsjoner ved å følge baner som består av banepunkter satt sammen av rette linjer. Minerva 2 er et fartøy som eies av Applied Underwater Robotics Laboratory (AUR-lab), et forskningssenter for undervannsrobotikk ved Norges Tekniske-Naturvitenskapelige Universitet (NTNU).

Masteroppgaven tilbyr en definisjon av det optimale baneplanleggingsproblemet for autonome dokkingoperasjoner. Problemdefinisjonen benytter innputtsparametre som startposisjon av det fjernstyrte fartøyet, posisjonen til dokkingstatsjonen, posisjoner til statiske hindringer som er modellert som kuler og sjødybde i operasjonsmiljøet. Det optimale baneplanleggingsproblemet er definert som et optimeringsproblem basert på fire kostfunksjoner. Kostfunksjonene er ansvarlige for å tilegne banene som genereres av baneplanleggeren ønskede egenskaper, og minimeres ved bruk av NSGA-II. De ønskede egenskapene er kort banelengde, tilstrekkelig sikkerhetsmargin til hindringer, fravær av skare svingninger i det horisontale plan, samt tilstrekkelig dybde for å måle høyden over havbunnen ved hjelp av en Doppler Velcity Log (DVL).

Baneplanleggeren er utviklet ved å løse baneplanleggingsproblemet ved hjelp av NSGA-II, som genererer en populasjon av optimale baner basert på kostfunksjonene. Ytelsen til baneplanleggeren som en frittstående applikasjon utenfor det integrerte systemet er verdifisert gjennom simuleringer. Siden baneplanleggingsproblemet har flere kostfunksjoner, gir optimeringen et sett med Pareto-optimale baner. Det betyr baner som er like optimale og ikke kan skilles fra hver andre med tanke pa kostfunskjonsverdier. Etter optimeringen velges en av banene fra det Pareto-optimale settet med baner av en banevelger-algoritme. Banevelgeren er basert på ytterligere brukerdefinerte preferanser på kostfunksjonsverdier.

Den NSGA-II-baserte optimale baneplanleggeren er effektiv med tanke på beregningsmessig komplexitet. NSGA-II har en beregningsmessig komplexitet pa O(MN2), der M er antall kostfunksjoner og N er antall baner i populasjonen. Dessuten avenger dimensjonen til N av antallbanepunkter i hver bane.

Ytelsen til det integrerte systemet er verdifisert gjennom Hardware-In-The-Loop (HIL) simuleringer. Det integrerte systemet består av implementeringen av baneplanleggeren i det avanserte kontrollsystemet til Minerva 2. I det integrerte systemet, kan autonome dokkingoperasjoner gjennomføres i to forskjellige moduser med forskjellige styringsstrategier. Det første moduset kalles auto-depth mode, og er ganske rett fram. Minerva 2 følger ganske enkelt den banen som genereres av baneplanleggeren slik den er. I det andre moduset, som kalles auto-altitude mode, gjøres en online oppdatering av dybdekoordinatene til den genererete banen slik at ROVen følger havbunnen på en konstant ønsket høyde over havbunnen ved hjelp av høydekontroll. Begge modusene for autonome dokkingoperasjoner gir banefølging som ungår kollisjoner med statiske hingringer, og samtidig oppfyller de andre ønskede egenskapene til en optimal bane. Det er imidlertil forksjell på auto-depth mode og auto-altitude mode, ettersom i sistnevnte dykker Minerva 2 ned til ønsket høyde over havbunnen før forflyttningen i det horisontale plan starter. Stort sett er ytelsene god i begge moduser, men det er tendenser til mer oscillatorisk oppførsel i auto-altitude mode. Dette er en utfordring som antas å være løselig ved å endre på parameterinstillingene for høydekontroll i kontrollsystemet. Fordelen med auto-altitude mode er imidlertid at på grunn av den konstante høyden over havbunnen, garanteres pålitelige DVL-målinger. Dette fører til at risikoen for kollisjon med havbunnen elimineres og fører samtidig til pålitelig ytelse av observeren. Ytelsen til observerern viser seg å forfalle dersom DVL-målingene er fraværende eller dårlige. På bakgrunn av disse fordelene er auto-altitude mode anbefalt for autonome dokkingoperasjoner der havbunnen er kompleks eller kunnskap om havdybden er delvis fraværende.

The contribution from this master’s thesis is an optimal path planner for Remotely Operated Vehicles (ROVs) based on the Non-dominated Sorting Genetic Algorithm (NSGA-II). This contribution is a result of the exploration of a research hypothesis stating that path planning is an essential research area in terms of achieving persistent autonomy, and thus, persistent autonomy could be achieved by implementation of a high-performance optimal path planner based on NSGA-II in the control system. Beforehand to the establishment of the research hypothesis, a comprehensive literature review is carried out intended to provide an overview of different optimization techniques applied in path planning. The overall concluding remark from this literature review, is that NSGAII is contained within the category of evolutionary algorithms that is well suited for path planning both in terms of computational complexity and optimization performance.

The overall motivation behind the work is to increase the level of autonomy in ROV operations. Likely, a higher level of autonomy streamlines such operations, that is, save costs, increase efficiency and accuracy, while maintaining safety. Less dependence on human intervention and the mothership causes cost savings. An advanced control architecture, including the path planner, increase efficiency and accuracy. Lastly, obtaining satisfactory performance of the integrated system, and indirectly, the reduced dependence of human intervention, maintain safety. The path planner is developed and implemented into the control system of the ROV Minerva 2, constituting an integrated system enabling Minerva 2 to perform autonomous docking missions by trajectory of paths consisting of waypoints interconnected by straight line segments. The ROV Minerva 2 is an asset of the Applied Underwater Robotics Laboratory (AUR-lab) at the Norwegian University of Science and Technology (NTNU).

Furthermore, the thesis proposes a definition of the optimal path planning problem for autonomous docking missions. The problem definition takes into account parameters, for instance, the initial position of the ROV, the position of the docking station, obstacle positions of static spherically modelled obstacles and depth in the environment. The optimal path planning problem is defined as a multi-objective optimization problem, taking into account four objective functions responsible for assigning the generated paths four desired properties. The objective functions are to be minimized by applying NSGA-II, and thus, obtaining optimal paths. The desirable properties are short path length, sufficient safety margin to obstacles, absence of sharp turns in the horizontal plane, and sufficient depth, ensuring reliable altitude measurements by the Doppler Velocity Log (DVL). The optimal path planner is developed by applying NSGA-II to the optimal path planning problem, generating a population of paths based on the objective functions. The optimization performance of the path planner is thoroughly verified in simulations of the path planner solving the optimal path planning problem as a stand-alone application. Due to the multi-objective nature of the path planning problem, optimization yields a set of Pareto-optimal paths. That is paths that are equally optimal and indistinguishable from each in terms of objective function values. Post-processing of the Pareto-optimal set of paths selects one path for the ROV trajectory in autonomous docking missions, done by a path selector algorithm. The path selector is based on additional user-defined preferences on the objectives.

The NSGA-II based optimal path planner is efficient in terms of computational complexity. By the big-O notation, NSGA-II has the complexity O(MN2), where M is the number of objectives, and N is the number of paths in a population. Furthermore, the dimension of N depends on the number of waypoints in each path. Moreover, Minerva 2 utilizes constant jerk guidance for reference position, which is a waypoint based guidance scheme. Such waypoint based guidance schemes eliminate the need for further path refinement, and thus, save computational resources. Therefore, constant jerk guidance is directly compatible with the NSGA-II based optimal path planner.

The performance of the integrated system is verified in Hardware-In-the-Loop (HIL) simulations. The integrated system is obtained by implementing the NSGA-II based optimal path planner into the advanced control system of Minerva 2. In the integrated system, autonomous docking missions can be performed in two different modes, with different control strategies. The former mode, called auto-depth mode, is straight forward. It merely follows the path as it is, generated by the NSGA-II based optimal path planner. The latter mode, called auto-altitude mode, performs an online update of the depth-coordinate of the waypoints causing the ROV to follow the seafloor at the desired altitude by applying altitude control.

Both modes for autonomous docking missions render trajectories avoiding static obstacles, while also fulfilling the other objectives. However, the auto-altitude mode differs from auto-depth mode, as the former initially in the mission dives down to the desired altitude. Overall, both modes show satisfactory performance in simulations, even though the auto-altitude mode renders a slightly more oscillatory behaviour. This challenge considering the auto-altitude mode is assumed to be solvable by tuning of the altitude control scheme in the control system. The benefit of the auto-altitude mode is that, in this mode, the ROV takes on a fixed desired altitude such that reliable DVL measurements are available. This result eliminates the risk of bottom collision and ensures reliable state estimation. State estimation performed by the vehicle observer is known to deteriorate with the absence of reliable DVL measurements. Thus, the auto-altitude mode is recommended due to its benefits concerning safety when performing autonomous docking missions in complex scenarios where the seafloor is complex or data on the sea depth is partly lacking.