Algoritmos de Planejamento (Planejamento Automatizado)

O planejamento automatizado (automated planning) estuda como um agente pode computar uma sequência (ou ordem parcial) de ações que transforma um estado inicial do mundo em um estado que satisfaça um objetivo. No planejamento clássico (classical planning), o mundo normalmente é modelado como:

Discreto (conjunto finito de proposições/objetos)
Determinístico (as ações têm efeitos certos)
Totalmente observável
Frequentemente sem tempo (sem durações), embora muitos planejadores se estendam para variantes temporais/numéricas

Este artigo apresenta as principais famílias de algoritmos usadas no planejamento clássico/simbólico — como funcionam, quando funcionam bem e como se conectam a representações comuns de planejamento como STRIPS e PDDL e ao design de heurísticas (ver Planejamento Heurístico).

Configuração do problema de planejamento (clássico)

Uma tarefa de planejamento clássico é frequentemente definida como uma tupla ((S, A, s_0, G)):

(S): conjunto de estados (cada estado é uma atribuição de proposições)
(A): ações/operadores (pré-condições e efeitos)
(s_0): estado inicial
(G): condição de objetivo (conjunto de proposições que devem ser verdadeiras)

Em uma forma do tipo STRIPS, uma ação (a) tem:

Pré-condições (pre(a))
Efeitos de adição (add(a))
Efeitos de deleção (del(a))

Aplicar uma ação atualiza o estado: [ s' = (s \setminus del(a)) \cup add(a) ] se (pre(a) \subseteq s).

Exemplo prático (mini STRIPS no estilo logística)

Um robô pode se mover entre salas e carregar um pacote:

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

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

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

Esta é a camada de representação; a camada algorítmica decide como buscar por um plano de forma eficiente.

Principais trade-offs algorítmicos

Algoritmos de planejamento são comumente avaliados ao longo de alguns eixos:

Completude: se um plano existe, o algoritmo encontrará um (dado tempo/memória suficientes)?
Otimalidade: ele encontrará um plano mais curto (ou de menor custo)?
Escalabilidade: quão bem ele lida com grandes espaços de estados e muitos objetos/ações?
Expressividade: consegue lidar com linguagens mais ricas (efeitos condicionais, quantificadores, fluentes numéricos, tempo)?
Comportamento a qualquer momento / satisfatório: consegue encontrar rapidamente um plano e depois melhorá-lo?

Uma realidade central: mesmo o planejamento clássico é PSPACE-completo em geral. Por isso, planejadores práticos dependem fortemente de estrutura, heurísticas e truques de compilação.

Família 1: Busca no espaço de estados (state-space search) (para frente e para trás)

O planejamento no espaço de estados reduz o planejamento a uma busca em grafos: nós são estados, arestas são ações. Isso conecta o planejamento diretamente a métodos como Busca A* (A* Search) e busca heurística best-first.

Busca para frente (forward search) (progressão (progression))

Ideia: começar do estado inicial e aplicar ações aplicáveis até o objetivo ser satisfeito.

Nó: um estado concreto do mundo (s)
Sucessores: (Result(s, a)) para todas as ações (a) aplicáveis em (s)
Teste de objetivo: (G \subseteq s)

Pontos fortes

Simples conceitualmente e em termos de implementação
Funciona bem com heurísticas fortes (abordagem dominante em muitos planejadores clássicos modernos)
Natural para simulação e monitoramento de execução

Desafios

Grande fator de ramificação (branching factor) quando muitas ações são aplicáveis
Estados duplicados são comuns → precisa de hashing (hashing) / listas fechadas (closed lists)
Sem boas heurísticas, rapidamente se torna inviável

Algoritmos típicos

Busca em largura (completa, ótima para custos unitários, mas pesada em memória)
Custo uniforme / Dijkstra (ótimo, mas frequentemente lento demais)
Busca A* (A* Search) (ótima com heurísticas admissíveis; ainda pode ser pesada em memória)
Busca gulosa best-first (GBFS) (greedy best-first search) (satisfatória e rápida; não é ótima)
Busca A* ponderada (Weighted A*) (trade-off ajustável entre velocidade e subotimalidade)

Busca para trás (backward search) (regressão (regression))

Ideia: buscar para trás a partir do objetivo raciocinando sobre quais ações poderiam tê-lo produzido.

Nó: uma condição de objetivo (conjunto de proposições requeridas), não um estado completo
Passo de regressão: substituir alguns literais de objetivo pelas pré-condições de uma ação, levando em conta o que a ação alcança e o que ela não destrói

Intuitivamente, a regressão tenta responder: “O que precisava ser verdade antes da última ação?”

Pontos fortes

Às vezes reduz a ramificação: condições de objetivo podem ser menores do que estados completos
Pode ser eficaz quando os objetivos são restritos e informativos

Desafios

Tratar pré-condições negativas e efeitos de deleção com cuidado
Interações entre subobjetivos: regredir diferentes literais de objetivo pode introduzir conflitos
Em muitos domínios STRIPS, a busca para frente com boas heurísticas tende a vencer

Heurísticas na busca no espaço de estados (por que elas importam)

A diferença entre “problema de brinquedo resolvido” e “escala industrial resolvida” tipicamente é a heurística.

Famílias comuns de heurísticas incluem:

Heurísticas de relaxamento de deleção (delete-relaxation heuristics) (ignorar efeitos de deleção): gera heurísticas como (h_{max}), (h_{add}) e a heurística de plano relaxado (relaxed-plan heuristic) do FF
Heurísticas de marcos (landmark heuristics): identificam proposições/ações que devem ocorrer em qualquer plano válido
Bancos de dados de padrões (pattern databases): pré-computam distâncias em abstrações do espaço de estados
Heurísticas de grafo de planejamento (planning-graph heuristics): derivadas de grafos de planejamento (ver próxima seção)

Elas são tratadas com mais profundidade em Planejamento Heurístico, mas o ponto-chave é que busca para frente + heurística forte é um baseline dominante no planejamento clássico.

Família 2: Grafos de planejamento e planejamento no estilo Graphplan (Graphplan-style planning)

Grafos de planejamento (planning graphs) fornecem uma representação compacta, em camadas, de alcançabilidade ao longo do tempo. Eles foram popularizados pelo Graphplan e continuam importantes porque:

permitem detectar eficientemente certas impossibilidades (via restrições mutex),
dão suporte à extração de planos,
e inspiram heurísticas eficazes.

Estrutura do grafo de planejamento

Um grafo de planejamento alterna entre:

Camadas de proposições (P_0, P_1, \dots)
Camadas de ações (A_0, A_1, \dots)

Onde:

(P_0) é o conjunto de proposições verdadeiras no estado inicial.
(A_i) contém todas as ações cujas pré-condições estão em (P_i).
(P_{i+1}) contém a união dos efeitos das ações em (A_i).
Ações no-op (no-op actions) carregam proposições para frente para camadas posteriores.

Relações mutex (exclusão mútua (mutual exclusion))

O Graphplan rastreia pares de ações ou proposições que não podem ambos valer na mesma camada:

Mutex de ação: necessidades concorrentes, efeitos inconsistentes, interferência (uma deleta a pré-condição/efeito da outra)
Mutex de proposição: se todas as formas de alcançá-las são mutex par a par

Mutexes são sinais de poda poderosos: mesmo que cada literal de objetivo apareça em uma camada, eles podem ser mutuamente exclusivos e, portanto, não alcançáveis em conjunto naquele “passo de tempo”.

Extração de plano

Quando todos os literais de objetivo aparecem em alguma camada de proposições sem mutex, o Graphplan tenta extrair um plano por seleção reversa de ações de suporte, usando backtracking com restrições mutex.

Pontos fortes

Bom em identificar cedo objetivos inalcançáveis
Dá suporte naturalmente a planos paralelos (parallel plans) (ações na mesma camada podem ocorrer concorrentemente se não interferirem)
Fornece estimativas heurísticas (por exemplo, o primeiro nível em que os objetivos aparecem)

Desafios

Grafos de planejamento podem crescer muito
A extração de planos ainda pode ser exponencial no pior caso
Muitos planejadores modernos usam grafos de planejamento mais como maquinário de heurística do que como solucionador central

Uso prático: heurísticas derivadas de grafos de planejamento

Exemplos:

Custo de nível (level cost): primeira camada em que uma proposição aparece
Set-level: primeira camada em que todas as proposições de objetivo aparecem sem mutex
Aproximações do comprimento do plano relaxado (relaxed plan length)

O conhecido planejador FF usa um grafo de planejamento relaxado (relaxed planning graph) para computar uma heurística rápida e informativa (e então realiza busca heurística para frente).

Família 3: Planejamento baseado em SAT/SMT e CSP (SAT/SMT- and CSP-based planning) (planejamento como satisfação de restrições)

Em vez de buscar diretamente no espaço de estados, o planejamento baseado em restrições codifica o planejamento como um problema de decisão: “Existe um plano de comprimento (k)?” Isso é chamado de planejamento limitado (bounded planning).

SATPlan: planejamento como satisfatibilidade booleana (Boolean satisfiability)

Para um horizonte (k), introduza variáveis booleanas como:

(At(p, t)): a proposição (p) vale no tempo (t)
(Do(a, t)): a ação (a) ocorre no tempo (t)

Então, adicione restrições para:

Estado inicial: fatos em (t=0)
Objetivo: fatos de objetivo em (t=k)
Pré-condições de ação: (Do(a,t) \Rightarrow pre(a,t))
Efeitos de ação: (Do(a,t) \Rightarrow effects(a,t+1))
Axiomas de quadro (frame axioms) (inércia (inertia)): fatos persistem a menos que sejam mudados
Mutex / exclusão: impedir ações concorrentes incompatíveis (dependendo da semântica paralela/sequencial)

Um solucionador SAT (SAT solver) é então usado para encontrar uma atribuição satisfatória, que corresponde a um plano.

Propriedades

Para (k) fixo: a resolução de SAT é NP-completa, mas solucionadores SAT modernos são extremamente otimizados.
Para obter completude: aumente (k) (0, 1, 2, …) até que um plano seja encontrado ou que um limite superior seja provado impossível.
Otimalidade (em comprimento de plano/makespan (makespan)): se você verifica (k) em ordem crescente, o primeiro plano encontrado é ótimo para essa métrica.

Planejamento baseado em SMT (SMT-based planning)

SMT estende SAT com teorias como:

aritmética linear (útil para recursos numéricos),
arrays, vetores de bits,
funções não interpretadas, etc.

Isso pode tornar as codificações mais limpas e, às vezes, mais escaláveis para domínios com restrições numéricas do que “bit-blasting (bit-blasting)” tudo em SAT.

Planejamento baseado em CSP (CSP-based planning)

Como uma formulação de Problemas de Satisfação de Restrições (Constraint Satisfaction Problems), o planejamento usa variáveis para:

ações em cada passo,
variáveis de estado ao longo do tempo (domínio finito),
restrições de ordenação (em variantes de ordem parcial).

Solucionadores CSP usam propagação (consistência de arco, filtragem de domínio) mais backtracking.

Quando o planejamento baseado em restrições brilha

Quando o horizonte (k) é pequeno/moderado, mas o espaço de estados é enorme
Quando as restrições capturam estrutura que os solucionadores exploram (simetria, propagação)
Quando o planejamento envolve restrições ricas (recursos, limites numéricos, estrutura tipo escalonamento (scheduling))

Limitações

Exige escolher/iterar um horizonte (k) (limitação por horizonte)
Codificações podem ficar muito grandes para horizontes longos
Escolhas de modelagem (estilo de mutex, axiomas de quadro) afetam drasticamente o desempenho

Família 4: Planejamento no espaço de planos (plan-space) (planejamento de ordem parcial (partial-order) )

O planejamento no espaço de planos busca no espaço de planos parciais, não em trajetórias completas de estados. A marca registrada é o princípio do menor comprometimento (least-commitment principle): adiar decisões (como ordenações exatas de ações) até que seja necessário.

Ideias centrais

Um plano de ordem parcial tipicamente inclui:

Um conjunto de ações (passos)
Restrições de ordenação: (a \prec b) significando que (a) deve ocorrer antes de (b)
Elos causais (causal links): (a \xrightarrow{p} b) significando que a ação (a) estabelece a condição (p) para a ação (b)
Um conjunto de pré-condições em aberto (open preconditions) (falhas (flaws) a resolver)

O plano começa com duas ações fictícias:

Start: efeitos = estado inicial
Finish: pré-condições = objetivo

O planejamento prossegue corrigindo falhas:

Escolher uma pré-condição em aberto (p) de algum passo (b).
Selecionar uma ação (a) que possa alcançar (p).
Adicionar (a) (se for nova), adicionar a ordenação (a \prec b) e adicionar um elo causal (a \xrightarrow{p} b).
Detectar e resolver ameaças (threats): alguma ação (c) pode negar (p) entre (a) e (b). Resolver por promoção (promotion) ((b \prec c)) ou rebaixamento (demotion) ((c \prec a)), ou outras restrições.

Pontos fortes

Produz planos flexíveis em que algumas ações podem ser reordenadas no momento da execução
Natural para problemas em que a ordenação não é totalmente determinada
Historicamente influente (UCPOP e sistemas relacionados)

Desafios

Detecção de ameaças e seleção de falhas podem ser custosas
Muitas vezes menos competitivo do que a busca heurística para frente em domínios padrão de benchmark (embora possa ser forte em certas tarefas estruturadas)
Estender para planejamento numérico/temporal requer mais mecanismos

Onde o planejamento de ordem parcial é útil

Domínios que enfatizam concorrência (concurrency) e flexibilidade de ordenação
Reuso de planos e explicação: elos causais fornecem estrutura interpretável (“por que este passo está aqui?”)
Alguma integração com escalonamento e monitoramento de execução

Escolhendo entre famílias de algoritmos

Nenhuma abordagem domina em todos os lugares. Padrões típicos de decisão:

Precisa de um plano rápido (satisfatório), domínio STRIPS/PDDL clássico
→ Busca heurística para frente (GBFS, heurísticas no estilo FF)
Precisa de plano ótimo em comprimento ou custo (e tamanhos de problema são moderados)
→ Busca A* com heurísticas admissíveis; ou SAT/CSP com horizonte crescente; ou planejadores ótimos especializados
Paralelismo forte / minimização de makespan
→ Métodos de grafo de planejamento ou codificações SAT que modelam concorrência
Restrições ricas (recursos numéricos, restrições rígidas de escalonamento)
→ Formulações SMT/CSP (ou planejadores temporais/numéricos, além do clássico puro)
Precisa de ordem parcial flexível, explicação ou menor comprometimento
→ Planejamento no espaço de planos (planejamento de ordem parcial)

Relação com representações (STRIPS/PDDL) e compilação

Algoritmos de planejamento dependem fortemente de como o domínio é representado. Em domínios no estilo PDDL (ver STRIPS e PDDL), recursos como:

Efeitos condicionais
Quantificadores
Predicados derivados
Pré-condições negativas
Custos de ação

podem ser tratados nativamente ou via compilação (transformação para operadores mais simples, do tipo STRIPS). Compilações podem aumentar o número de ações ou proposições, afetando a busca.

De modo similar, abordagens baseadas em restrições frequentemente se beneficiam de codificações que minimizam:

restrições de quadro redundantes,
escolhas simétricas de ações,
concorrência desnecessária.

Completude e otimalidade na prática

É útil distinguir garantias teóricas de como planejadores são comumente usados:

Planejadores completos existem (por exemplo, busca em largura em espaços finitos de estados, Busca A* sob condições apropriadas, SATPlan com (k) crescente), mas podem ser lentos demais para instâncias grandes.
Planejadores ótimos existem (Busca A*, custo uniforme, aprofundamento iterativo em custo, SAT limitado com horizonte crescente), mas a otimalidade tipicamente custa caro.
Muitos planejadores amplamente usados são satisfatórios (satisficing): eles visam encontrar planos bons o suficiente rapidamente, frequentemente refinando-os depois (comportamento a qualquer momento (anytime behavior)).

Em benchmarks e sistemas reais, planejamento satisfatório é comum porque:

modelos são imperfeitos,
o replanejamento é frequente,
“rápido e adequado” vence “lento e ótimo”.

Aplicações práticas

Embora o planejamento clássico seja uma abstração, essas ideias algorítmicas aparecem amplamente:

Planejamento de tarefas em robótica: gerar sequências de ações de alto nível (pegar, colocar, mover) antes do planejamento de movimento; frequentemente combinado com replanejamento.
Logística e armazenagem: roteamento, carregamento/descarregamento, sequenciamento com restrições.
Fluxos de trabalho automatizados e orquestração de TI: ações são chamadas de serviço com pré-condições/efeitos.
IA para jogos: planejamento simbólico de ações para comportamento de NPCs e perseguição de objetivos.
Síntese de programas e automação: busca do tipo planejamento sobre transformações para atingir uma especificação desejada (conceitualmente relacionado mesmo quando não codificado como STRIPS).

Para tomada de decisão sob incerteza, planejadores tipicamente migram para modelos probabilísticos como Processos de Decisão de Markov (Markov Decision Processes), mas o planejamento clássico ainda frequentemente serve como uma espinha dorsal determinística rápida.

Resumo

Algoritmos de planejamento automatizado se agrupam em algumas famílias centrais:

Busca no espaço de estados para frente/para trás: trata planejamento como busca em grafo; o desempenho depende de heurísticas.
Grafos de planejamento (Graphplan): alcançabilidade em camadas + raciocínio por mutex; também uma fonte rica de heurísticas.
Planejamento baseado em SAT/SMT/CSP: reduz planejamento a satisfação de restrições, tipicamente via horizontes limitados; forte para restrições estruturadas e makespan/comprimento ótimo em horizontes pequenos.
Planejamento no espaço de planos (ordem parcial): busca sobre planos parcialmente ordenados usando elos causais e resolução de ameaças; enfatiza menor comprometimento e flexibilidade.

Em todas as famílias, a principal lição prática é que escolhas de representação e de heurística/codificação frequentemente importam tanto quanto o algoritmo subjacente. Para um mergulho mais profundo na construção de heurísticas e relaxamentos que impulsionam muitos planejadores modernos, veja Planejamento Heurístico.