Risk-based Traffic Rules Compliant Collision Avoidance for Autonomous Ships

Abstract

Summary As the maritime traffic sector is expected to increase over the next years, effort should be invested into protocols and technology for ensuring safe and efficient voyage over the seas. Autonomous ships can here offer multiple benefits, such as increased safety and efficiency, lessened environmental impact and higher rates of reliability and consistency. Recently, there has been an increased focus on the development of such autonomous surface vehicle platforms, with examples such as Yara Birkeland and Zeabuz leading the way in Norway. For this development to be successful, there is a need for robust autonomy systems onboard the ship, which can make intelligent decisions in reasonable time in order to avoid collision and adhere to the International Regulations for Preventing Collisions at Sea (COLREGS), when faced with a challenging and uncertain environment involving multiple grounding hazards and dynamic vessels or obstacles. In this setting, a robust collision avoidance (COLAV) system is vital for the safety and efficacy of the autonomous ship. Topics within this field has been the focus in this thesis. During the PhD, two sampling-based Collision Probability Estimators (CPEs) were developed, one based on a combination of Monte Carlo Simulation (MCS) and a Kalman-filter, and the other based on the Cross-Entropy (CE) method. Both CPEs estimate the probability that a ship will collide with a nearby dynamic obstacle, by taking the kinematic uncertainty of the obstacle into account. For the first CPE, samples from the obstacle Probability Density Function (PDF) involving both position and velocity are used to estimate the probability, which is then filtered through the KF to obtain the final estimate. The KF makes it possible to reduce the statistical variance introduced by the MCS. However, the method struggles with estimating low collision probabilities, as the assumption of constant obstacle velocities in the sampling and the curse of dimensionality makes evident. This was solved through the CE-based CPE, which can adaptively converge towards the optimal density to sample from using iterative optimization by minimizing the Kullback-Leibler divergence between the optimal and the current importance densities. Because of the adaptivity, the CE-based estimator can obtain low variance collision probability estimates at reasonably low computational cost. Simulation studies are shown to verify the methods. Simultaneously, the Probabilistic Scenario-based Model Predictive Control (PSBMPC) was introduced, based on the original Scenario-based MPC (SB-MPC), as an aim towards taking situational uncertainty into account for COLAV. The PSB-MPC employs a CPE to have probabilistic risk assessment, by using collision probability estimates in its cost function, which increases the COLAV situational awareness. The PSB-MPC was further enhanced throughout the thesis work to also consider intention uncertainty for nearby dynamic obstacles, by evaluating the probabilities of multiple different maneuvering scenarios for each obstacle. Ornstein-Uhlenbeck (OU) processes and Line-of-Sight (LOS) guidance based models have been used to improve its prediction scheme and allow for also taking into account this intention uncertainty. Simulation results are shown throughout the thesis chapters to prove that the method incrementally gets more and more viable for use as a means for robust COLAV. This is also evident after a parallelized and efficient implementation of the algorithm was developed, which facilitates both static and dynamic obstacle avoidance through the use of a Graphical Processing Unit (GPU) in the MPC cost evaluation. In the last part of the thesis work, the GPU-based PSB-MPC with a Dynamic Bayesian Net (DBN) for intention inference is validated in full-scale experiments, which demonstrates the viability of the method. Lastly, a new approach to joint vessel destination inference and long-term kinematics prediction for dynamic obstacles was developed. The method uses a maritime graph in combination with a piecewise OU process and a so-called bridge model, in a Bayesian inference setting. The piecewise OU process utilizes maritime traffic pattern information through the maritime graph, for more accurate predictions of typical vessel trajectories along common sea lanes. After the vessel has reached the end of its trajectory along the maritime graph, the bridge model enables the continued vessel prediction to converge towards the considered destinations. It is demonstrated using historical Automatic Identification System (AIS) data that the method performs better than current state-of-the-art in terms of both destination inference and prediction quality. Improved vessel predictions, in addition to information on their most likely goal destinations, is valuable for ship autonomy applications, and the next step will be to also incorporate this in risk-based COLAV systems. The thesis work has contributed to the progress of research within robust COLAV systems, for both the situational awareness and decision making aspects of the topic. Still, there are considerable challenges to solve. How to tune COLAV systems such as the PSB-MPC, with all involved modules, for use in a large variety of situations with different geographies and dynamic obstacle configurations is highly non-trivial. It will here be important to investigate methods for making such systems adaptive and capable of learning from experience, in order to properly adopt them on maritime vessels.

Samandrag: Ein ventar at den maritime sektoren vil auke i dei komande åra. Det bør derfor investerast i protokollar og teknologi for å gjere sjøtransport både sikrare og meir effektiv. Her kan autonome skip tilby fleire fordelar, som auka sikkerheit og effektivitet, mindre miljømessig påverknad samt ein i større grad påliteleg og repeterbar oppførsel. I det siste har det vore auka fokus på utvikling av slike platformar for autonome overflatefartøy, med eksempel som Yara Birkeland og Zeabus i Noreg. For at denne utviklinga skal vere vellukka, trengst det robuste autonomisystem på skipet, som kan ta intelligente avgjersler i rimeleg tid for å unngå kollisjon med andre båtar. Eit utfordrande og usikkert miljø med fleire grunningsfarar og dynamiske hindringar krev også at ein føyer seg etter det internasjonale regelverket for å forhindre kollisjon på sjøen (COLREGS). I denne samanhengen så er eit robust kollisjonsunngåingssystem viktig for sikkerheita og effektiviteten til det autonome skipet. Emne innan dette feltet har vore fokuset i denne avhandlinga. I løpet av PhD-en blei to samplingsbaserte kollisjonssannsynsestimatorar utvikla. Den første er basert på ein kombinasjon av Monte Carlo-simulering og eit Kalmanfilter, medan den andre er basert på kryssentropi-metoden. Begge estimerer sannsynet for at eit skip vil kollidere med ei nærliggande dynamisk hindring, ved å ta omsyn til den kinematiske usikkerheiten til hindringa. For den første estimatoren, blir sampel av både posisjon og hastigheit frå sannsynstettleiken til hindringa brukt til å estimere sannsynet, som vidare blir filtrert gjennom Kalmanfilteret for å få det endelege estimatet. Kalmanfilteret gjer det mogleg å redusere den statistiske variansen som kjem frå bruk av Monte Carlo-simulering. På den andre sida slit metoden med å estimere låge kollisjonssannsyn, på grunn av at ein i samplinga reknar hastigheiten som konstant, samt den såkalla dimensjonalitetsforbanninga. Dette blei løyst gjennom bruk av den kryssentropibaserte estimatoren, som på ein adaptiv måte kan konvergere mot den optimale tettleiken å sample frå, ved bruk av iterativ optimalisering for å minimalisere Kullback-Leibler-divergensen mellom den optimale og nåverande viktigheitstettleiken. På grunn av adaptiviteten kan den andre estimatoren oppnå låg varians på kollisjonssannsynsestimata ved liten reknemessig kostnad. Simuleringsstudiar er her vist for å verifisera dei to estimatorane. Samtidig blei den probabilistisk scenariobaserte modellprediktive regulatoren (PSBMPC) introdusert, basert på den opprinnelege scenariobaserte MPC-en (SB-MPC), med målet om å kunne ta omsyn til situasjonsspesifikk usikkerheit for kollisjonsunngåing. PSB-MPC-en bruker ein kollisjonssannsynsestimator for å oppnå probabilistisk risikovurdering der kollisjonssannsynsestimata inngår i kostnadsfunksjonen, noko som igjen aukar situasjonsforståinga til systemet. Algoritmen blei vidare forbetra gjennom arbeidet i doktorgraden til å også kunne ta omsyn til intensjonsusikkerheit for nærliggande dynamiske hindringar. Dette var mogleg ved å evaluere sannsyna for fleire ulike manøverscenariar for kvar hindring. Ornstein-Uhlenbeck (OU)-prosessen og siktelinjemetoden blei brukt til å forbetre prediksjonsdelen av MPC-en, for å kunne ta omsyn til intensjonsusikkerheit. Simuleringsresultat er vist for å demonstrere at metoden gradvis gir meir robust kollisjonsunngåing. Dette blir endå meir tydeleg etter at ein parallellisert og effektiv implementasjon av algoritmen blei utvikla. Denne innlemma kollisjonsunngåing med omsyn til både statiske og dynamiske hindringar ved å ta i bruk ein grafikkprosessor i kostnadsevalueringa til MPC-en. Den paralleliserte versjonen av PSB-MPC-algorithmen blei til sist testa experimentelt ilag med eit dynamisk Bayesiansk nettverk brukt til intensjonsinferens for dynamiske hindringar, som demonstrerte at algoritmen kan brukast i praksis. Sist blei ein ny måte å samtidig estimere eit skip sin planlagte destinasjon og langtidsprediksjon mot denne, utvikla. Metoden bruker ein maritim graf kombinert med ein stykkevis OU-prosess og ein såkalla brumodell i ein Bayesiansk setting. Den stykkevise OU-prosessen utnyttar informasjon om maritime trafikkmønster gjennom den maritime grafen, for meir nøyaktige prediksjonar av typiske skipsbanar langs vanlege sjøvegar. Etter at skipet har nådd enden av banen langs den maritime grafen, gjer brumodellen det mogleg å få baneprediksjonen til å konvergere mot vurderte destinasjonar. Ved bruk av historisk data frå eit automatisk identifikasjons system (AIS), blir det demonstrert at metoden yter betre enn den nåverande forskningsfronten på emnet, med tanke på destinasjonsinferens og kvaliteten på skipsprediksjonane. Avhandlinga har bidratt til framgang på forskninga innan robuste system for kollisjonsunngåing, for både situasjonsforståing- og beslutningstakingsaspektet på feltet. Det finst derimot framleis betydelege utfordringar å løyse. Korleis ein skal justere parametrane for slike system, som for eksempel PSB-MPC-algoritmen, med alle involverte modular til bruk i eit stort spekter av situasjonar med forskjellig geografi og konfigurasjonar av dynamiske hindringar, er ikkje trivielt. Det vil her vere viktig å utforske moglege metodar for å gjere slike system adaptive og i stand til å lære frå erfaring, for å kunne ta dei i bruk på maritime fartøy.