☆ Salvar Busca AND-OR — Busca por planejamento contingente em ambientes não determinísticos

01/14/2026

A busca AND-OR constrói um plano contingente—e não um caminho linear—modelando ao mesmo tempo as escolhas do agente (OR) e os múltiplos resultados que o agente não controla (AND). Ela é especialmente útil quando as ações são não determinísticas, isto é, quando a mesma ação pode levar a resultados diferentes.

Intuição: decidir levar ou não um guarda-chuva é sua escolha (OR). Mas, ao sair, pode chover ou não—isso você não controla (AND). A busca AND-OR não para em “não levar guarda-chuva”. Em vez disso, ela monta um plano como: “não levo, mas se chover, compro um”. Em outras palavras, ela planeja o que fazer em seguida para cada resultado possível.

As escolhas são nós OR, as ramificações de resultados são nós AND, e a árvore inteira codifica um plano contingente.

Como funciona (mecanismo e características)

OR significa “ponto de decisão sob seu controle”
- Um nó OR é um ponto em que o agente escolhe uma ação entre alternativas.
- Ele captura decisões como “ir para a esquerda ou para a direita?” onde o agente controla a escolha.
- Em um nó OR, pode bastar encontrar um bom filho para seguir em frente.
- Por isso, nós OR focam em selecionar a opção mais favorável.
AND significa “se há vários resultados, você precisa cobrir todos”
- Um nó AND representa que, após uma ação, podem ocorrer múltiplos resultados.
- Por exemplo, abrir uma porta pode resultar em “abre / não abre / dispara um alarme”.
- Em um nó AND não basta que um resultado funcione: é preciso ter continuação para todo resultado plausível.
- Assim, nós AND testam se o plano é robusto diante da incerteza.
O resultado não é um caminho, mas um conjunto de regras
- A busca clássica costuma devolver um caminho único como “A → B → C”.
- A busca AND-OR devolve “se acontecer X, faça isto; se acontecer Y, faça aquilo”.
- Logo, a resposta é um plano ramificado, e não uma rota linear.
- Em resumo: ela constrói um plano que continua mesmo quando o ambiente “surpreende”.
Ela é representada como uma árvore de busca AND-OR
- O processo é estruturado como uma árvore de busca AND-OR.
- Nós OR correspondem a escolhas de ação; nós AND correspondem a ramificações de resultados.
- Por isso, a busca vira uma árvore ramificada, e não um único caminho descendente.
- A árvore inteira codifica um plano contingente que cobre diferentes resultados possíveis.
Por que isso importa: planeja o fracasso, não apenas o sucesso
- Em problemas reais, a mesma ação nem sempre produz o mesmo resultado.
- Por isso, é preciso ter planos que continuem funcionando mesmo quando algo dá errado.
- A busca AND-OR incorpora explicitamente modos de falha na estrutura do plano.
- Essa ideia se conecta naturalmente a políticas (policy) em tomada de decisão e planejamento robótico.
Condições de sucesso: OR precisa de um, AND precisa de todos
- Em um nó OR, basta que pelo menos um filho possa levar ao sucesso.
- Em um nó AND, a ação só é segura se todas as ramificações de resultado puderem ser tratadas com sucesso.
- Quanto mais ramificações AND existirem, maior tende a ser o custo da busca.
- Essa estrutura filtra “planos que só funcionam se você der sorte”.
\[ \text{Nó OR: sucesso se um filho pode ter sucesso} \]

\[ \text{Nó AND: sucesso apenas se todos os filhos podem ter sucesso} \]

OR é “basta um ramo bom”, enquanto AND é “cobrir todos os resultados”, o que gera naturalmente planos contingentes.

Relevância e custos

A busca AND-OR é valiosa porque produz planos contingentes para ambientes em que uma ação pode levar a resultados diferentes. Isso combina com muitos cenários reais, como robótica (uma porta pode emperrar) ou interações incertas em que é preciso se preparar para várias possibilidades. A desvantagem é que, conforme aumentam as ramificações de resultado, nós AND exigem cobrir todos os casos, e o custo pode crescer rapidamente. Na prática, usam-se aproximações, profundidade limitada ou restrições do domínio para manter o problema tratável.

Leituras prévias recomendadas (3/5)

Leituras recomendadas a seguir (5/16)