Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

Each language version is independently generated for its own context, not a direct translation.

Imagine que você é o diretor de uma peça de teatro complexa. Você tem atores (ações) que precisam entrar e sair do palco em momentos específicos, alguns precisam ficar no palco por um tempo (ações durativas), e outros precisam interagir perfeitamente sem se chocar.

O problema é que o seu "roteiro" atual (chamado PDDL 2.1) é como um esboço feito à mão: ele diz o que deve acontecer, mas é difícil para os computadores entenderem a lógica de quando e como tudo deve acontecer ao mesmo tempo, especialmente quando envolve números (como quantos litros de água regar uma planta enquanto ela cresce).

Os autores deste artigo, Andrea, Enrico e Alessandro, criaram uma máquina de tradução mágica. Eles pegaram esse esboço complicado e o transformaram em um novo tipo de roteiro (chamado PDDL+) que os computadores conseguem ler e executar muito melhor.

Aqui está a explicação do que eles fizeram, usando analogias do dia a dia:

1. O Problema: O "Relógio de Areia" vs. O "Motorista de Uber"

No mundo do planejamento automático, temos dois tipos de problemas:

Ações Instantâneas: Como clicar em um botão. Acontece num piscar de olhos.
Ações Durativas: Como cozinhar um bolo. Leva tempo. Enquanto o bolo assa, a temperatura do forno muda e você não pode tirar o bolo antes da hora.

O problema é que os computadores que lidam com "ações que levam tempo" (PDDL 2.1) muitas vezes travam ou ficam confusos quando as coisas ficam complexas (com números e tempo misturados). É como tentar dirigir um carro usando apenas um mapa de papel, sem GPS.

2. A Solução: A Tradução para o "PDDL+"

Os autores criaram um compilador (um tradutor) que transforma o problema antigo em um novo formato (PDDL+). Eles não apenas mudaram a linguagem; eles mudaram a lógica de funcionamento.

Em vez de dizer "o ator fica no palco por 5 minutos", o novo sistema PDDL+ usa três ferramentas diferentes para simular isso:

Ações Instantâneas: O "Sinal Verde" para começar.
Processos: O "Motor" que roda enquanto a ação acontece (ex: o forno aquecendo).
Eventos: O "Alarme" que toca quando uma condição é atingida (ex: o bolo está pronto).

A Analogia da Fábrica de Bolos:
Imagine que você quer assar um bolo (ação durativa).

No sistema antigo, você dizia: "Asse o bolo por 30 minutos". O computador tinha que adivinhar o que acontece durante esses 30 minutos.
No novo sistema (PDDL+), você diz:
1. Ação: "Ligue o forno" (começa o processo).
2. Processo: "A temperatura sobe 1 grau a cada segundo" (o motor rodando).
3. Evento: "Se a temperatura chegar a 180°C, tire o bolo" (o alarme).

Isso torna muito mais fácil para o computador calcular o melhor momento de fazer tudo.

3. O Grande Truque: O "Guarda-Costas" (Locks)

Um dos maiores desafios é evitar que duas ações tentem mexer na mesma coisa ao mesmo tempo (como duas pessoas tentando abrir a mesma porta de uma vez).

Os autores criaram um sistema de "Trancas e Chaves" (Locks):

Imagine que cada variável (como a temperatura ou o nível de água) tem um guarda-costas.
Antes de qualquer ação tocar na variável, ela precisa pedir permissão ao guarda.
Se a ação está "lendo" a variável, o guarda segura a porta.
Se a ação está "escrevendo" (mudando) a variável, o guarda bloqueia qualquer outra pessoa de ler ou escrever.
Assim que o tempo passa um pouquinho, o guarda solta a porta e tudo fica livre novamente.

Isso garante que nada dê errado por causa de "atropelos" no tempo. É como um semáforo inteligente que garante que apenas um carro passe na interseção de cada vez, mas de forma super rápida e eficiente.

4. O Resultado: Mais Rápido e Inteligente

Os autores testaram essa tradução em problemas reais e difíceis (como regar plantas em um jardim gigante enquanto um barco salva pessoas em um lago).

O que eles descobriram: O novo sistema (usando o tradutor PDDL+) foi mais rápido e resolveu mais problemas do que os melhores sistemas antigos que tentavam fazer tudo de uma vez só.
Por que? Porque eles delegaram a parte difícil (o tempo e os números) para uma linguagem que os computadores já são muito bons em entender. É como usar uma calculadora científica em vez de fazer a conta de cabeça.

Resumo Final

Pense neste artigo como a criação de um tradutor universal para o tempo.
Antes, tentar planejar ações que duram tempo e envolvem números era como tentar montar um quebra-cabeça 3D de olhos vendados. Agora, com essa tradução para PDDL+, eles colocaram óculos de realidade aumentada no computador, mostrando exatamente onde cada peça se encaixa, garantindo que nada se choque e que tudo aconteça na hora certa.

O resultado? Computadores que conseguem planejar tarefas complexas do mundo real (como gerenciar recursos de água ou logística de emergência) de forma muito mais eficiente.

Each language version is independently generated for its own context, not a direct translation.

Visão Geral

O artigo aborda o problema de planeamento temporal com ações durativas (especificamente no nível 3 da linguagem PDDL 2.1) e propõe uma compilação prática e formalmente fundamentada para a linguagem PDDL+. Embora seja conhecido teoricamente que o PDDL+ pode modelar ações durativas através de processos e eventos, não existia anteriormente uma compilação completa, rigorosa e experimentalmente validada na literatura. Os autores preenchem essa lacuna, demonstrando que essa abordagem é não apenas teoricamente sólida, mas também competitiva em problemas complexos de planeamento numérico-temporal.

1. O Problema

O planeamento temporal envolve encontrar uma sequência de ações que atinja um objetivo a partir de um estado inicial, onde as ações têm duração e ocorrem em pontos específicos de uma linha do tempo.

PDDL 2.1: Utiliza "ações durativas" com condições de início, fim e invariantes (condições que devem ser mantidas durante toda a execução).
Desafio: Muitos planeadores temporais nativos têm dificuldade em lidar com a interação complexa entre variáveis numéricas, condições temporais e a não sobreposição de ações (regra de "alvo não móvel" ou no-self-overlapping).
Objetivo: Transformar um problema de planeamento temporal (PDDL 2.1) em um problema equivalente em PDDL+, delegando o raciocínio temporal a planeadores que suportam nativamente processos contínuos e eventos discretos.

2. Metodologia e Compilação

Os autores propõem uma compilação polinomial que mapeia cada ação durativa do PDDL 2.1 para uma combinação de ações instantâneas, processos e eventos no PDDL+. A semântica assume que as ações não se sobrepõem a si mesmas (non-self-overlapping).

Estrutura da Compilação

Para cada ação durativa $a$ no problema original, o modelo compilado introduz:

Ações Instantâneas (Snap Actions):
- Início ( $a_{\vdash}$ ): Dispara o início da ação, define um predicado de estado $r_a$ (indicando que a ação está ativa), reinicia um relógio numérico $c_a$ e incrementa um contador global de ações ativas ( $oc$ ).
- Fim ( $a_{\dashv}$ ): Para ações de duração variável, esta ação encerra o processo, verifica se a duração está dentro dos limites e decrementa $oc$ .
Processos (Processes):
- Um processo $\bar{p}_a$ associado a cada ação durativa, ativo enquanto $r_a$ for verdadeiro, incrementando o relógio $c_a$ a uma taxa constante (ex: $dc_a/dt = 1$ ).
- Um processo global $\bar{p}_E$ que incrementa uma variável $gc$ para auxiliar na gestão de mutex (exclusão mútua) em tempo superdenso.
Eventos (Events):
- Fim de Ações Fixas ( $\bar{e}^{\dashv}_a$ ): Para ações de duração fixa, um evento é disparado automaticamente quando o relógio $c_a$ atinge a duração fixa.
- Verificação de Invariantes ( $\bar{e}^{\leftrightarrow}_a$ ): Se a condição global da ação ( $\gamma_a$ ) for violada enquanto a ação está ativa, um evento define um predicado de erro ok como falso, invalidando o plano.
- Reset de Locks ( $\bar{e}_E$ ): Um evento crucial que reseta todas as variáveis de "trava" (locks) para verdadeiro sempre que o tempo avança (detectado pela variável $gc$ ).

Mecanismo de "Locks" (Exclusão Mútua)

Um dos contributos mais inovadores é o mecanismo de locks para garantir a não interferência de ações simultâneas (requisito do PDDL 2.1):

São introduzidas variáveis booleanas de travamento ( $rlf, alf, ilf$ ) para cada variável fluente.
Ao "ler" uma variável, define-se o seu lock de leitura como falso.
Ao "escrever" ou "incrementar", define-se o lock de escrita como falso.
As ações têm pré-condições que exigem que os locks estejam ativos.
O evento $\bar{e}_E$ reseta todos os locks para verdadeiro após um passo de tempo, permitindo que novas ações leiam/escrevam no próximo instante, mas impedindo que duas ações interferentes ocorram no mesmo "instante superdenso".

Propriedades Teóricas

Corretude (Soundness): Qualquer plano válido gerado no PDDL+ corresponde a um plano temporal válido no PDDL 2.1 original.
Completude: Para qualquer plano temporal válido, existe um passo de discretização $\delta$ suficientemente pequeno que permite gerar um plano válido no PDDL+ compilado.
Complexidade: A compilação é polinomial em relação ao tamanho do problema e o comprimento do plano aumenta apenas por um fator constante.

3. Resultados Experimentais

Os autores realizaram uma campanha experimental em domínios de planeamento numérico-temporal, comparando a abordagem de compilação (usando o planeador ENHSP com heurísticas lazy greedy e $WA^*$ ) contra planeadores temporais de última geração (ARIES, NextFLAP, TFLAP, OPTIC, TAMER, Patty).

Domínios Testados: MatchCellar, MAJSP, T-Sailing (resgate de barcos com prazos) e T-Plant-Watering (coordenação de agentes).
Desempenho:
- O ENHSP-WA (usando a compilação) obteve a maior cobertura de instâncias resolvidas, especialmente em domínios com forte interação numérica e temporal.
- Em domínios puramente temporais, os planeadores nativos foram mais rápidos, mas a abordagem compilada mostrou-se competitiva.
- Em domínios numéricos-temporais complexos (como MAJSP e T-Plant-Watering), a compilação superou significativamente os planeadores nativos, demonstrando que a expressividade do PDDL+ e a eficiência dos planeadores baseados em busca heurística (como o ENHSP) são vantajosas para estes problemas.
Conclusão Experimental: A compilação não é apenas teoricamente viável, mas prática e superior para problemas difíceis que envolvem variáveis numéricas e restrições temporais complexas.

4. Contribuições Principais

Primeira Compilação Formal Completa: Oferece a primeira descrição formal rigorosa e completa de como compilar PDDL 2.1 (nível 3) para PDDL+, cobrindo semântica, invariantes e restrições de não sobreposição.
Mecanismo de Locks para Não-Interferência: Desenvolveu uma técnica elegante usando processos e eventos para impor a regra de "alvo não móvel" (no-moving-target) e exclusão mútua em tempo superdenso, resolvendo um problema de semântica sutil.
Validação Empírica: Demonstrou que planeadores PDDL+ (geralmente focados em sistemas híbridos) podem superar planeadores temporais especializados em problemas numéricos complexos, sugerindo uma nova direção para o desenvolvimento de solvers.
Suporte a Recursos Avançados: A compilação lida naturalmente com variáveis numéricas, efeitos atrasados e literais iniciais temporizados.

5. Significado e Impacto

Este trabalho é significativo porque:

Ponte entre Domínios: Conecta o campo do planeamento temporal clássico com o de sistemas híbridos (PDDL+), permitindo reutilizar avanços em um domínio para o outro.
Eficiência Prática: Mostra que a compilação para uma linguagem mais expressiva (PDDL+) pode ser uma estratégia mais eficiente do que desenvolver planeadores temporais ad-hoc para problemas numéricos complexos.
Fundamentação Teórica: Estabelece as bases para futuras extensões, como o suporte ao nível 4 do PDDL 2.1 (mudança contínua) e semânticas de tempo contínuo no PDDL+.

Em resumo, o artigo prova que a compilação de planeamento temporal para PDDL+ é uma abordagem viável, correta e, em muitos casos, superior, oferecendo uma nova ferramenta poderosa para resolver problemas de planeamento complexos.