Track, Stop, and Eliminate: an Algorithm to Solve Stochastic Orienteering Problems Using MCTS

Abstract

We present a novel algorithm to solve the stochastic orienteering problem with chance constraints that combines Monte Carlo Tree Search (MCTS) with a best arm identification (BAI) algorithm. This method extends our recently proposed solution that builds a search planning tree considering both an objective function to maximize, as well as a chance constraint on the failure probability, i.e., the probability of violating the assigned budget constraint. By combining these two approaches, we obtain a new planner that tunes the amount of tree search at run time. Extensive simulation results on our benchmark problems show that the new approach is significantly faster than the previous one, while incurring in just marginal decrements in terms of performance.