STRIPS e PDDL

Planejamento clássico em um parágrafo

O planejamento clássico (classical planning) estuda como gerar automaticamente uma sequência de ações (um plano (plan)) que transforma um estado inicial do mundo em um estado que satisfaz um objetivo. As suposições “clássicas” são fortes, mas úteis: o mundo é determinístico (deterministic), totalmente observável (fully observable), estático exceto pelas ações do agente, e tipicamente descrito com fatos simbólicos discretos (discrete symbolic facts). Sob essas suposições, o planejamento se torna um problema bem definido de busca (search) e raciocínio e inspirou muitos algoritmos usados em robótica, logística e suporte automatizado à decisão. Dois padrões fundamentais para expressar tais problemas são STRIPS (uma representação compacta de ações) e PDDL (uma família de linguagens de descrição de domínios padronizada por meio das Competições Internacionais de Planejamento (International Planning Competitions)).

Este artigo oferece uma visão de alto nível de ambos, com exemplos práticos e orientações de modelagem. Para entender como os planejadores resolvem essas representações de forma eficiente, veja Planejamento Heurístico.

STRIPS: a representação clássica de ações

O que é STRIPS

STRIPS (do Stanford Research Institute Problem Solver, início dos anos 1970) é, ao mesmo tempo:

  1. Um modelo de problema de planejamento: estados são conjuntos de fatos; ações transformam estados.
  2. Uma linguagem restrita de ações: pré-condições são simples, e efeitos são expressos como listas de adição/remoção.

Apesar da idade, STRIPS permanece central porque muitos planejadores modernos compilam internamente linguagens mais ricas para um núcleo semelhante ao STRIPS antes de realizar a busca.

Conceitos centrais e semântica

Uma tarefa de planejamento STRIPS geralmente é definida como uma tupla:

  • Fatos / proposições (F): enunciados atômicos como On(A,B) ou At(truck1, depot).
  • Estado inicial (s_0 \subseteq F): fatos que são verdadeiros inicialmente.
  • Objetivo (G \subseteq F): fatos que devem ser verdadeiros em um estado objetivo.
  • Ações (A): cada ação tem:
    • Pré-condições Pre(a) ⊆ F (fatos que já devem ser verdadeiros)
    • Lista de adição Add(a) ⊆ F (fatos tornados verdadeiros)
    • Lista de remoção Del(a) ⊆ F (fatos tornados falsos)

Um estado (s) é simplesmente um conjunto de fatos verdadeiros. STRIPS normalmente assume a suposição de mundo fechado (closed-world assumption): qualquer fato que não está em (s) é falso.

Uma ação (a) é aplicável no estado (s) se:

  • Pre(a) ⊆ s

e o estado sucessor é:

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

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

Esquemas de ação STRIPS (ações parametrizadas (lifted actions))

Em domínios realistas, as ações normalmente são escritas como esquemas com parâmetros (variáveis), posteriormente instanciados (“aterrados” (grounded)) com objetos.

Exemplo (esquema STRIPS informal) para o Mundo dos Blocos (Blocks World):

  • Ação: Stack(x, y)
  • Pre: {Holding(x), Clear(y)}
  • Add: {On(x, y), Clear(x), HandEmpty}
  • Del: {Holding(x), Clear(y)}

Isso diz: se você está segurando o bloco x e o bloco y está livre, você pode colocar x sobre y.

Exemplo STRIPS resolvido (Mundo dos Blocos minúsculo)

Fatos:

  • On(A,Table), On(B,Table), Clear(A), Clear(B), HandEmpty

Objetivo:

  • On(A,B)

Ações (simplificadas):

  • PickUp(x)
    Pre: On(x,Table), Clear(x), HandEmpty
    Add: Holding(x)
    Del: On(x,Table), HandEmpty

  • Stack(x,y)
    Pre: Holding(x), Clear(y)
    Add: On(x,y), HandEmpty, Clear(x)
    Del: Holding(x), Clear(y)

Um plano:

  1. PickUp(A)
  2. Stack(A,B)

STRIPS torna explícita a mecânica da mudança: você consegue ver exatamente quais fatos se tornam verdadeiros/falsos após cada passo.

O que STRIPS deixa de fora

O STRIPS “puro” é intencionalmente limitado:

  • Pré-condições são tipicamente conjunções positivas de fatos atômicos (sem or, sem quantificadores, sem negação geral).
  • Efeitos são listas de adição/remoção incondicionais (sem efeitos “se … então …”).
  • Não há tempo explícito nem duração de ações.
  • Não há recursos numéricos (combustível, capacidade) a menos que sejam codificados de forma pouco natural como fatos.

Essas limitações motivaram linguagens mais ricas — sobretudo a PDDL.

PDDL: a Planning Domain Definition Language

Por que PDDL existe

PDDL foi introduzida no fim dos anos 1990 para padronizar benchmarks de planejamento e permitir comparação justa entre planejadores. Ela separa:

  • um domínio (domain) reutilizável (predicados + esquemas de ação)
  • de uma instância de problema (problem instance) específica (objetos + estado inicial + objetivo)

A PDDL evoluiu por versões (por exemplo, PDDL1.2, PDDL2.1 para tempo/numéricos, extensões posteriores como preferências e predicados derivados). Na prática, “PDDL” se refere a uma família de dialetos com sintaxe compartilhada, semelhante a Lisp.

PDDL em um relance: arquivos de domínio vs. problema

Um fluxo de trabalho típico:

  • domain.pddl: define quais ações existem e sua lógica.
  • problem.pddl: define quais objetos existem agora, o que é verdadeiro inicialmente e o que queremos.

Os planejadores leem ambos e tentam produzir um plano.

Um exemplo concreto de PDDL: um domínio logístico minúsculo

Abaixo está um domínio PDDL mínimo (semelhante a STRIPS) para mover um caminhão entre locais.

`domain.pddl`

(define (domain tiny-logistics)
  (:requirements :strips :typing)
  (:types truck location)
  (:predicates
    (at ?t - truck ?l - location)
    (road ?from - location ?to - location))

  (:action drive
    :parameters (?t - truck ?from - location ?to - location)
    :precondition (and (at ?t ?from) (road ?from ?to))
    :effect (and (not (at ?t ?from)) (at ?t ?to)))
)

Pontos-chave:

  • :requirements declara quais recursos da linguagem são usados. Aqui, é essencialmente STRIPS com tipos.
  • Predicados definem o vocabulário.
  • A ação é um esquema. Sua pré-condição e seu efeito são fórmulas lógicas.

`problem.pddl`

(define (problem deliver1)
  (:domain tiny-logistics)
  (:objects
    truck1 - truck
    depot store - location)
  (:init
    (at truck1 depot)
    (road depot store)
    (road store depot))
  (:goal
    (at truck1 store))
)

Um plano válido é simplesmente:

  • drive truck1 depot store

Este exemplo é intencionalmente simples, mas ilustra a separação central da PDDL entre dinâmicas reutilizáveis (domínio) e dados da instância (problema).

De STRIPS à PDDL “completa”: recursos expressivos que você verá

Muitos planejadores suportam apenas um subconjunto de PDDL, mas ajuda reconhecer recursos comuns e o que eles significam.

Pré-condições negativas e construções do tipo ADL

STRIPS tradicionalmente proíbe negação em pré-condições. A PDDL pode permitir (com :negative-preconditions) e, de forma mais geral, oferece suporte a construções no estilo ADL (Action Description Language) (com :adl), como:

  • Disjunção: (or ...)
  • Quantificação universal / existencial: (forall ...), (exists ...)
  • Implicações (muitas vezes eliminadas por compilação)

Exemplo de ideia (nem sempre suportada por todos os planejadores):

:precondition (and (at ?t ?from) (not (= ?from ?to)))

Mesmo que um planejador não lide diretamente com isso, frequentemente esses recursos são compilados para STRIPS introduzindo predicados auxiliares e ações adicionais.

Efeitos condicionais

Efeitos condicionais permitem “se a condição vale no momento da ação, aplique estes efeitos”.

:effect (and
  (at ?t ?to)
  (not (at ?t ?from))
  (when (has-trailer ?t) (not (trailer-at ?from))))

Eles são poderosos para modelagem, mas podem complicar o planejamento. Muitos planejadores os compilam em múltiplas ações ou em predicados adicionais de controle.

Fluentes numéricos e recursos (PDDL2.1)

A PDDL2.1 introduziu variáveis numéricas de estado (“fluentes”), úteis para combustível, energia, capacidade e custos.

Esboço:

(:functions (fuel ?t - truck))

(:action drive
  :parameters (?t - truck ?from - location ?to - location)
  :precondition (and (at ?t ?from) (road ?from ?to) (>= (fuel ?t) 1))
  :effect (and (not (at ?t ?from)) (at ?t ?to) (decrease (fuel ?t) 1)))

Fluentes numéricos empurram o planejamento em direção à resolução de restrições e à otimização; alguns planejadores lidam com isso nativamente, outros exigem compilação ou técnicas especializadas.

Ações durativas e tempo (também PDDL2.1)

Ações durativas modelam ações que levam tempo e podem ter condições/efeitos em diferentes pontos temporais:

  • no início
  • ao longo de toda a duração
  • no fim

Exemplo de esboço (simplificado):

(:durative-action drive
  :parameters (?t - truck ?from - location ?to - location)
  :duration (= ?duration 10)
  :condition (and
    (at start (at ?t ?from))
    (over all (road ?from ?to)))
  :effect (and
    (at start (not (at ?t ?from)))
    (at end (at ?t ?to))))

Planejamento temporal é uma área grande por si só; muitos planejadores “clássicos” focam em ações instantâneas (estilo STRIPS), mesmo que a linguagem de entrada permita mais.

Predicados derivados (axiomas)

Predicados derivados definem fatos que são inferidos em vez de serem alterados diretamente por ações (como regras lógicas). Eles podem representar alcançabilidade, fecho transitivo ou abstrações específicas do domínio.

Ideia de exemplo:

  • (connected ?a ?b) é verdadeiro se existe um caminho de estradas de ?a até ?b.

Planejadores frequentemente tratam predicados derivados com cuidado porque eles introduzem uma etapa de raciocínio (calcular o fecho) durante a busca.

Preferências, objetivos suaves e custos (PDDL3 e além)

Algumas extensões de PDDL representam:

  • Custos de ação (minimizar custo total)
  • Preferências (restrições suaves)
  • Restrições de trajetória (“nunca visitar um estado inseguro”)

Nem todos os planejadores suportam isso, mas é comum em suítes de benchmarks e em aplicações que exigem otimização, e não apenas viabilidade.

Como os planejadores usam STRIPS/PDDL internamente

Mesmo quando você escreve um domínio com recursos mais ricos de PDDL, o planejador frequentemente o transforma em uma forma interna mais simples:

  1. Parsing (análise sintática) e verificação de tipos
  2. Aterramento (grounding): instanciar esquemas de ação sobre todas as combinações de objetos (pode ser enorme)
  3. Normalização/compilação:
    • eliminar quantificadores, disjunções, efeitos condicionais (se necessário)
    • traduzir para operadores no estilo STRIPS ou outra forma normal
  4. Busca: explorar o espaço de estados guiado por heurísticas
    (veja Planejamento Heurístico)

Existem paradigmas alternativos de resolução:

  • Planejamento baseado em SAT (SAT-based planning): compilar o planejamento para satisfatibilidade ao longo de passos de tempo (veja Resolução SAT)
  • Planejamento CSP/SMT (CSP/SMT planning): compilar para resolução de restrições (veja Problemas de Satisfação de Restrições)
  • Busca simbólica (symbolic search) usando BDDs (Binary Decision Diagrams) em alguns cenários

Ainda assim, operadores no estilo STRIPS são a lingua franca do planejamento clássico.

Orientações de modelagem: acertando STRIPS/PDDL

Escolha o nível certo de abstração

O planejamento clássico funciona melhor quando:

  • o estado pode ser descrito com um número moderado de fatos Booleanos
  • os efeitos das ações são previsíveis e locais
  • restrições de tempo/recursos estão ausentes ou podem ser modeladas de forma simples

Se seu domínio é contínuo, parcialmente observável, estocástico ou aprendido a partir de dados, o planejamento clássico pode precisar de complementos (por exemplo, planejamento hierárquico, replanejamento ou integração com Aprendizado por Reforço).

Padrões comuns de modelagem

  • Use predicados para estrutura relacional: at(robot, room), connected(room1, room2).
  • Represente condições mutuamente exclusivas com cuidado:
    • Frequentemente codificadas garantindo que as ações mantenham invariantes como “um robô está em exatamente um local”.
  • Evite objetos desnecessários: o aterramento escala com a contagem de objetos.
  • Prefira tipos para reduzir combinações acidentais no aterramento.
  • Adicione “predicados estáticos” para estrutura imutável (por exemplo, road, adjacent).
  • Mantenha efeitos mínimos: altere apenas o que realmente muda.

Armadilhas comuns

  • Esquecer efeitos de remoção: se você adiciona (at ?t ?to) mas esquece de remover (at ?t ?from), você permite estados impossíveis.
  • Exagerar no uso de negação e disjunção: pode ser suportado sintaticamente, mas não de forma eficiente pelo planejador escolhido.
  • Subespecificar restrições por acidente: planejadores clássicos explorarão qualquer brecha.
  • Explosões enormes no aterramento: ações com muitos parâmetros sobre muitos objetos podem produzir milhões de ações aterradas.

Dicas de depuração

  • Comece com uma instância minúscula (2–3 objetos) e valide planos manualmente.
  • Use um validador de planos (por exemplo, VAL em muitas toolchains de planejamento) para verificar a semântica.
  • Imprima operadores aterrados intermediários se sua ferramenta permitir — muitos “bugs” são erros de modelagem, não erros do planejador.

Aplicações práticas do planejamento no estilo STRIPS/PDDL

Mesmo com avanços modernos em ML, o planejamento simbólico continua valioso quando você precisa de estrutura explícita, garantias e interpretabilidade.

Aplicações comuns:

  • Planejamento de tarefas em robótica: sequenciamento de ações em alto nível (pegar, colocar, mover), frequentemente combinado com planejamento de movimento.
  • Logística e automação de armazéns: roteamento, carregamento/descarregamento, fluxos de trabalho de múltiplas etapas.
  • Operações automatizadas: runbooks para sistemas de TI, playbooks de resposta a incidentes.
  • IA para jogos: comportamento orientado a objetivos com modelos explícitos de ações.
  • Síntese de fluxos de trabalho (workflow synthesis): montagem de serviços/ações para atingir um objetivo declarativo.

Em muitos sistemas reais, a PDDL fica dentro de uma arquitetura maior:

  • plano em PDDL como uma política de alto nível
  • monitoramento de execução detecta desvios
  • replanejamento é acionado quando o mundo muda

Essa abordagem híbrida lida com as suposições clássicas sem descartar os benefícios dos modelos simbólicos.

STRIPS vs PDDL: como pensar sobre a relação

  • STRIPS é o núcleo conceitual e matemático: estados como conjuntos de fatos; ações como pré-condições mais efeitos de adição/remoção.
  • PDDL é a linguagem de superfície padrão usada para descrever benchmarks e domínios de planejamento, variando de fragmentos semelhantes a STRIPS a variantes temporais/numéricas mais ricas.

A maior parte da pesquisa e das ferramentas de “planejamento clássico” pode ser vista como:

  1. escrever em (um fragmento de) PDDL
  2. compilar em direção a operadores no estilo STRIPS
  3. resolver via busca heurística e métodos relacionados (veja Planejamento Heurístico)

Resumo

  • STRIPS fornece uma semântica simples e robusta para planejamento clássico: ações aplicáveis transformam conjuntos de fatos por meio de listas de adição/remoção.
  • PDDL padroniza como escrevemos domínios e problemas, permitindo modelos de domínio reutilizáveis e avaliação comparável entre planejadores.
  • Recursos mais ricos de PDDL (construções ADL, efeitos condicionais, fluentes numéricos, ações durativas) aumentam o poder de modelagem, mas também influenciam compatibilidade e desempenho dos planejadores.
  • Na prática, um planejamento eficaz com STRIPS/PDDL é tanto sobre boa modelagem (predicados limpos, efeitos bem definidos, aterramento gerenciável) quanto sobre algoritmos de resolução.

Se você quer a “próxima camada” (como heurísticas como grafos de planejamento relaxado (relaxed planning graphs) e relaxação de remoção (delete relaxation) guiam a busca), continue em Planejamento Heurístico.