Collision Avoidance using the Velocity Obstacle Algorithm for Underactuated Surface Vehicles

Abstract

Denne masteravhandlingen presenterer en matematisk analyse av hastighet hindring algoritmen (eng. the velocity obstacle algorithm) for kollisjonsunngåelse i det horisontale planet. Algoritmen, som er hyppig brukt for reaktiv kollisjonsunngåelse, er basert på å regne ut samtlige hastighetsvektorer fartøyet kan inneha, som ved et ubestemt tidspunkt i fremtiden, fører til en kollisjon mellom fartøyet og en hindring. Ved å alltid unngå disse hastighetene unngår derav fartøyet en kollisjon med den spesifikke hindringen. En ulempe ved tidligere analyser av algoritmen er at fartøyet og hindringen er begrenset til å følge rette linjer, eller at hastighetene er antatt konstante. I tillegg tar få i betraktning dynamikken til fartøyet, som i kollisjonssituasjoner kan være avgjørende. I denne avhandlingen undersøker vi algoritmen uten slike begrensinger. Vi gir betingelser for at et ikke-holonomt fartøy unngår kollisjon med en hindring som beveger seg med tidsvarierende hastighet. Videre utvider vi analysen til å garantere kollisjonsunngåelse for et underaktuert fartøy, det vil si et fartøy som ikke kan styre en eller flere av sine frihetsgrader direkte. Vi kombinerer kollisjonsunngåelse med føring av fartøyet mot et ønsket mål eller en sti. Numeriske simuleringer er inkludert for å validere de teoretiske resultatene.

This thesis presents a mathematical analysis of the velocity obstacle algorithm for collision avoidance of a moving obstacle in the plane. The velocity obstacle algorithm can be used for local navigation among dynamic obstacles by continually computing a set of unsafe velocities, and avoid the velocities inside this set. The method is commonly used for reactive collision avoidance as it requires only limited knowledge of the obstacle behaviour and is computationally inexpensive. A drawback of the previous analyses of the algorithm is the assumption that the vehicle and the obstacle are constrained to follow specific types of paths or that the velocities are assumed constant. Additionally, few consider the vehicle's dynamics when applying the algorithm, which in collision avoidance scenarios can be fatal if unaccounted for. In this thesis, we analyze the algorithm without these limitations. We provide conditions ensuring that a nonholonomic vehicle avoids a collision with an obstacle capable of both turning and accelerating towards the vehicle at any given moment in time. We extend the analysis to provide conditions under which safety is ensured for an underactuated vehicle, i.e. a vehicle unable to produce control forces in one or more of its degrees of freedom, in the presence of a moving obstacle. The theoretical proofs of collision avoidance are combined with proofs of target reaching and path following, and supported by numerical simulations.