Conflict detection and resolution for autonomous vehicles

Van Daalen, Corne Edwin (Stellenbosch : University of Stellenbosch, 2010-03)

Thesis

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

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/3994
This item appears in the following collections: