Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

Resumo Técnico: Expansão Vertical de Informação Dupla para Seleção de Nós Multiobjetivo em Busca Baseada em Conflitos de Tempo Real (Anytime)

Definição do Problema
A Busca Baseada em Conflitos (CBS) é um algoritmo exato líder para o Planejamento de Trajetórias de Múltiplos Agentes (MAPF). A CBS padrão emprega uma estratégia de busca de melhor primeira (BFS) no nível superior, selecionando nós com a chave de limite inferior mínima para expansão. Embora essa abordagem seja eficiente na minimização do número de nós expandidos e no avanço rápido do limite dual (o certificado de otimalidade), ela sofre de três desvantagens significativas em implementações práticas:

1. Intensidade de Memória: Mantém uma fronteira aberta extensa, que pode exceder os limites de memória embarcada.
2. Baixa Continuidade Pai-Filho: Salta frequentemente entre ramos não relacionados da árvore de restrições, falhando em explorar os ganhos de eficiência de processar um nó filho imediatamente após seu pai (onde apenas uma restrição muda).
3. Ausência de Comportamento Anytime: Tipicamente não fornece uma solução viável (incumbente) até que o algoritmo termine e a otimalidade seja certificada, tornando-o inadequado para sistemas que exigem planos viáveis intermediários sob restrições de tempo ou recursos.

Alternativas existentes, como a CBS de Indução Iterativa (IDCBS), abordam a memória usando passagens de busca em profundidade, mas introduzem trabalho repetido e ainda falham em fornecer incumbentes intermediários. Este artigo argumenta que a seleção de nós deve ser tratada como uma escolha de design modular, em vez de um detalhe de implementação fixo, permitindo um trade-off multiobjetivo entre nós expandidos, uso de memória, continuidade pai-filho e descoberta de incumbentes.

Metodologia
Os autores formalizam a seleção de nós de alto nível em CBS como uma política modular $\pi$ que determina a ordem de expansão dos nós sem alterar a busca de baixo nível, as regras de ramificação ou as heurísticas admissíveis. Eles provam que a alteração desta política preserva a exatidão da CBS, desde que as condições padrão de poda de branch-and-bound sejam mantidas.

O artigo introduz a Expansão Vertical de Informação Dupla (DIVE), uma nova política de seleção de nós projetada para ocupar um "meio-termo ausente" no espaço de design. A DIVE opera através de dois mecanismos distintos:

1. Fase de Mergulho (Dive Phase - Orientada à Profundidade): Quando um nó é expandido, a DIVE tenta continuar um "mergulho" expandindo imediatamente seu melhor filho (menor limite inferior) se o limite desse filho for estritamente menor que o custo do incumbente atual ($z_P$). Isso explora a localidade pai-filho e busca soluções viáveis precocemente.
2. Fase de Reancoragem (Reanchoring Phase - Melhor Limite): Se um mergulho termina (porque o melhor filho não pode melhorar o incumbente ou não existem filhos), a política retorna à fronteira global de melhor limite para selecionar a raiz do próximo mergulho. Isso garante progresso regular em direção ao certificado de otimalidade.

A DIVE também incorpora a poda de incumbente: qualquer nó com um limite inferior maior ou igual à atual melhor solução viável é podado. Isso permite que a DIVE explore com segurança a "zona primal" (nós com custos superiores ao ótimo) para encontrar boas soluções viáveis sem comprometer a prova de otimalidade final.

O artigo propõe ainda a DIVE com Restrição de Memória (MC-DIVE), uma variante responsiva que alterna para uma busca de profundidade pura se a fila aberta exceder um limite específico de memória, demonstrando como a seleção de nós pode se adaptar a restrições de tempo de execução.

Principais Contribuições

1. Separação Formal de Política e Correção: O artigo prova que a seleção de nós é independente da exatidão da CBS. Sob condições padrão de branch-and-bound, qualquer política que selecione nós do conjunto aberto preserva a otimalidade, permitindo o design de políticas que otimizem métricas além do simples número de nós.
2. A Política DIVE: A introdução da DIVE, que combina o reancoramento de melhor limite com mergulhos orientados à profundidade. Demonstra-se que ela é um ponto de Pareto distinto no espaço multiobjetivo, minimizando as quebras de mergulho (transições entre cadeias pai-filho) enquanto mantém o progresso do melhor limite.
3. Estrutura Multiobjetivo: Os autores definem um framework para avaliar políticas baseadas em cinco objetivos concorrentes: nós expandidos, quebras de mergulho, tamanho máximo da fila, progresso do limite primal (qualidade do incumbente) e progresso do limite dual (velocidade do certificado).
4. Análise Teórica: O artigo fornece limites teóricos sobre o desempenho da BFS, DFS, ID e DIVE em árvores de busca perfeitas, prevendo que a BFS minimiza nós, a ID minimiza o tamanho da fila e a DIVE minimiza as quebras de mergulho.

Resultados Experimentais
Experimentos em benchmarks padrão de MAPF (mapas vazios, aleatórios, salas e armazéns) com densidades variáveis de robôs apoiam o mapa de trade-off teórico:

• Nós Expandidos: A BFS permanece a mais eficiente em termos de número de nós expandidos. A DIVE expande um pouco mais de nós (18–57% a mais em alguns benchmarks) devido à exploração controlada da zona primal, mas significativamente menos que a ID (que pode expandir 13–134% a mais devido a reinicializações repetidas).
• Quebras de Mergulho: A DIVE reduz consistentemente o número de quebras de mergulho em 6% a 51% em comparação com a BFS, melhorando significativamente a continuidade pai-filho.
• Uso de Memória: A DIVE reduz o tamanho máximo da fila em 44% a 86% em comparação com a BFS, embora a ID permaneça a mais eficiente em memória (reduzindo o tamanho da fila em 89–97%).
• Comportamento Anytime: A DIVE é a única política que fornece consistentemente incumbentes viáveis precoces com lacunas (gaps) primal-duais certificadas antes da conclusão da busca. Em muitos casos, a DIVE encontra uma solução ótima antes que o limite dual alcance o ótimo, enquanto a BFS e a ID não fornecem solução até a terminação.
• Inícios Quentes (Warm Starts): Em regimes densos onde encontrar um incumbente inicial é difícil, a DIVE beneficia-se significativamente de inícios quentes (ex: de PIBT), permitindo resolver instâncias que de outra forma sofreriam timeout.
• Ablação: Remover o componente de "busca diversificada" (recomeços de melhor limite) da DIVE resulta em uma política que se comporta como uma DFS podada, exigindo substancialmente mais nós e quebras de mergulho, confirmando que o mecanismo de reancoragem é crítico para a eficiência da DIVE.

Significância e Alegações
O artigo afirma que a DIVE não domina universalmente as políticas existentes, mas oferece um ponto de operação distinto no espaço de design da CBS exata. Sua significância reside em transformar a CBS exata em um algoritmo anytime que pode:

• Fornecer soluções viáveis de alta qualidade com lacunas certificadas sob restrições de tempo ou memória.
• Reduzir a pressão de memória e melhorar o tempo de execução da implementação através de melhor continuidade pai-filho.
• Adaptar-se a contextos de implantação (ex: robôs com memória limitada) através de variantes responsivas como a MC-DIVE.

Os autores enfatizam que, embora a BFS seja ótima para minimizar a contagem de nós e a ID seja ótima para minimizar a memória explícita, a DIVE é a escolha preferencial quando o sistema exige um equilíbrio desses fatores, especificamente quando soluções viáveis precoces e redução de quebras de mergulho são críticas para aplicações robóticas do mundo real. O trabalho motiva uma mudança de visão, tratando a seleção de nós não como um heurístico fixo, mas como um parâmetro de design multiobjetivo ajustável.