Resumo Técnico: Busca Baseada em Conflitos de Horizonte Adaptativo para Busca de Caminhos Multiagente em Malha Fechada

Declaração do Problema

A Busca de Caminhos Multiagente (MAPF) é um problema fundamental de coordenação para grandes frotas de robôs em armazéns automatizados e logística, exigindo que agentes se movam de vértices de início a objetivo em um grafo sem colisões. Embora o MAPF ótimo seja NP-difícil, os solvers existentes enfrentam um compromisso entre escalabilidade e garantias de desempenho.

• Planejadores de malha aberta (ex: Conflict-Based Search padrão, CBS) computam trajetórias completas antes da execução. Embora ofereçam garantias de otimalidade, sofrem com alta latência de planejamento e baixa escalabilidade em instâncias densas de longo horizonte, atrasando a execução das ações.
• Heurísticas de malha fechada reduzem a latência ao replanejar a partir do estado atual, mas frequentemente carecem de garantias de desempenho confiáveis, limitando sua utilidade em implantações de missão crítica.
• Abordagens de horizonte finito (ex: Windowed CBS/RHCR) tentam preencher essa lacalidade, mas enfrentam um "dilema de seleção de horizonte": um horizonte de planejamento fixo deve ser escolhido a priori. Um horizonte pequeno é eficiente, mas míope, enquanto um horizonte grande melhora a qualidade da solução ao custo de um crescimento exponencial da busca. Além disso, métodos de janela fixa frequentemente perdem as garantias de completude e otimalidade assintótica do CBS padrão.

Metodologia: Busca Baseada em Conflitos de Malha Fechada com Horizonte Adaptativo (ACCBS)

O artigo propõe o ACCBS, um algoritmo de MAPF de malha fechada que combina o CBS de horizonte finito com um mecanismo de horizonte dinâmico inspirado no Controle Preditivo Baseado em Modelo (MPC).

Mecanismos Principais

1. CBS de Malha Fechada de Horizonte Finito:

   • Em vez de resolver para a trajetória completa, o algoritmo planeja sobre um horizonte de olhar à frente (lookahead) finito $H$.
   • Ele otimiza uma função de custo composta por um custo corrente (passos dados para atingir o objetivo) e um custo terminal (heurística admissível que estima a distância restante até o objetivo).
   • Em cada passo de tempo $t$, ele resolve conflitos apenas dentro da janela de olhar à frente, executa o primeiro movimento e replaneja a partir do novo estado.

2. Horizonte Adaptativo via Aprofundamento Iterativo:

   • O ACCBS não fixa o horizonte $H$ antecipadamente. Em vez disso, ele mantém um horizonte corrente $h_r$ que começa em 1 e cresce incrementalmente até um máximo de $H_{max}$, desde que o orçamento de tempo o permita.
   • Isso permite que o algoritmo retorne uma solução viável de baixa latência imediatamente (com $h_r=1$) e a refine com horizontes de olhar mais longos se o tempo permitir, exibindo comportamento anytime.

3. Prefixo Ativo e Reuso da Árvore de Restrições:

   • Para evitar o custo proibitivo de reiniciar a busca toda vez que o horizonte aumenta, o ACCBS introduz o conceito de um prefixo ativo. Os conflitos são resolvidos apenas dentro do prefixo ativo atual de comprimento $h_r$; conflitos além deste prefixo são temporariamente ignorados.
   • Invariância de Custo (Lema III.1): O artigo prova que, sob suposições específicas de planejadores de baixo nível (sufixos seguem caminhos curtos), o custo de um nó permanece invariante quando o horizonte é estendido.
   • Reuso da Árvore de Restrições (Proposição III.1): Como os custos e as relações pai-filho são preservados, a árvore de restrições construída para um horizonte menor $h$ é uma subárvore válida para $h+1$. Isso permite que o ACCBS expanda o horizonte de forma contínua sem reiniciar a busca, tornando o esforço computacional cumulativo comparável a uma única execução no horizonte máximo.

Garantias Teóricas

• Completude e Otimalidade: O Teorema III.1 estabelece que, se o orçamento de tempo for infinito e $H_{max}$ for pelo menos o makespan de uma solução ótima, o ACCBS é completo e retorna uma solução globalmente ótima (Soma de Custos, SOC).
• Propriedade Anytime: À medida que o tempo de execução aumenta, o custo da melhor solução encontrada é monotonicamente não decrescente (limitado pelo custo ótimo) e converge para o ótimo.
• Viabilidade de Passo Único: O algoritmo garante um comando de passo único livre de colisões em cada passo de tempo por construção, pois sempre executa o primeiro passo de um nó com um prefixo ativo livre de conflitos (onde $h_r \ge 1$).

Resultados Experimentais

Os autores avaliaram o ACCBS contra baselines incluindo PIBT, EECBS, MAPF-LNS2, LaCAM2/3 e RHCR em configurações de execução de tiro único (one-shot), vitalícia (lifelong) e estocástica.

• MAPF de Tiro Único (One-Shot): O ACCBS alcança um equilíbrio favorável entre eficiência computacional e qualidade da solução. À medida que o orçamento de tempo por passo aumenta, o ACCBS reduz a Soma de Custos (SOC) e se aproxima da otimalidade, superando heurísticas rápidas como o PIBT e evitando as falhas de timeout de solvers de trajetória completa como o EECBS em mapas densos.
• MAPF Vitalício (Lifelong): Em cenários com objetivos variáveis, o ACCBS demonstra um rendimento (throughput) competitivo. Seu horizonte adaptativo permite que ele escale para frotas maiores onde métodos de janela fixa (RHCR) sofrem timeout.
• Incertezas Estocásticas: Em simulações com atrasos de execução e chegada de novos agentes, o ACCBS supera os baselines de malha aberta. Métodos de malha aberta são limitados pela necessidade de replanejar trajetórias completas após distúrbios, enquanto o ACCBS absorve naturalmente os distúrbios ao replanejar a partir do estado atual.
• Estudo de Ablação: O artigo observa que adicionar a seleção de conflito priorizado (PC) ao ACCBS pode, às vezes, reduzir a qualidade da solução sob orçamentos fixos, pois o custo de classificação de conflitos supera os benefícios da redução nas expansões da árvore.

Significância e Alegações

O artigo afirma que o ACCBS aborda o compromisso crítico entre latência de planejamento e qualidade da solução em sistemas multiagente. Suas principais contribuições são:

1. Eliminação de Escolhas de Design Frágeis: Ao adaptar o horizonte online, o ACCBS remove a necessidade de ajustar manualmente um horizonte fixo que depende das características específicas da instância e dos orçamentos de tempo.
2. Expansão Eficiente do Horizonte: Através da invariância de custo e do reuso da árvore de restrições, o algoritmo alcança os benefícios do aprofundamento iterativo sem o custo computacional associado de reiniciar buscas.
3. Restauração de Garantias: Diferente dos métodos de malha fechada de janela fixa, o ACCBS recupera as garantias de otimalidade assintótica e completude do CBS padrão.
4. Robustez: A formulação de malha fechada acomoda naturalmente distúrbios online (atrasos, novos agentes) sem exigir o replanejamento de trajetórias completas.

Os autores posicionam o ACCBS como uma solução prática para implantações de larga escala e missão crítica, onde tanto a flexibilidade de execução quanto as garantias de desempenho são necessárias.