An AO^* Based Exact Algorithm for the Canadian Traveler Problem

References

• Aksakalli V (2007) The BAO* algorithm for stochastic shortest path problems with dynamic learning. Proc. 46th IEEE Conf. Decision Control (Wiley-IEEE Press, Hoboken, NJ), 6003–6008.Crossref, Google Scholar
• Aksakalli V, Ari I (2014) Penalty-based algorithms for the stochastic obstacle scene problem. INFORMS J. Comput. 26(2):370–384.Link, Google Scholar
• Aksakalli V, Ceyhan E (2012) Optimal obstacle placement with disambiguations. Ann. Appl. Stat. 6(4):1730–1774.Crossref, Google Scholar
• Aksakalli V, Fishkind DE, Priebe CE, Ye X (2011) The reset disambiguation policy for navigating stochastic obstacle fields. Naval Res. Logist. 58(4):389–399.Crossref, Google Scholar
• Baglietto M, Battistelli G, Vitali F, Zoppoli R (2003) Shortest path problems on stochastic graphs: A neuro dynamic programming approach. Proc. 42nd IEEE Conf. Decision Control (Wiley-IEEE Press, Hoboken, NJ), 6187–6193.Crossref, Google Scholar
• Bander JL, White CC (2002) A heuristic search approach for a nonstationary stochastic shortest path problem with terminal cost. Transportation Sci. 36(2):218–230.Link, Google Scholar
• Blei DM, Kaelbling LP (1999) Shortest paths in a dynamic uncertain domain. Proc. IJCAI Workshop Adaptive Spatial Representations Dynamic Environ. (AAAI Press, Palo Alto, CA).Google Scholar
• Bnaya Z, Felner A, Fried D, Maksin O, Shimony SE (2011) Repeated-Task Canadian Traveler Problem (AAAI Press, Palo Alto, CA).Google Scholar
• Bonet B (2009) Deterministic POMDPs revisited. Proc. 25th Conf. Uncertainty Artificial Intelligence (AAAI Press, Palo Alto, CA), 59–66.Google Scholar
• Chang CR, Slagle JR (1971) An admissible and optimal algorithm for searching and/or graphs. Artificial Intelligence 2(2):117–128.Crossref, Google Scholar
• Chang HS, Marcus SI (2003) Approximate receding horizon approach for Markov decision processes: Average reward case. J. Math. Anal. Appl. 286(2):636–651.Crossref, Google Scholar
• de Farias DP, Roy BV (2003) The linear programming approach to approximate dynamic programming. Oper. Res. 51(6):850–865.Link, Google Scholar
• Eyerich P, Keller T, Helmert M (2009) High-quality policies for the Canadian traveler problem. Proc. 24th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 51–58.Google Scholar
• Fawcett J, Robinson P (2000) Adaptive routing for road traffic. IEEE Comp. Graphics Appl. 20(3):46–53.Crossref, Google Scholar
• Ferguson D, Stenz A, Thrun S (2004) PAO* for planning with hidden state. Proc. 2004 IEEE Internat. Conf. Robotics Automation (Wiley-IEEE Press, Hoboken, NJ), 2840–2847.Crossref, Google Scholar
• Fiosins M, Fiosina J, Müller JP, Görmer J (2011) Reconciling strategic and tactical decision making in agent-oriented simulation of vehicles in urban traffic. Proc. 4th Internat. ICST Conf. Simulation Tools Techniques (Institute for Computer Sciences, Social-Informatics, and Telecommunications Engineering, Brussels), 144–151.Crossref, Google Scholar
• Fishkind DE, Priebe CE, Giles K, Smith LN, Aksakalli V (2007) Disambiguation protocols based on risk simulation. IEEE Trans. Systems, Man, Cybernetics, Part A 37(5):814–823.Crossref, Google Scholar
• Fried D, Shimony SE, Benbassat A, Wenner C (2013) Complexity of Canadian traveler problem variants. Theoret. Comput. Sci. 487: 1–16.Crossref, Google Scholar
• Kearns M, Singh S (2002) Near-optimal reinforcement learning in polynomial time. Machine Learning 49(2):209–232.Crossref, Google Scholar
• Likhachev M, Stentz A (2009) Probabilistic planning with clear preferences on missing information. Artificial Intelligence 173(5–6):696–721.Crossref, Google Scholar
• Martelli A, Montanari U (1978) Optimizing decision trees through heuristically guided search. Comm. ACM 21(12):1025–10039.Crossref, Google Scholar
• Nikolova E, Karger DR (2008) Route planning under uncertainty: The Canadian traveller problem. Proc. 23rd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 969–974.Google Scholar
• Nilsson NJ (1980) Principles of Artificial Intelligence (Morgan Kaufmann, Palo Alto, CA).Google Scholar
• Papadimitriou CH, Yannakakis M (1991) Shortest paths without a map. Theoret. Comp. Sci. 84(1):127–150.Crossref, Google Scholar
• Priebe CE, Fishkind DE, Abrams L, Piatko CD (2005) Random disambiguation paths for traversing a mapped hazard field. Naval Res. Logist. 52(3):285–292.Crossref, Google Scholar
• Sahin OF, Aksakalli V (2014) A fast and effective online algorithm for the Canadian traveler problem. Finzi A, Orlandini A, eds. Proc. ICAPS Workshop Planning Robotics (AAAI, Palo Alto, CA), 166–171.Google Scholar
• Smith DL (1995) Detection technologies for mines and minelike targets. Proc. SPIE (International Society for Optical Engineering, Bellingham, WA), 404–408.Google Scholar
• Witherspoon NH, Holloway JH, Davis KS, Miller RW, Dubey AC (1995) The coastal battlefield reconnaissance and analysis (COBRA) program for minefield detection. Proc. SPIE (International Society for Optical Engineering, Bellingham, WA), 500–508.Google Scholar
• Xu Y, Hu M, Su B, Zhu B, Zhu Z (2009) The Canadian traveller problem and its competitive analysis. J. Combinatorial Opt. 18(2):195–205.Crossref, Google Scholar
• Ye X, Priebe CE (2010) A graph-search based navigation algorithm for traversing a potentially hazardous area with disambiguation. Internat. J. Oper. Res. Inform. Sys. 1(3):14–27.Crossref, Google Scholar