Mejorando políticas locales de MAPF aprendidas con búsqueda heurística

La búsqueda de caminos para múltiples agentes (MAPF) es el problema de encontrar caminos libres de colisiones para un equipo de agentes que alcanzan sus ubicaciones objetivo. Los solucionadores MAPF clásicos de última generación emplean típicamente la búsqueda heurística para encontrar soluciones para cientos de agentes, pero suelen ser centralizados y pueden tener dificultades para escalar cuando se ejecutan con tiempos de espera cortos. Los enfoques de aprendizaje automático (ML) que aprenden políticas para cada agente son atractivos, ya que podrían permitir sistemas descentralizados y escalar bien mientras mantienen una buena calidad de solución. Los enfoques actuales de ML para MAPF han propuesto métodos que han comenzado a arañar la superficie de este potencial. Sin embargo, los enfoques ML de última generación producen políticas "locales" que solo planifican para un único instante y tienen bajas tasas de éxito y escalabilidad. Nuestra idea principal es que podemos mejorar una política local de ML utilizando métodos de búsqueda heurística en la distribución de probabilidad de salida para resolver puntos muertos y permitir la planificación a horizonte completo. Mostramos varias maneras agnósticas al modelo de usar búsqueda heurística con políticas aprendidas que mejoran significativamente las tasas de éxito y la escalabilidad de las políticas. Según nuestro mejor conocimiento, demostramos que por primera vez los enfoques MAPF basados en ML han escalado a escenarios de alta congestión (por ejemplo, 20% de densidad de agentes).