4.2 Article

Repeated-task Canadian Traveler Problem

Journal

AI COMMUNICATIONS
Volume 28, Issue 3, Pages 453-477

Publisher

IOS PRESS
DOI: 10.3233/AIC-150665

Keywords

Navigation; Monte-Carlo tree search; UCT; uncertainty

Ask authors/readers for more resources

In the Canadian Traveler Problem (CTP) a traveling agent is given a graph where some of the edges may be blocked with a known probability. The agent has to travel from a given start state to a given goal state. A solution for CTP is a policy, that has the smallest expected traversal cost. CTP is known to be intractable. Previous work has focused on the task of performing a single trip. We generalize CTP to its repeated task version where a number of trips from the start to the goal should be performed (either by the same agent or by multiple agents) while the aim is to minimize the total travel cost in all trips. We provide optimal algorithms for the special case of repeated-task CTP on disjoint path graphs. Based on these findings, we provide a scheme for solving the problem on general graphs. According to this scheme, we first solve a simplified variant of the problem and then apply the solution to the original problem. Empirical results show the benefits of the suggested scheme. For small graphs, where we could compare to optimal policies, our approach achieves near-optimal results with only a fraction of the computation cost. We also provide suboptimal solutions based on UCT that use our heuristics scheme. Experimental results show the benefits of using our scheme for UCT.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.2
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available