Improving Execution Concurrency in Partial-Order Plans via Block-Substitution

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

Imagine que você é o gerente de uma grande equipe de construção. O seu trabalho é criar um plano para construir uma casa.

O Problema: O Plano Rígido vs. O Plano Flexível

No mundo da Inteligência Artificial (IA), existem dois tipos de planos:

Plano Sequencial (Rígido): É como uma receita de bolo passo a passo. "Primeiro bata os ovos, depois adicione a farinha, depois o açúcar." Você não pode pular etapas ou fazer coisas ao mesmo tempo. Se você tentar bater os ovos e adicionar a farinha ao mesmo tempo, a cozinha vira uma bagunça.
Plano de Ordem Parcial (Flexível): É como uma lista de tarefas para uma festa. Você precisa "comprar bebidas", "decorar a sala" e "chamar os convidados". A IA diz: "Você pode fazer essas coisas em qualquer ordem, desde que a festa aconteça". Isso é ótimo porque dá liberdade.

Mas e se a IA pudesse dizer: "Você pode fazer essas três coisas ao mesmo tempo"? Isso seria ainda melhor, pois a festa estaria pronta muito mais rápido. O problema é que, às vezes, tentar fazer tudo ao mesmo tempo causa conflitos. Por exemplo, você não pode "comprar bebidas" e "entregar bebidas" ao mesmo tempo se só tiver um carro.

A Solução: O "CIBS" (O Mestre da Troca)

Os autores deste artigo criaram um método chamado CIBS (Melhoria de Concorrência via Substituição de Blocos). Eles querem transformar planos flexíveis em planos super-rápidos, onde várias tarefas acontecem simultaneamente sem causar desastres.

Eles fazem isso em três etapas mágicas:

1. O "Desemaranhamento" (Block Deordering)

Imagine que seu plano de construção é um novelo de lã emaranhado. O primeiro passo é tentar desenrolar o máximo possível sem cortar nada. A IA agrupa tarefas que estão logicamente conectadas em "blocos".

Analogia: Em vez de pensar em "pintar a parede A" e depois "pintar a parede B", a IA cria um bloco chamado "Pintar o Quarto". Isso simplifica o plano, mostrando que o Quarto pode ser pintado em qualquer ordem em relação à Cozinha, desde que não haja conflito.

2. A Detecção de Conflitos (O "Não-Pode-Fazer-Junto")

Aqui está o segredo. Às vezes, mesmo que duas tarefas não estejam numa ordem rígida, elas não podem ser feitas ao mesmo tempo porque usam o mesmo recurso.

Analogia: Imagine que você tem dois blocos de trabalho: "Levar o passageiro A ao 3º andar" e "Levar o passageiro B ao 2º andar". Se você só tem um elevador, você não pode levar os dois ao mesmo tempo, mesmo que o plano diga que a ordem é livre. O elevador é o recurso compartilhado. A IA identifica esse conflito e coloca um sinal de "Proibido Fazer Junto" (#).

3. A Troca Mágica (Block Substitution)

Aqui é onde a mágica acontece. Se a IA vê que dois blocos não podem trabalhar juntos porque usam o mesmo elevador, ela pergunta: "E se trocássemos um dos elevadores?"

A Metáfora do Táxi: Imagine que você precisa levar duas pessoas para destinos diferentes.
- Situação Atual: Você tem apenas um táxi (Elevador 1). O plano diz: "Leve o passageiro A, depois leve o passageiro B". Eles não podem ir juntos.
- A Troca: A IA olha para o plano e diz: "Espere! Temos um segundo táxi (Elevador 2) disponível na garagem, mas o plano original não o usou."
- A Ação: A IA substitui a parte do plano que usava o "Elevador 1" por uma nova versão que usa o "Elevador 2".
- O Resultado: Agora, o passageiro A vai no Táxi 1 e o passageiro B vai no Táxi 2. Eles podem viajar ao mesmo tempo! O tempo total da viagem cai pela metade.

Por que isso é importante?

O artigo mostra que, ao fazer essas trocas inteligentes (substituir um recurso por outro disponível), a IA consegue criar planos onde muito mais coisas acontecem simultaneamente.

Eles mediram isso com um índice chamado cflex (flexibilidade de concorrência).

Um cflex baixo significa que o plano é lento e as coisas acontecem uma de cada vez.
Um cflex alto significa que o plano é um "relâmpago", com muitas coisas acontecendo em paralelo.

O Resultado Final

Os autores testaram isso em centenas de problemas reais (como logística, elevadores, robôs e até jogos de xadrez). Eles descobriram que:

A técnica funciona muito bem em planos de tamanho médio.
Ao trocar recursos (como usar um segundo robô ou um segundo elevador em vez de reutilizar o mesmo), eles conseguiram reduzir drasticamente o tempo de execução dos planos.
É como se a IA tivesse aprendido a dizer: "Não vamos esperar o elevador voltar; vamos pegar o outro que está livre!"

Em resumo: Este papel ensina a IA a não apenas organizar tarefas, mas a ser criativa na hora de escolher quais ferramentas usar, permitindo que o trabalho seja feito em equipe, simultaneamente, e muito mais rápido.

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

Título: Melhoria da Concorrência de Execução em Planos de Ordem Parcial via Substituição de Blocos

Autores: Sabah Binte Noor e Fazlul Hasan Siddiqui.

1. O Problema

No planejamento de IA, os Planos de Ordem Parcial (POP) oferecem flexibilidade ao permitir que ações não ordenadas sejam executadas em qualquer sequência. No entanto, a mera existência de ações não ordenadas não garante que elas possam ser executadas em paralelo (concorrentemente).

O problema central abordado é que, mesmo em um POP onde duas ações ou subplanos (blocos) não possuem uma restrição de ordem explícita, eles podem ainda assim não ser executáveis simultaneamente devido a conflitos de recursos (interferência). Por exemplo, dois blocos que utilizam o mesmo elevador ou robô não podem rodar em paralelo, mesmo que a ordem entre eles não esteja fixada.

A literatura anterior focou em otimizar a flexibilidade de ordenação (deordering/reordering), mas houve pouco foco em otimizar a concorrência (capacidade de execução paralela). O objetivo deste trabalho é minimizar as restrições de não-concorrência (pares de ações que não podem rodar juntos) para reduzir o tempo total de execução do plano.

2. Metodologia

Os autores propõem uma abordagem baseada em três pilares principais: formalização semântica, técnicas de desordenação e substituição de blocos.

A. Formalização e Definições

Plano Paralelo (Parallel Plan): Introduzido por Bäckström, inclui uma relação de não-concorrência (#) que especifica quais pares de ações não podem ser executados simultaneamente.
Plano Paralelo Decomposto em Blocos (PBD): Uma extensão dos Planos de Ordem Parcial Decompostos em Blocos (BDPO). Um PBD é definido como uma quadrupla $\langle O, B, \prec, \# \rangle$ , onde $O$ são operadores, $B$ são blocos (subplanos), $\prec$ são restrições de ordem e $\#$ são restrições de não-concorrência.
Condições de Não-Concorrência: O artigo estabelece condições necessárias e suficientes para que dois operadores (ou blocos) tenham uma restrição de não-concorrência, baseadas nas variáveis de estado do domínio (FDR - Finite Domain Representation). Dois operadores são não-concorrentes se:
1. Têm pré-condições diferentes na mesma variável.
2. Têm efeitos diferentes na mesma variável.
3. A pré-condição de um é diferente do efeito do outro na mesma variável.

B. Algoritmo CIBS (Concurrency Improvement via Block-Substitution)

O núcleo da proposta é o algoritmo CIBS, que opera em três fases para transformar um plano sequencial em um plano paralelo otimizado:

Generalização de Ordem Baseada em Explicação (EOG): Converte o plano sequencial em um POP, removendo ordens desnecessárias e identificando restrições de não-concorrência iniciais.
Desordenação de Blocos (Block Deordering - BD): Agrupa operadores coerentes em blocos hierárquicos. Isso remove muitas restrições de ordem, mas frequentemente mantém restrições de não-concorrência entre os blocos (ex: dois blocos usando o mesmo recurso).
Substituição para Concorrência (SC): Esta é a contribuição inovadora. O algoritmo tenta eliminar as restrições de não-concorrência restantes substituindo um bloco problemático por um subplano alternativo que não conflita com o bloco vizinho.
- Extensão de Blocos: Antes de substituir, o algoritmo pode "estender" um bloco, incorporando seus predecessores ou sucessores imediatos. Isso é crucial para garantir que o novo subplano substituto possa realizar a mesma tarefa sem depender de recursos específicos do bloco original (ex: usar um segundo elevador disponível em vez do primeiro).
- Geração de Subplanos: Utiliza um planejador externo (como o LAMA) para gerar soluções alternativas para a subtarefa definida pelo bloco estendido.
- Validação: A substituição só é aceita se eliminar a restrição de não-concorrência, não aumentar o custo do plano e manter a validade do plano global.

3. Principais Contribuições

Condições Necessárias e Suficientes: Formalização rigorosa das condições de não-concorrência entre operadores e subplanos no contexto de FDR.
Semântica PBD: Introdução do conceito de Parallel Block Decomposed (PBD) plans, definindo a semântica para permitir paralelismo em planos estruturados em blocos.
Algoritmo de Substituição de Blocos: Desenvolvimento de um método que não apenas reordena, mas substitui subplanos inteiros para resolver conflitos de recursos, algo que técnicas anteriores (como MaxSAT) não faziam eficientemente ou permitiam.
Métrica cflex: Introdução de uma nova métrica normalizada (cflex) que mede a razão entre pares de ações concorrentes e o total de pares. Os autores demonstram uma forte correlação negativa entre cflex e a duração mínima de execução do plano.
Extensão de Blocos: Procedimento para expandir blocos capturando vizinhos coesos, permitindo a substituição de subplanos que dependem de recursos específicos.

4. Resultados Experimentais

Os autores testaram o algoritmo CIBS em 3.303 planos provenientes de 33 domínios das Competições Internacionais de Planejamento (IPC).

Melhoria na Concorrência: O algoritmo demonstrou melhorias consistentes na métrica cflex ao longo das três fases (EOG $\to$ $\to$ BD $\to$ $\to$ SC).
- A média de cflex aumentou de 0,237 (após EOG) para 0,242 (após SC).
- Em domínios específicos como logistics, elevator, depots e pipesworld, a melhoria foi estatisticamente significativa.
Custo Computacional: Houve um aumento no tempo de execução (de ~1,6s para ~34s), mas isso é considerado aceitável dado o ganho em flexibilidade e potencial redução no tempo de execução real.
Comparação com MaxSAT: O CIBS superou abordagens baseadas em MaxSAT (MR e MRR) em termos de cobertura (capacidade de resolver mais problemas dentro do limite de tempo) e eficiência, embora as abordagens MaxSAT possam encontrar soluções ótimas em casos menores. O CIBS fornece soluções viáveis rapidamente e melhora a concorrência iterativamente.
Correlação com Tamanho do Plano: A melhoria na concorrência foi mais pronunciada em planos de tamanho médio (50 a 300 operadores). Planos muito grandes (>350 operadores) apresentaram limitações devido ao tempo de computação e à estrutura do domínio.

5. Significância e Conclusão

Este trabalho é significativo porque muda o paradigma de otimização de planos: em vez de apenas reorganizar a ordem das ações existentes, ele modifica a estrutura do plano substituindo subplanos inteiros para eliminar conflitos de recursos.

Impacto Prático: Ao aumentar a concorrência, o tempo total de execução de planos em sistemas multiagente ou robóticos pode ser reduzido significativamente.
Viabilidade: A abordagem é computacionalmente mais eficiente que métodos de reordenação global baseados em MaxSAT para problemas de grande escala.
Futuro: Os autores sugerem que a técnica pode ser expandida para planos com operadores interagentes e que a descoberta de novos subplanos candidatos (além dos encapsulados em blocos) é uma direção promissora.

Em resumo, o artigo apresenta uma solução robusta para transformar planos parciais em planos verdadeiramente paralelos, superando limitações de recursos através da substituição inteligente de subplanos.