Open Source Robotics

Uma coleção selecionada de projetos, ferramentas e software de robótica de código aberto de alta qualidade.

Monte Carlo Tree Search

  • Também chamado: MCTS
  • Categoria: Planning & manipulation › Task-level
  • Tags: planning, tree-search, decision-making, pomdp, sampling-based

Um algoritmo de planejamento online que faz crescer uma árvore de busca simulando muitas trajetórias a partir de um modelo e usa seus retornos para escolher a ação mais promissora.

Definição

Busca em árvore de Monte Carlo (Monte Carlo tree search, MCTS) é uma família de algoritmos de planejamento que decidem o que fazer em seguida construindo uma árvore de busca de forma incremental a partir de experiência simulada. Cada iteração tem quatro etapas: a seleção percorre a árvore para baixo a partir do estado atual, escolhendo os filhos por uma regra que equilibra ações com valor estimado alto e ações experimentadas apenas poucas vezes; a expansão adiciona um ou mais nós novos; a simulação (ou rollout) estima o valor do novo nó, classicamente executando uma política aleatória ou uma política padrão simples até o fim do episódio; e a retropropagação atualiza as contagens de visitas e as estimativas de valor de cada nó do caminho. Quando o orçamento de tempo ou de iterações se esgota, o algoritmo se compromete com a ação raiz mais visitada ou de melhor valor e repete o processo a partir do estado seguinte. O termo foi introduzido por Rémi Coulom em 2006, e no mesmo ano Kocsis e Szepesvári publicaram o UCT (Upper Confidence bounds applied to Trees), que usa a regra de bandit UCB1 na seleção e é a variante mais usada.

A MCTS precisa apenas de um modelo gerador: um simulador que, dados um estado e uma ação, retorna um próximo estado amostrado e uma recompensa. Ela não precisa de uma matriz de transição explícita, de um modelo diferenciável nem de uma heurística escrita à mão, e é um algoritmo anytime: mais computação gera decisões melhores, e a busca pode ser interrompida sempre que uma resposta for necessária. Sob condições adequadas, o UCT converge para a ação ótima à medida que o número de simulações cresce, mas, na prática, a qualidade de uma decisão depende muito do orçamento, da política de rollout e de como a busca é guiada. AlphaGo e AlphaZero mostraram que substituir os rollouts aleatórios por estimativas de valor aprendidas e usar uma política aprendida para enviesar a seleção torna a busca muito mais eficiente.

Na robótica, a MCTS é usada para decisões ao longo de um horizonte em que os resultados são incertos. O POMCP e sua variante POUCT estendem o UCT a problemas parcialmente observáveis buscando sobre históricos de ações e observações, o que os torna solvers comuns para formulações POMDP de busca de objetos, percepção ativa e coleta de informação. Estados e ações contínuos exigem cuidado extra: o alargamento progressivo (progressive widening) adiciona novas ações filhas ou observações amostradas somente à medida que a contagem de visitas de um nó cresce, e muitos sistemas robóticos buscam, em vez disso, sobre um conjunto discreto de macroações ou primitivas de movimento, enquanto planejadores de nível mais baixo cuidam do movimento contínuo.

Por que importa

Muitas decisões de um robô, como para onde olhar em seguida ou qual objeto mover primeiro, têm resultados que só aparecem vários passos depois e dependem de observações incertas. A MCTS oferece uma forma prática de planejar ao longo desses horizontes com nada além de um simulador, e escala para problemas em que resolver o MDP ou o POMDP completo offline está fora de alcance.

Principais aplicações

  • Busca de objetos e percepção ativa formuladas como POMDPs
  • Planejamento de tarefas e movimentos, escolhendo a ordem das ações simbólicas
  • Tomada de decisão para direção autônoma em cruzamentos e convergências de faixas
  • Coordenação e exploração multirrobô
  • Planejamento com modelos aprendidos, como em sistemas no estilo do AlphaZero

Na prática

Um manipulador móvel precisa encontrar vários objetos em um cômodo desarrumado. A equipe modela a tarefa como um POMDP com uma crença sobre as posições dos objetos, macroações para se deslocar até pontos de vista e uma ação de detecção, além de um modelo de observação para a câmera. A cada decisão, o POUCT executa alguns milhares de simulações a partir da crença atual dentro de um orçamento de tempo fixo, usando o modelo gerador para amostrar posições de objetos e detecções. O robô executa a ação raiz de maior valor, atualiza sua crença com o resultado real da detecção e planeja de novo. Os engenheiros ajustam a constante de exploração, a política de rollout e o horizonte de busca, e mantêm o conjunto de macroações pequeno o bastante para que a árvore possa crescer em profundidade dentro do orçamento.

Equívocos comuns

  • A MCTS é um algoritmo de aprendizado — é um método de planejamento que precisa de um modelo ou simulador; costuma ser combinada com redes de valor e de política aprendidas, mas a busca em si não aprende uma política
  • A MCTS exige rollouts aleatórios até o fim do episódio — os rollouts podem usar, em vez disso, políticas heurísticas, horizontes truncados ou uma função de valor aprendida
  • A MCTS funciona diretamente com ações contínuas — o UCT padrão pressupõe um conjunto finito de ações, então problemas contínuos precisam de alargamento progressivo, amostragem ou um conjunto discreto de macroações
  • A MCTS encontra a ação ótima — ela só converge para essa ação à medida que as simulações crescem; com um orçamento de tempo real, o resultado é aproximado e depende de como a busca é guiada

Quem deve saber

  • Engenheiros de planejamento e tomada de decisão
  • Pesquisadores que trabalham com POMDPs e percepção ativa
  • Desenvolvedores de planejamento de tarefas e movimentos
  • Profissionais de aprendizado por reforço que combinam busca e aprendizado

Tecnologias relacionadas

  • UCT
  • POMCP
  • AlphaZero
  • Alargamento progressivo (Progressive Widening)
  • Upper Confidence Bound (UCB1)

Termos relacionados

  • Markov Decision Process (MDP)
  • Partially Observable Markov Decision Process (POMDP)
  • Belief-Space Planning
  • Task and Motion Planning
  • Robotic information gathering
  • Reinforcement Learning

Projetos 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

Este site requer JavaScript. Por favor, habilite o JavaScript para explorar nossos projetos de robótica.