IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v66y2019i1p15-37.html
   My bibliography  Save this article

Robust shortest path planning and semicontractive dynamic programming

Author

Listed:
  • Dimitri P. Bertsekas

Abstract

In this article, we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit‐evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra‐like algorithm for problems with nonnegative arc lengths.© 2016 Wiley Periodicals, Inc. Naval Research Logistics 66:15–37, 2019

Suggested Citation

  • Dimitri P. Bertsekas, 2019. "Robust shortest path planning and semicontractive dynamic programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(1), pages 15-37, February.
    • Handle: RePEc:wly:navres:v:66:y:2019:i:1:p:15-37
    DOI: 10.1002/nav.21697
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21697
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21697?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. L. Grüne & O. Junge, 2008. "Global Optimal Control of Perturbed Systems," Journal of Optimization Theory and Applications, Springer, vol. 136(3), pages 411-429, March.
    2. Dimitri P. Bertsekas & John N. Tsitsiklis, 1991. "An Analysis of Stochastic Shortest Path Problems," Mathematics of Operations Research, INFORMS, vol. 16(3), pages 580-595, August.
    3. Dimitri P. Bertsekas & Huizhen Yu, 2012. "Q-Learning and Enhanced Policy Iteration in Discounted Dynamic Programming," Mathematics of Operations Research, INFORMS, vol. 37(1), pages 66-94, February.
    4. Huizhen Yu & Dimitri Bertsekas, 2013. "Q-learning and policy iteration algorithms for stochastic shortest path problems," Annals of Operations Research, Springer, vol. 208(1), pages 95-132, September.
    5. Stuart E. Dreyfus, 1969. "An Appraisal of Some Shortest-Path Algorithms," Operations Research, INFORMS, vol. 17(3), pages 395-412, June.
    6. Alexander Vladimirsky, 2008. "Label-Setting Methods for Multimode Stochastic Shortest Path Problems on Graphs," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 821-838, November.
    7. Blai Bonet, 2007. "On the Speed of Convergence of Value Iteration on Stochastic Shortest-Path Problems," Mathematics of Operations Research, INFORMS, vol. 32(2), pages 365-373, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Huizhen Yu & Dimitri Bertsekas, 2013. "Q-learning and policy iteration algorithms for stochastic shortest path problems," Annals of Operations Research, Springer, vol. 208(1), pages 95-132, September.
    2. Martino Bardi & Juan Pablo Maldonado López, 2016. "A Dijkstra-Type Algorithm for Dynamic Games," Dynamic Games and Applications, Springer, vol. 6(3), pages 263-276, September.
    3. Daniel Lücking & Wolfgang Stadje, 2013. "The stochastic shortest-path problem for Markov chains with infinite state space with applications to nearest-neighbor lattice chains," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(2), pages 239-264, April.
    4. Dimitri P. Bertsekas, 2018. "Proximal algorithms and temporal difference methods for solving fixed point problems," Computational Optimization and Applications, Springer, vol. 70(3), pages 709-736, July.
    5. Huizhen Yu & Dimitri P. Bertsekas, 2015. "A Mixed Value and Policy Iteration Method for Stochastic Control with Universally Measurable Policies," Mathematics of Operations Research, INFORMS, vol. 40(4), pages 926-968, October.
    6. Alexander Vladimirsky, 2008. "Label-Setting Methods for Multimode Stochastic Shortest Path Problems on Graphs," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 821-838, November.
    7. Levering, Nikki & Boon, Marko & Mandjes, Michel & Núñez-Queija, Rudesindo, 2022. "A framework for efficient dynamic routing under stochastically varying conditions," Transportation Research Part B: Methodological, Elsevier, vol. 160(C), pages 97-124.
    8. E. Nikolova & N. E. Stier-Moses, 2014. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times," Operations Research, INFORMS, vol. 62(2), pages 366-382, April.
    9. Pijls, Wim & Post, Henk, 2009. "A new bidirectional search algorithm with shortened postprocessing," European Journal of Operational Research, Elsevier, vol. 198(2), pages 363-369, October.
    10. Carey E. Priebe & Donniell E. Fishkind & Lowell Abrams & Christine D. Piatko, 2005. "Random disambiguation paths for traversing a mapped hazard field," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 285-292, April.
    11. Yang, Jinling & Chen, Zhiwei & Criado, Regino & Zhang, Shenggui, 2024. "A mathematical framework for shortest path length computation in multi-layer networks with inter-edge weighting and dynamic inter-edge weighting: The case of the Beijing bus network, China," Chaos, Solitons & Fractals, Elsevier, vol. 182(C).
    12. Yueyue Fan & Yu Nie, 2006. "Optimal Routing for Maximizing the Travel Time Reliability," Networks and Spatial Economics, Springer, vol. 6(3), pages 333-344, September.
    13. Pretolani, Daniele, 2000. "A directed hypergraph model for random time dependent shortest paths," European Journal of Operational Research, Elsevier, vol. 123(2), pages 315-324, June.
    14. Azar Sadeghnejad-Barkousaraie & Rajan Batta & Moises Sudit, 2017. "Convoy movement problem: a civilian perspective," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 14-33, January.
    15. Huang, He & Gao, Song, 2012. "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 579-598.
    16. Azadian, Farshid & Murat, Alper E. & Chinnam, Ratna Babu, 2012. "Dynamic routing of time-sensitive air cargo using real-time information," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 355-372.
    17. Emin Karagözoglu & Cagri Saglam & Agah R. Turan, 2020. "Tullock Brings Perseverance and Suspense to Tug-of-War," CESifo Working Paper Series 8103, CESifo.
    18. Arthur Flajolet & Sébastien Blandin & Patrick Jaillet, 2018. "Robust Adaptive Routing Under Uncertainty," Operations Research, INFORMS, vol. 66(1), pages 210-229, January.
    19. Benkert, Jean-Michel & Letina, Igor & Nöldeke, Georg, 2018. "Optimal search from multiple distributions with infinite horizon," Economics Letters, Elsevier, vol. 164(C), pages 15-18.
    20. Francesca Guerriero & Roberto Musmanno & Valerio Lacagnina & Antonio Pecorella, 2001. "A Class of Label-Correcting Methods for the K Shortest Paths Problem," Operations Research, INFORMS, vol. 49(3), pages 423-429, June.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:66:y:2019:i:1:p:15-37. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.