Repeated-task Canadian Traveler Problem

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. A solution for CTP is a policy, that has the smallest expected traversal cost. CTP is intracable. Previous work has focused on the case of a single agent. We generalize CTP to a repeated task version where a number of agents need to travel to the same goal, minimizing their combined travel cost. We provide optimal algorithms for the special case of disjoint path graphs. Based on a previous UCT-based approach for the single agent case, a framework is developed for the multi-agent case and four variants are given - two of which are based on the results for disjoint-path graphs. Empirical results show the benefits of the suggested framework and the resulting heuristics. For small graphs where we could compare to optimal policies, our approach achieves near-optimal results at only a fraction of the computation cost.