Abstract

We introduce a new approach to solving path-finding problems under uncertainty by representing them as probabilistic models and applying domain-independent inference algorithms to the models. This approach separates problem representation from the inference algorithm and provides a framework for efficient learning of path-finding policies. We evaluate the new approach on the Canadian Traveller Problem, which we formulate as a probabilistic model, and show how probabilistic inference allows efficient stochastic policies to be obtained for this problem.

We suggest a justification for the use of a fixed threshold on the number of conflicts based on the analysis of a model problem. Following the suggested justification, we introduce a new algorithm, which differs in the ways when and how meta-agents are created and handled during search. The new algorithm exhibits considerably better performance compared to the original algorithm. The new algorithm is evaluated on several sets of problems, chosen to highlight different aspects of the algorithm.

Full PDF

This is a short version of Justifying and Improving MA-CBS.

Abstract

UCT, a state-of-the art algorithm for Monte Carlo tree search (MCTS) in games and Markov decision processes, is based on UCB1, a sampling policy for the Multi-armed Bandit problem (MAB) that minimizes the cumulative regret. However, search differs from MAB in that in MCTS it is usually only the final “arm pull” (the actual move selection) that collects a reward, rather than all “arm pulls”. In this paper, an MCTS sampling policy based on Value of Information (VOI) estimates of rollouts is suggested. Empirical evaluation of the policy and comparison to UCB1 and UCT is performed on random MAB instances as well as on Computer Go.