[BibTeX] [RIS]
High-Quality Policies for the Canadian Traveler's Problem
Type of publication: Inproceedings
Citation: eyerich-et-al:aaai-2010
Booktitle: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI)
Year: 2010
Month: July
Pages: 51--58
Publisher: AAAI Press
Abstract: We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost. We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.
Userfields: date-added={2012-09-25 10:06:31 +0200}, date-modified={2012-09-25 10:06:31 +0200}, project={fremdliteratur},
Authors Eyerich, Patrick
Keller, Thomas
Helmert, Malte