Stochastic motion planning and applications to traffic
This paper presents a stochastic motion planning algorithm and its application to traffic navigation. The algorithm copes with the uncertainty of road traffic conditions by stochastic modeling of travel delay on road networks. The algorithm determines paths between two points that optimize a cost fu...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Book chapter |
| Language: | en_US |
| Published: |
Springer Berlin/Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72494 https://orcid.org/0000-0002-7470-3265 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0003-1709-4034 https://orcid.org/0000-0002-1455-9652 |
| _version_ | 1826218163993313280 |
|---|---|
| author | Lim, Sejoon Balakrishnan, Hari Gifford, David K. Madden, Samuel R. Rus, Daniela L. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Lim, Sejoon Balakrishnan, Hari Gifford, David K. Madden, Samuel R. Rus, Daniela L. |
| author_sort | Lim, Sejoon |
| collection | MIT |
| description | This paper presents a stochastic motion planning algorithm and its application to traffic navigation. The algorithm copes with the uncertainty of road traffic conditions by stochastic modeling of travel delay on road networks. The algorithm determines paths between two points that optimize a cost function of the delay probability distribution. It can be used to find paths that maximize the probability of reaching a destination within a particular travel deadline. For such problems, standard shortest-path algorithms don’t work because the optimal substructure property doesn’t hold. We evaluate our algorithm using both simulations and real-world drives, using delay data gathered from a set of taxis equipped with GPS sensors and a wireless network. Our algorithm can be integrated into on-board navigation systems as well as route-finding Web sites, providing drivers with good paths that meet their desired goals. |
| first_indexed | 2024-09-23T17:15:31Z |
| format | Book chapter |
| id | mit-1721.1/72494 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:15:31Z |
| publishDate | 2012 |
| publisher | Springer Berlin/Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/724942022-10-03T11:23:38Z Stochastic motion planning and applications to traffic Lim, Sejoon Balakrishnan, Hari Gifford, David K. Madden, Samuel R. Rus, Daniela L. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Balakrishnan, Hari Lim, Sejoon Balakrishnan, Hari Gifford, David K. Madden, Samuel R. Rus, Daniela L. This paper presents a stochastic motion planning algorithm and its application to traffic navigation. The algorithm copes with the uncertainty of road traffic conditions by stochastic modeling of travel delay on road networks. The algorithm determines paths between two points that optimize a cost function of the delay probability distribution. It can be used to find paths that maximize the probability of reaching a destination within a particular travel deadline. For such problems, standard shortest-path algorithms don’t work because the optimal substructure property doesn’t hold. We evaluate our algorithm using both simulations and real-world drives, using delay data gathered from a set of taxis equipped with GPS sensors and a wireless network. Our algorithm can be integrated into on-board navigation systems as well as route-finding Web sites, providing drivers with good paths that meet their desired goals. National Science Foundation (U.S.) (grant EFRI-0710252) National Science Foundation (U.S.) (grant IIS-0426838) 2012-08-31T18:41:59Z 2012-08-31T18:41:59Z 2009-12 Book chapter http://purl.org/eprint/type/ConferencePaper 978-3-642-00311-0 1610-7438 1610-742X http://hdl.handle.net/1721.1/72494 Lim, Sejoon et al. “Stochastic Motion Planning and Applications to Traffic.” Algorithmic Foundation of Robotics VIII. Ed. Gregory S. Chirikjian et al. Vol. 57. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 483-500. https://orcid.org/0000-0002-7470-3265 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0003-1709-4034 https://orcid.org/0000-0002-1455-9652 en_US http://dx.doi.org/10.1007/978-3-642-00312-7_30 Algorithmic Foundation of Robotics VIII Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin/Heidelberg MIT web domain |
| spellingShingle | Lim, Sejoon Balakrishnan, Hari Gifford, David K. Madden, Samuel R. Rus, Daniela L. Stochastic motion planning and applications to traffic |
| title | Stochastic motion planning and applications to traffic |
| title_full | Stochastic motion planning and applications to traffic |
| title_fullStr | Stochastic motion planning and applications to traffic |
| title_full_unstemmed | Stochastic motion planning and applications to traffic |
| title_short | Stochastic motion planning and applications to traffic |
| title_sort | stochastic motion planning and applications to traffic |
| url | http://hdl.handle.net/1721.1/72494 https://orcid.org/0000-0002-7470-3265 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0003-1709-4034 https://orcid.org/0000-0002-1455-9652 |
| work_keys_str_mv | AT limsejoon stochasticmotionplanningandapplicationstotraffic AT balakrishnanhari stochasticmotionplanningandapplicationstotraffic AT gifforddavidk stochasticmotionplanningandapplicationstotraffic AT maddensamuelr stochasticmotionplanningandapplicationstotraffic AT rusdanielal stochasticmotionplanningandapplicationstotraffic |