Planejamento Heurístico

O que é planejamento heurístico (heuristic planning)?

Planejamento heurístico (heuristic planning) é a abordagem dominante no planejamento clássico (classical planning) — ou planejamento simbólico (symbolic planning) — para encontrar sequências de ações de forma eficiente em grandes espaços de estados. A ideia central é guiar um algoritmo de busca (search algorithm) usando uma função heurística (heuristic function) (h(s)) que estima quão “longe” um estado (s) está do objetivo. Boas heurísticas reduzem drasticamente o número de estados explorados em comparação com a busca não informada (uninformed search).

No planejamento clássico, o problema é tipicamente especificado em um formato no estilo STRIPS (STRIPS-like) ou em STRIPS e PDDL, com:

um conjunto de fatos proposicionais,
um estado inicial,
uma condição de objetivo,
ações com pré-condições (preconditions) e efeitos.

O planejamento heurístico é “prático” porque as heurísticas com melhor desempenho não são números arbitrários projetados à mão — elas frequentemente são computadas ao resolver uma versão relaxada (relaxed version) do problema de planejamento, que é mais fácil do que o original.

Cenário de planejamento clássico (brevemente)

Uma tarefa de planejamento clássico é frequentemente modelada como um problema determinístico de caminho mínimo (deterministic shortest-path problem):

Estados: conjuntos de fatos verdadeiros (hipótese de mundo fechado (closed-world assumption): fatos que não estão no conjunto são falsos).
Ações (a): têm pré-condições (\text{pre}(a)), efeitos de adição (add effects) (\text{add}(a)) e efeitos de deleção (delete effects) (\text{del}(a)).
Transição: aplicar (a) no estado (s) é possível se (\text{pre}(a)\subseteq s); o sucessor é [ s' = (s \setminus \text{del}(a)) \cup \text{add}(a). ]
Objetivo: um conjunto de fatos objetivo (G) tal que (G \subseteq s).
Custo: frequentemente custo unitário por ação, ou custos gerais por ação.

Um planejador tipicamente busca a partir do estado inicial em direção a qualquer estado objetivo (busca para frente (forward search)), embora busca para trás (backward search) (regressão (regression)) e outras formulações existam.

Por que heurísticas importam: combinatória

Mesmo com um pequeno número de predicados, o número de estados alcançáveis pode ser enorme. A busca cega (como busca em largura (breadth-first search, BFS)) frequentemente se torna inviável rapidamente. O planejamento heurístico usa algoritmos de Busca Heurística, como:

A* (ótimo com heurísticas admissíveis (admissible)),
Busca Best-First Gulosa (Greedy Best-First Search, GBFS) (planejamento satisfatório (satisficing) rápido),
A* Ponderado (Weighted A*) (troca otimalidade por velocidade).

A heurística (h(s)) é a alavanca principal: melhores estimativas focam a exploração em partes “promissoras” do espaço de estados.

Fundamentos: o que torna uma heurística “boa”?

Uma heurística é uma função (h(s)\ge 0) que estima o custo até o objetivo (distância até um objetivo) a partir do estado (s).

Propriedades importantes:

Admissível (admissible): (h(s)) nunca superestima o custo ótimo verdadeiro (h^*(s)). Isso é necessário para otimalidade com Busca A*.
Consistente (consistent): (h(s) \le c(s,a,s') + h(s')) para qualquer transição. Consistência implica admissibilidade e torna o A* mais eficiente (sem reexpansões (re-expansions) na busca em grafo (graph search) sob certas condições).
Informativa (informative): mais próxima de (h^*) em instâncias típicas.
Barata de calcular (cheap to compute): em planejamento, heurísticas são computadas por nó expandido, então mesmo heurísticas “moderadamente caras” podem dominar o tempo de execução.

O planejamento heurístico é, em grande parte, sobre o trade-off de engenharia: precisão da heurística vs. custo de computação.

Relaxações (relaxations): a ideia central por trás de muitas heurísticas de planejamento

Uma relaxação torna o problema mais fácil ao remover restrições. Se conseguirmos resolver o problema relaxado de forma eficiente, seu custo de solução pode ser usado como uma estimativa heurística para o problema original.

Relaxação de deleção (delete relaxation) (a mais famosa)

No planejamento STRIPS, ações podem apagar fatos, o que cria interações negativas (você pode desfazer progresso). A relaxação de deleção remove todos os efeitos de deleção:

o estado sucessor passa a ser (s' = s \cup \text{add}(a)),
fatos apenas se acumulam e nunca deixam de ser verdadeiros.

Isso transforma o planejamento em um tipo de problema de alcançabilidade monótona (monotone reachability) / estilo cobertura de conjuntos (set-cover). O problema relaxado ainda é não trivial, mas fica muito mais fácil de aproximar.

A relaxação de deleção sustenta várias heurísticas amplamente usadas:

(h^{\max})
(h^{\text{add}})
heurística FF (FF heuristic) (h_{\text{FF}}) (do Fast Forward)

Outras relaxações e abstrações

Além da relaxação de deleção, planejadores usam:

Abstração de estado (state abstraction): fundir ou ignorar partes do estado (bases de dados de padrões (pattern databases), mesclar-e-reduzir (merge-and-shrink)).
Relaxações de restrições (constraint relaxations): ignorar restrições de recursos, restrições numéricas ou condições de exclusão mútua (mutual exclusion, mutex).
Decomposição do problema (problem decomposition): identificar subobjetivos obrigatórios (marcos (landmarks)).

Elas podem gerar heurísticas admissíveis ou inadmissíveis, dependendo de como a relaxação é definida.

Heurísticas a partir da relaxação de deleção

Assuma que queremos um valor heurístico para um estado (s) e um conjunto de objetivos (G).

\(h^{\max}\): “o fato objetivo mais difícil”

Defina o custo de alcançar um único fato (p) como o custo relaxado mínimo, e o custo de um conjunto de objetivos como o máximo sobre os fatos:

[ h^{\max}(s) = \max_{g \in G} \text{cost}(g). ]

Intuição: você precisa alcançar todos os objetivos, então, no mínimo, deve pagar pelo mais difícil. Ela é:

tipicamente admissível (sob custos unitários; mais geralmente pode ser tornada admissível dependendo do modelo de custo),
frequentemente fraca porque ignora que múltiplos objetivos podem exigir múltiplas ações.

\(h^{\text{add}}\): custo aditivo dos objetivos

Em vez de máximo, soma:

[ h^{\text{add}}(s) = \sum_{g \in G} \text{cost}(g). ]

Isso costuma ser mais informativo, mas pode ser inadmissível porque conta ações em dobro quando uma mesma ação alcança múltiplos objetivos simultaneamente.

Heurística FF \(h_{\text{FF}}\): tamanho do plano relaxado

A heurística FF constrói um grafo de planejamento relaxado (relaxed planning graph) (ou uma estrutura equivalente de alcançabilidade), extrai um plano relaxado (relaxed plan) (um conjunto/sequência de ações que alcança o objetivo no problema relaxado) e usa o número (ou custo) de ações nesse plano relaxado:

Frequentemente mais precisa do que (h^{\text{add}}) porque leva em conta algumas interações positivas (uma ação apoiando múltiplos objetivos).
Tipicamente inadmissível, mas muito eficaz para planejamento satisfatório.

O FF popularizou ideias práticas adicionais:

Ações úteis (helpful actions): restringir o fator de ramificação às ações que aparecem na primeira camada do plano relaxado. Isso pode acelerar muito a busca, mas também pode torná-la incompleta se usado sem cuidado (na prática, costuma ser usado em modos incompletos ou “quase completos”).

Mini-exemplo trabalhado (informal)

Considere um pequeno problema tipo logística:

Fatos:

at(truck,A), at(truck,B)
at(pkg,A), at(pkg,B)
in(pkg,truck)

Ações:

load(A): pre at(truck,A) ∧ at(pkg,A), add in(pkg,truck), del at(pkg,A)
drive(A,B): pre at(truck,A), add at(truck,B), del at(truck,A)
unload(B): pre at(truck,B) ∧ in(pkg,truck), add at(pkg,B), del in(pkg,truck)

Inicial: at(truck,A) ∧ at(pkg,A)
Objetivo: at(pkg,B)

No problema real, você deve fazer load(A), drive(A,B), unload(B).

No problema relaxado por deleção, deleções não acontecem:

Após load(A), você mantém at(pkg,A) e obtém in(pkg,truck).
Após drive(A,B), você mantém at(truck,A) e obtém at(truck,B).

Um plano relaxado ainda precisa das três ações aqui, então (h_{\text{FF}}\approx 3). Em muitos domínios (por exemplo, Mundo dos Blocos (Blocks World)), a relaxação de deleção pode ser otimista demais porque ignora que mover um bloco pode desfazer outro arranjo.

Grafo de planejamento (planning graph) e raciocínio de mutex

A relaxação de deleção ignora interações negativas. Outra linha clássica de heurísticas usa grafos de planejamento (estruturas no estilo Graphplan (Graphplan-style)) e, às vezes, restrições mutex (exclusão mútua (mutual exclusion)):

Um grafo de planejamento alterna camadas de proposições e camadas de ações capturando alcançabilidade ao longo de passos de tempo.
Se um objetivo é inalcançável no nível (k), então a estimativa heurística é (> k).

Heurísticas baseadas no primeiro nível em que todos os objetivos aparecem (nível de conjunto (set-level)) podem ser informativas, mas o raciocínio completo de mutex pode ser caro. Muitos planejadores modernos preferem heurísticas com melhores trade-offs de custo/desempenho (como FF, heurísticas de marcos ou heurísticas de abstração), embora ideias de grafo de planejamento permaneçam influentes.

Heurísticas de marcos (landmark heuristics): subobjetivos obrigatórios

Um marco (landmark) é um fato (ou disjunção de fatos) que deve ser verdadeiro em algum momento em qualquer plano válido. Heurísticas de marcos estimam a distância contando (ou precificando) marcos ainda não alcançados, possivelmente com restrições de ordenação entre eles.

Por que marcos ajudam:

Eles capturam a estrutura necessária da tarefa mesmo quando a relaxação de deleção é otimista demais.
Eles podem guiar a busca em domínios com planos relaxados enganosos.

Heurísticas de marcos são comumente combinadas com outras heurísticas em planejadores práticos (por exemplo, no ecossistema do Fast Downward).

Heurísticas de abstração (abstraction heuristics): bases de dados de padrões e mesclar-e-reduzir

Outra família importante vem de abstração (abstraction): mapear o espaço de estados completo para um espaço de estados abstrato menor, onde caminhos mínimos exatos podem ser computados.

Heurísticas de Base de Dados de Padrões (Pattern Database, PDB)

Escolha um subconjunto de variáveis (um “padrão”).
Pré-calcule distâncias exatas de estados abstratos até objetivos abstratos via BFS reversa/Dijkstra.
Use essa distância como (h(s)).

Pontos-chave:

Heurísticas PDB frequentemente são admissíveis (excelentes para planejamento ótimo).
Múltiplas PDBs podem ser combinadas de forma aditiva se forem baseadas em partes disjuntas (disjoint) do problema (para manter admissibilidade).

Mesclar-e-reduzir (merge-and-shrink)

Comece com abstrações pequenas e iterativamente mescle (merge).
Reduza (shrink) a abstração para mantê-la dentro de um limite de tamanho.
A heurística resultante pode ser admissível e muito forte para planejamento ótimo.

Esses métodos são mais pesados computacionalmente para construir, mas podem compensar em instâncias difíceis.

Planejamento ótimo em custo (cost-optimal planning) vs. planejamento satisfatório (satisficing)

Planejamento aparece em dois modos comuns:

Planejamento satisfatório

Objetivo: encontrar algum plano rapidamente (não necessariamente ótimo).

Abordagem típica:

GBFS com uma heurística informativa porém inadmissível (por exemplo, FF, marcos).
Melhorias: operadores preferidos (preferred operators) (“ações úteis”), avaliação adiada (deferred evaluation), poda por novidade (novelty pruning), passeios aleatórios (random walks).

Este é o modo mais associado a “planejamento prático” em grandes domínios.

Planejamento ótimo em custo

Objetivo: encontrar o plano de menor custo sob custos de ação.

Abordagem típica:

A* ou variantes com heurísticas admissíveis (PDBs, mesclar-e-reduzir, LM-cut, variantes admissíveis de heurísticas relaxadas).

Uma heurística admissível clássica para planejamento ótimo em custo é LM-cut, que usa uma sequência de computações de corte derivadas do problema relaxado por deleção para produzir um limite inferior forte. (Os detalhes são envolvidos, mas a principal conclusão é que ela tende a ser muito mais apertada do que heurísticas admissíveis mais simples.)

Algoritmos de busca comumente usados com heurísticas de planejamento

Mesmo com a mesma heurística, a escolha da estratégia de busca importa.

A\*

A* expande nós em ordem crescente de: [ f(s) = g(s) + h(s) ] onde (g(s)) é o custo do caminho até agora.

Se (h) é admissível (e tipicamente com condições adicionais), A* retorna um plano ótimo.
Em planejamento, a memória pode ser o fator limitante: A* armazena muitos nós.

Busca Best-First Gulosa (GBFS)

GBFS usa: [ f(s) = h(s) ] Ela costuma ser muito mais rápida do que A* para encontrar qualquer plano, mas:

não garante otimalidade,
pode ficar presa em platôs heurísticos (heuristic plateaus).

A\* Ponderado

A* Ponderado usa: [ f(s) = g(s) + w \cdot h(s), \quad w>1 ] Ele frequentemente encontra soluções mais rápido do que A*, com subotimalidade limitada (bounded suboptimality) sob certas suposições.

Truques práticos em planejadores

Planejadores modernos frequentemente incluem:

busca multi-heurística (multi-heuristic search): alternar ou combinar várias heurísticas,
operadores preferidos: enviesar a lista aberta (open list) em direção às ações sugeridas por uma heurística,
avaliação preguiçosa (lazy evaluation): computar heurísticas caras apenas quando um nó é selecionado para expansão.

Sistemas e fluxos de trabalho práticos

Na prática, “planejamento heurístico” normalmente significa um pipeline como:

Analisar e instanciar um domínio/problema em STRIPS e PDDL (possivelmente usando representações elevadas (lifted representations) ou instanciação parcial (partial grounding) para escalabilidade).
Traduzir/normalizar o problema para uma representação interna (frequentemente variáveis de domínio finito (finite-domain variables) em vez de predicados brutos (raw predicates)).
Computar heurísticas sob demanda durante a busca (planejamento relaxado, marcos, abstrações).
Executar um algoritmo de busca (GBFS, A*, etc.) para encontrar um plano.
Opcionalmente pós-processar (post-process) o plano (remover redundâncias, melhorar custo, escalonar no tempo).

Uma plataforma de pesquisa e referência (baseline platform) amplamente usada é o Fast Downward, que oferece suporte a muitas heurísticas de estado da arte (FF-style, marcos, mesclar-e-reduzir, LM-cut) e múltiplas configurações de busca. Muitos planejadores da Competição Internacional de Planejamento (International Planning Competition, IPC) se baseiam em componentes semelhantes.

Exemplo: computando uma heurística de plano relaxado (alto nível)

Abaixo está um esboço simplificado de como uma heurística de plano relaxado poderia ser computada (conceitualmente semelhante à expansão de grafo de planejamento no estilo FF + extração de plano). Isso não é código de produção, mas mostra a estrutura:

function relaxed_plan_heuristic(state s, goal G):
    layers = []
    P0 = facts_true_in(s)
    layers.append(P0)

    while G not subset of layers.last:
        A = { action a | pre(a) subset of layers.last }
        P_next = layers.last union (union over a in A of add(a))
        if P_next == layers.last:
            return infinity  // goals unreachable even in relaxation
        layers.append(P_next)

    // Backward extraction (greedy):
    needed = G
    plan = []
    for level from last_layer down to 1:
        choose actions in level-1 that add facts in needed
        add chosen actions to plan
        needed = (needed - added_facts) union preconditions_of(chosen_actions)

    return cost(plan)  // number of actions or sum of action costs

Planejadores reais incorporam:

melhor seleção de ações durante a extração,
propagação sensível a custo (cost-sensitive) (no estilo Dijkstra) em vez de contagem por níveis,
memoização (memoization) entre estados,
operadores preferidos derivados do primeiro passo de extração.

Onde o planejamento heurístico é usado

Planejamento heurístico é usado quando você precisa de sequências de ações interpretáveis, guiadas por restrições, e consegue modelar o mundo simbolicamente:

Planejamento de tarefas em robótica: sequenciamento de alto nível (“pick”, “place”, “open”) frequentemente combinado com planejamento de movimento.
Fluxos de trabalho automatizados e orquestração: processos de negócio, operações de TI, resposta a incidentes.
Jogos e simulações: planejamento de comportamento de NPCs com ações simbólicas.
Raciocínio automatizado: síntese de sequências de ações sob restrições lógicas.
Operações e logística: quando problemas se encaixam nas suposições clássicas (determinísticos, discretos, totalmente observados) ou podem ser aproximados dessa forma.

Para incerteza e resultados estocásticos, planejadores frequentemente migram para políticas (policies) e formulações como Processos de Decisão de Markov e Aprendizado por Reforço, embora o planejamento heurístico ainda possa aparecer como componente (por exemplo, para subproblemas determinísticos).

Limitações e modos de falha comuns

O planejamento heurístico é poderoso, mas tem fraquezas conhecidas:

Otimismo excessivo de relaxações: a relaxação de deleção pode ignorar interações negativas cruciais, produzindo orientação enganosa.
Platôs heurísticos: muitos estados compartilham o mesmo valor de (h) (comum em GBFS), causando exploração ampla.
Explosão de instanciação (grounding blow-up): instanciação ingênua de PDDL pode explodir em tamanho; planejadores modernos mitigam isso, mas continua sendo um gargalo importante.
Lacunas de expressividade (expressiveness gaps): suposições do planejamento clássico (determinístico, totalmente observável, tempo discreto) não se encaixam em todos os problemas reais.
Complexidade numérica/temporal/de recursos: recursos mais ricos de PDDL (durações, fluentes numéricos (numeric fluents)) frequentemente exigem heurísticas e busca especializadas (ou técnicas de compilação (compilation techniques)), e o desempenho pode variar bastante por domínio.

Conexões com outros paradigmas de resolução

O planejamento heurístico é um pilar da resolução simbólica de problemas, mas também se conecta a:

Planejamento baseado em SAT (SAT-based planning): compilar planejamento em satisfatibilidade booleana (Boolean satisfiability) e usar Resolução SAT. Isso pode ser muito forte para certos benchmarks.
Codificações CSP e ILP (CSP and ILP encodings): compilar em Problemas de Satisfação de Restrições ou em programação inteira (integer programming) para um raciocínio global forte.
Planejamento aprimorado por aprendizado (learning-augmented planning): heurísticas aprendidas (learned heuristics) ou orientação por política (policy guidance) podem melhorar a busca, mas precisam lidar com mudança de distribuição (distribution shift) e manter correção (correctness) se garantias forem importantes.

Em muitos sistemas reais, planejadores são híbridos (hybrid): heurísticas simbólicas mais componentes aprendidos para orientação ou previsão de custo (cost prediction).

Orientação prática: escolhendo heurísticas e busca

Algumas regras gerais vistas na prática:

Se você precisa de qualquer plano rapidamente: comece com GBFS + FF/marcos (planejamento satisfatório).
Se você precisa de custo ótimo: use A* (ou variantes) + heurísticas admissíveis como mesclar-e-reduzir, LM-cut ou PDBs fortes.
Se você tem custos de ação (não unitários): garanta que a heurística seja sensível a custo (cost-aware) (muitos planejadores suportam variantes sensíveis a custo).
Combine heurísticas quando possível: uma heurística pode ser forte em algumas regiões do espaço e fraca em outras.

Resumo

O planejamento heurístico faz o planejamento clássico escalar ao combinar:

algoritmos de busca (A*, GBFS, A* Ponderado),
heurísticas estimando a distância restante até o objetivo,
relaxações e abstrações para computar essas estimativas eficientemente.

As técnicas mais influentes computam heurísticas a partir da relaxação de deleção (FF, (h^{\max}), (h^{\text{add}})), da estrutura de subobjetivos obrigatórios (marcos) ou de abstrações admissíveis (PDBs, mesclar-e-reduzir, LM-cut). Em conjunto, esses métodos formam a espinha dorsal dos planejadores simbólicos modernos e permanecem altamente relevantes em robótica, automação e tarefas de raciocínio em que ações explícitas e restrições importam.