Otimização da Seleção de Nós na Busca Baseada em Múltiplos Agentes para Encontrar Caminhos

Resumo Um problema de Encontrar Caminhos em Múltiplos Agentes (MAPF) envolve a tarefa de encontrar caminhos para múltiplos agentes que desejam alcançar seus destinos sem obstruir outros agentes. Embora o MAPF seja essencial para inúmeras aplicações do mundo real, encontrar uma solução ótima para esse problema é NP-difícil. Muitas abordagens foram propostas na literatura, oferecendo soluções sub-ótimas para esse problema para melhorar a eficiência do tempo de execução. A adição de restrições preguiçosas na busca para MAPF (LaCAM) é um algoritmo sub-ótimo de MAPF de última geração que emprega geração de sucessores preguiçosos baseada em árvore para minimizar o esforço de planejamento. No entanto, o sucesso do algoritmo depende fortemente da seleção eficaz de nós para expansão. O LaCAM emprega uma heurística fixa ao longo de todo o processo de busca, desconsiderando as preferências dos agentes ou as características do ambiente subjacente. No entanto, experimentos com várias heurísticas indicam que nenhuma heurística única supera consistentemente as outras em todos os cenários. Consequentemente, em ambientes diversos, à medida que o número de agentes aumenta, a dependência de uma única heurística geral leva a um desempenho de tempo de execução reduzido. Nesse contexto, com a intenção de acelerar ainda mais o tempo de execução, propomos uma nova abordagem, chamada eLaCAM, que seleciona nós de forma adaptativa durante o processo de busca, considerando o cenário atual do ambiente e as preferências dos agentes. Introduzimos dois métodos distintos dentro dessa abordagem. O primeiro, eLaCAM-stat, analisa estatisticamente resultados anteriores do uso de diferentes heurísticas e seleciona nós de acordo. O segundo método, eLaCAM-ML, emprega uma estrutura de Aprendizado de Máquina (ML) para ajudar na seleção de nós. Nossos extensos resultados empíricos mostram uma melhoria notável no tempo de execução e uma redução no espaço de busca em comparação com algoritmos de MAPF de última geração.