Multi-Agent Path Finding

También llamado: MAPF, multi-agent pathfinding, multi-robot path planning
Categoría: Learning & autonomy › Multi-robot
Etiquetas: multi-robot, path-planning, warehouse-automation, coordination, graph-search

El problema de calcular caminos sin colisiones para muchos agentes que se mueven a la vez sobre un grafo compartido, como robots de almacén en una cuadrícula, de modo que cada agente llegue a su objetivo sin conflictos.

Definición

Búsqueda de caminos multiagente (Multi-Agent Path Finding, MAPF) es el problema de planificar caminos para un grupo de agentes que comparten un entorno, de modo que cada agente vaya de su inicio a su objetivo sin que dos agentes ocupen el mismo lugar al mismo tiempo ni se intercambien de posición a lo largo de la misma arista. El entorno suele modelarse como un grafo, a menudo una cuadrícula, y el tiempo se divide en pasos discretos en los que cada agente se mueve a un vértice vecino o espera.

Las soluciones de MAPF suelen evaluarse por la suma de costes, el tiempo total que tardan todos los agentes en llegar a sus objetivos, o por el makespan, el tiempo hasta que llega el último agente. Encontrar una solución óptima con estos objetivos es NP-difícil en general, por lo que el campo ha desarrollado algoritmos que sacrifican optimalidad a cambio de velocidad. Entre los métodos óptimos está Conflict-Based Search (CBS), que planifica cada agente de forma independiente y después resuelve las colisiones añadiendo restricciones en un árbol de búsqueda. Los métodos subóptimos, como la planificación priorizada, en la que los agentes planifican uno a uno y tratan a los agentes anteriores como obstáculos en movimiento, escalan a equipos mucho mayores.

La MAPF continua (lifelong MAPF) es una variante en la que los agentes reciben nuevos objetivos en cuanto alcanzan los anteriores, lo que coincide con cómo trabajan realmente los robots de almacén y de clasificación. La planificación se ejecuta entonces de forma continua, a menudo sobre una ventana de tiempo limitada, y el rendimiento pasa a ser la medida principal.

Los robots reales también rompen las suposiciones de manual: tienen tamaño, límites de aceleración y retardos de ejecución, por lo que los planes de MAPF suelen ejecutarse con una capa de coordinación adicional que mantiene a los robots seguros cuando algunos se retrasan respecto al plan. Los métodos basados en aprendizaje, incluido el aprendizaje por imitación a partir de planificadores basados en búsqueda, son una línea de investigación activa para escalar a flotas muy grandes.

Por qué importa

Los almacenes, las fábricas y los centros de clasificación operan flotas crecientes de robots móviles en suelos compartidos, y su rendimiento depende de lo bien que se coordinen esos robots. La MAPF aporta los algoritmos que mantienen los robots en movimiento sin colisiones ni bloqueos mutuos a medida que crecen las flotas.

Aplicaciones clave

Flotas de robots de almacenes y centros de preparación de pedidos
Sistemas de clasificación de paquetes con muchos robots móviles
Coordinación de vehículos de guiado automático en fábricas
Coordinación de múltiples drones y del tráfico terrestre en aeropuertos
Movimiento de personajes en videojuegos y simulación de multitudes

En la práctica

Un equipo que opera una flota de almacén normalmente modela el suelo como una cuadrícula o un grafo de rutas, con cada celda dimensionada para que quepa un robot. Un planificador central recibe los objetivos del sistema de pedidos y calcula caminos coordinados, a menudo con una búsqueda priorizada o por ventanas que replanifica cada pocos segundos en lugar de resolver todo el problema de forma óptima. Los caminos se convierten en puntos de paso temporizados y se envían a los robots, y una capa de ejecución, como un grafo de dependencias de acciones, garantiza que un robot no entre en una celda hasta que el robot que va delante la haya dejado libre. Los ingenieros miden el rendimiento, el tiempo de espera y la frecuencia de bloqueos mutuos en simulación con la flota completa antes de cambiar la distribución del suelo o el algoritmo en el sistema real.

Ideas erróneas comunes

Cada robot puede planificar su propio camino más corto de forma independiente — los caminos independientes colisionan, así que los robots deben coordinarse tanto en el tiempo como en el espacio
La MAPF óptima escala a cualquier tamaño de flota — la resolución óptima es NP-difícil, por lo que las flotas grandes dependen de métodos subóptimos o por ventanas
Un plan de MAPF puede ejecutarse exactamente como se calculó — los robots reales van adelantados o retrasados, así que la ejecución necesita su propia capa de seguridad y coordinación

Quién debería saberlo

Ingenieros de automatización de almacenes y de gestión de flotas
Investigadores en planificación multirrobot
Integradores de sistemas AMR y AGV
Investigadores operativos que trabajan en logística

Tecnologías relacionadas

Conflict-Based Search
Planificación priorizada (Prioritized Planning)
Búsqueda A (A Search)
Sistemas de gestión de flotas (Fleet Management Systems)
Aprendizaje por imitación (Imitation Learning)

Términos relacionados

Proyectos relacionados

Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots