Melhorando a Busca de Caminho para Vários Agentes

Encontrar Caminhos para Múltiplos Agentes (MAPF) é um lance bem importante na robótica. Ele lida com a parada de criar caminhos pra vários agentes que evitam colisões enquanto se movem por uma área compartilhada. Tem muita gente estudando esse problema, mas os métodos que existem hoje em dia têm dificuldades quando o número de agentes aumenta. O grande problema é que esses métodos costumam criar caminhos ótimos pra cada agente sem pensar no impacto nos outros, resultando em engarrafamentos.

Pra resolver isso, a gente sugere um novo método pra MAPF que ajuda os agentes a chegarem nos destinos evitando rotas congestionadas. Testamos a ideia em dois cenários: MAPF de um só lance, onde cada agente tem só um destino, e MAPF de longa duração, onde os agentes recebem novas tarefas o tempo todo. Nos nossos testes, descobrimos que o nosso método melhorou muito os resultados no MAPF de um só lance e aumentou bastante a eficiência no MAPF de longa duração.

#Entendendo o Encontrar Caminhos para Múltiplos Agentes

MAPF é um problema de coordenação bem importante na robótica e é essencial pra várias aplicações industriais. Por exemplo, em armazéns, os robôs precisam trabalhar juntos pra entregar pacotes. Cada robô precisa navegar por um espaço compartilhado pra chegar no seu alvo. Eles têm que chegar rápido enquanto evitam colisões com obstáculos fixos e outros robôs que estão se movendo.

No problema clássico do MAPF de um só lance, os robôs são vistos como agentes simples, cada um com um único local como alvo. O MAPF de longa duração é uma variação onde os agentes recebem novas tarefas à medida que alcançam seus objetivos. Tanto o MAPF de um só lance quanto o de longa duração foram amplamente pesquisados, com muitos avanços relatados. Alguns dos principais algoritmos de MAPF conseguem lidar com centenas de agentes, mas em aplicações reais, muitas vezes precisamos gerenciar milhares de agentes ao mesmo tempo. Atualmente, só alguns métodos conseguem lidar com essa escala.

Dois quadros principais pra lidar com MAPF subótimos são Busca de Grande Vizinhança (LNS) e Herança de Prioridade com Retrocesso (PIBT). O LNS funciona ajustando um plano atual pra reduzir colisões ou melhorar os tempos de chegada, mas enfrenta dificuldades com números maiores de agentes e mapas maiores. PIBT usa um sistema baseado em regras pra planejar os caminhos dos agentes um passo de cada vez, o que geralmente é mais rápido, permitindo lidar com mais agentes do que o LNS. Contudo, o PIBT tende a criar alta congestão só focando na rota mais eficiente de cada agente sem considerar os outros.

#Problema de Atribuição de Tráfego

O Problema de Atribuição de Tráfego (TAP) é semelhante ao MAPF e se concentra em encontrar rotas ótimas para agentes em um espaço compartilhado. No TAP, vários agentes podem usar o mesmo caminho ao mesmo tempo, mas o tempo de viagem aumenta com o número de agentes. As soluções do TAP buscam um estado onde nenhum agente consegue melhorar seu tempo de chegada mudando pra uma rota diferente.

Partindo dessas ideias, a gente tem a intenção de calcular rotas pra agentes MAPF que considerem a congestão esperada devido a outros agentes. Usamos os caminhos gerados como guias melhorados para o PIBT, permitindo um planejamento rápido pra muitos agentes enquanto continuamente melhoramos os caminhos à medida que mais dados são coletados.

#Definição do Problema

O problema MAPF começa com uma grade e um número de agentes, onde cada agente começa em um ponto de partida e precisa alcançar um objetivo. Os agentes podem se mover de uma célula da grade para outra em qualquer direção. A cada passo de tempo, cada agente deve ou se mover ou esperar.

Um conflito ocorre quando dois agentes ocupam a mesma célula ao mesmo tempo, e um tipo diferente de conflito acontece quando os agentes passam por um mesmo caminho em direções opostas. Um caminho válido é aquele que evita esses conflitos, e o objetivo do MAPF é encontrar uma solução que minimize o custo total para todos os agentes chegarem aos seus destinos.

#Encontrar Caminhos de Longa Duração para Múltiplos Agentes

No MAPF de longa duração, os agentes recebem múltiplas tarefas, se movendo continuamente para novas localizações de objetivo. O objetivo é maximizar o total de tarefas completadas dentro de um certo período de tempo. Importante notar que a atribuição de tarefas é gerenciada separadamente do sistema de planejamento, e os agentes só sabem seus objetivos atuais.

#Trabalhos e Métodos Anteriores

A Busca FOCAL é um método que usa uma abordagem de melhor primeiro pra encontrar soluções subótimas. Ele prioriza nós pra expansão pra garantir que todos os caminhos permaneçam dentro de um certo intervalo aceitável da melhor solução conhecida. PIBT e LaCAM são duas abordagens iterativas pra resolver problemas de MAPF.

O PIBT permite que os agentes avancem em direção ao seu objetivo em uma ordem priorizada e ajuda a evitar deadlocks. Porém, pode levar a livelocks em cenários de um só lance. No MAPF de longa duração, o PIBT pode lidar com a situação de forma eficiente, já que novas tarefas ajudam a resolver a contenda.

LaCAM combina busca sistemática com PIBT pra encontrar melhores soluções organizando melhor o espaço de planejamento.

#Congestionamento de Tráfego no MAPF

Em um exemplo simples de MAPF com quatro agentes, fica claro que só seguir caminhos ótimos independentes pode muitas vezes criar congestionamento. Isso acontece porque os caminhos mais curtos frequentemente se sobrepõem, tornando alguns locais mais lotados que outros. Pra resolver isso, propomos novos caminhos que levam em conta o tráfego potencial.

Depois de calcular um caminho mais curto, aumentamos os custos das arestas que foram usadas, tornando-as mais caras para futuros agentes. Isso reflete estratégias usadas em Problemas de Atribuição de Tráfego, onde custos de tráfego aumentados levam a replanejamentos.

#Custos de Tráfego Definidos

Definimos algumas métricas pra ajudar a entender a congestão:

• Fluxo: O número de agentes usando um determinado caminho.
• Congestão de Vértice: O número total de agentes entrando em um ponto, determinando atrasos para cada agente.
• Congestão de Contrafluxo: Isso se refere à situação em que agentes se movendo em direções opostas afetam o tempo de viagem uns dos outros.

#Planejamento e Melhoria de Caminhos

Começamos com custos de tráfego zero e calculamos os caminhos mais curtos para os agentes. Uma vez que um caminho é determinado, atualizamos os custos das arestas usadas, então os agentes subsequentes podem considerar esses custos em seus cálculos. Isso ajuda a reduzir a congestão enquanto continuamos a planejar.

O processo envolve selecionar um grupo de agentes pra replanoar seus caminhos, melhorando seus tempos de viagem. Esse método não garante uma solução em todos os casos, mas tem mostrado ser eficaz na prática.

#Caminhos Guiados e Heurísticas

No PIBT, os movimentos preferidos são baseados na distância de fluxo livre, mas isso não considera o tráfego. Sugerimos modificar o PIBT pra que os agentes sigam caminhos que levam em conta a congestão. Cada agente recebe uma heurística guia baseada na menor distância restante até o objetivo, considerando os caminhos que já foram computados.

#Considerações sobre o MAPF de Longa Duração

À medida que os agentes completam suas tarefas, os dados guias antigos podem ficar desatualizados. Pra lidar com isso, estamos continuamente refinando os dados de orientação em tempo real, tornando-os relevantes para os agentes enquanto se movem.

Ao começar um problema de longa duração, os caminhos guia são computados um passo de cada vez. Agentes sem caminhos simplesmente seguem o caminho mais curto até que tenham a chance de atualizar suas informações mais tarde. Isso permite um melhor planejamento enquanto os agentes se movem.

#Resultados Experimentais

Comparamos nosso método de caminhos guia com abordagens tradicionais em grande escala. Nossos testes incluíram diferentes mapas e números de agentes, com até 12.000 agentes no total. Cada mapa tinha suas próprias características, influenciando como os agentes interagiam e a eficiência dos caminhos.

Para o MAPF de longa duração, monitoramos as ações de todos os agentes a cada passo de tempo. Nosso método de caminhos guia mostrou melhorias significativas no rendimento, mantendo tempos de resposta rápidos bem abaixo de 1 segundo. O método deslocou a densidade máxima de agentes, permitindo uma melhor gestão de grupos maiores.

#Resultados no MAPF de Um Só Lance

Para o MAPF de um só lance, avaliamos como nossos caminhos guia afetaram a qualidade da solução. Observamos que, embora nosso método exigisse um tempo inicial de configuração, ele levou a soluções melhores no final.

#Conclusão

Esse trabalho analisa como caminhos guiados que levam em conta a congestão podem melhorar o desempenho tanto do MAPF de um só lance quanto do de longa duração. Ao integrar ideias do Problema de Atribuição de Tráfego, desenvolvemos novos métodos pra gerenciar grupos grandes de agentes de forma eficiente. Nossos resultados mostram melhorias claras no desempenho, especialmente em cenários com alta densidade de agentes. Esforços futuros vão se concentrar em refinar o design das funções objetivas usadas na busca de caminhos pra alcançar um desempenho ainda melhor.