Monte Carlo planning for mobile robots in large action spaces with velocity obstacles

Motion planning in dynamic environments is a challenging robotic task, requiring collision avoidance and real-time computation. State-of-the-art online methods as Velocity Obstacles (VO) guarantee safe local planning, while global planning methods based on reinforcement learning or graph discretization are either computationally inefficient or not provably collision-safe. In this paper, we combine Monte Carlo Tree Search (MCTS) with VO to prune unsafe actions (i.e., colliding velocities). In this way, we can plan with very few MCTS simulations even in very large action spaces (60 actions), achieving higher cumulative reward and lower computational time per step than pure MCTS with many simulations. Moreover, our methodology guarantees collision avoidance thanks to action pruning with VO, while pure MCTS does not. Results in this paper pave the way towards deployment of MCTS planning on real robots and multi-agent decentralized motion planning.