Probabilistic conflict prediction: an accurate and computationally efficient approach
Date
2023-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Collision (or conflict) prediction is a vital component of motion planning for autonomous vehicles to ensure safe operation, both in the context of autonomous navigation and in the context of an advisory system for manned vehicles. Prediction methods must be accurate to know whether motion planning corrections are required. However, computationally efficient prediction methods are Essential in order to ensure that motion planning corrections are brought about in a timely manner. Efficient prediction methods are especially crucial when testing large sets of candidate trajectories for conflict, given the accumulation of computational cost for each candidate. This dissertation presents a probabilistic conflict prediction method that demonstrates the same accuracy as existing methods, but at a significantly reduced computational cost. This is achieved by a novel reformulation of the conflict prediction problem in terms of the first-passage time using a dimension-reduction transform. First-passage time distributions are analytically derived for a subset of Gaussian motion models which describe vehicle motion. The proposed method is applicable for stochastic processes where the vehicle mean motion can be approximated by linear segments, and the conflict boundary is modelled as – or approximated by – either piece-wise straight lines in 2-D, or neighbouring planes in 3-D. The proposed method was tested in simulation and compared to state-of-the-art conflict prediction methods. These comparison methods consist of two probability flow methods, as well as an instantaneous conflict probability method. The results demonstrate a significant decrease of computation time.
AFRIKAANSE OPSOMMING: Botsingsvoorspelling (of konflikvoorspelling) is ’n belangrike komponent van padbeplanning vir outonome voertuie om veiligheid te verseker, beide in die konteks van outonome navigasie en in die konteks van ’n advieseringsstelsel vir bemandevoertuie. Voorspellingsmetodes moet akkuraat wees om te bepaal of bewegingsbeplanning-regstellings nodig is. Rekenkundig effektiewe (computationally efficient) voorspellingsmetodes is egter noodsaaklik om te verseker dat bewegingsbeplanning regstellings betyds teweeggebring word. Effektiewe voorspellingsmetodes is van kardinale belang wanneer groot stelle kandidaatpaaie getoets word vir konflik, gegee die opgaring van berekenings tyd vir elke kandidaat. Hierdie proefskrif bied ’n voorspellingsmetode aan wat dieselfde akkuraatheid as bestaande metodes vertoon, maar teen ’n noemenswaardige verlaagde berekeningskoste. Die verbetering word bereik deur ’n nuwe herformulering van die konflikvoorspellingsprobleem in terme van die eerste-gang tydverspreiding (first-passage time distribution) deur gebruik te maak van ’n dimensie-reduksie transform. Eerste-gang tydverspreiding word analities afgelei vir ’n substel van Gaussiese bewegingsmodelle wat voertuigbeweging beskryf. Die voorgestelde metode is van toepassing op stogastiese prosesse waar die gemiddelde beweging benader kan word deur lineêre segmente, en die konflikgrens word gemodelleer as – of kan benader word as – óf stuksgewyse reguitlyne in 2-D, óf naburige vlakke in 3-D. Die voorgestelde metode is in simulasie getoets en vergelyk met bestaande (gestigde) konflikvoorspellingsmetodes. Die set methodes bestaan uit twee waarskynlikheidsvloei metodes, sowel as ’n oombliklike onflikwaarskynlikheids metode. Die resultate toon ’n beduidende afname in berekeningstyd.
AFRIKAANSE OPSOMMING: Botsingsvoorspelling (of konflikvoorspelling) is ’n belangrike komponent van padbeplanning vir outonome voertuie om veiligheid te verseker, beide in die konteks van outonome navigasie en in die konteks van ’n advieseringsstelsel vir bemandevoertuie. Voorspellingsmetodes moet akkuraat wees om te bepaal of bewegingsbeplanning-regstellings nodig is. Rekenkundig effektiewe (computationally efficient) voorspellingsmetodes is egter noodsaaklik om te verseker dat bewegingsbeplanning regstellings betyds teweeggebring word. Effektiewe voorspellingsmetodes is van kardinale belang wanneer groot stelle kandidaatpaaie getoets word vir konflik, gegee die opgaring van berekenings tyd vir elke kandidaat. Hierdie proefskrif bied ’n voorspellingsmetode aan wat dieselfde akkuraatheid as bestaande metodes vertoon, maar teen ’n noemenswaardige verlaagde berekeningskoste. Die verbetering word bereik deur ’n nuwe herformulering van die konflikvoorspellingsprobleem in terme van die eerste-gang tydverspreiding (first-passage time distribution) deur gebruik te maak van ’n dimensie-reduksie transform. Eerste-gang tydverspreiding word analities afgelei vir ’n substel van Gaussiese bewegingsmodelle wat voertuigbeweging beskryf. Die voorgestelde metode is van toepassing op stogastiese prosesse waar die gemiddelde beweging benader kan word deur lineêre segmente, en die konflikgrens word gemodelleer as – of kan benader word as – óf stuksgewyse reguitlyne in 2-D, óf naburige vlakke in 3-D. Die voorgestelde metode is in simulasie getoets en vergelyk met bestaande (gestigde) konflikvoorspellingsmetodes. Die set methodes bestaan uit twee waarskynlikheidsvloei metodes, sowel as ’n oombliklike onflikwaarskynlikheids metode. Die resultate toon ’n beduidende afname in berekeningstyd.
Description
Thesis (PhD)--Stellenbosch University, 2023.