Monte Carlo Tree Search
- Detto anche: MCTS
- Categoria: Planning & manipulation › Task-level
- Tag: planning, tree-search, decision-making, pomdp, sampling-based
Un algoritmo di pianificazione online che fa crescere un albero di ricerca simulando molte traiettorie a partire da un modello e ne usa i ritorni per scegliere l'azione più promettente.
Definizione
Ricerca ad albero Monte Carlo (Monte Carlo tree search, MCTS) è una famiglia di algoritmi di pianificazione che decidono cosa fare dopo costruendo un albero di ricerca in modo incrementale a partire da esperienza simulata. Ogni iterazione ha quattro passi: la selezione scende lungo l'albero dallo stato corrente, scegliendo i figli con una regola che bilancia le azioni con un valore stimato alto e le azioni provate solo poche volte; l'espansione aggiunge uno o più nuovi nodi; la simulazione (o rollout) stima il valore del nuovo nodo, classicamente eseguendo una policy casuale o una semplice policy predefinita fino alla fine dell'episodio; e la retropropagazione aggiorna i conteggi delle visite e le stime di valore di ogni nodo del percorso. Esaurito il budget di tempo o di iterazioni, l'algoritmo si impegna sull'azione radice più visitata o con il valore migliore, quindi ripete dallo stato successivo. Il termine è stato introdotto da Rémi Coulom nel 2006, e nello stesso anno Kocsis e Szepesvári hanno pubblicato UCT (Upper Confidence bounds applied to Trees), che usa la regola di bandit UCB1 per la selezione ed è la variante più usata.
La MCTS ha bisogno solo di un modello generativo: un simulatore che, dati uno stato e un'azione, restituisce uno stato successivo campionato e una ricompensa. Non richiede una matrice di transizione esplicita, un modello differenziabile né un'euristica scritta a mano, ed è un algoritmo anytime: più calcolo dà decisioni migliori e la ricerca può essere fermata ogni volta che serve una risposta. In condizioni adeguate UCT converge all'azione ottima al crescere del numero di simulazioni, ma in pratica la qualità di una decisione dipende molto dal budget, dalla policy di rollout e da come viene guidata la ricerca. AlphaGo e AlphaZero hanno mostrato che sostituire i rollout casuali con stime di valore apprese e usare una policy appresa per orientare la selezione rende la ricerca molto più efficiente.
In robotica la MCTS si usa per decisioni su un orizzonte in cui gli esiti sono incerti. POMCP e la sua variante POUCT estendono UCT ai problemi parzialmente osservabili cercando su storie di azioni e osservazioni, il che li rende solver comuni per formulazioni POMDP di ricerca di oggetti, percezione attiva e raccolta di informazioni. Stati e azioni continui richiedono attenzione in più: l'allargamento progressivo (progressive widening) aggiunge nuove azioni figlie o osservazioni campionate solo man mano che cresce il conteggio delle visite di un nodo, e molti sistemi robotici cercano invece su un insieme discreto di macro-azioni o primitive di movimento, mentre pianificatori di livello inferiore gestiscono il moto continuo.
Perché è importante
Molte decisioni di un robot, come dove guardare dopo o quale oggetto spostare per primo, hanno esiti che si vedono solo diversi passi più avanti e dipendono da osservazioni incerte. La MCTS offre un modo pratico di pianificare su questi orizzonti con nient'altro che un simulatore, e scala a problemi in cui risolvere offline l'intero MDP o POMDP è fuori portata.
Applicazioni principali
- Ricerca di oggetti e percezione attiva formulate come POMDP
- Pianificazione di compiti e movimenti, scegliendo l'ordine delle azioni simboliche
- Decisioni per la guida autonoma agli incroci e nelle immissioni
- Coordinamento ed esplorazione multi-robot
- Pianificazione con modelli appresi, come nei sistemi alla AlphaZero
In pratica
Un manipolatore mobile deve trovare diversi oggetti in una stanza ingombra. Il team modella il compito come un POMDP con una credenza sulle posizioni degli oggetti, macro-azioni per spostarsi verso punti di vista e un'azione di rilevamento, e un modello di osservazione per la telecamera. A ogni decisione POUCT esegue alcune migliaia di simulazioni dalla credenza corrente entro un budget di tempo fisso, usando il modello generativo per campionare posizioni degli oggetti e rilevamenti. Il robot esegue l'azione radice con il valore più alto, aggiorna la credenza con il risultato reale del rilevamento e ripianifica. Gli ingegneri regolano la costante di esplorazione, la policy di rollout e l'orizzonte di ricerca, e mantengono l'insieme di macro-azioni abbastanza piccolo da permettere all'albero di crescere in profondità entro il budget.
Idee sbagliate comuni
- La MCTS è un algoritmo di apprendimento — è un metodo di pianificazione che richiede un modello o un simulatore; spesso è combinata con reti di valore e di policy apprese, ma la ricerca in sé non apprende una policy
- La MCTS richiede rollout casuali fino alla fine dell'episodio — i rollout possono usare invece policy euristiche, orizzonti troncati o una funzione di valore appresa
- La MCTS funziona direttamente su azioni continue — UCT standard presuppone un insieme finito di azioni, quindi i problemi continui richiedono allargamento progressivo, campionamento o un insieme discreto di macro-azioni
- La MCTS trova l'azione ottima — converge verso di essa solo al crescere delle simulazioni; con un budget in tempo reale il risultato è approssimato e dipende da come viene guidata la ricerca
Chi dovrebbe saperlo
- Ingegneri della pianificazione e del processo decisionale
- Ricercatori che lavorano su POMDP e percezione attiva
- Sviluppatori di pianificazione di compiti e movimenti
- Professionisti dell'apprendimento per rinforzo che combinano ricerca e apprendimento
Tecnologie correlate
- UCT
- POMCP
- AlphaZero
- Allargamento progressivo (Progressive Widening)
- Upper Confidence Bound (UCB1)
Termini correlati
- Markov Decision Process (MDP)
- Partially Observable Markov Decision Process (POMDP)
- Belief-Space Planning
- Task and Motion Planning
- Robotic information gathering
- Reinforcement Learning
Progetti correlati
- 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
Video
- Monte Carlo Tree Search: John Levine
- AI 101: Monte Carlo Tree Search: AI and Games