Shortest path optimization under limited information
The problem of finding an optimal path in an uncertain graph arises in numerous applications, including network routing, path-planning for vehicles, and the control of finite-state systems. While techniques in robust and stochastic programming can be employed to compute, respectively, worst-case and...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/60275 https://orcid.org/0000-0002-1470-2148 |
| _version_ | 1826208968732573696 |
|---|---|
| author | Dahleh, Munther A. Rinehart, Michael David |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Dahleh, Munther A. Rinehart, Michael David |
| author_sort | Dahleh, Munther A. |
| collection | MIT |
| description | The problem of finding an optimal path in an uncertain graph arises in numerous applications, including network routing, path-planning for vehicles, and the control of finite-state systems. While techniques in robust and stochastic programming can be employed to compute, respectively, worst-case and average-optimal solutions to the shortest-path problem, we consider an alternative problem where the agent that traverses the graph can request limited information about the graph before choosing a path to traverse. In this paper, we define and quantify a notion of information that is compatible to this performance-based framework, bound the performance of the agent subject to a bound on the capacity of the information it can request, and present algorithms for optimizing information. |
| first_indexed | 2024-09-23T14:15:38Z |
| format | Article |
| id | mit-1721.1/60275 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:15:38Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/602752022-09-28T19:32:06Z Shortest path optimization under limited information Dahleh, Munther A. Rinehart, Michael David Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Dahleh, Munther A. Dahleh, Munther A. Rinehart, Michael David The problem of finding an optimal path in an uncertain graph arises in numerous applications, including network routing, path-planning for vehicles, and the control of finite-state systems. While techniques in robust and stochastic programming can be employed to compute, respectively, worst-case and average-optimal solutions to the shortest-path problem, we consider an alternative problem where the agent that traverses the graph can request limited information about the graph before choosing a path to traverse. In this paper, we define and quantify a notion of information that is compatible to this performance-based framework, bound the performance of the agent subject to a bound on the capacity of the information it can request, and present algorithms for optimizing information. 2010-12-10T21:07:51Z 2010-12-10T21:07:51Z 2010-01 2009-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-3871-6 0191-2216 INSPEC Accession Number: 11148793 http://hdl.handle.net/1721.1/60275 Rinehart, M., and M.A. Dahleh. “Shortest path optimization under limited information.” Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference on. 2009. 2064-2069. ©2010 IEEE. https://orcid.org/0000-0002-1470-2148 en_US http://dx.doi.org/10.1109/CDC.2009.5399666 Proceedings of the 48th IEEE Conference on Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Dahleh, Munther A. Rinehart, Michael David Shortest path optimization under limited information |
| title | Shortest path optimization under limited information |
| title_full | Shortest path optimization under limited information |
| title_fullStr | Shortest path optimization under limited information |
| title_full_unstemmed | Shortest path optimization under limited information |
| title_short | Shortest path optimization under limited information |
| title_sort | shortest path optimization under limited information |
| url | http://hdl.handle.net/1721.1/60275 https://orcid.org/0000-0002-1470-2148 |
| work_keys_str_mv | AT dahlehmunthera shortestpathoptimizationunderlimitedinformation AT rinehartmichaeldavid shortestpathoptimizationunderlimitedinformation |