Optimised path planning and path tracking for autonomous vehicles with constrained kinematics in ROS
Date
2020-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: A significant growth of interest in the pursuit of autonomous vehicles from various stakeholders has been witnessed recently. This indicates that future transportation systems will be autonomous.
By the nature of the transportation problem, a transportation system is favourable if it is fast,
safe and reliable. Therefore, if autonomous vehicles are to offer a genuinely superior alternative to present-day transportation systems, it is imperative that they do better than present-day transport in all these criteria.
This thesis focusses on two submodules of a typical autonomous navigation system that play a critical role in the fulfilment of these criteria. These submodules are path planning and path tracking. Path planning generates safe and optimal paths that result in reaching destinations safely and in minimal time. A path planner should also generate a plan quickly, otherwise delays
are incurred. Path tracking is concerned with the accurate following of planned paths so that no collisions result. For a path tracker to accurately follow a planned path, it is necessary that the path be feasible for the target vehicle, otherwise both the path-planning and path-tracking efforts are in vain, as the vehicle will certainly deviate from the path and run the risk of collision.
Path-planning algorithms exist that plan paths quickly and efficiently. Such path planners have, however, been proven to be almost-surely suboptimal. At the other end of the spectrum, path-planning algorithms exist that are guaranteed to find optimal paths. However, their optimality guarantee hinges on the number of planning iterations approaching infinity – in technical terms
they are said to be asymptotically optimal, with the practical implication being that they may run
for unbearably long periods.
This thesis investigates the application of path optimisation to accelerate the rate of convergence
of path-planning algorithms towards the optimal solution. The thesis first selects and develops suitable path-planning and path-optimisation algorithms to be used for the investigation. To ensure that the paths generated can be accurately executed by targeted vehicles, the developed path planners and path optimisers are adapted to incorporate motion constraints. The path
optimisers are then incorporated into the various path planners with the aim of accelerating the
rate of convergence and the effectiveness of each path optimiser in accelerating the convergence of
each path planner is analysed. Of interest in this investigation is to ascertain if the application
of path optimisation to accelerate the rate of convergence of the path planners helps a quick and efficient, though almost-surely suboptimal, path planner attain comparable or better performance than that of an asymptotically optimal path planner. Results obtained from the experiments indicate the affirmative.
Without demonstrating that the planned paths are indeed executable, the practical value of the developed optimised path-planning algorithms would be unclear. A path tracker has therefore been developed that accurately tracks planned paths in the absence of disturbances, and is able to correct for deviations when disturbances are encountered.
AFRIKAANSE OPSOMMING: ’n Beduidende toename in belangstelling in die ontwikkeling van outonome voertuie deur verskeie rolspelers is onlangs waargeneem. Dit dui aan dat vervoerstelsels in die toekoms outonoom gaan wees. Uit die aard van die vervoerprobleem is ’n vervoerstelsel goed as dit vinnig, veilig en betroubaar is. Dus, vir outonome voertuie om regtig ’n beter alternatief vir hedendaagse vervoerstelsels te bied is dit nodig dat hulle beter as die hedendaagse vervoerstelsels werk vir al hierdie kriteria. Hierdie tesis fokus op twee submodules van ’n tipiese outonome navigasiestelsel wat ’n kritiese rol speel om aan hierdie kriteria te voldoen. Hierdie submodules is padbeplanning en padvolging. Padbeplanning produseer veilige en optimale paaie wat daartoe lei dat bestemmings veilig en in ’n minimale tyd bereik word. ’n Padbeplanner moet ook paaie vinnig bereken, anders word vertragings veroorsaak. Padvolging het te doen met die akkurate volging van beplande paaie sodat geen botsings plaasvind nie. Vir ’n padvolger om ’n beplande pad akkuraat te volg, is dit nodig dat die pad uitvoerbaar is vir die voertuig, anders is die moeite van beide die padbeplanner en padvolger nutteloos, aangesien die voertuig sekerlik sal afwyk van die pad en moontlik botsings sal ervaar. Daar bestaan padbeplanning-algoritmes wat paaie vinnig en effektief beplan. Dit is egter bewys dat hierdie padbeplanners amper-seker suboptimaal is. Aan die ander kant van die spektrum bestaan daar padbeplanning-algoritmes wat gewaarborg is om optimale paaie te vind. Hul optimaliteit-waarborg hang egter af daarvan dat die hoeveelheid beplannings-iterasies na oneindig streef – in tegniese terme word daar gesê dat hulle asimptoties optimaal is, met die praktiese gevolg dat hulle onaanvaarbare lang periodes kan neem om uit te voer. Hierdie tesis ondersoek die toepassing van pad-optimeerders om die tempo van konvergensie van padbeplanning-algoritmes na die optimale oplossing te verhaas. Die tesis kies en ontwikkel eers toepaslike padbeplanning- en pad-optimering-algoritmes om te gebruik in die ondersoek. Om te verseker dat die paaie wat geproduseer word akkuraat uitgevoer kan word deur toepaslike voertuie, word die ontwikkelde padbeplanners en pad-optimeerders aangepas om bewegingsbeperkings in ag te neem. Die pad-optimeerders word dan saamgevoeg met die onderskeie padbeplanners met die doel om die tempo van konvergensie te verhaas, en die effektiwiteit van elke pad-optimeerder om die konvergensie van elke padbeplanner te verhaas word geanaliseer. ’n Doelwit van hierdie ondersoek is om te bepaal of die toepassing van pad-optimering om die tempo van konvergensie van die padbeplanners te verhaas daartoe lei dat ’n vinnige en effektiewe dog amper-seker suboptimale beplanner vergelykbare of beter resultate kan behaal as die van ’n asimptotiese optimale beplanner. Resultate van eksperimente dui aan dat dit wel die geval is. Sonder om te demonstreer dat die beplande paaie inderdaad uitvoerbaar is, is die praktiese nut van die ontwikkelde geoptimeerde padbeplanning-algoritmes onseker. ’n Padvolger is dus ontwikkel wat beplande paaie akkuraat volg in die afwesigheid van steurseine, en dit is ook in staat om afwykings te korrigeer wanneer steurseine ondervind word.
AFRIKAANSE OPSOMMING: ’n Beduidende toename in belangstelling in die ontwikkeling van outonome voertuie deur verskeie rolspelers is onlangs waargeneem. Dit dui aan dat vervoerstelsels in die toekoms outonoom gaan wees. Uit die aard van die vervoerprobleem is ’n vervoerstelsel goed as dit vinnig, veilig en betroubaar is. Dus, vir outonome voertuie om regtig ’n beter alternatief vir hedendaagse vervoerstelsels te bied is dit nodig dat hulle beter as die hedendaagse vervoerstelsels werk vir al hierdie kriteria. Hierdie tesis fokus op twee submodules van ’n tipiese outonome navigasiestelsel wat ’n kritiese rol speel om aan hierdie kriteria te voldoen. Hierdie submodules is padbeplanning en padvolging. Padbeplanning produseer veilige en optimale paaie wat daartoe lei dat bestemmings veilig en in ’n minimale tyd bereik word. ’n Padbeplanner moet ook paaie vinnig bereken, anders word vertragings veroorsaak. Padvolging het te doen met die akkurate volging van beplande paaie sodat geen botsings plaasvind nie. Vir ’n padvolger om ’n beplande pad akkuraat te volg, is dit nodig dat die pad uitvoerbaar is vir die voertuig, anders is die moeite van beide die padbeplanner en padvolger nutteloos, aangesien die voertuig sekerlik sal afwyk van die pad en moontlik botsings sal ervaar. Daar bestaan padbeplanning-algoritmes wat paaie vinnig en effektief beplan. Dit is egter bewys dat hierdie padbeplanners amper-seker suboptimaal is. Aan die ander kant van die spektrum bestaan daar padbeplanning-algoritmes wat gewaarborg is om optimale paaie te vind. Hul optimaliteit-waarborg hang egter af daarvan dat die hoeveelheid beplannings-iterasies na oneindig streef – in tegniese terme word daar gesê dat hulle asimptoties optimaal is, met die praktiese gevolg dat hulle onaanvaarbare lang periodes kan neem om uit te voer. Hierdie tesis ondersoek die toepassing van pad-optimeerders om die tempo van konvergensie van padbeplanning-algoritmes na die optimale oplossing te verhaas. Die tesis kies en ontwikkel eers toepaslike padbeplanning- en pad-optimering-algoritmes om te gebruik in die ondersoek. Om te verseker dat die paaie wat geproduseer word akkuraat uitgevoer kan word deur toepaslike voertuie, word die ontwikkelde padbeplanners en pad-optimeerders aangepas om bewegingsbeperkings in ag te neem. Die pad-optimeerders word dan saamgevoeg met die onderskeie padbeplanners met die doel om die tempo van konvergensie te verhaas, en die effektiwiteit van elke pad-optimeerder om die konvergensie van elke padbeplanner te verhaas word geanaliseer. ’n Doelwit van hierdie ondersoek is om te bepaal of die toepassing van pad-optimering om die tempo van konvergensie van die padbeplanners te verhaas daartoe lei dat ’n vinnige en effektiewe dog amper-seker suboptimale beplanner vergelykbare of beter resultate kan behaal as die van ’n asimptotiese optimale beplanner. Resultate van eksperimente dui aan dat dit wel die geval is. Sonder om te demonstreer dat die beplande paaie inderdaad uitvoerbaar is, is die praktiese nut van die ontwikkelde geoptimeerde padbeplanning-algoritmes onseker. ’n Padvolger is dus ontwikkel wat beplande paaie akkuraat volg in die afwesigheid van steurseine, en dit is ook in staat om afwykings te korrigeer wanneer steurseine ondervind word.
Description
Thesis (MEng)--Stellenbosch University, 2020.
Keywords
Motor vehicles -- Automatic control, Automated vehicles -- Safety measures, Automated vehicles -- Route choice, Path planning, Patch tracking, Kinematics, UCTD