Repeated-task Canadian Traveler Problem

Article type: Research Article

Authors: Bnaya, Zahy^{; *} | Felner, Ariel | Fried, Dror | Maksin, Olga | Shimony, Solomon Eyal

Affiliations: Ben Gurion University, Beer Sheva, Israel

Correspondence: [*] Corresponding author. E-mail: zahy@post.bgu.ac.il.

Abstract: 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.

Keywords: Navigation, Monte-Carlo tree search, UCT, uncertainty

DOI: 10.3233/AIC-150665

Journal: AI Communications, vol. 28, no. 3, pp. 453-477, 2015