Perros que obedecen: control predictivo en tiempo real en el navegador
En las dos primeras partes (la heurística frente al óptimo y un rebaño que no es un disco) el control óptimo ganaba siempre a la heurística del TFM, pero con dos trampas. La primera, que tardaba 105 minutos en calcularse antes de que el perro diera un paso. La segunda, que una vez calculado se reproducía tal cual: si una oveja hacía algo distinto de lo previsto, el plan no se enteraba. Es control en lazo abierto.
Lo de arriba es lo contrario: un controlador en lazo cerrado que cada 2,5 unidades de tiempo mira dónde están las ovejas, resuelve un problema de control óptimo corto y decide. Tarda unos 200 ms, en tu navegador, y por eso puedes cambiarle la orden a mitad de camino haciendo clic. Este artículo cuenta cómo se llega de lo uno a lo otro y, sobre todo, todo lo que hizo falta añadir para que tres perros con un MPC se comporten como perros.
Del óptimo al MPC
La idea del control predictivo (MPC, model predictive control) es vieja y sencilla: en vez de planificar todo el trayecto una vez, se planifica un trozo corto, se aplica solo el principio y se vuelve a planificar desde lo que realmente ha pasado. Aquí el horizonte son 20 intervalos de 2,5 (50 unidades de tiempo) y se replanifica en cada intervalo.
Con 200 ovejas eso no cabe en 200 ms: el problema del óptimo tiene 812 estados y cada evaluación del coste integra todas las interacciones entre ovejas. El truco es que el MPC no necesita ver cada oveja. Antes de cada decisión, las ovejas se agrupan (k-medias) en 10 superovejas: cada una en el centro de su grupo, con su velocidad media y un peso igual a su número de ovejas. El modelo interno pasa de 812 estados a 52, y la física es la misma.
El primer experimento, sin corrales, ya lo dejó claro: con 12 superovejas el MPC llevaba el rebaño de 200 al objetivo en t = 57,5 (el óptimo de la primera parte, en t = 60) gastando algo menos esfuerzo, y decidiendo en unos 150 ms en Python. El óptimo en lazo abierto pasa a ser lo que siempre debió ser: la referencia de lo que es posible, no el controlador.
Por qué en el navegador: CasADi, C y WebAssembly
El MPC se resolvía con IPOPT, que depende de librerías de álgebra lineal en Fortran y no se lleva bien a un navegador. Pero no hace falta IPOPT. El problema solo tiene una restricción por perro y por intervalo, que la aceleración quepa en un círculo, y proyectar sobre un círculo es trivial. Así que el resolvedor es un gradiente proyectado espectral (SPG, Birgin, Martínez y Raydan, 2000) de unas ochenta líneas, que solo necesita el coste y su gradiente.
Y eso es justo lo que CasADi sabe exportar: el coste del MPC, con su gradiente por diferenciación automática, se genera como C plano, que Emscripten compila a WebAssembly (0,9 MB). El resto, la simulación de las ovejas, el agrupamiento y el reparto de tareas, es JavaScript y corre en un Web Worker, un hilo aparte de la página.
Detalle técnicoLo que costó que el C fuera pequeño y rápido
La primera versión del C ocupaba 23 MB. Al convertir la dinámica a la representación simbólica compacta de CasADi (SX), los 10 subpasos del integrador y sus 4 etapas se desenrollaban en código lineal, y la derivada hacia atrás, aún más. Definir en SX un solo subpaso y encadenarlo en MX lo bajó a 2,7 MB.
Después, el tiempo: 28 ms por evaluación, demasiado. Medí por partes y casi todo era la interpolación del mapa de distancias (una B-spline paramétrica), evaluada 260 veces por coste, algunas con derivadas segundas. Evaluarla solo en 4 instantes del horizonte y pasar como parámetro la dirección «detrás del grupo» de cada perro lo dejó en 5 ms por evaluación. Con 30 iteraciones del resolvedor, una decisión cuesta 150–250 ms.
Para que el corral y el destino puedan cambiar sin recompilar, todo lo que depende del escenario entra como parámetro: las paredes (hasta 10 segmentos), el mapa de distancias en una rejilla de 6 unidades y los pesos que decide el reparto de tareas. La B-spline usa los valores del mapa directamente como puntos de control, sin ajuste: suaviza del orden de una celda y evita resolver un sistema lineal en cada evaluación.
Lo que hubo que añadir para que obedecieran
Con el coste de la primera parte («lleva el rebaño allí, sin dispersarlo y sin gastar mucho») el MPC funcionaba en campo abierto. En cuanto hubo corrales, órdenes que cambian y perros de velocidad realista, aparecieron uno detrás de otro comportamientos que ningún perro haría. Ninguno de los arreglos sale solo del objetivo «lleva el rebaño allí».
- Llegar sin quedarse lejos. Con la distancia al cuadrado normalizada por el trayecto, estar a 20 del objetivo no costaba nada y el rebaño se escapaba mientras los perros esperaban. Se cambió por una función de Huber que muerde también cerca.
- Disponibilidad. Tras cumplir una orden, los perros se alejaban para no molestar y la siguiente orden les pillaba fuera del alcance del horizonte. Ahora pagan si se alejan del rebaño más de su radio + 60.
- Repartirse al esperar. Con los tres perros esperando en el mismo lado, su repulsión empujaba el rebaño despacio hacia el otro. Ahora, con el rebaño en el objetivo, se reparten alrededor y sus empujes se compensan.
- Velocidades realistas. Las ovejas corrían más que los perros (hasta 16 frente a 7) y el MPC lo explotaba dando arreones. Ahora una oveja no pasa de 2 y un perro de 2,8.
- No molestar al compañero. Cada perro paga por meterse en la zona del grupo que lleva otro.
- Reunir. El coste de los corrales no premiaba tener el rebaño junto. Con un término de dispersión, el rebaño va un 25 % más compacto y entra en el corral en los 12 casos de prueba, frente a 8 sin él.
- Suavidad. Los perros temblaban: el control cambia cada intervalo y el resolvedor no converge del todo. Penalizar los cambios de aceleración entre intervalos y filtrar sus puntos de referencia redujo el giro medio entre decisiones un 29 %.
Corrales, puertas y rutas
Con paredes, «llevar el rebaño allí» deja de ser una línea recta. El objetivo se mide por el camino: un mapa de distancias que rodea las paredes (Dijkstra en una rejilla), y es su pendiente la que lleva a las ovejas hacia la puerta. Los perros tienen el suyo propio: un planificador de rutas hacia su puesto, con las paredes como obstáculos y el cuerpo del rebaño y los grupos de otros perros como terreno caro. Así rodean el rebaño sin empujarlo y entran por la puerta desde cualquier sitio.
Por encima de ambos va un reparto de tareas. Los grupos de ovejas se ordenan por prioridad y, mientras quede un grupo grande, las ovejas sueltas esperan: si no, un perro se iba a por una sola y dejaba al rebaño sin empuje. Un perro, el líder, se pone justo detrás del grupo principal y es el único que empuja; los que sobran van a sus flancos, más abiertos y algo más lejos, para contener por los lados sin empujar en otra dirección ni estorbarle. Un perro que lleva un grupo encerrado no se reasigna hasta sacarlo.
Con el rebaño arrinconado contra la valla, el puesto del líder cae fuera del campo. Girarlo hasta que quede dentro lo ponía delante del rebaño, empujándolo contra la esquina; ahora se pega a la valla y el líder va directo al hueco entre ella y las ovejas, que se apartan y se despegan. En la prueba de ese caso, que antes no salía, entran las 80.
Con tres perros, uno hace además de recogedor: mientras el líder y un flanco llevan el grueso, él va a por las rezagadas que no van a llegar solas (lejos del rebaño o con una pared en medio, como una oveja que se ha quedado en el corral) y las devuelve. Para eso el coste tiene un peso por perro, «acompañar»: los demás pagan por alejarse del rebaño, el recogedor no. Medido sobre la batería de abajo, con el recogedor el rebaño entra en más casos (33 de 36 frente a 29) y unas 30 unidades de tiempo antes por caso.
Lo que más ayudó, curiosamente, salió de jugar con el visor: el rebaño se lleva mejor si se le dan objetivos cercanos que si se le da el destino lejano de golpe. Con el destino al otro lado del corral, el MPC empuja a todo el rebaño hacia la puerta a la vez y lo atasca; con objetivos intermedios, converge en cada etapa. Ahora lo hace solo: el MPC no ve el destino final sino una zanahoria 80 unidades por delante en el camino del rebaño, con su propio mapa de distancias. Pasó de 8 a 10 casos completos de 12, más deprisa y sin que el rebaño se partiera.
Sacar el rebaño: la maniobra difícil
Sacar ovejas de un recinto por una puerta pequeña es difícil también para un perro de verdad, y aquí fue lo que más costó. El primer perro que entraba empujaba el rebaño hacia el fondo, lo aplastaba contra la pared opuesta y ya no había hueco para ponerse detrás. Y había algo más sutil: el MPC no quería entrar. Entrar aleja a las ovejas del destino durante un rato y, en un horizonte de 50, eso solo sube el coste. Que haga falta para ponerse detrás queda fuera de lo que ve.
La solución es una maniobra: entra un solo perro, por una ruta que bordea la pared con un margen amplio alrededor del rebaño y con la guía hacia su puesto reforzada, para que se imponga a ese aumento momentáneo del coste. Los otros dos esperan fuera, a los lados de la puerta, sin taponarla, y recogen a las que salen.
Contra qué se comprueba
Que el navegador calcula lo mismo que Python. La versión JavaScript (simulación, mapa de distancias, agrupamiento, reparto, empaquetado de parámetros) y el coste en WebAssembly se compararon pieza a pieza con la referencia en Python sobre los mismos estados: el mapa coincide exactamente, un intervalo de simulación a 10⁻¹⁴ y la decisión del resolvedor a 10⁻¹³.
Que el resolvedor de ochenta líneas no pierde calidad. En las ejecuciones del corral, cada cierto número de decisiones se resolvió el mismo problema con IPOPT: el coste que alcanza el SPG queda casi siempre igual hasta el duodécimo decimal y, en el peor caso, un 6 % por encima.
Que funciona en más de un caso. Cada cambio se midió sobre dos baterías reproducibles, para no ajustar el controlador a una ejecución con suerte. Y cada caso se repite tres veces con una perturbación de una millonésima en un peso: el sistema es caótico y ese cambio basta para que un caso pase de completarse a no hacerlo, así que con una sola ejecución por caso diferencias de decenas en el tiempo medio no significan nada.
| Batería | Casos | Resultado |
|---|---|---|
| Meter el rebaño (3 corrales × 4 semillas, perros en cualquier lado) | 12 × 3 | 33/36 completos, mediana t = 333 |
| Sacar el rebaño (2 corrales × 6 semillas, destino al azar) | 12 × 3 | sale el 84 % en t = 700; en 14 de 36 quedan dos o menos, solo 2 lo vacían |
Las baterías sirvieron sobre todo para tirar cosas: varias versiones que en un vídeo parecían mejores empeoraban la batería, y se descartaron.
Detalle técnicoFallos que solo salieron al mirar los casos que fallaban
Más de la mitad de las mejoras no eran del controlador, sino de cosas alrededor que estaban mal y que solo se vieron dibujando los casos fallidos:
- Una puerta cerrada en la rejilla. Al calcular el mapa de distancias se bloqueaban las celdas a menos de 4,5 de una pared; con la rejilla de 6, la puerta estrecha de 12 quedaba cerrada y el mapa no tenía ninguna pista. Con otro margen, el mapa «atravesaba» las paredes que caían entre dos filas. La corrección fue prohibir los pasos entre celdas que corten una pared.
- Ovejas que se atraían a través de las paredes. En el modelo del TFM cada oveja atrae a todas las demás, a cualquier distancia. Las de fuera se quedaban pegadas a la pared intentando llegar a las de dentro. Ahora solo interactúan las que se ven, con una regla de línea de visión.
- Perros que empezaban fuera de la valla cuando el rebaño arrancaba cerca del borde, y desde ahí no podían entrar.
- Un modelo interno que explotaba. El rozamiento que limita la velocidad de las ovejas crece como (v/v_max)⁴ y, con un integrador explícito, divergía ante cualquier empujón fuerte. En la simulación se integra de forma implícita; en el modelo del MPC, que tiene que poder derivarse, se limita la fuerza en vez de la velocidad.
Qué no demuestra esto
- No es un óptimo. Es un MPC con un modelo reducido, horizonte corto y 20–30 iteraciones por decisión, más una capa de reglas (reparto de tareas, zanahoria, maniobra de sacar) que decide cosas que el MPC no ve. Funciona bien en los casos medidos, pero no hay certificado de que sea lo mejor posible.
- Las ovejas son las del modelo del TFM, no ovejas reales. Las velocidades, la cohesión y el miedo están puestos a mano con criterios razonables, no medidos.
- Pocos escenarios. Tres corrales con una puerta y 24 casos de prueba. Los pesos se ajustaron mirando esas baterías: con corrales más complicados (varias puertas, pasillos) probablemente haría falta reajustarlos.
- Las rezagadas siguen costando. Sacar el rebaño saca la gran mayoría, pero las últimas, arrinconadas en las esquinas, salen muy despacio.
- El rendimiento en móvil no está medido. En un portátil va sobrado a 10× (y a 20× con menos margen); en un móvil más lento la animación podría ir a tirones.
Cómo reproducirlo
Todo está en control/pastoreo-mpc
del repositorio de las simulaciones:
./wasm/build.sh # CasADi -> C -> librería nativa y WebAssembly
node web/prueba/compara.mjs tmp/traza_<esc>.json # JavaScript frente a Python, pieza a pieza
node web/prueba/lazo.mjs tmp/traza_<esc>.json # meter el rebaño, en lazo cerrado
node web/prueba/salida.mjs <semilla> izquierda # sacarlo del corral
cd web && python3 -m http.server # el visor de arriba, en localLa referencia en Python (python/valida.py) contiene la misma planta y el mismo reparto de
tareas que la versión del navegador hasta la coordinación por grupos; el planificador de rutas,
la zanahoria y la maniobra de sacar solo existen en JavaScript.