Monte Carlo Tree Search
- Aussi appelé: MCTS
- Catégorie: Planning & manipulation › Task-level
- Mots-clés: planning, tree-search, decision-making, pomdp, sampling-based
Algorithme de planification en ligne qui fait croître un arbre de recherche en simulant de nombreuses trajectoires à partir d'un modèle et utilise leurs retours pour choisir l'action la plus prometteuse.
Définition
La recherche arborescente Monte-Carlo (Monte Carlo tree search, MCTS) est une famille d'algorithmes de planification qui décident de la prochaine action en construisant progressivement un arbre de recherche à partir d'expérience simulée. Chaque itération comporte quatre étapes : la sélection descend dans l'arbre depuis l'état courant en choisissant les enfants selon une règle qui met en balance les actions à forte valeur estimée et celles qui n'ont été essayées que quelques fois ; l'expansion ajoute un ou plusieurs nouveaux nœuds ; la simulation (ou déroulement) estime la valeur du nouveau nœud, classiquement en jouant une politique aléatoire ou une politique par défaut simple jusqu'à la fin de l'épisode ; et la rétropropagation met à jour le nombre de visites et les estimations de valeur de chaque nœud du chemin. Une fois le budget de temps ou d'itérations épuisé, l'algorithme s'engage sur l'action racine la plus visitée ou de meilleure valeur, puis recommence à partir de l'état suivant. Le terme a été introduit par Rémi Coulom en 2006, et la même année Kocsis et Szepesvári ont publié UCT (Upper Confidence bounds applied to Trees), qui utilise la règle de bandit UCB1 pour la sélection et constitue la variante la plus utilisée.
La MCTS n'a besoin que d'un modèle génératif : un simulateur qui, pour un état et une action donnés, renvoie un état suivant échantillonné et une récompense. Elle ne requiert ni matrice de transition explicite, ni modèle différentiable, ni heuristique écrite à la main, et c'est un algorithme anytime : davantage de calcul donne de meilleures décisions, et la recherche peut être arrêtée dès qu'une réponse est nécessaire. Sous des conditions appropriées, UCT converge vers l'action optimale à mesure que le nombre de simulations augmente, mais en pratique la qualité d'une décision dépend fortement du budget, de la politique de déroulement et de la manière dont la recherche est guidée. AlphaGo et AlphaZero ont montré que remplacer les déroulements aléatoires par des estimations de valeur apprises et utiliser une politique apprise pour orienter la sélection rend la recherche bien plus efficace.
En robotique, la MCTS sert aux décisions sur un horizon où les résultats sont incertains. POMCP et sa variante POUCT étendent UCT aux problèmes partiellement observables en cherchant parmi des historiques d'actions et d'observations, ce qui en fait des solveurs courants pour les formulations POMDP de la recherche d'objets, de la perception active et de la collecte d'informations. Les états et actions continus demandent un soin particulier : l'élargissement progressif (progressive widening) n'ajoute de nouvelles actions enfants ou de nouvelles observations échantillonnées qu'à mesure que le nombre de visites d'un nœud augmente, et de nombreux systèmes robotiques cherchent plutôt parmi un ensemble discret de macro-actions ou de primitives de mouvement, tandis que des planificateurs de plus bas niveau gèrent le mouvement continu.
Pourquoi c'est important
De nombreuses décisions d'un robot, comme l'endroit où regarder ensuite ou l'objet à déplacer en premier, ont des conséquences qui n'apparaissent que plusieurs étapes plus tard et dépendent d'observations incertaines. La MCTS offre un moyen pratique de planifier sur de tels horizons avec rien de plus qu'un simulateur, et elle passe à l'échelle sur des problèmes où résoudre hors ligne le MDP ou le POMDP complet est hors de portée.
Applications principales
- Recherche d'objets et perception active formulées comme des POMDP
- Planification de tâches et de mouvements, pour choisir l'ordre des actions symboliques
- Prise de décision en conduite autonome aux intersections et aux insertions
- Coordination et exploration multirobots
- Planification avec des modèles appris, comme dans les systèmes de type AlphaZero
En pratique
Un manipulateur mobile doit trouver plusieurs objets dans une pièce encombrée. L'équipe modélise la tâche comme un POMDP avec une croyance sur la position des objets, des macro-actions pour se rendre à des points de vue et une action de détection, ainsi qu'un modèle d'observation pour la caméra. À chaque décision, POUCT exécute quelques milliers de simulations à partir de la croyance courante dans un budget de temps fixe, en utilisant le modèle génératif pour échantillonner les positions des objets et les détections. Le robot exécute l'action racine de plus haute valeur, met à jour sa croyance avec le résultat réel de la détection et replanifie. Les ingénieurs règlent la constante d'exploration, la politique de déroulement et l'horizon de recherche, et maintiennent l'ensemble des macro-actions assez petit pour que l'arbre puisse croître en profondeur dans le budget.
Idées reçues
- La MCTS est un algorithme d'apprentissage — c'est une méthode de planification qui a besoin d'un modèle ou d'un simulateur ; elle est souvent combinée à des réseaux de valeur et de politique appris, mais la recherche elle-même n'apprend pas de politique
- La MCTS exige des déroulements aléatoires jusqu'à la fin de l'épisode — les déroulements peuvent utiliser à la place des politiques heuristiques, des horizons tronqués ou une fonction de valeur apprise
- La MCTS fonctionne directement sur des actions continues — UCT standard suppose un ensemble fini d'actions, donc les problèmes continus nécessitent l'élargissement progressif, l'échantillonnage ou un ensemble discret de macro-actions
- La MCTS trouve l'action optimale — elle ne converge vers celle-ci qu'à mesure que les simulations augmentent ; avec un budget temps réel, le résultat est approché et dépend de la manière dont la recherche est guidée
Qui devrait le savoir
- Ingénieurs en planification et en prise de décision
- Chercheurs travaillant sur les POMDP et la perception active
- Développeurs en planification de tâches et de mouvements
- Praticiens de l'apprentissage par renforcement qui combinent recherche et apprentissage
Technologies associées
- UCT
- POMCP
- AlphaZero
- Élargissement progressif (Progressive Widening)
- Upper Confidence Bound (UCB1)
Termes associés
- Markov Decision Process (MDP)
- Partially Observable Markov Decision Process (POMDP)
- Belief-Space Planning
- Task and Motion Planning
- Robotic information gathering
- Reinforcement Learning
Projets associés
- BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
Vidéos
- Monte Carlo Tree Search: John Levine
- AI 101: Monte Carlo Tree Search: AI and Games