A Path-Velocity Decomposition Approach to Collision Avoidance for Autonomous Passenger Ferries

Abstract

Under utviklingen av autonome systemer, som for eksempel autonome passasjerferger, er det to kritiske sub-systemer som må være på plass for at systemet ikke bare skal være automatisert. Det første er et situasjonsforståelses-system som kan detektere og beskrive alle aspekter ved omgivelsene som er relevant for oppdraget som skal utføres. Det andre er et system som planlegger utførelsen av oppdraget basert på situasjonen i omgivelsene og oppdragets natur. Oppdragsplanleggeren må også kunne tilpasse planen underveis dersom det skjer endringer i situasjonsforståelses-systemets beskrivelse av omgivelsene. For autonome overflatefartøyer kalles et slikt oppdragsplanleggings-system gjerne et kollisjonsungåelses-system (COLAV-system).

I denne masteroppgaven presenteres et forslag til et komplett COLAV-system for autonome passasjerferger. Systemet har en tredelt struktur med en planleggende del, en organiserende del og en reaktivt del. Den planleggende delen består av en global ruteplanlegger. Den deler oppgaven inn i baneplanlegging og hastighetsplanlegging, og benytter seg av en eller flere forhåndsdefinerte baner som ikke kolliderer med statiske hindringer i omgivelsene. Dette reduserer problemet til å planlegge en hastighetsprofil langs den forhåndsdefinerte banen som sørger for at fergen ikke kolliderer med andre fartøyer i omgivelsene. Problemet løses ved at alle fartøyer representeres som noder i et bane-tid rom, for så å løse det som et minste-kostnad-nodesøk problem. Den reaktive delen av systemet følger ruten som er planlagt, og samtidig driver en kontinuerlig vurdering av planens holdbarhet, basert på oppdatert informasjon om fartøyene i omgivelsene. Om vurderingen viser at planen ikke holder, igangsettes en ny planlegging i den planleggende delen. Den organiserende delen håndterer kommunikasjonen mellom det planleggende og den reaktive delen i tillegg til å håndtere oppdragsforespørseler.

To versjoner av COLAV-systemet er implementert. Den første bruker en forhåndsdefinert bane som input til hastighetsplanleggingsproblemet, den andre bruker et sett med parallelle forhåndsdefinerte baner der algoritmen får lov til å skifte mellom banene underveis i overfarten.

En simulator er utviklet basert på modellparametere fra en prototype av en autonom passasjerferge som heter milliAmpere. Simulatoren brukes til testing av COLAV-systemet med opptil fire bevegelige objekter med forskjellig oppførsel. De to versjonene av COLAV-systemet er testet og sammenlignet med en versjon av Velocity Obstacle algoritmen.

Begge systemene viser god oppførsel i simulatoren. De klarer å planlegge globale ruter uten problemer, og tilpasser seg endringer i omgivelsene underveis. De utfører også overfarten med mindre manøvrering enn Velocity Obstacle algoritmen.

Systemet er også validert gjennom sjøprøver der begge metodene igjen gir tilfredsstillende resultater. Systemet med bare én bane viser seg å være det mest overbevisende systemet når det gjelder passasjerkomfort og sikkerhet.

When developing fully autonomous surface vessels such as passenger ferries, two critical systems need to be in place for it to be autonomous, and not merely automated. Firstly, it needs to have a situational awareness system that is able to capture all the features of the situation that are relevant for the mission of the ferry, and describe the features in a way that is usable. Secondly, it needs to have a mission planning system that uses the understanding of the situation along with the mission goal to make a feasible plan. The mission planner also needs to be able to adjust the plan underway, if changes in the perception of the situation were to occur. Such a mission-planning system for an autonomous surface vessel is typically called a collision avoidance (COLAV) system.

This Master's thesis presents an approach to a complete COLAV system for autonomous passenger ferries. The COLAV system has a three-layered structure with a deliberate, reactive and executive layer. The deliberate layer is a global trajectory planner that uses path-velocity decomposition, with a predefined path, or set of paths, that is collision-free with regard to any static objects. This reduces the task of avoiding moving objects down to a velocity planning problem. The problem is solved by firstly transforming an object representation onto the path-time space as nodes, and subsequently solving the velocity planning as a minimum cost node search problem. The reactive layer tracks the trajectory reference and continuously validates the feasibility of the current global plan. It also monitors changes in the object situation based on estimated time to closest approach and distance of closest approach and invokes a replan in the deliberate layer when necessary. The executive layer acts as a relay between the deliberate and reactive layer and handles mission-request and invocations.

Two versions of the velocity-planning algorithm in the deliberate layer are implemented. The first uses a single predefined path as input to the velocity planning problem, while the second uses a set of predefined parallel paths, where the algorithm is allowed to switch between the paths freely during the transit.

A simulator is developed based on model parameters from a prototype of an autonomous passenger ferry called milliAmpere. The simulator is used to test the COLAV system with up to four moving objects with different behaviours. The two versions of the COLAV system are tested and compared to an implementation of the existing velocity obstacle algorithm.

Through simulations, both the new velocity-planning algorithm prove to be effective. They are able to plan global trajectories with ease, adapt to rapid changes in the environment and perform transits with lower maneuvering efforts than the velocity obstacle approach.

The proposed COLAV system is also validated through sea trials, where both algorithms again performed satisfactory. The single-path approach turns out to be the most convincing algorithm in terms of passenger comfort and safety.