High-Quality Policies for the Canadian Traveler's Problem (Extended Abstract)
Patrick Eyerich, Thomas Keller, Malte Helmert · 2010
The Canadian Traveler’s Problem (CTP; Papadimitriou and Yannakakis 1991) is a path planning problem with imperfect information about the roadmap. We consider its stochastic version, which has drawn considerable attention from researchers in AI search (e. g., Nikolova and Karger 2008) and is closely related to navigation tasks in uncertain terrain considered in the robotics literature (e. g., Koenig and Likhachev 2002; Likhachev and Stentz 2006). 1The objective in the CTP is to travel from the initial location v0 to some goal location v ⋆ on a roadmap given as an undirected weighted graph with vertex set V (locations) and edge set E (roads). Complicating things, only a subset of roads W ⊆ E, called the weather, is actually traversable. The weather remains static while the agent traverses the graph. The agent does not know the weather; however, it does knows with which probability each road