Conflict detection and resolution for autonomous vehicles
Date
2010-03
Authors
Van Daalen, Corne Edwin
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : University of Stellenbosch
Abstract
ENGLISH ABSTRACT: Autonomous vehicles have recently received much attention from researchers. The prospect of
safe and reliable autonomous vehicles for general, unregulated environments promises several
advantages over human-controlled vehicles, including increased efficiency, reliability and capability
with the associated decrease in danger to humans and reduction in operating costs. A
critical requirement for the safe operation of fully autonomous vehicles is their ability to avoid
collisions with obstacles and other vehicles. In addition, they are often required to maintain a
minimum separation from obstacles and other vehicles, which is called conflict avoidance. The
research presented in thesis focuses on methods for effective conflict avoidance.
Existing conflict avoidance methods either make limiting assumptions or cannot execute in
real-time due to computational complexity. This thesis proposes methods for real-time conflict
avoidance in uncertain, cluttered and dynamic environments. These methods fall into the
category of non-cooperative conflict avoidance. They allow very general vehicle and environment
models, with the only notable assumption being that the position and velocity states of the
vehicle and obstacles have a jointly Gaussian probability distribution.
Conflict avoidance for fully autonomous vehicles consists of three functions, namely modelling
and identification of the environment, conflict detection and conflict resolution. We
present an architecture for such a system that ensures stable operation.
The first part of this thesis comprises the development of a novel and efficient probabilistic
conflict detection method. This method processes the predicted vehicle and environment states
to compute the probability of conflict for the prediction period. During the method derivation,
we introduce the concept of the flow of probability through the boundary of the conflict region,
which enables us to significantly reduce the complexity of the problem. The method also assumes
Gaussian distributed states and defines a tight upper bound to the conflict probability, both
of which further reduce the problem complexity, and then uses adaptive numerical integration
for efficient evaluation. We present the results of two simulation examples which show that the
proposed method can calculate in real-time the probability of conflict for complex and cluttered
environments and complex vehicle maneuvers, offering a significant improvement over existing
methods.
The second part of this thesis adapts existing kinodynamic motion planning algorithms
for conflict resolution in uncertain, dynamic and cluttered environments. We use probabilistic
roadmap methods and suggest three changes to them, namely using probabilistic conflict detection
methods, sampling the state-time space instead of the state space and batch generation of
samples. In addition, we propose a robust and adaptive way to choose the size of the sampling
space using a maximum least connection cost bound. We then put all these changes together in
a proposed motion planner for conflict resolution. We present the results of two simulation examples
which show that the proposed motion planner can only find a feasible path in real-time
for simple and uncluttered environments. However, the manner in which we handle uncertainty
and the sampling space bounds offer significant contributions to the conflict resolution field
AFRIKAANSE OPSOMMING: Outonome voertuie het die afgelope tyd heelwat aandag van navorsers geniet. Die vooruitsig van veilige en betroubare outonome voertuie vir algemene en ongereguleerde omgewings beloof verskeie voordele bo menslik-beheerde voertuie en sluit hoër effektiwiteit, betroubaarheid en vermoëns asook die gepaardgaande veiligheid vir mense en laer bedryfskoste in. ’n Belangrike vereiste vir die veilige bedryf van volledig outonome voertuie is hul vermoë om botsings met hindernisse en ander voertuie te vermy. Daar word ook dikwels van hulle vereis om ’n minimum skeidingsafstand tussen hulle en die hindernisse of ander voertuie te handhaaf – dit word konflikvermyding genoem. Die navorsing in hierdie tesis fokus op metodes vir effektiewe konflikvermyding. Bestaande konflikvermydingsmetodes maak óf beperkende aannames óf voer te stadig uit as gevolg van bewerkingskompleksiteit. Hierdie tesis stel metodes voor vir intydse konflikvermyding in onsekere en dinamiese omgewings wat ook baie hindernisse bevat. Die voorgestelde metodes val in die klas van nie-samewerkende konflikvermydingsmetodes. Hulle kan algemene voertuig- en omgewingsmodelle hanteer en hul enigste noemenswaardige aanname is dat die posisie- en snelheidstoestande van die voertuig en hindernisse Gaussiese waarskynliksheidverspreidings toon. Konflikvermyding vir volledig outonome voertuie bestaan uit drie stappe, naamlik modellering en identifikasie van die omgewing, konflikdeteksie en konflikresolusie. Ons bied ’n argitektuur vir so ’n stelsel aan wat stabiele werking verseker. Die eerste deel van die tesis beskryf die ontwikkeling van ’n oorspronklike en doeltreffende metode vir waarskynliksheid-konflikdeteksie. Die metode gebruik die voorspelde toestande van die voertuig en omgewing en bereken die waarskynlikheid van konflik vir die betrokke voorspellingsperiode. In die afleiding van die metode definiëer ons die konsep van waarskynliksheidvloei oor die grens van die konflikdomein. Dit stel ons in staat om die kompleksiteit van die probleem beduidend te verminder. Die metode aanvaar ook Gaussiese waarskynlikheidsverspreiding van toestande en definiëer ’n nou bogrens tot die waarskynlikheid van konflik om die kompleksiteit van die probleem verder te verminder. Laastens gebruik die metode aanpasbare integrasiemetodes vir vinnige berekening van die waarskynlikheid van konflik. Die eerste deel van die tesis sluit af met twee simulasies wat aantoon dat die voorgestelde konflikdeteksiemetode in staat is om die waarskynlikheid van konflik intyds te bereken, selfs vir komplekse omgewings en voertuigbewegings. Die metode lewer dus ’n beduidende bydrae tot die veld van konflikdeteksie. Die tweede deel van die tesis pas bestaande kinodinamiese beplanningsalgoritmes aan vir konflikresolusie in komplekse omgewings. Ons stel drie veranderings voor, naamlik die gebruik van waarskynliksheid-konflikdeteksiemetodes, die byvoeg van ’n tyd-dimensie in die monsterruimte en die generasie van meervoudige monsters. Ons stel ook ’n robuuste en aanpasbare manier voor om die grootte van die monsterruimte te kies. Al die voorafgaande voorstelle word saamgevoeg in ’n beplanner vir konflikresolusie. Die tweede deel van die tesis sluit af met twee simulasies wat aantoon dat die voorgestelde beplanner slegs intyds ’n oplossing kan vind vir eenvoudige omgewings. Die manier hoe die beplanner onsekerheid hanteer en die begrensing van die monsterruimte lewer egter waardevolle bydraes tot die veld van konflikresolusie
AFRIKAANSE OPSOMMING: Outonome voertuie het die afgelope tyd heelwat aandag van navorsers geniet. Die vooruitsig van veilige en betroubare outonome voertuie vir algemene en ongereguleerde omgewings beloof verskeie voordele bo menslik-beheerde voertuie en sluit hoër effektiwiteit, betroubaarheid en vermoëns asook die gepaardgaande veiligheid vir mense en laer bedryfskoste in. ’n Belangrike vereiste vir die veilige bedryf van volledig outonome voertuie is hul vermoë om botsings met hindernisse en ander voertuie te vermy. Daar word ook dikwels van hulle vereis om ’n minimum skeidingsafstand tussen hulle en die hindernisse of ander voertuie te handhaaf – dit word konflikvermyding genoem. Die navorsing in hierdie tesis fokus op metodes vir effektiewe konflikvermyding. Bestaande konflikvermydingsmetodes maak óf beperkende aannames óf voer te stadig uit as gevolg van bewerkingskompleksiteit. Hierdie tesis stel metodes voor vir intydse konflikvermyding in onsekere en dinamiese omgewings wat ook baie hindernisse bevat. Die voorgestelde metodes val in die klas van nie-samewerkende konflikvermydingsmetodes. Hulle kan algemene voertuig- en omgewingsmodelle hanteer en hul enigste noemenswaardige aanname is dat die posisie- en snelheidstoestande van die voertuig en hindernisse Gaussiese waarskynliksheidverspreidings toon. Konflikvermyding vir volledig outonome voertuie bestaan uit drie stappe, naamlik modellering en identifikasie van die omgewing, konflikdeteksie en konflikresolusie. Ons bied ’n argitektuur vir so ’n stelsel aan wat stabiele werking verseker. Die eerste deel van die tesis beskryf die ontwikkeling van ’n oorspronklike en doeltreffende metode vir waarskynliksheid-konflikdeteksie. Die metode gebruik die voorspelde toestande van die voertuig en omgewing en bereken die waarskynlikheid van konflik vir die betrokke voorspellingsperiode. In die afleiding van die metode definiëer ons die konsep van waarskynliksheidvloei oor die grens van die konflikdomein. Dit stel ons in staat om die kompleksiteit van die probleem beduidend te verminder. Die metode aanvaar ook Gaussiese waarskynlikheidsverspreiding van toestande en definiëer ’n nou bogrens tot die waarskynlikheid van konflik om die kompleksiteit van die probleem verder te verminder. Laastens gebruik die metode aanpasbare integrasiemetodes vir vinnige berekening van die waarskynlikheid van konflik. Die eerste deel van die tesis sluit af met twee simulasies wat aantoon dat die voorgestelde konflikdeteksiemetode in staat is om die waarskynlikheid van konflik intyds te bereken, selfs vir komplekse omgewings en voertuigbewegings. Die metode lewer dus ’n beduidende bydrae tot die veld van konflikdeteksie. Die tweede deel van die tesis pas bestaande kinodinamiese beplanningsalgoritmes aan vir konflikresolusie in komplekse omgewings. Ons stel drie veranderings voor, naamlik die gebruik van waarskynliksheid-konflikdeteksiemetodes, die byvoeg van ’n tyd-dimensie in die monsterruimte en die generasie van meervoudige monsters. Ons stel ook ’n robuuste en aanpasbare manier voor om die grootte van die monsterruimte te kies. Al die voorafgaande voorstelle word saamgevoeg in ’n beplanner vir konflikresolusie. Die tweede deel van die tesis sluit af met twee simulasies wat aantoon dat die voorgestelde beplanner slegs intyds ’n oplossing kan vind vir eenvoudige omgewings. Die manier hoe die beplanner onsekerheid hanteer en die begrensing van die monsterruimte lewer egter waardevolle bydraes tot die veld van konflikresolusie
Description
Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2010.
Keywords
Autonomous vehicles, Conflict avoidance, Probability flow, Gaussian distribution, Dissertations -- Electronic engineering, Theses -- Electronic engineering, Vehicles, Remotely piloted, Vehicles, Remotely piloted -- Control