Monte Carlo Tree Search with Velocity Obstacles for safe and efficient motion planning in dynamic environments

2025-01-16 · Lorenzo Bonanni, Daniele Meli, Alberto Castellini, Alessandro Farinelli

Online motion planning is a challenging problem for intelligent robots moving in dense environments with dynamic obstacles, e.g., crowds. In this work, we propose a novel approach for optimal and safe online motion planning with minimal information about dynamic obstacles. Specifically, our approach requires only the current position of the obstacles and their maximum speed, but it does not need any information about their exact trajectories or dynamic model. The proposed methodology combines Monte Carlo Tree Search (MCTS), for online optimal planning via model simulations, with Velocity Obstacles (VO), for obstacle avoidance. We perform experiments in a cluttered simulated environment with walls, and up to 40 dynamic obstacles moving with random velocities and directions. With an ablation study, we show the key contribution of VO in scaling up the efficiency of MCTS, selecting the safest and most rewarding actions in the tree of simulations. Moreover, we show the superiority of our methodology with respect to state-of-the-art planners, including Non-linear Model Predictive Control (NMPC), in terms of improved collision rate, computational and task performance.

📄 PDF Abstract BibTeX arXiv:2501.09649

Code (0)

등록된 구현이 없습니다.

Tasks

Model Predictive ControlMotion Planning

Active Reinforcement Learning with Monte-Carlo Tree Search

2018-03-13 · Sebastian Schulze, Owain Evans

Active Reinforcement Learning (ARL) is a twist on RL where the agent observes reward information only if it pays a cost. This subtle change makes exploration substantially more challenging. Powerful principles in RL like…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Thompson Sampling

Monte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms

2024-04-14 · Tristan Cazenave

Monte Carlo Tree Search and Monte Carlo Search have good results for many combinatorial problems. In this paper we propose to use Monte Carlo Search to design mathematical expressions that are used as exploration terms f…

Hedging of Financial Derivative Contracts via Monte Carlo Tree Search

2021-02-11 · Oleg Szehr

The construction of approximate replication strategies for pricing and hedging of derivative contracts in incomplete markets is a key problem of financial engineering. Recently Reinforcement Learning algorithms for hedgi…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Learning Position Evaluation Functions Used in Monte Carlo Softmax Search

2019-01-30 · Harukazu Igarashi, Yuichi Morioka, Kazumasa Yamamoto

This paper makes two proposals for Monte Carlo Softmax Search, which is a recently proposed method that is classified as a selective search like the Monte Carlo Tree Search. The first proposal separately defines the node…

Position Reinforcement Learning

Is Monte Carlo Tree Search Just Every-Visit Monte Carlo Control?

2026-08-28 · Xianyi Wu arxiv

Monte Carlo Tree Search (MCTS) and every-visit Monte Carlo (MC) control are usually presented as different methods. MCTS is described in the language of search (selection, expansion, simulation, and backup), whereas MC c…

Reinforcement Learning