An AO^* based exact algorithm for the Canadian traveler problem

DOI10.1287/IJOC.2015.0668MaRDI QIDQ2806869zbMATH OpenOpenAlexFDO

Authors Vural Aksakalli, O. Furkan Sahin, Ibrahim Ari

Publication date 19 May 2016

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.2015.0668

zbMATH Keywords

Markov decision processpath planningCanadian traveler problem\(\mathrm{AO}^{*}\) search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15) Markov and semi-Markov decision processes (90C40)

Recommendations

• Complexity of Canadian traveler problem variants
• Repeated-task Canadian traveler problem
• Canadians should travel randomly
• On the randomized online strategies for the \(k\)-Canadian traveler problem
• Generalized Canadian traveller problems

Cites work

• A Heuristic Search Approach for a Nonstationary Stochastic Shortest Path Problem with Terminal Cost
• An admissible and optimal algorithm for searching AND/OR graphs
• Approximate receding horizon approach for Markov decision processes: average reward case
• Complexity of Canadian traveler problem variants
• Near-optimal reinforcement learning in polynomial time
• Optimal obstacle placement with disambiguations
• Optimizing decision trees through heuristically guided search
• Penalty-based algorithms for the stochastic obstacle scene problem
• Probabilistic planning with clear preferences on missing information
• Random disambiguation paths for traversing a mapped hazard field
• Shortest paths without a map
• The Canadian Traveller Problem and its competitive analysis
• The Linear Programming Approach to Approximate Dynamic Programming
• The reset disambiguation policy for navigating stochastic obstacle fields

Cited in

(6)

• The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem
• Repeated-task Canadian traveler problem
• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• Improved deterministic strategy for the Canadian Traveller Problem exploiting small max-\((s,t)\)-cuts
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• Complexity of Canadian traveler problem variants

This page was built for publication: An \(\mathrm{AO}^{*}\) based exact algorithm for the Canadian traveler problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806869)