Handling Infinite Domain Parameters in Planning Through Best-First Search with Delayed Partial Expansions

Este artigo propõe um algoritmo de busca heurística de melhor primeiro com expansões parciais adiadas para tratar explicitamente parâmetros de controle de domínio infinito como pontos de decisão em esquemas de planejamento sistemático, demonstrando ser uma alternativa competitiva às abordagens existentes.

O essencial

Imagine que você é um chef de cozinha tentando criar a receita perfeita para um prato novo. No mundo da "planejamento automático" (onde computadores decidem o que fazer), os computadores geralmente trabalham com ingredientes fixos: "pegue 1 ovo", "pegue 2 xícaras de farinha". O número de opções é limitado e finito.

Mas, e se o computador precisasse decidir exatamente quanto de um ingrediente usar, e essa quantidade pudesse ser qualquer número? E se pudesse ser 1,5 xícara, ou 1,532456... ou qualquer valor entre 1 e 2?

É aqui que entra o problema que este artigo resolve. Vamos explicar a ideia de forma simples, usando analogias do dia a dia.

O Problema: O "Mar de Infinitas Escolhas"

No planejamento tradicional, o computador olha para um mapa com estradas finitas. Ele sabe que, na interseção A, pode virar à esquerda ou à direita. São apenas duas opções.

Mas, com os parâmetros de controle (como a velocidade de um robô, a quantidade de combustível injetado ou a força de um braço mecânico), o computador não tem apenas duas opções. Ele tem um mar infinito de escolhas. Ele poderia escolher a velocidade 10, 10,1, 10,0001, etc.

Se o computador tentar verificar todas as possibilidades (como um chef provando cada grama de sal possível), ele nunca terminaria. O computador ficaria travado, tentando calcular infinitas opções.

A Solução: O "Explorador Ametodico" (S-BFS)

Os autores criaram um novo algoritmo chamado S-BFS (Busca em Primeira Melhor por Amostragem). Em vez de tentar ver tudo de uma vez, eles propuseram uma estratégia inteligente de "exploração parcial".

Pense nisso como um detetive investigando uma cidade gigante:

1. A Abordagem Antiga (O Detetive Perfeccionista):
   O detetive antigo tentaria visitar cada casa da cidade antes de decidir para onde ir. Como a cidade é infinita, ele nunca sairia do ponto de partida.

2. A Abordagem Nova (O Detetive Inteligente):
   O novo detetive (nosso algoritmo) faz algo diferente:

   • Ele chega em uma encruzilhada.
   • Em vez de visitar todas as casas, ele escolhe aleatoriamente (ou de forma inteligente) visitar apenas uma casa vizinha.
   • Ele olha para dentro dessa casa. Se parecer promissor, ele anota o caminho.
   • O Pulo do Gato (Expansão Parcial Atrasada): O detetive não descarta a encruzilhada original! Ele volta para ela, mas agora sabe que já explorou uma das opções. Ele deixa a encruzilhada "aberta" para voltar lá mais tarde e escolher outra casa vizinha, caso a primeira não fosse tão boa assim.

Isso é o que chamam de "Expansão Parcial Atrasada". O computador não tenta resolver tudo de uma vez. Ele dá um "tiro de prova", vê se funciona, e se precisar, volta e tenta outro número.

As Duas Ferramentas Mágicas

Para que esse detetive não fique perdido ou vire em círculos, o algoritmo usa duas ferramentas:

1. A Função de Amostragem (O Mapa de Probabilidades):
   É como um guia que diz: "Ei, tente visitar casas na faixa de 1 a 2 metros de distância primeiro". O algoritmo não chuta qualquer número; ele "amostra" (escolhe) números dentro de um intervalo com uma certa probabilidade. Às vezes ele escolhe números aleatórios (como jogar um dado), às vezes escolhe os extremos (0 e 1) para ver o que acontece.

2. A Função de Retificação (O "Cinto de Segurança"):
   Imagine que o detetive volta muitas vezes para a mesma encruzilhada para tentar novas casas. Se ele ficar lá para sempre, ele nunca chega ao destino.
   A "Retificação" é como um relógio que aumenta o preço da estadia. Cada vez que o detetive volta para tentar outra opção no mesmo lugar, o "custo" de ficar ali aumenta um pouco (como se a gasolina estivesse subindo).

   • No começo, é barato tentar várias opções.
   • Depois de um tempo, fica tão caro ficar tentando novas opções no mesmo lugar que o detetive é forçado a seguir em frente para explorar novos caminhos.
     Isso garante que o algoritmo não fique preso em um loop infinito e, eventualmente, encontre uma solução.

O Resultado: O que eles descobriram?

Os autores testaram essa ideia em vários cenários (como drones voando, robôs movendo blocos e sistemas de controle).

• Comparação: Eles compararam seu método com outras técnicas que tentam resolver o problema transformando-o em equações matemáticas complexas (como o planner "NextFLAP").
• Vantagem: O método deles (S-BFS) conseguiu resolver muito mais problemas do que os outros. Enquanto os outros ficavam travados tentando calcular o "número perfeito" de forma exata, o S-BFS foi explorando, testando e encontrando soluções "boas o suficiente" rapidamente.
• Qualidade: As soluções encontradas pelo S-BFS às vezes não são as absolutamente perfeitas (o caminho mais curto possível), mas são soluções viáveis encontradas em tempo recorde, o que é crucial para robôs e sistemas reais que não podem esperar horas para decidir.

Resumo em uma frase

O artigo apresenta um jeito inteligente de computadores lidarem com infinitas opções numéricas: em vez de tentar calcular tudo de uma vez (o que é impossível), eles tiram amostras aleatórias, testam, e voltam para tentar outras opções apenas se necessário, garantindo que nunca fiquem presos e sempre encontrem um caminho para o objetivo.

É como dizer: "Não tente adivinhar o número exato de açúcar para o bolo de uma vez. Tente 1 colher, veja como fica. Se precisar, tente 1,5. Se não ficar bom, tente 2. E assim você chega no sabor perfeito sem precisar provar todas as combinações possíveis do universo."

Resumo técnico

1. O Problema

O planejamento automatizado clássico lida com um espaço de estados finito, onde o número de ações instanciadas é limitado pelo número de objetos no mundo. No entanto, com a introdução de variáveis numéricas contínuas (parâmetros de controle) em extensões do PDDL (como PDDL2.1 e propostas futuras), o espaço de decisão torna-se infinito.

• Desafio Central: Os parâmetros de controle representam quantidades físicas contínuas que o planejador deve escolher para que uma ação tenha o efeito desejado (ex: quanto de combustível injetar, quanto tempo durar uma ação).
• Limitação das Abordagens Atuais: Os planejadores de última geração (como POPCORN e NextFLAP) tratam esses parâmetros implicitamente como restrições a serem satisfeitas (usando Programação Linear ou SMT), em vez de pontos de decisão explícitos na busca. Outras abordagens usam redes neurais para concretizar planos abstratos, tratando os parâmetros como "caixas pretas" e contornando a busca sistemática.
• Objetivo do Artigo: Desenvolver um algoritmo de busca sistemática que trate os parâmetros de controle como pontos de decisão explícitos dentro de um espaço infinito, garantindo a completude e a eficiência na resolução de problemas de planejamento.

2. Metodologia

Os autores propõem um novo algoritmo chamado Busca Best-First por Amostragem (Sampling Best-First Search - S-BFS). A metodologia baseia-se em duas modificações fundamentais ao framework clássico de Busca Best-First (BFS):

A. Formalização do Problema

O problema é definido como um sistema de transição onde o espaço de decisão de um estado $s$ é o conjunto de pares $\langle a, \mu \rangle$, sendo $a$ uma ação e $\mu$ uma valoração dos parâmetros de controle (variáveis contínuas em intervalos). Diferente de abordagens anteriores, o espaço de decisão é explicitamente infinito.

B. Expansão Parcial Diferida (Delayed Partial Expansions)

Como um nó na árvore de busca pode ter infinitos sucessores (devido aos valores contínuos), é impossível expandi-lo completamente. O S-BFS resolve isso através de:

1. Função de Amostragem ($\phi$): Em vez de gerar todos os sucessores, o algoritmo amostra um subconjunto de sucessores de acordo com uma densidade de probabilidade definida sobre o espaço de decisão.
2. Expansão Incremental: Um estado não é fechado após uma expansão parcial. Ele é reinsertado na lista aberta (fila de prioridade) para futuras expansões parciais se parecer promissor.
3. Função de Retificação ($r_h$): Para evitar que estados reinsertados dominem a busca infinitamente ou causem loops, o valor de avaliação do nó (NEC - Node Evaluation Criterion) é ajustado com base no número de vezes que o nó foi reexpandido. Isso equilibra a exploração (tentar novos sucessores) e a exploração (aprofundar caminhos promissores).

C. Algoritmo S-BFS

O algoritmo opera em um ciclo:

1. Seleciona o nó com o menor valor $f$ (geralmente $g + h$ ou apenas $h$).
2. Se não é o objetivo, amostra um sucessor $\langle a, \mu \rangle$ usando $\phi$.
3. Gera o estado sucessor $s'$ e insere na fila.
4. Reinsere o estado original $s$ na fila com um valor $f$ retificado ($r_h$) para garantir que ele seja reavaliado.

3. Principais Contribuições

1. Novo Paradigma de Busca: Propõe tratar parâmetros de controle como variáveis de decisão explícitas em vez de restrições, permitindo uma busca sistemática em espaços infinitos.
2. Algoritmo S-BFS: Introduz o conceito de expansão parcial diferida combinada com amostragem probabilística para lidar com a infinitude do espaço de decisão.
3. Garantias Teóricas:
   • Completude Probabilística: O artigo prova que, sob condições específicas (função de amostragem com suporte total no domínio de decisão e função de retificação monotonamente crescente), o algoritmo encontrará uma solução com probabilidade 1 quando o número de passos tende ao infinito.
   • Limites de Qualidade: Para a variante que considera o custo acumulado (S-A), é provado que o custo da solução encontrada é limitado pelo valor $f$ do estado inicial após um certo número de reexpansões.
4. Análise de Estratégias: Investiga o impacto de diferentes funções de retificação (linear, quadrática, logarítmica) e estratégias de amostragem (sistemática, uniforme, guiada por heurística).

4. Resultados Experimentais

Os autores compararam o S-BFS com o planejador NextFLAP (que usa otimização e busca parcial de ordem) e com MCTS (Monte-Carlo Tree Search) com Progressive Widening.

• Domínios: Testes realizados em domínios existentes (CASHPOINT, PROCUREMENT, TERRARIA) e extensões de domínios do IPC Numérico (COUNTERS, BLOCKS-GROUPING, DRONE, SAILING).
• Desempenho em Cobertura:
  • O S-BFS (especificamente a variante S-G com retificação logarítmica) resolveu todos os 140 problemas propostos.
  • O NextFLAP resolveu menos problemas que o S-BFS, embora tendesse a gerar planos com menos ações (mais curtos) nos problemas que ambos resolveram.
  • O MCTS teve desempenho muito inferior, resolvendo poucos problemas.
• Estratégias Otimas:
  • Retificação Logarítmica: Foi a mais eficaz, permitindo que a heurística guiasse a busca sem penalidades excessivas que atrasariam a convergência.
  • Amostragem: As estratégias Sistemática (amostrar extremos e meios) e Uniforme superaram a amostragem guiada por heurística. A amostragem guiada falhou devido a "platôs" na função heurística, tornando-a computacionalmente custosa sem ganho real de eficiência.
• Qualidade da Solução: O S-A (que considera o custo) produziu soluções de maior qualidade (menos ações) que o S-G, mas com menor cobertura de instâncias resolvidas e maior tempo de execução.

5. Significado e Conclusão

Este trabalho representa um avanço significativo na interseção entre planejamento automatizado e variáveis contínuas.

• Mudança de Perspectiva: Demonstra que tratar parâmetros de controle como pontos de decisão em uma busca sistemática é viável e competitivo, superando a abordagem tradicional de tratá-los apenas como restrições de otimização.
• Viabilidade Prática: A prova de completude probabilística e os resultados experimentais mostram que é possível navegar em espaços de decisão infinitos de forma eficiente sem recorrer a métodos de "caixa preta" ou discretização grosseira prévia.
• Futuro: O trabalho estabelece as bases para integrar essa abordagem em planejamento temporal (PDDL+) e para o desenvolvimento de novas heurísticas que considerem explicitamente espaços de decisão infinitos.

Em resumo, o S-BFS oferece uma alternativa robusta e teoricamente fundamentada para resolver problemas de planejamento complexos que envolvem quantidades contínuas, superando os planejadores atuais em termos de capacidade de encontrar soluções (cobertura), embora ainda haja espaço para melhorar a qualidade ótima dos planos gerados.