Planejamento (Simbólico)

O que é planejamento simbólico (clássico)?

Planejamento simbólico (symbolic planning) (frequentemente chamado de planejamento clássico (classical planning)) é a parte da IA Clássica / Simbólica que calcula uma sequência de ações que transforma um estado inicial do mundo em outro que satisfaça um objetivo. Ele pressupõe que o mundo pode ser descrito com símbolos (fatos como at(robot, room1)), e que ações têm pré-condições e efeitos (por exemplo: “para mover, você deve estar na sala de origem; depois disso, você está na sala de destino”).

Em sua formulação padrão (clássica), o planejamento é:

• Determinístico: ações têm resultados previsíveis.
• Totalmente observável: o agente conhece o estado atual.
• Estático durante o planejamento: o mundo não muda de forma inesperada.
• Discreto: estados e ações são simbólicos e finitos (após o aterramento).

Essas suposições são fortes, mas fazem do planejamento uma abstração poderosa e amplamente usada — especialmente quando combinada com boas heurísticas e busca eficiente.

O planejamento simbólico está fortemente conectado a:

• Representação de Conhecimento (como estados/ações são representados)
• algoritmos de busca (planejamento costuma ser “busca no espaço de estados”)
• Satisfação de Restrições e codificações SAT/SMT (o planejamento pode ser compilado em restrições)
• heurísticas práticas, abordadas com mais profundidade em Planejamento Heurístico
• representações como STRIPS & PDDL

Formulação central: estados, ações, objetivos e planos

Um problema de planejamento clássico é comumente definido como uma tupla:

• Estados: cada estado é um conjunto de predicados aterrados (fatos) que são verdadeiros.
• Estado inicial (s_0): os fatos verdadeiros no início.
• Ações (A): cada ação tem:
  • Pré-condições: fatos que devem ser verdadeiros para aplicar a ação
  • Efeitos: fatos que se tornam verdadeiros/falsos após aplicá-la
• Condição de objetivo (G): um conjunto (ou fórmula) de fatos que devem valer.
• Opcionalmente: custos de ação para planejamento de custo ótimo.

Um plano é uma sequência de ações ([a_1, a_2, \dots, a_n]) tal que aplicá-las a partir de (s_0) produz um estado que satisfaz (G).

Semântica de transição (estilo STRIPS)

No modelo STRIPS clássico:

• Pré-condições: (Pre(a))
• Efeitos de adição: (Add(a))
• Efeitos de remoção: (Del(a))

Se (Pre(a) \subseteq s), então aplicar (a) produz:

[ \gamma(s, a) = (s \setminus Del(a)) \cup Add(a) ]

Essa semântica simples baseada em conjuntos é uma das razões pelas quais o planejamento STRIPS escala bem e dá suporte a heurísticas fortes.

Um exemplo concreto: um minúsculo domínio de “entrega por robô”

Imagine um robô que deve entregar um pacote de room1 para room2.

Conceitos do domínio (informal)

Fatos:

• at(robot, r)
• at(pkg, r)
• carrying(pkg)

Ações:

• move(r1, r2)
• pick(pkg, r)
• drop(pkg, r)

Um plano poderia ser:

1. pick(pkg, room1)
2. move(room1, room2)
3. drop(pkg, room2)

Esboço mínimo no estilo PDDL

PDDL é a linguagem padrão de entrada para muitos planejadores; veja STRIPS & PDDL para detalhes.

(define (domain delivery)
  (:predicates
    (at ?x ?r)
    (carrying ?p))

  (:action move
    :parameters (?from ?to)
    :precondition (and (at robot ?from))
    :effect (and (not (at robot ?from))
                 (at robot ?to)))

  (:action pick
    :parameters (?p ?r)
    :precondition (and (at robot ?r) (at ?p ?r))
    :effect (and (not (at ?p ?r))
                 (carrying ?p)))

  (:action drop
    :parameters (?p ?r)
    :precondition (and (at robot ?r) (carrying ?p))
    :effect (and (not (carrying ?p))
                 (at ?p ?r))))

Um problema correspondente especificaria os objetos, os fatos iniciais e um objetivo como (at pkg room2).

Mesmo em exemplos pequenos, o planejamento captura estrutura de longo horizonte: você não pode soltar o pacote em room2 a menos que primeiro se mova até lá, e você não pode se mover com o pacote a menos que o tenha pegado.

Planejamento como busca

Uma visão amplamente usada é: planejamento = busca em grafo em que

• nós são estados
• arestas são ações
• o objetivo é encontrar um caminho de (s_0) até qualquer estado que satisfaça (G)

Isso conecta o planejamento diretamente a métodos de busca heurística como A* e busca gulosa best-first (frequentemente cobertos em tópicos de busca como A*).

Busca para frente vs. busca para trás

• Busca para frente (progressão): começa em (s_0), aplica ações aplicáveis, busca até o objetivo valer.
• Busca para trás (regressão): começa a partir da condição de objetivo e raciocina para trás sobre o que deve ter sido verdadeiro antes da última ação.

Muitos planejadores modernos usam busca para frente porque ela interage bem com avaliação heurística (estimativa de distância até o objetivo a partir de um estado).

Tamanho do espaço de estados e aterramento

Um desafio prático é que ações PDDL são tipicamente elevadas (lifted) (com parâmetros), mas a busca precisa de ações aterradas (ground) (com objetos concretos). Aterrar todas as ações de forma ingênua pode explodir combinatoriamente.

Por isso, planejadores usam técnicas como:

• análise de relevância (ignorar fatos/ações inalcançáveis)
• aterramento preguiçoso / aterramento parcial
• detecção de invariantes e poda
• codificações compactas de estado (bitsets para predicados)

Complexidade computacional (por que heurísticas importam)

O planejamento clássico é computacionalmente difícil:

• Existência de plano para planejamento proposicional no estilo STRIPS é PSPACE-completa em geral.
• Muitas versões limitadas (bounded) são NP-completas.

Na prática, grandes ganhos vêm de:

• heurísticas independentes de domínio fortes
• compilação e poda cuidadosas
• estruturas de dados eficientes

Por isso o planejamento simbólico frequentemente é discutido junto com Planejamento Heurístico.

Representações de plano: planos sequenciais vs. planos de ordem parcial

O plano mais simples é uma ordem total (uma sequência). Outra representação importante é um plano de ordem parcial, que especifica apenas as restrições necessárias de ordenação entre ações.

• O planejamento de ordem parcial pode representar concorrência e a estrutura de “mínimo compromisso”.
• Muitos planejadores clássicos modernos ainda produzem planos sequenciais, mesmo que internamente explorem ordenação parcial.

Ideias relacionadas também aparecem em escalonamento, planejamento temporal e planejamento hierárquico (além do escopo estrito “clássico”).

Heurísticas para planejamento clássico

Heurísticas estimam “quão longe” um estado está do objetivo. Elas tornam a busca viável ao guiar a exploração em direção a estados promissores.

Dois conceitos-chave:

• Heurística admissível (admissible heuristic): nunca superestima o custo real restante (permite optimalidade com A*).
• Heurística inadmissível (inadmissible heuristic): pode superestimar, mas frequentemente acelera o planejamento de forma dramática.

Relaxamento de deleção (a ideia central)

Muitas heurísticas de planejamento são baseadas em relaxar o problema. O relaxamento mais famoso é o relaxamento de deleção (delete relaxation): ignorar efeitos negativos (de remoção) das ações.

Intuição: se as ações apenas adicionam fatos e nunca os removem, o problema fica mais fácil, e podemos computar distâncias aproximadas.

Heurísticas comuns derivadas do relaxamento de deleção incluem:

• (h_{\max}): o custo de uma conjunção é o custo máximo de seus subobjetivos.
• (h_{\text{add}}): assume que subobjetivos são independentes e soma seus custos.
• Heurística FF ((h_{\text{FF}})): constrói um plano relaxado e usa seu comprimento como estimativa (popular em planejadores rápidos).

Heurísticas de relaxamento de deleção tendem a ser:

• informativas em muitos domínios estruturados (logística, variações do mundo dos blocos)
• rápidas o suficiente para serem computadas repetidamente durante a busca

Limitação: elas podem ser enganadas quando remoções importam, por exemplo, restrições de recursos, exclusões mútuas ou a necessidade de “desfazer” coisas.

Grafos de planejamento e raciocínio mutex (estilo Graphplan)

Outra abordagem clássica é o grafo de planejamento (planning graph), que alterna camadas de fatos e ações e computa relações mutex (mutual exclusion) (exclusão mútua). Essa estrutura pode produzir heurísticas e pode ser usada para extrair planos (Graphplan).

A informação de mutex reintroduz parcialmente interações negativas que o relaxamento de deleção ignora.

Heurísticas de abstração e bases de padrões

Abstração mapeia um grande problema de planejamento para um menor, resolve (ou pré-computa distâncias no) espaço menor e usa essa distância como heurística.

• Bases de padrões (PDBs) (pattern databases) pré-computam distâncias exatas para um problema abstraído (por exemplo, rastrear apenas um subconjunto de variáveis).
• Frequentemente admissíveis e poderosas quando existem boas abstrações.
• Amplamente usadas em domínios do tipo quebra-cabeça e em planejamento ótimo.

Marcos

Um marco (landmark) é um fato (ou ação) que deve ser alcançado (ou executado) em todo plano válido.

Heurísticas baseadas em marcos:

• contam marcos restantes
• estimam ordenação entre eles

Elas podem fornecer forte orientação global mesmo quando heurísticas locais baseadas em planos relaxados têm dificuldade.

Principais arquiteturas de planejadores na prática

Planejadores clássicos modernos normalmente são construídos em torno de algumas arquiteturas recorrentes:

Busca heurística para frente (a mais comum)

Pipeline:

1. analisar (parse) domínio/problema
2. pré-processar (aterramento, invariantes, simplificação)
3. buscar a partir do estado inicial usando uma heurística (h(s))

Estratégias de busca comuns:

• Busca gulosa best-first (greedy best-first search) (rápida, não ótima)
• A* ponderado (Weighted A*) (troca optimalidade por velocidade)
• A* (ótima com heurísticas admissíveis, frequentemente cara)

Planejamento como satisfatibilidade (SATPlan e além)

O planejamento pode ser compilado em um problema SAT por:

• escolher um horizonte (T)
• criar variáveis para quais fatos/ações valem em cada passo de tempo
• adicionar restrições para pré-condições/efeitos de ações e axiomas de quadro (frame axioms)
• perguntar ao resolvedor SAT: “existe um plano de comprimento (T)?”

Então aumentar (T) até ser satisfatível.

Isso conecta o planejamento a Satisfação de Restrições e abordagens de resolução SAT. O planejamento baseado em SAT pode ser muito forte para certos problemas estruturados, embora a busca heurística no espaço de estados frequentemente seja melhor para domínios de longo horizonte.

Planejamento baseado em restrições e escalonamento

Se você adicionar:

• tempo, durações
• capacidades de recursos
• quantidades numéricas

o problema começa a se parecer com planejamento + escalonamento, frequentemente resolvido via programação por restrições, MILP ou métodos híbridos. Embora isso vá além do “planejamento clássico puro”, é um passo comum no mundo real.

Aplicações práticas

Apesar das suposições clássicas, o planejamento simbólico é usado em muitos sistemas reais, frequentemente com replanejamento ou monitoramento de execução para lidar com incerteza.

Robótica e planejamento de tarefas

Robôs frequentemente separam:

• planejamento de tarefas (simbólico: pegar, colocar, navegar)
• planejamento de movimento (geometria contínua)

Um planejador simbólico pode decidir o que fazer; um planejador de movimento decide como se mover com segurança. Quando o planejamento de movimento falha, o sistema pode replanejar no nível simbólico (por exemplo, escolher uma preensão diferente ou uma ordem diferente de ações).

Logística, armazenagem e operações

O planejamento clássico se ajusta bem a:

• mover itens entre locais
• decisões de agrupamento e roteamento (às vezes com otimização adicional)
• fluxos de trabalho automatizados de armazéns (separar/embalar/enviar)

Mesmo quando o mundo real é estocástico, planos determinísticos fornecem uma base forte e podem ser adaptados online.

Automação de TI e orquestração de workflows

Modelos de planejamento se mapeiam bem para:

• pré-condições = requisitos do estado do sistema (serviço ativo, dependência disponível)
• ações = scripts ou chamadas de API (implantar, reiniciar, migrar)
• objetivos = configuração desejada

O modelo simbólico fornece sequências de ações explicáveis e auditáveis — frequentemente preferíveis a políticas puramente aprendidas em operações críticas para segurança.

IA para jogos e planejamento narrativo

Em jogos, planejadores simbólicos podem gerar:

• sequências de comportamento de NPC
• cadeias de missões e eventos de história
• respostas dinâmicas às ações do jogador

Como objetivos e restrições são explícitos, designers podem controlar e depurar resultados com mais facilidade do que com políticas de caixa-preta.

Orientação de modelagem: como construir um bom domínio de planejamento clássico

Na prática, o sucesso depende fortemente do modelo.

Dicas principais:

• Escolha os predicados certos: predicados muito grosseiros tornam impossível expressar restrições; predicados muito finos fazem o espaço de estados explodir.
• Mantenha as ações “honestas”: pré-condições devem impedir ações impossíveis, em vez de depender de falhas posteriores.
• Evite predicados redundantes a menos que acelerem dramaticamente as heurísticas (alguma redundância pode ajudar, mas também pode criar inconsistências).
• Explore tipos e invariantes (comuns em PDDL) para reduzir o aterramento.
• Valide com instâncias pequenas antes de escalar.
• Meça a qualidade do plano: menor comprimento de plano vs. menor custo de plano pode levar a comportamentos diferentes.

Limitações e extensões (o que o planejamento clássico não cobre)

O planejamento clássico deixa de funcionar quando as suposições falham:

• Incerteza / observabilidade parcial: requer planejamento contingente, planejamento em espaço de crença, ou frameworks como POMDPs (veja Processos de Decisão de Markov e Aprendizado por Reforço para perspectivas probabilísticas relacionadas).
• Resultados estocásticos: precisa de planejamento probabilístico.
• Tempo e recursos contínuos: precisa de planejamento temporal/numérico e escalonamento.
• Universos de objetos muito grandes: o aterramento pode se tornar intratável sem raciocínio elevado ou representações especializadas.

Ainda assim, o planejamento clássico permanece uma base fundamental: muitos planejadores avançados começam a partir de núcleos clássicos e adicionam recursos incrementalmente.

Planejamento e IA moderna: aprender a planejar vs. planejar com símbolos

Trabalhos recentes frequentemente combinam planejamento simbólico com aprendizado de máquina (machine learning):

• Heurísticas aprendidas: usam Redes Neurais para prever valores heurísticos ou preferências de ação, acelerando a busca.
• Orientação por política: uma política aprendida sugere ações promissoras; um planejador simbólico garante correção.
• Uso de ferramentas por LLM: modelos de linguagem grandes (large language models) podem propor objetivos, restrições ou rascunhar planos, enquanto um planejador simbólico verifica a viabilidade e produz sequências de ações válidas.

Essa direção híbrida é atraente porque combina:

• a confiabilidade e interpretabilidade do planejamento simbólico
• o reconhecimento de padrões e generalização de métodos baseados em aprendizado

Resumo

O planejamento simbólico (clássico) é o estudo e a prática de calcular sequências de ações que atingem objetivos em domínios determinísticos, totalmente observáveis e discretos. Ele se baseia em representações explícitas de estado/ação (frequentemente STRIPS/PDDL) e se torna prático por meio de algoritmos de busca e heurísticas fortes — especialmente métodos de relaxamento de deleção, grafos de planejamento, abstrações e marcos. Embora ambientes reais raramente sejam totalmente clássicos, o planejamento clássico permanece um motor central para planejamento de tarefas, automação e tomada de decisão explicável, e cada vez mais serve como uma espinha dorsal confiável para sistemas híbridos que incorporam aprendizado.

---