Resumo Técnico: Revisão, Simulações e Modificações em Métodos de Busca de Caminho Multiagente Dinâmico

1. Definição do Problema

Este artigo aborda a Busca de Caminho Multiagente Dinâmica (D-MAPF), um problema de planejamento complexo situado na interseção entre ambientes dinâmicos, observabilidade parcial e coordenação entre agentes. Diferente da Busca de Caminho Multiagente (MAPF) estática, onde o mapa é fixo, a D-MAPF envolve ambientes onde obstáculos aparecem e desaparecem em cronogramas desconhecidos. Além disso, os agentes operam sob observabilidade parcial, o que significa que eles apenas detectam obstáculos quando entram em seu raio de visão específico (via ray-casting), em vez de possuírem conhecimento global do ambiente.

O estudo foca em um cenário baseado em grade com movimento de quatro conexões, onde múltiplos agentes devem atingir objetivos individuais simultaneamente. O problema é limitado por:

• Obstáculos Dinâmicos: Os obstáculos seguem cronogramas determinísticos ou aleatórios (tempos de aparecimento/desaparecimento) desconhecidos para os agentes até serem detectados.
• Planejamento Priorizado: Para gerenciar a complexidade combinatória, o sistema utiliza uma abordagem desacoplada onde os agentes planejam sequencialmente com base em uma ordem de prioridade fixa, tratando agentes planejados anteriormente como obstáculos móveis em uma tabela de reserva compartilhada.
• Exclusão de Solucionadores Acoplados Ótimos: Algoritmos como a Busca Baseada em Conflitos (CBS) são excluídos devido à sua inviabilidade computacional em cenários de replanejamento reativo e em tempo real com mudanças ambientais frequentes e observabilidade parcial.

2. Metodologia

Os autores avaliaram seis algoritmos representativos dentro de um framework de simulação unificado. Todos os algoritmos compartilham o mesmo mapa, cronogramas de obstáculos, parâmetros de agentes e sistemas de reserva para garantir uma comparação justa.

2.1 Algoritmos Avaliados

1. Dijkstra: Serve como um planejador estático de linha de base. Ele realiza buscas de custo uniforme completas em cada etapa de replanejamento sem orientação heurística ou consciência temporal, tratando as reservas como blocos estáticos.
2. D Lite:* Uma busca heurística incremental projetada para ambientes dinâmicos. Ele repara caminhos existentes propagando correções de custo apenas para as partes afetadas do grafo, em vez de recomputar do zero.
3. Space-Time A (STA):** Estende o A* incorporando o tempo na representação do estado (posição + passo de tempo), permitindo a evasão de colisões via tabelas de reserva.
4. WHCA (Windowed Hierarchical Cooperative A):** Um algoritmo cooperativo que restringe o planejamento a uma janela de tempo fixa (ex: 16 passos), planejando em direção a waypoints iterativamente.
5. M (M-Star):* Um algoritmo multiagente que planeja caminhos independentemente e apenas expande o espaço de busca para configurações conjuntas quando colisões são detectadas.
6. A (Proposto):** Um novo método introduzido como a principal contribuição.

2.2 O Algoritmo A**

O A** é projetado especificamente para planejamento reativo em configurações dinâmicas e de observabilidade parcial. Sua inovação central é o desacoplamento da geração de caminho geométrico offline da adaptação temporal online usando uma abordagem baseada em templates:

• Geração de Templates (Offline/Pré-computação): Após a inicialização ou quando o conjunto de obstáculos conhecidos de um agente muda, o algoritmo gera $k$ caminhos candidatos (templates) usando uma busca A 2D penalizada*.
  • Após encontrar um caminho, uma penalidade fixa é adicionada ao custo de travessia de cada célula desse caminho.
  • Isso força as buscas subsequentes a encontrarem rotas geometricamente distintas, criando um conjunto diversificado de caminhos candidatos.
  • Obstáculos dinâmicos ativos conhecidos recebem penalidades adicionais para desviar os templates de regiões perigosas.
• Reconexão Online (Adaptação Temporal): Quando um replanejamento é acionado (ex: um obstáculo bloqueia o caminho atual), o A** não busca em todo o espaço. Em vez disso, ele tenta reconectar a posição atual do agente a qualquer ponto acessível ao longo dos templates armazenados.
  • Ele computa uma "ponte" usando Space-Time A* da posição atual para um ponto específico em um template.
  • Ele valida a "cauda" (o restante do template) contra o tempo absoluto esperado para garantir que nenhum obstáculo dinâmico seja ativado ao longo da rota.
  • A combinação de ponte e cauda que minimiza o comprimento total do caminho é selecionada.
• Fallback: Se a reconexão a todos os templates existentes falhar, novos templates são gerados a partir do estado atual, e o processo se repete.

3. Contribuições Principais

O artigo apresenta cinco contribuições específicas:

1. Formalização e Framework: Os autores formalizam a D-MAPF como um problema reativo e de observabilidade parcial em uma grade com obstáculos dinâmicos agendados no tempo e alcances de visão por agente. Eles fornecem um framework de simulação para instanciar este cenário para benchmarking.
2. Integração Algorítmica: Seis algoritmos diversos (Dijkstra, D* Lite, STA*, WHCA*, M* e A**) foram integrados em um framework comum, permitindo benchmarking sistemático e comparação direta de desempenho.
3. Filtro de Obstáculos Baseado em Visão: Um filtro transparente é introduzido para impor a observabilidade parcial em todos os planejadores sem modificar sua lógica de busca central, garantindo que os agentes apenas reajam aos obstáculos observados.
4. Avaliação Empírica: Uma avaliação abrangente é conduzida em 8 mapas de benchmark, 10 configurações de contagem de agentes (1–10 agentes) e 100 repetições por combinação. As métricas incluem Soma de Custos (SoC), Makespan, taxas de falha e tempo de computação.
5. Caracterização do A:** O artigo introduz e avalia o A**, demonstrando que sua abordagem baseada em templates equilibra efetivamente a qualidade da solução e a eficiência do replanejamento em ambientes dinâmicos.

4. Resultados Experimentais

Os experimentos foram realizados em 8 mapas (incluindo configurações de vazio, labirinto, aleatório e salas) com obstáculos dinâmicos aparecendo e desaparecendo dentro de intervalos aleatórios.

• Qualidade da Solução (Soma de Custos - SoC):

  • O A consistentemente alcançou o menor SoC para contagens de agentes de 1 a 9.
  • O mecanismo de template permite que o A** contorne regiões temporariamente bloqueadas ao alternar para rotas geometricamente distintas pré-computadas, reduzendo a necessidade de desvios online custosos.
  • Para 10 agentes, o M* apresentou um SoC ligeiramente inferior ao do A**, embora o A** tenha permanecido competitivo.
  • O Dijkstra exibiu o maior SoC (exceto para 1 agente) devido à sua falta de consciência temporal, forçando os agentes a esperar ou realizar desvios mais longos.

• Eficiência Computacional:

  • Dijkstra e D Lite* foram os mais rápidos, com tempos médios de computação total abaixo de 6 ms, devido à sua simplicidade e natureza incremental.
  • O A exibiu tempos de computação significativamente maiores (variando de centenas a milhares de milissegundos). O overhead provém da geração de $k$ templates (exigindo $k$ execuções de A* 2D penalizado) e da avaliação de pontes (exigindo múltiplas buscas STA*).
  • Frequência de Replanejamento: Embora o A** replaneje com menos frequência que o WHCA* ou o Dijkstra (porque os templates antecipam conflitos futuros), o custo por replanejamento é alto. Consequentemente, o tempo de computação total para o A** é o mais alto entre todos os métodos.

• Robustez (Taxa de Falha):

  • STA* e WHCA* demonstraram as menores taxas de falha (abaixo de 11%), atribuídas à sua busca exaustiva expandida no tempo, que tem maior probabilidade de encontrar uma solução dentro do horizonte de planejamento.
  • O A teve uma taxa de falha maior (média de 21%), que os autores atribuem à complexidade da lógica de replanejamento e às restrições específicas do ambiente dinâmico.
  • D Lite* e M* também mostraram taxas de falha mais altas (20%), particularmente em configurações densas de agentes.

5. Significância e Alegações

O artigo afirma que o A representa um avanço significativo no tratamento de D-MAPF com observabilidade parcial. Ao desacoplar a geração de diversidade geométrica da verificação de viabilidade temporal, o A** alcança uma qualidade de solução superior (menor SoC) na maioria das configurações, navegando efetivamente em ambientes com mudanças frequentes e sensores limitados.

Os autores reconhecem o compromisso: o A** alcança melhores caminhos ao custo de um maior overhead computacional. No entanto, eles argumentam que em cenários onde a qualidade da solução (minimização do tempo/custo total de viagem) é priorizada sobre a velocidade bruta de replanejamento, a abordagem baseada em templates oferece uma alternativa robusta aos planejadores incrementais ou de janela tradicionais. O estudo conclui que, embora nenhum algoritmo domine todas as métricas, o A** é particularmente eficaz para minimizar a Soma de Custos em sistemas multiagentes dinâmicos e de observabilidade parcial.