El problema de búsqueda de rutas multiagente (MAPF, por sus siglas en inglés) consiste en guiar a un gran número de agentes desde sus puntos de partida hasta sus destinos en un mapa, evitando obstáculos y colisiones. Entre sus aplicaciones se encuentran la logística en almacenes y aeropuertos, la gestión del tráfico de vehículos aéreos no tripulados, la navegación en aparcamientos y los videojuegos.
Cuando los agentes se desplazan de forma continua, como sucede en la entrega automatizada de paquetes en almacenes, el problema adopta un nuevo paradigma denominado MAPF de por vida (L-MAPF). Cuando un agente llega a su destino, se le asigna inmediatamente uno nuevo. El objetivo es alcanzar un alto rendimiento —por ejemplo, en número de paquetes entregados— sin colisionar con obstáculos ni con otros agentes.
Para este contexto se han propuesto numerosos métodos. Una de las referencias principales es Priority Inheritance with Backtracking (PIBT), un método extremadamente rápido y escalable que constituye una sólida línea base, aunque puede comportarse de forma codiciosa. Frente a PIBT, otra solución muy extendida es el marco Rolling-Horizon Collision Resolution (RHCR), considerado uno de los métodos de mayor rendimiento para alcanzar un alto flujo de trabajo.
Por desgracia, RHCR tiene un coste computacional elevado, especialmente en comparación con PIBT. En escenarios prácticos, como la navegación de robots en almacenes, RHCR debe utilizar repetidamente solvers MAPF de una sola ejecución en intervalos de tiempo breves. Incluso con solvers subóptimos como Priority Based Search (PBS), observamos que el coste computacional de RHCR crece de forma exponencial. En la comunidad investigadora, ejecutar RHCR como línea base se considera una parte computacionalmente costosa de las simulaciones y a menudo obliga a informar de un plan parcial antes de que se agote el tiempo o a trabajar con un subconjunto más pequeño de problemas. En la práctica, RHCR puede utilizarse junto con un mecanismo de respaldo que cambie a otro algoritmo, como PIBT, cuando se alcanza el tiempo límite.
Aunque resulta tentador acelerar RHCR desarrollando versiones paralelizadas entre agentes, sigue sin estar claro cómo hacerlo de manera teóricamente fundamentada sin sacrificar su rendimiento.
Contribuciones
El objetivo de este trabajo es desarrollar métodos RHCR paralelizados y teóricamente fundamentados que mantengan o superen el alto flujo de trabajo de RHCR, planificando con una fracción de su coste computacional. Para ello, construimos una nueva base teórica para RHCR que conduce a una paralelización teóricamente fundamentada denominada Group Decentralized RHCR (GD-RHCR).
En cantidades reducidas de agentes, que RHCR ya puede gestionar, GD-RHCR alcanza en muchos casos un flujo de trabajo similar con una velocidad de planificación considerablemente mayor. Para grandes cantidades de agentes, que solo PIBT podía gestionar, GD-RHCR también logra resolver el problema y mantiene de forma consistente un flujo de trabajo superior.
Validación experimental
Demostramos empíricamente el rendimiento de GD-RHCR en una variedad de mapas. El tiempo medio de planificación puede reducirse en un factor de [the reported speedup factor] y alcanzar un rendimiento equivalente al de RHCR antes de que este colapse. GD-RHCR también mantiene un buen rendimiento en rangos de cantidades de agentes mayores y muestra una mejora de hasta [the reported throughput improvement] en el flujo de trabajo frente a PIBT y RHCR colapsado.
Trabajos relacionados
Métodos MAPF basados en aprendizaje
Los métodos basados en aprendizaje utilizan directamente aprendizaje por refuerzo o aprendizaje por imitación para resolver el problema MAPF. Estos métodos pueden lograr cierto grado de paralelismo mediante la descentralización, pero no ofrecen garantías sobre cuánto rendimiento se pierde debido a la paralelización o la descentralización.
MAPF de por vida
La bibliografía sobre MAPF de por vida se divide principalmente entre soluciones lentas pero de alta calidad, como RHCR, y soluciones rápidas pero codiciosas, como PIBT.
RHCR permite adaptar solvers MAPF de una sola ejecución al contexto de por vida, pero puede implicar un tiempo de cálculo elevado, ya que MAPF de una sola ejecución es un problema NP-difícil.
PIBT puede utilizarse tanto en el contexto de una sola ejecución como en el de por vida. PIBT y sus variantes siguen siendo alternativas rápidas, pero son codiciosas y a menudo sufren bloqueos cuando el grafo no es biconexo.
De forma análoga, también se han desarrollado métodos de aprendizaje por refuerzo multiagente y de aprendizaje por imitación para este contexto.
Agrupación en MAPF
Varios trabajos anteriores intentan acelerar el cálculo agrupando agentes. Un método de agrupación estática puede dividir el mapa en subregiones y tratar como grupo a los agentes de cada subregión. En otro contexto, métodos más sofisticados intentan identificar dinámicamente agrupaciones independientes.
Esto se hace para acelerar un algoritmo que mantiene garantías de completitud, no para identificar grupos de coordinación que puedan funcionar bien conjuntamente.
MDP multiagente con interdependencia local
En un área próxima a la bibliografía sobre MAPF, se ha producido recientemente un avance importante en el estudio de entornos de procesos de decisión de Markov multiagente con descuento y dependencias locales dinámicas. Se propuso un modelo denominado Locally Interdependent Multi-Agent MDP (LI-MDP) como modelo teórico para sistemas multiagente con interacciones locales.
Los mismos trabajos propusieron el contexto descentralizado por grupos, que conecta transitivamente a los agentes en función de su visibilidad. Los agentes conectados pueden coordinarse. Esta estructura de observabilidad, situada entre los contextos centralizado y descentralizado, permite obtener sólidas garantías teóricas que no están disponibles en el contexto descentralizado, incluido un rendimiento exponencialmente cercano al óptimo con respecto a la visibilidad, al tiempo que permite a los grupos de agentes planificar en paralelo.
El marco LI-MDP aporta información sobre la eficacia de métodos existentes como RHCR, permite demostrar su cuasioptimalidad y puede utilizarse para proponer nuevos métodos, como GD-RHCR, que integran esta estructura de observabilidad.
Conclusiones y trabajo futuro
Este trabajo proporciona una base teórica para RHCR mediante métodos de la bibliografía sobre LI-MDP. A continuación, utilizamos esas técnicas analíticas para motivar el nuevo marco GD-RHCR, que satisface garantías teóricas similares a las de RHCR y ofrece un buen rendimiento empírico en numerosos mapas con cantidades de agentes mayores que las que RHCR puede gestionar.
La descentralización por grupos es un concepto relativamente nuevo en la comunidad MAPF y puede integrarse de diversas formas. Por ejemplo, podría combinarse con métodos tradicionales basados en aprendizaje o utilizarse para paralelizar otros métodos, como PIBT. Este trabajo también proporciona una configuración sencilla para emplear distintos algoritmos en diferentes ubicaciones o contextos, lo que abre numerosas líneas de investigación.
Agradecimientos
Guannan Qu cuenta con el apoyo de las ayudas NSF 2339112 y 2512805, Jane Street y la Pennsylvania Infrastructure Technology Alliance. Jiaoyang Li cuenta con el apoyo de las ayudas NSF 2328671 y 2441629. Alex DeWeese cuenta con el apoyo de la Leo Finzi Memorial Fellowship in Electrical & Computer Engineering, la David H. Barakat and LaVerne Owen-Barakat CIT Dean’s Fellowship y la Fritsch Family Fellowship.
Simulaciones de ablación
El resultado de las simulaciones de ablación en warehouse-10-20-10-2-1 se muestra en los resultados de ablación del artículo.
Preguntas frecuentes
¿Qué es la búsqueda de rutas multiagente de por vida? El MAPF de por vida asigna continuamente nuevos destinos a los agentes cuando alcanzan los anteriores, y exige evitar colisiones y mantener un alto flujo de trabajo.
¿Por qué RHCR es costoso desde el punto de vista computacional? RHCR utiliza repetidamente solvers MAPF de una sola ejecución, cuyo coste computacional puede crecer de forma exponencial y provocar tiempos de espera agotados cuando aumenta el número de agentes.
¿Qué es GD-RHCR? GD-RHCR es una paralelización descentralizada por grupos de RHCR que permite a los grupos de agentes coordinarse y planificar en paralelo.
¿Cómo se compara GD-RHCR con PIBT? GD-RHCR resuelve problemas con más agentes que RHCR y alcanza de forma consistente un flujo de trabajo superior al de PIBT en los experimentos publicados.