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].)


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Lane-Level Route Planning for Autonomous Vehicles


    Weitere Titelangaben:

    Springer Proceedings in Advanced Robotics


    Beteiligte:
    LaValle, Steven M. (Herausgeber:in) / O’Kane, Jason M. (Herausgeber:in) / Otte, Michael (Herausgeber:in) / Sadigh, Dorsa (Herausgeber:in) / Tokekar, Pratap (Herausgeber:in) / Jones, Mitchell (Autor:in) / Haas-Heger, Maximilian (Autor:in) / van den Berg, Jur (Autor:in)

    Kongress:

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



    Erscheinungsdatum :

    2022-12-15


    Format / Umfang :

    16 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    LANE-LEVEL ROUTE PLANNER FOR AUTONOMOUS VEHICLES

    WRAY KYLE HOLLINS / WITWICKI STEFAN / ZILBERSTEIN SHLOMO | Europäisches Patentamt | 2022

    Freier Zugriff

    LANE-LEVEL ROUTE PLANNER FOR AUTONOMOUS VEHICLES

    WRAY KYLE HOLLINS / WITWICKI STEFAN / ZILBERSTEIN SHLOMO | Europäisches Patentamt | 2024

    Freier Zugriff

    Navigation route planning method for autonomous vehicles

    YU NING / ZHU FAN | Europäisches Patentamt | 2024

    Freier Zugriff

    NAVIGATION ROUTE PLANNING METHOD FOR AUTONOMOUS VEHICLES

    YU NING / ZHU FAN | Europäisches Patentamt | 2022

    Freier Zugriff

    ROUTING AUTONOMOUS VEHICLES BASED ON LANE-LEVEL PERFORMANCE

    RIZK SARAH / GARCIA ZACHARY WRIGHT / XIE CHEN et al. | Europäisches Patentamt | 2021

    Freier Zugriff