Monte Carlo Tree Search
- Auch genannt: MCTS
- Kategorie: Planning & manipulation › Task-level
- Schlagwörter: planning, tree-search, decision-making, pomdp, sampling-based
Ein Online-Planungsalgorithmus, der einen Suchbaum wachsen lässt, indem er viele Trajektorien aus einem Modell simuliert, und deren Erträge nutzt, um die vielversprechendste Aktion zu wählen.
Definition
Monte-Carlo-Baumsuche (Monte Carlo tree search, MCTS) ist eine Familie von Planungsalgorithmen, die entscheiden, was als Nächstes zu tun ist, indem sie aus simulierter Erfahrung schrittweise einen Suchbaum aufbauen. Jede Iteration hat vier Schritte: Die Selektion steigt vom aktuellen Zustand aus im Baum ab und wählt Kindknoten nach einer Regel, die Aktionen mit hohem geschätztem Wert gegen Aktionen abwägt, die erst wenige Male ausprobiert wurden; die Expansion fügt einen oder mehrere neue Knoten hinzu; die Simulation (oder Rollout) schätzt den Wert des neuen Knotens, klassischerweise indem eine zufällige oder einfache Standard-Policy bis zum Ende der Episode ausgespielt wird; und die Backpropagation aktualisiert die Besuchszähler und Wertschätzungen aller Knoten auf dem Pfad. Ist das Zeit- oder Iterationsbudget aufgebraucht, legt sich der Algorithmus auf die Aktion an der Wurzel fest, die am häufigsten besucht wurde oder den besten Wert hat, und wiederholt das Ganze vom nächsten Zustand aus. Der Begriff wurde 2006 von Rémi Coulom eingeführt, und im selben Jahr veröffentlichten Kocsis und Szepesvári UCT (Upper Confidence bounds applied to Trees), das für die Selektion die Banditenregel UCB1 verwendet und die am weitesten verbreitete Variante ist.
MCTS benötigt nur ein generatives Modell: einen Simulator, der zu einem Zustand und einer Aktion einen gesampelten Folgezustand und eine Belohnung zurückgibt. Eine explizite Übergangsmatrix, ein differenzierbares Modell oder eine von Hand geschriebene Heuristik sind nicht nötig, und MCTS ist ein Anytime-Algorithmus: Mehr Rechenaufwand ergibt bessere Entscheidungen, und die Suche kann jederzeit abgebrochen werden, wenn eine Antwort gebraucht wird. Unter geeigneten Bedingungen konvergiert UCT mit wachsender Zahl der Simulationen gegen die optimale Aktion, in der Praxis hängt die Qualität einer Entscheidung aber stark vom Budget, von der Rollout-Policy und davon ab, wie die Suche gelenkt wird. AlphaGo und AlphaZero zeigten, dass die Suche weit effizienter wird, wenn zufällige Rollouts durch gelernte Wertschätzungen ersetzt werden und eine gelernte Policy die Selektion gewichtet.
In der Robotik wird MCTS für Entscheidungen über einen Horizont eingesetzt, auf dem die Ergebnisse unsicher sind. POMCP und seine Variante POUCT erweitern UCT auf teilweise beobachtbare Probleme, indem sie über Verläufe von Aktionen und Beobachtungen suchen; das macht sie zu verbreiteten Lösern für POMDP-Formulierungen von Objektsuche, aktiver Wahrnehmung und Informationssammlung. Kontinuierliche Zustände und Aktionen erfordern zusätzliche Sorgfalt: Progressive Widening fügt neue Kindaktionen oder gesampelte Beobachtungen erst hinzu, wenn der Besuchszähler eines Knotens wächst, und viele Robotersysteme suchen stattdessen über eine diskrete Menge von Makroaktionen oder Bewegungsprimitiven, während Planer auf tieferer Ebene die kontinuierliche Bewegung übernehmen.
Warum es wichtig ist
Viele Entscheidungen eines Roboters, etwa wohin er als Nächstes schaut oder welches Objekt er zuerst bewegt, haben Folgen, die sich erst einige Schritte später zeigen und von unsicheren Beobachtungen abhängen. MCTS bietet einen praktikablen Weg, über solche Horizonte mit nichts weiter als einem Simulator zu planen, und skaliert auf Probleme, bei denen das vollständige Lösen des MDP oder POMDP offline außer Reichweite ist.
Wichtige Anwendungen
- Als POMDPs formulierte Objektsuche und aktive Wahrnehmung
- Aufgaben- und Bewegungsplanung: Wahl der Reihenfolge symbolischer Aktionen
- Entscheidungsfindung beim autonomen Fahren an Kreuzungen und Einmündungen
- Koordination und Exploration mit mehreren Robotern
- Planen mit gelernten Modellen wie in Systemen nach dem Vorbild von AlphaZero
In der Praxis
Ein mobiler Manipulator soll in einem unaufgeräumten Raum mehrere Objekte finden. Das Team modelliert die Aufgabe als POMDP mit einem Belief über die Objektpositionen, Makroaktionen zum Anfahren von Beobachtungspunkten und einer Detektionsaktion sowie einem Beobachtungsmodell für die Kamera. Bei jeder Entscheidung führt POUCT innerhalb eines festen Zeitbudgets einige tausend Simulationen ab dem aktuellen Belief aus und sampelt dabei mit dem generativen Modell Objektpositionen und Detektionen. Der Roboter führt die Wurzelaktion mit dem höchsten Wert aus, aktualisiert seinen Belief mit dem tatsächlichen Detektionsergebnis und plant erneut. Die Ingenieure stimmen die Explorationskonstante, die Rollout-Policy und den Suchhorizont ab und halten die Menge der Makroaktionen klein genug, dass der Baum innerhalb des Budgets in die Tiefe wachsen kann.
Häufige Missverständnisse
- MCTS ist ein Lernalgorithmus — es ist eine Planungsmethode, die ein Modell oder einen Simulator benötigt; sie wird oft mit gelernten Wert- und Policy-Netzen kombiniert, aber die Suche selbst lernt keine Policy
- MCTS erfordert zufällige Rollouts bis zum Ende der Episode — Rollouts können stattdessen heuristische Policies, abgeschnittene Horizonte oder eine gelernte Wertfunktion verwenden
- MCTS funktioniert direkt mit kontinuierlichen Aktionen — Standard-UCT setzt eine endliche Menge von Aktionen voraus, daher brauchen kontinuierliche Probleme Progressive Widening, Sampling oder eine diskrete Menge von Makroaktionen
- MCTS findet die optimale Aktion — es konvergiert nur mit wachsender Zahl der Simulationen gegen sie; mit einem Echtzeitbudget ist das Ergebnis eine Näherung und hängt davon ab, wie die Suche gelenkt wird
Wer das wissen sollte
- Ingenieure für Planung und Entscheidungsfindung
- Forschende, die an POMDPs und aktiver Wahrnehmung arbeiten
- Entwickler für Aufgaben- und Bewegungsplanung
- Praktiker im Reinforcement Learning, die Suche und Lernen kombinieren
Verwandte Technologien
- UCT
- POMCP
- AlphaZero
- Progressive Widening
- Upper Confidence Bound (UCB1)
Verwandte Begriffe
- Markov Decision Process (MDP)
- Partially Observable Markov Decision Process (POMDP)
- Belief-Space Planning
- Task and Motion Planning
- Robotic information gathering
- Reinforcement Learning
Verwandte Projekte
- 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
Videos
- Monte Carlo Tree Search: John Levine
- AI 101: Monte Carlo Tree Search: AI and Games