Resumen Técnico: Búsqueda Basada en Conflictos de Horizonte Adaptativo para la Búsqueda de Caminos de Agentes Múltiples en Bucle Cerrado

Planteamiento del Problema

La Búsqueda de Caminos de Agentes Múltiples (MAPF) es un problema de coordinación fundamental para grandes flotas de robots en almacenes automatizados y logística, que requiere que los agentes se muevan desde vértices de inicio a meta en un grafo sin colisiones. Aunque el MAPF óptimo es NP-duro, los solvers existentes enfrentan un compromiso entre escalabilidad y garantías de rendimiento.

• Planificadores de bucle abierto (por ejemplo, la Búsqueda Basada en Conflictos estándar, CBS) computan trayectorias completas antes de la ejecución. Aunque ofrecen garantías de optimalidad, sufren de alta latencia de planificación y baja escalabilidad en instancias densas de largo horizonte, retrasando la ejecución de las acciones.
• Heurísticas de bucle cerrado reducen la latencia replanificando desde el estado actual, pero a menudo carecen de garantías de rendimiento fiables, lo que limita su utilidad en despliegues críticos para la seguridad.
• Enfoques de horizonte finito (por ejemplo, Windowed CBS/RHCR) intentan cerrar esta brecha, pero enfrentan un "dilema de selección del horizonte": se debe elegir un horizonte de planificación fijo a priori. Un horizonte pequeño es eficiente pero miope, mientras que uno grande mejora la calidad de la solución a costa de un crecimiento exponencial de la búsqueda. Además, los métodos de ventana fija suelen perder las garantías de completitud y optimalidad asintótica del CBS estándar.

Metodología: Búsqueda Basada en Conflictos de Bucle Cerrado de Tiempo de Ejecución Continuo (ACCBS)

El artículo propone ACCBS, un algoritmo MAPF de bucle cerrado que combina el CBS de horizonte finito con un mecanismo de horizonte dinámico inspirado en el Control Predictivo por Modelo (MPC).

Mecanismos Centrales

1. CBS de Bucle Cerrado de Horizonte Finito:

   • En lugar de resolver la trayectoria completa, el algoritmo planifica sobre un horizonte de mirada hacia adelante (lookahead) finito $H$.
   • Optimiza una función de costo que comprende un costo de ejecución (pasos dados para alcanzar la meta) y un costo terminal (heurística admisible que estima la distancia restante a la meta).
   • En cada paso de tiempo $t$, resuelve conflictos solo dentro de la ventana de mirada hacia adelante, ejecuta el primer movimiento y replanifica desde el nuevo estado.

2. Horizonte Adaptativo mediante Profundización Iterativa:

   • ACCBS no fija el horizonte $H$ de antemano. En su lugar, mantiene un horizonte de ejecución $h_r$ que comienza en 1 y crece incrementalmente hasta un máximo $H_{max}$ siempre que el presupuesto de tiempo computacional lo permita.
   • Esto permite que el algoritmo devuelva una solución factible de baja latencia inmediatamente (con $h_r=1$) y la refine con miradas más largas si el tiempo lo permite, exhibiendo un comportamiento de tiempo de ejecución continuo (anytime).

3. Prefijo Activo y Reutilización del Árbol de Restricciones:

   • Para evitar el costo prohibitivo de reiniciar la búsqueda cada vez que el horizonte aumenta, ACCBS introduce el concepto de un prefijo activo. Los conflictos solo se resuelven dentro del prefijo activo actual de longitud $h_r$; los conflictos más allá de este prefijo se ignoran temporalmente.
   • Invarianza de Costo (Lema III.1): El artículo demuestra que, bajo supuestos específicos de planificador de bajo nivel (los sufijos siguen rutas cortas), el costo de un nodo permanece invariante cuando el horizonte se extiende.
   • Reutilización del Árbol de Restricciones (Proposición III.1): Debido a que los costos y las relaciones padre-hijo se preservan, el árbol de restricciones construido para un horizonte menor $h$ es un subárbol válido para $h+1$. Esto permite que ACCBS expanda el horizonte sin reiniciar la búsqueda de manera fluida, haciendo que el esfuerzo computacional acumulado sea comparable al de una única ejecución con el horizonte máximo.

Garantías Teóricas

• Completitud y Optimalidad: El Teorema III.1 establece que si el presupuesto de tiempo es infinito y $H_{max}$ es al menos la duración (makespan) de una solución óptima, ACCBS es completo y devuelve una solución globalmente óptima (Suma de Costos, SOC).
• Propiedad de Tiempo de Ejecución Continuo (Anytime): A medida que aumenta el tiempo de ejecución, el costo de la mejor solución encontrada es monótonamente no decreciente (acotado por el costo óptimo) y converge al óptimo.
• Factibilidad de Paso Único: El algoritmo garantiza un comando de paso único libre de colisiones en cada paso de tiempo por construcción, ya que siempre ejecuta el primer paso de un nodo con un prefijo activo libre de conflictos (donde $h_r \ge 1$).

Resultados Experimentales

Los autores evaluaron ACCBS frente a líneas base que incluyen PIBT, EECBS, MAPF-LNS2, y LaCAM2/3, así como en entornos de ejecución de un solo paso (one-shot), de por vida (lifelong) y estocásticos.

• MAPF de un Solo Paso (One-Shot): ACCBS logra un equilibrio favorable entre eficiencia computacional y calidad de la solución. A medida que aumenta el presupuesto de tiempo por paso, ACCBS reduce la Suma de Costos (SOC) y se acerca a la optimalidad, superando a heurísticas rápidas como PIBT y evitando los fallos por tiempo de espera de los solvers de trayectoria completa como EECBS en mapas densos.
• MAPF de Por Vida (Lifelong): En escenarios con metas cambiantes, ACCBS demuestra un rendimiento competitivo. Su horizonte adaptativo le permite escalar a flotas más grandes donde los métodos de ventana fija (RHCR) agotan el tiempo.
• Incertidumbres Estocásticas: En simulaciones con retrasos en la ejecución y llegada de agentes, ACCBS supera a las líneas base de bucle abierto. Los métodos de bucle abierto están limitados por la necesidad de replanificar trayectorias completas ante perturbaciones, mientras que ACCBS absorbe naturalmente las perturbaciones al replanificar desde el estado actual.
• Estudio de Ablación: El artículo señala que añadir la selección de conflicto priorizado (PC) a ACCBS puede, en ocasiones, reducir la calidad de la solución bajo presupuestos fijos, ya que la sobrecarga de la clasificación de conflictos supera los beneficios de la reducción de expansiones del árbol.

Significado y Reivindicaciones

El artículo afirma que ACCBS aborda el compromiso crítico entre la latencia de planificación y la calidad de la solución en sistemas multi-agente. Sus principales contribuciones son:

1. Eliminación de Decisiones de Diseño Frágiles: Al adaptar el horizonte en línea, ACCBS elimina la necesidad de ajustar manualmente un horizonte fijo que depende de las características específicas de la instancia y de los presupuestos de tiempo.
2. Expansión Eficiente del Horizonte: A través de la invarianza de costo y la reutilización del árbol de restricciones, el algoritmo logra los beneficios de la profundización iterativa sin la penalización computacional asociada de reiniciar las búsquedas.
3. Restauración de Garantías: A diferencia de los métodos de bucle cerrado de ventana fija, ACCBS recupera las garantías de optimalidad asintótica y completitud del CBS estándar.
4. Robustez: La formulación de bucle cerrado acomoda naturalmente las perturbaciones en línea (retrasos, nuevos agentes) sin requerir la replanificación de la trayectoria completa.

Los autores posicionan a ACCBS como una solución práctica para despliegues a gran escala y críticos para la seguridad, donde se requieren tanto flexibilidad de ejecución como garantías de rendimiento.