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

DOI10.1287/IJOC.2015.0668zbMATH Open1338.90278OpenAlexW2267848830MaRDI QIDQ2806869FDOQ2806869

Vural Aksakalli, Ibrahim Ari, O. Furkan Sahin

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

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

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)

Cites Work

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

Cited In (4)

• 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
• The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem

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)