{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:01:43Z","timestamp":1777716103918,"version":"3.51.4"},"reference-count":32,"publisher":"SAGE Publications","issue":"9","license":[{"start":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T00:00:00Z","timestamp":1704844800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:p>\n                    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\u2014for example\u2014reduce 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\u2014under reasonable assumptions\u2014we can use a Dijkstra-like approach to solve this stochastic problem, and benefit from its efficient\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>n<\/jats:italic>\n                    ) running time. This enables an autonomous vehicle to exhibit lane-selection behavior as it efficiently plans an optimal route to its destination.\n                  <\/jats:p>","DOI":"10.1177\/02783649231225474","type":"journal-article","created":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T04:23:56Z","timestamp":1704860636000},"page":"1425-1440","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["Lane-level route planning for autonomous vehicles"],"prefix":"10.1177","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2971-398X","authenticated-orcid":false,"given":"Mitchell","family":"Jones","sequence":"first","affiliation":[{"name":"Nuro, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maximilian","family":"Haas-Heger","sequence":"additional","affiliation":[{"name":"Nuro, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jur","family":"van den Berg","sequence":"additional","affiliation":[{"name":"Nuro, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2024,1,10]]},"reference":[{"key":"e_1_3_5_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSCI.2017.22"},{"key":"e_1_3_5_3_1","first-page":"1001","volume-title":"Generalized Prioritized Sweeping NIPS","author":"Andre D","year":"1997","unstructured":"Andre D, Friedman N, Parr R (1997) Generalized Prioritized Sweeping NIPS. Cambridge, MA: The MIT Press, 1001\u20131007."},{"key":"e_1_3_5_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113816"},{"issue":"102","key":"e_1_3_5_5_1","first-page":"1","article-title":"Ai-toolbox: a c++ library for reinforcement learning and planning (with python bindings)","volume":"21","author":"Bargiacchi E","year":"2020","unstructured":"Bargiacchi E, Roijers DM, Now\u00e9 A (2020) Ai-toolbox: a c++ library for reinforcement learning and planning (with python bindings). Journal of Machine Learning Research 21(102): 1\u201312. https:\/\/jmlr.org\/papers\/v21\/18-402.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_5_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"e_1_3_5_7_1","volume-title":"Dynamic Programming and Optimal Control: Volume II","author":"Bertsekas D","year":"2012","unstructured":"Bertsekas D (2012) Dynamic Programming and Optimal Control: Volume II. Nashua, NH: Athena Scientific."},{"key":"e_1_3_5_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.16.3.580"},{"key":"e_1_3_5_9_1","first-page":"12","article-title":"Labeled RTDP: improving the convergence of real-time dynamic programming","volume":"3","author":"Bonet B","year":"2003","unstructured":"Bonet B, Geffner H (2003) Labeled RTDP: improving the convergence of real-time dynamic programming. ICAPS 3: 12\u201321.","journal-title":"ICAPS"},{"key":"e_1_3_5_10_1","volume-title":"Autonomous Vehicle Routing at RideOS","author":"Chen B","year":"2018","unstructured":"Chen B (2018) Autonomous Vehicle Routing at RideOS. https:\/\/Medium.Com."},{"key":"e_1_3_5_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936531"},{"key":"e_1_3_5_12_1","volume-title":"Introduction to Algorithms","author":"Cormen TH","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, et al. (2009) Introduction to Algorithms. 3rd edition. Cambridge, MA: MIT Press.","edition":"3"},{"key":"e_1_3_5_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3830"},{"key":"e_1_3_5_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"e_1_3_5_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2004.07.028"},{"key":"e_1_3_5_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.02.001"},{"key":"e_1_3_5_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48113-3_22"},{"key":"e_1_3_5_18_1","first-page":"156","volume-title":"Symposium on Discrete Algorithms (SODA)","author":"Goldberg AV","year":"2005","unstructured":"Goldberg AV, Harrelson C (2005) Computing the shortest path: A* search meets graph theory. Symposium on Discrete Algorithms (SODA). New Delhi: SIAM, 156\u2013165. https:\/\/dl.acm.org\/citation.cfm?id=1070432.1070455."},{"key":"e_1_3_5_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.10.052"},{"key":"e_1_3_5_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00106-0"},{"key":"e_1_3_5_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_5_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eng.2018.11.032"},{"key":"e_1_3_5_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"e_1_3_5_24_1","first-page":"151","volume-title":"Fast Exact Planning in Markov Decision Processes","author":"McMahan HB","year":"2005","unstructured":"McMahan HB, Gordon GJ (2005) Fast Exact Planning in Markov Decision Processes. Washington, DC: AAAI, 151\u2013160."},{"key":"e_1_3_5_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIV.2016.2578706"},{"key":"e_1_3_5_26_1","volume-title":"Autonomous Robots","author":"Rossi F","year":"2018","unstructured":"Rossi F, Zhang R, Hindy Y, et al. (2018) Routing autonomous vehicles in congested transportation networks: structural properties and coordination algorithms. Autonomous Robots. Berlin, Germany: Springer."},{"key":"e_1_3_5_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.4.1591"},{"key":"e_1_3_5_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.412624"},{"key":"e_1_3_5_29_1","first-page":"199","article-title":"Methods and systems for determination of a routing policy for an autonomous vehicle","volume":"11","author":"van den Berg J","year":"2021","unstructured":"van den Berg J (2021) Methods and systems for determination of a routing policy for an autonomous vehicle. US Patent 11: 199.","journal-title":"US Patent"},{"key":"e_1_3_5_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0321"},{"key":"e_1_3_5_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095032"},{"key":"e_1_3_5_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/01691864.2012.729559"},{"key":"e_1_3_5_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC48978.2021.9564444"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231225474","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649231225474","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231225474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:21Z","timestamp":1777457841000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649231225474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,10]]},"references-count":32,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10.1177\/02783649231225474"],"URL":"https:\/\/doi.org\/10.1177\/02783649231225474","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,10]]}}}