We present an algorithm that, given a representation of a road network in lane-level detail, computes a route that minimizes the expected cost to reach a given destination. In doing so, our algorithm allows us to solve for the complex trade-offs encountered when trying to decide not just which roads to follow, but also when to change between the lanes making up these roads, in order to—for example—reduce the likelihood of missing a left exit while not unnecessarily driving in the leftmost lane. This routing problem can naturally be formulated as a Markov Decision Process (MDP), in which lane change actions have stochastic outcomes. However, MDPs are known to be time-consuming to solve in general. In this paper, we show that—under reasonable assumptions—we can use a Dijkstra-like approach to solve this stochastic problem, and benefit from its efficient O ( n log n ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \log n)$$\end{document} running time. This enables an autonomous vehicle to exhibit natural lane-selection behavior as it efficiently plans an optimal route to its destination. 1 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$^{1}$$\end{document}( 1 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$^{1}$$\end{document}The contents of this paper are covered by US Patent 11,199,841 [5].)


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Lane-Level Route Planning for Autonomous Vehicles


    Additional title:

    Springer Proceedings in Advanced Robotics



    Conference:

    International Workshop on the Algorithmic Foundations of Robotics ; 2022 ; , MD, USA June 22, 2022 - June 24, 2022



    Publication date :

    2022-12-15


    Size :

    16 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English




    LANE-LEVEL ROUTE PLANNER FOR AUTONOMOUS VEHICLES

    WRAY KYLE HOLLINS / WITWICKI STEFAN / ZILBERSTEIN SHLOMO | European Patent Office | 2022

    Free access

    LANE-LEVEL ROUTE PLANNER FOR AUTONOMOUS VEHICLES

    WRAY KYLE HOLLINS / WITWICKI STEFAN / ZILBERSTEIN SHLOMO | European Patent Office | 2024

    Free access

    Navigation route planning method for autonomous vehicles

    YU NING / ZHU FAN | European Patent Office | 2024

    Free access

    NAVIGATION ROUTE PLANNING METHOD FOR AUTONOMOUS VEHICLES

    YU NING / ZHU FAN | European Patent Office | 2022

    Free access

    ROUTING AUTONOMOUS VEHICLES BASED ON LANE-LEVEL PERFORMANCE

    RIZK SARAH / GARCIA ZACHARY WRIGHT / XIE CHEN et al. | European Patent Office | 2021

    Free access