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

Random disambiguation paths for traversing a mapped hazard field

Author

Listed:
  • Carey E. Priebe
  • Donniell E. Fishkind
  • Lowell Abrams
  • Christine D. Piatko

Abstract

We consider the problem of safely and swiftly navigating through a spatial arrangement of potential hazard detections in which each detection has associated with it a probability that the detection is indeed a true hazard. When in close proximity to a detection, we assume the ability—for a cost—to determine whether or not the hazard is real. Our approach to this problem involves a new object, the random disambiguation path (RDP), which is a curve‐valued random variable parametrized by a binary tree with particular properties. We prove an admissibility result showing that there is positive probability that the use of an RDP reduces the expected traversal length compared to the conventional shortest zero‐risk path, and we introduce a practically computable additive‐constant approximation to the optimal RDP. The theoretical considerations are complemented by simulation and example. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005

Suggested Citation

  • 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.
    • Handle: RePEc:wly:navres:v:52:y:2005:i:3:p:285-292
    DOI: 10.1002/nav.20071
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20071
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20071?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. 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.
    2. Priebe, Carey E. & Naiman, Daniel Q. & Cope, Leslie M., 2001. "Importance sampling for spatial scan analysis: computing scan statistic p-values for marked point processes," Computational Statistics & Data Analysis, Elsevier, vol. 35(4), pages 475-485, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Vural Aksakalli & Donniell E. Fishkind & Carey E. Priebe & Xugang Ye, 2011. "The reset disambiguation policy for navigating stochastic obstacle fields," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(4), pages 389-399, June.
    2. X Ye & D E Fishkind & L Abrams & C E Priebe, 2011. "Sensor information monotonicity in disambiguation protocols," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 142-151, January.
    3. Vural Aksakalli & O. Furkan Sahin & Ibrahim Ari, 2016. "An AO* Based Exact Algorithm for the Canadian Traveler Problem," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 96-111, February.
    4. Vural Aksakalli & Ibrahim Ari, 2014. "Penalty-Based Algorithms for the Stochastic Obstacle Scene Problem," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 370-384, May.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Emin Karagözoglu & Cagri Saglam & Agah R. Turan, 2020. "Tullock Brings Perseverance and Suspense to Tug-of-War," CESifo Working Paper Series 8103, CESifo.
    6. 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.
    7. Arthur Flajolet & Sébastien Blandin & Patrick Jaillet, 2018. "Robust Adaptive Routing Under Uncertainty," Operations Research, INFORMS, vol. 66(1), pages 210-229, January.
    8. 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.
    9. 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.
    10. James L. Bander & Chelsea C. White, 2002. "A Heuristic Search Approach for a Nonstationary Stochastic Shortest Path Problem with Terminal Cost," Transportation Science, INFORMS, vol. 36(2), pages 218-230, May.
    11. Matsubayashi, Nobuo & Nishino, Hisakazu, 1999. "An application of Lemke's method to a class of Markov decision problems," European Journal of Operational Research, Elsevier, vol. 116(3), pages 584-590, August.
    12. Özlem Çavuş & Andrzej Ruszczyński, 2014. "Computational Methods for Risk-Averse Undiscounted Transient Markov Models," Operations Research, INFORMS, vol. 62(2), pages 401-417, April.
    13. Huizhen Yu & Dimitri P. Bertsekas, 2013. "On Boundedness of Q-Learning Iterates for Stochastic Shortest Path Problems," Mathematics of Operations Research, INFORMS, vol. 38(2), pages 209-227, May.
    14. Fengying Li & Yuqiang Li & Xianyi Wu, 2024. "Minimax weight learning for absorbing MDPs," Statistical Papers, Springer, vol. 65(6), pages 3545-3582, August.
    15. Guillot, Matthieu & Stauffer, Gautier, 2020. "The Stochastic Shortest Path Problem: A polyhedral combinatorics perspective," European Journal of Operational Research, Elsevier, vol. 285(1), pages 148-158.
    16. Karagözoğlu, Emin & Sağlam, Çağrı & Turan, Agah R., 2021. "Perseverance and suspense in tug-of-war," Journal of Mathematical Economics, Elsevier, vol. 95(C).
    17. Jorge Lorca & Emerson Melo, 2020. "Choice Aversion in Directed Networks," Working Papers Central Bank of Chile 879, Central Bank of Chile.
    18. Raymond K. Cheung & B. Muralidharan, 2000. "Dynamic Routing for Priority Shipments in LTL Service Networks," Transportation Science, INFORMS, vol. 34(1), pages 86-98, February.
    19. Eric A. Hansen, 2017. "Error bounds for stochastic shortest path problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(1), pages 1-27, August.
    20. Fernando Ordóñez & Nicolás E. Stier-Moses, 2010. "Wardrop Equilibria with Risk-Averse Users," Transportation Science, INFORMS, vol. 44(1), pages 63-86, February.

    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:52:y:2005:i:3:p:285-292. 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.