Monte Carlo Tree Search
- También llamado: MCTS
- Categoría: Planning & manipulation › Task-level
- Etiquetas: planning, tree-search, decision-making, pomdp, sampling-based
Un algoritmo de planificación en línea que hace crecer un árbol de búsqueda simulando muchas trayectorias a partir de un modelo y usa sus retornos para elegir la acción más prometedora.
Definición
Búsqueda en árbol de Monte Carlo (Monte Carlo tree search, MCTS) es una familia de algoritmos de planificación que deciden qué hacer a continuación construyendo un árbol de búsqueda de forma incremental a partir de experiencia simulada. Cada iteración tiene cuatro pasos: la selección recorre el árbol hacia abajo desde el estado actual y elige los hijos con una regla que equilibra las acciones con un valor estimado alto frente a las acciones que solo se han probado unas pocas veces; la expansión añade uno o más nodos nuevos; la simulación (o rollout) estima el valor del nuevo nodo, clásicamente ejecutando una política aleatoria o una política por defecto sencilla hasta el final del episodio; y la retropropagación actualiza los recuentos de visitas y las estimaciones de valor de cada nodo del camino. Cuando se agota el presupuesto de tiempo o de iteraciones, el algoritmo se compromete con la acción raíz más visitada o con mejor valor y repite el proceso desde el estado siguiente. El término lo introdujo Rémi Coulom en 2006, y ese mismo año Kocsis y Szepesvári publicaron UCT (Upper Confidence bounds applied to Trees), que usa la regla de bandido UCB1 para la selección y es la variante más utilizada.
La MCTS solo necesita un modelo generativo: un simulador que, dados un estado y una acción, devuelve un estado siguiente muestreado y una recompensa. No necesita una matriz de transición explícita, un modelo diferenciable ni una heurística escrita a mano, y es un algoritmo anytime, de modo que más cómputo da mejores decisiones y la búsqueda puede detenerse en cuanto se necesita una respuesta. En condiciones adecuadas, UCT converge a la acción óptima a medida que crece el número de simulaciones, pero en la práctica la calidad de una decisión depende mucho del presupuesto, de la política de rollout y de cómo se guía la búsqueda. AlphaGo y AlphaZero demostraron que sustituir los rollouts aleatorios por estimaciones de valor aprendidas y usar una política aprendida para sesgar la selección hace que la búsqueda sea mucho más eficiente.
En robótica, la MCTS se usa para decisiones sobre un horizonte en el que los resultados son inciertos. POMCP y su variante POUCT extienden UCT a problemas parcialmente observables buscando sobre historiales de acciones y observaciones, lo que los convierte en solucionadores habituales para formulaciones POMDP de búsqueda de objetos, percepción activa y recopilación de información. Los estados y acciones continuos requieren un cuidado adicional: el ensanchamiento progresivo (progressive widening) añade nuevas acciones hijas u observaciones muestreadas solo a medida que crece el recuento de visitas de un nodo, y muchos sistemas robóticos buscan en cambio sobre un conjunto discreto de macroacciones o primitivas de movimiento, mientras que planificadores de nivel inferior se encargan del movimiento continuo.
Por qué importa
Muchas decisiones de un robot, como dónde mirar a continuación o qué objeto mover primero, tienen resultados que solo se ven varios pasos después y que dependen de observaciones inciertas. La MCTS ofrece una forma práctica de planificar sobre esos horizontes sin nada más que un simulador, y escala a problemas en los que resolver el MDP o el POMDP completo fuera de línea está fuera de alcance.
Aplicaciones clave
- Búsqueda de objetos y percepción activa formuladas como POMDP
- Planificación de tareas y movimientos, eligiendo el orden de las acciones simbólicas
- Toma de decisiones para la conducción autónoma en intersecciones e incorporaciones
- Coordinación y exploración multirrobot
- Planificación con modelos aprendidos, como en los sistemas de estilo AlphaZero
En la práctica
Un manipulador móvil tiene que encontrar varios objetos en una habitación desordenada. El equipo modela la tarea como un POMDP con una creencia sobre las ubicaciones de los objetos, macroacciones para desplazarse a puntos de vista y una acción de detección, y un modelo de observación para la cámara. En cada decisión, POUCT ejecuta unos pocos miles de simulaciones desde la creencia actual dentro de un presupuesto de tiempo fijo, usando el modelo generativo para muestrear ubicaciones de objetos y detecciones. El robot ejecuta la acción raíz con el valor más alto, actualiza su creencia con el resultado real de la detección y vuelve a planificar. Los ingenieros ajustan la constante de exploración, la política de rollout y el horizonte de búsqueda, y mantienen el conjunto de macroacciones lo bastante pequeño como para que el árbol pueda crecer en profundidad dentro del presupuesto.
Ideas erróneas comunes
- La MCTS es un algoritmo de aprendizaje — es un método de planificación que necesita un modelo o un simulador; a menudo se combina con redes de valor y de política aprendidas, pero la búsqueda en sí no aprende una política
- La MCTS requiere rollouts aleatorios hasta el final del episodio — los rollouts pueden usar en su lugar políticas heurísticas, horizontes truncados o una función de valor aprendida
- La MCTS funciona directamente sobre acciones continuas — el UCT estándar supone un conjunto finito de acciones, por lo que los problemas continuos necesitan ensanchamiento progresivo, muestreo o un conjunto discreto de macroacciones
- La MCTS encuentra la acción óptima — solo converge hacia ella a medida que crecen las simulaciones; con un presupuesto de tiempo real el resultado es aproximado y depende de cómo se guía la búsqueda
Quién debería saberlo
- Ingenieros de planificación y toma de decisiones
- Investigadores que trabajan en POMDP y percepción activa
- Desarrolladores de planificación de tareas y movimientos
- Profesionales del aprendizaje por refuerzo que combinan búsqueda y aprendizaje
Tecnologías relacionadas
- UCT
- POMCP
- AlphaZero
- Ensanchamiento progresivo (Progressive Widening)
- Upper Confidence Bound (UCB1)
Términos relacionados
- Markov Decision Process (MDP)
- Partially Observable Markov Decision Process (POMDP)
- Belief-Space Planning
- Task and Motion Planning
- Robotic information gathering
- Reinforcement Learning
Proyectos relacionados
- 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
Vídeos
- Monte Carlo Tree Search: John Levine
- AI 101: Monte Carlo Tree Search: AI and Games