Improving Plan Execution Flexibility using Block-Substitution

Este artigo propõe uma metodologia que aumenta a flexibilidade de execução de planos de IA ao substituir subplanos por ações externas dentro de uma estrutura de Plano de Ordem Parcial Decomposta em Blocos (BDPO), complementada por estratégias de redução de redundância e reordenação baseada em MaxSAT, demonstrando resultados superiores em benchmarks do IPC.

O essencial

Imagine que você é um gerente de uma grande empresa de entregas. Você precisa organizar a rota de vários caminhões para entregar pacotes em diferentes endereços.

O planejamento tradicional (como os usados por robôs e IAs antigas) é como dar uma lista de instruções rígida: "Caminhão A vai primeiro, depois o B, depois o C". Se o trânsito fechar na rua do Caminhão A, todo o plano trava. É inflexível.

Os planos de ordem parcial (uma evolução anterior) são melhores. Eles dizem: "O Caminhão A e o B podem sair em qualquer ordem, desde que o C saia depois de ambos". Isso já dá mais liberdade. Mas, mesmo assim, ainda existem regras rígidas demais.

Este artigo apresenta uma nova técnica chamada FIBS (Flexibilidade via Substituição de Blocos) que torna o plano ainda mais inteligente e adaptável. Vamos usar uma analogia de cozinha para explicar como funciona:

1. O Problema: A Receita Rígida

Imagine que você tem uma receita de bolo que diz:

1. Misture os ovos.
2. Adicione a farinha.
3. Adicione o açúcar.
4. Misture tudo.

Se você tiver que fazer isso em uma cozinha lotada onde só há uma batedeira, você é obrigado a seguir a ordem exata. Se a batedeira quebrar no passo 2, você não consegue terminar o bolo. O plano é "rígido".

2. A Solução Antiga: "Desembaralhar" a Receita

Antes desse novo método, os cientistas tentavam melhorar a flexibilidade apenas removendo regras desnecessárias.

• Exemplo: Eles perceberam que você pode adicionar o açúcar antes ou depois da farinha, desde que ambos estejam misturados. Então, eles diziam: "Ok, não importa a ordem entre farinha e açúcar".
• Resultado: Um pouco mais de liberdade, mas ainda limitado pelo que a receita original tinha.

3. A Grande Inovação: "Trocar o Ingrediente" (Substituição de Blocos)

Aqui entra a genialidade do método FIBS. Em vez de apenas tentar reorganizar os passos existentes, o algoritmo pergunta: "E se trocarmos um pedaço inteiro da receita por uma versão melhor?"

Imagine que o seu plano original diz: "Use a batedeira elétrica para misturar os ovos".
O FIBS olha para isso e pensa: "Espera! Se eu tiver uma batedeira manual (um recurso diferente) disponível, posso fazer essa parte de forma diferente, talvez até mais rápido ou sem depender da batedeira elétrica que pode quebrar."

• O "Bloco": O algoritmo agrupa vários passos que fazem sentido juntos (como "preparar a massa") em um "bloco".
• A Substituição: Ele tenta substituir esse "bloco" inteiro por uma nova sequência de ações que faz a mesma coisa, mas de um jeito mais flexível.
  • Na analogia da cozinha: Em vez de depender de uma batedeira específica, o novo plano diz: "Use a batedeira elétrica OU a manual OU bata com um fouet". Agora, se uma falhar, você tem outras opções. O plano não quebra!

4. Como o Algoritmo Funciona (Passo a Passo Simples)

1. Montar o Bloco: O algoritmo pega um plano rígido e agrupa tarefas que podem ser feitas juntas, criando "blocos" de ação.
2. Procurar Alternativas: Para cada bloco, ele pergunta: "Existe outra maneira de fazer isso usando recursos diferentes?" (Por exemplo, usar um segundo elevador em vez de um só, ou um robô diferente).
3. Trocar e Testar: Se encontrar uma alternativa, ele faz a troca.
   • Se a troca deixar o plano mais livre (menos regras de "quem vai antes de quem") e não custar mais caro, ele aceita a mudança.
   • Se a troca criar um conflito (ex: dois robôs tentando usar a mesma porta ao mesmo tempo), ele ajusta o plano para resolver o problema.
4. Limpar o Desperdício: No final, ele olha para o plano e remove qualquer passo que não seja mais necessário (como levar um pacote de volta para a loja quando já foi entregue).

Por que isso é importante?

• Resiliência: Se algo imprevisto acontecer (trânsito, máquina quebrada, falta de um funcionário), o plano não precisa ser refeito do zero. Como ele tem várias opções embutidas, o robô ou agente apenas escolhe o caminho alternativo que ainda funciona.
• Eficiência: O estudo mostrou que essa técnica consegue criar planos muito mais flexíveis do que os métodos anteriores, e faz isso em um tempo computacional razoável (não demora horas para calcular).
• Custo: Além de ser mais flexível, o método também consegue encontrar caminhos mais baratos, eliminando passos inúteis.

Resumo em uma frase

O artigo descreve um método inteligente que não apenas reorganiza as tarefas de um robô, mas troca pedaços inteiros do plano por versões alternativas e mais versáteis, garantindo que, mesmo quando o mundo real dá errado, o robô tenha sempre um "Plano B" pronto para funcionar sem travar.

Resumo técnico

Título: Melhorando a Flexibilidade de Execução de Planos usando Substituição de Blocos

Autores: Sabah Binte Noor e Fazlul Hasan Siddiqui (Universidade de Engenharia e Tecnologia de Dhaka, Bangladesh)
Publicação: Journal of Artificial Intelligence Research (JAIR), 2026.

---

1. O Problema

No planejamento de IA, planos de ordem parcial (POPs) são valorizados por sua flexibilidade, permitindo que ações sejam executadas em várias sequências válidas (linearizações) sem comprometer a correção do plano. Essa flexibilidade é crucial para agentes operarem em ambientes dinâmicos, onde recursos podem flutuar ou eventos inesperados podem ocorrer.

No entanto, os métodos tradicionais para maximizar essa flexibilidade têm limitações:

• Desordenação (Deordering): Remove ordenações desnecessárias, mas não altera o conjunto de ações do plano.
• Reordenação (Reordering): Modifica as ordenações existentes, mas geralmente mantém as mesmas ações e nomes de operadores.
• Limitação Atual: Estratégias existentes (como Explanation-based Order Generalization - EOG e Block Deordering) não permitem substituir subplanos inteiros por outros subplanos que utilizem recursos diferentes ou ações com nomes distintos, o que poderia eliminar redundâncias e aumentar significativamente a flexibilidade.

O problema central é: Como melhorar a flexibilidade de um plano existente substituindo seus subplanos (blocos) por alternativas externas ou internas que ofereçam menos restrições de ordenação, mantendo ou reduzindo o custo?

---

2. Metodologia Proposta: FIBS

Os autores propõem um novo algoritmo chamado FIBS (Flexibility Improvement via Block-Substitution). A abordagem baseia-se em três pilares principais:

A. Planos de Ordem Parcial Decompostos em Blocos (BDPO)

O método utiliza a estrutura de BDPO (Block Decomposed Partial-Order), onde ações coerentes são agrupadas em "blocos". Um bloco encapsula um subplano e pode ser tratado como uma unidade atômica. Isso permite que blocos distintos sejam executados em qualquer ordem, desde que não haja dependências entre eles.

B. Substituição de Blocos (Block-Substitution)

Diferente de métodos anteriores que apenas reordenam ou removem ações, o FIBS permite substituir um bloco existente (subplano) por um novo bloco (gerado por um planejador externo) que resolve o mesmo problema local, mas com:

1. Menos ordenações internas: Aumentando a flexibilidade.
2. Recursos alternativos: Por exemplo, usar um segundo elevador disponível em vez de um único, permitindo que tarefas sejam paralelizadas.
3. Validação de Ameaças: O algoritmo verifica rigorosamente se a substituição introduz ameaças (conflitos de fatos) e resolve-as através de promoção/demissão de ordenações ou substituições internas recursivas, garantindo que o plano resultante seja válido e acíclico.

C. O Algoritmo FIBS (Iterativo e "Anytime")

O algoritmo opera em quatro fases iterativas para otimizar o plano:

1. EOG (Generalização de Ordem Baseada em Explicação): Converte um plano sequencial inicial em um POP.
2. SD1 (Substituição-Desordenação 1): Tenta substituir blocos primitivos (ações individuais) para remover ordenações.
3. BD (Desordenação de Blocos): Agrupa ações coerentes em blocos compostos para eliminar mais ordenações.
4. SD2 (Substituição-Desordenação 2): Tenta substituir tanto blocos primitivos quanto compostos.

Critérios de Aceitação (RFO): Uma substituição é aceita apenas se resultar em um Otimização de Flexibilidade Relativa (RFO), definida como:

• Flexibilidade estritamente maior (flex(π') > flex(π)).
• Custo menor ou igual (cost(π') ≤ cost(π)).

Redução de Planos: O método também incorpora estratégias de Justificação Reversa e Justificação Gananciosa para eliminar operadores redundantes após a substituição, reduzindo o custo total do plano.

---

3. Contribuições Chave

1. Novo Paradigma de Substituição: Introduz a ideia de substituir subplanos inteiros por alternativas externas para melhorar a flexibilidade, indo além da simples reordenação de ações existentes.
2. Algoritmo FIBS: Desenvolve um algoritmo completo que integra desordenação de blocos com substituição de subplanos, garantindo a validade do plano através de mecanismos robustos de resolução de ameaças.
3. Prova de Corretude e Incompletude: O artigo fornece provas formais de que o algoritmo produz planos válidos, mas também demonstra sua incompletude (existem casos onde uma substituição válida existe, mas o algoritmo não a encontra devido a escolhas heurísticas de produtores mais antigos).
4. Redução de Custo: Demonstra que a substituição de blocos pode levar à identificação e remoção de ações redundantes, reduzindo o custo do plano além de aumentar a flexibilidade.

---

4. Resultados Experimentais

Os autores avaliaram o FIBS em 32 domínios das Competições Internacionais de Planejamento (IPC), utilizando 3.826 planos gerados pelo planejador LAMA.

• Melhoria na Flexibilidade:
  • O FIBS superou significativamente as técnicas de desordenação (EOG) e reordenação baseadas em MaxSAT (MR e MRR).
  • A flexibilidade média aumentou de 0.20 (EOG) para 0.32 (FIBS final).
  • O FIBS obteve melhor flexibilidade em 25 dos 32 domínios comparado ao MR e em 19 domínios comparado ao MRR.
• Desempenho Computacional:
  • Cobertura: O FIBS manteve 100% de cobertura (resolveu todos os problemas), enquanto as abordagens MaxSAT (MRR) tiveram queda de cobertura para 54% em planos grandes devido ao tamanho da codificação.
  • Tempo de Execução: O FIBS foi muito mais rápido (média de 106 segundos) comparado ao MRR (média de 1039 segundos) e MR (242 segundos). O FIBS mostrou-se escalável, enquanto o desempenho do MaxSAT degradou rapidamente com o aumento do tamanho do plano.
• Redução de Custo:
  • A aplicação de justificação para eliminar operadores redundantes resultou em uma redução média de custo de 5.33% a 5.91%, competindo favoravelmente com métodos de redução mínima de planos (MPR).
• Análise de Domínios:
  • O método foi particularmente eficaz em domínios onde recursos adicionais (como múltiplos robôs ou elevadores) estavam disponíveis, permitindo a substituição de subplanos sequenciais por alternativas paralelas.

---

5. Significância e Conclusão

Este trabalho representa um avanço significativo na otimização de planos de ordem parcial. Ao demonstrar que a substituição de subplanos é uma estratégia viável e superior à simples reordenação, os autores abrem novas portas para a criação de planos mais robustos e adaptáveis.

• Impacto Prático: O FIBS oferece uma solução "anytime" (que melhora com o tempo) que é computacionalmente eficiente, tornando-se viável para problemas de planejamento do mundo real onde o tempo de computação é limitado.
• Flexibilidade vs. Custo: O método consegue equilibrar a busca por máxima flexibilidade sem sacrificar a eficiência do custo, algo que métodos baseados em MaxSAT muitas vezes não conseguem fazer em escalas maiores.
• Futuro: Os autores sugerem que a exploração de blocos aleatórios e o uso de diferentes planejadores iniciais podem levar a melhorias adicionais, além da aplicação da substituição de blocos em outros contextos, como planejamento baseado em suposições.

Em resumo, o FIBS estabelece um novo estado da arte na melhoria da flexibilidade de execução de planos, combinando a eficiência da desordenação de blocos com o poder da substituição de subplanos.