Repeated-Task Canadian Traveler Problem


  • Zahy Bnaya Ben Gurion University
  • Ariel Felner Ben Gurion University
  • Dror Fried Ben-Gurion University
  • Olga Maksin Ben-Gurion University
  • Solomon Shimony Ben-Gurion University



In the Canadian Traveler Problem (CTP) a traveling agent is given a weighted graph, where some of the edges may be blocked, with a known probability. The agent needs to travel to a given goal. A solution for CTP is a policy, that has the smallest expected traversal cost. CTP is intractable. 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.