Priorización dinámica bajo incertidumbre: índices de Whittle y leyes de conservación parcial

El índice de Whittle constituye el enfoque de referencia para asignar prioridades dinámicas en múltiples aplicaciones. Sin embargo, demostrar su existencia y calcularlo pueden suponer retos formidables, especialmente bajo incertidumbre. Las leyes de conservación parcial ofrecen un método eficaz para superar estos desafíos.

El seguimiento de múltiples objetivos (multi‐target tracking) consiste en estimar simultáneamente las trayectorias de varios objetos con movimientos impredecibles, disponiendo de recursos de seguimiento limitados. Sus aplicaciones abarcan ámbitos tan diversos como el control del tráfico aéreo y marítimo, la conducción autónoma y la asistencia al conductor, la vigilancia en espacios públicos, la robótica colaborativa, el seguimiento de la fauna salvaje para su conservación y los sistemas de defensa militares.

A modo de ejemplo, imaginemos que queremos monitorizar las posiciones y velocidades de N aviones con un número menor M de radares, de forma que cada radar solo puede apuntar a un avión en cada instante. Cada vez que orientamos un radar hacia unos aviones, obtenemos información precisa sobre ellos, pero dejamos de monitorizar el resto. Esta disyuntiva –ganar información de unos a costa de perderla de otros– motiva que determinar una política efectiva para asignar prioridades de seguimiento a lo largo del tiempo sea uno de los problemas centrales en esta área.

En este contexto, mi artículo galardonado con el premio Sociedad Española de Estadística e Investigación Operativa (SEIO)-Fundación BBVA (FBBVA), en su primera edición (2020), en la categoría de mejor contribución metodológica en Investigación Operativa, presenta un método eficaz para abordar tales cuestiones.

Modelos multi-armed bandit de priorización dinámica óptima

Desde su introducción en la primera mitad del siglo XX, los modelos multi-armed bandit (MAB) se han consolidado como el paradigma teórico de referencia para formular problemas de priorización dinámica óptima. El término inglés bandit alude a las antiguas máquinas tragaperras de palanca —en inglés one-armed bandits—, de modo que un jugador debe decidir secuencialmente cuál de esas máquinas accionar para maximizar su ganancia esperada a lo largo del tiempo.

Esta metáfora emplea las máquinas tragaperras para representar diversas actividades —denominadas genéricamente proyectos— en múltiples aplicaciones. En cada periodo de tiempo, el decisor observa el estado de todos los proyectos y elige cuál activar. Esta elección genera una recompensa inmediata, que se descuenta en el tiempo, y el estado del proyecto seleccionado evoluciona al siguiente periodo según probabilidades de transición conocidas. En cuanto a los proyectos no activados, su estado no cambia.

El problema de diseñar una estrategia o política óptima de priorización en este modelo permaneció sin resolver durante varias décadas, hasta que, a principios de los años setenta del pasado siglo, Gittins y Jones presentaron una solución sorprendentemente sencilla e intuitiva. Asignaron a cada proyecto un índice de prioridad, conocido posteriormente como índice de Gittins, una función de su estado actual, y demostraron que la política óptima consiste en activar en cada periodo un proyecto con el índice más alto. 

Más allá del MAB: modelos restless y el índice de Whittle

No obstante, el modelo clásico MAB adolece de una limitación fundamental: asume que los proyectos inactivos (no seleccionados) permanecen estáticos. En 1988, Whittle eliminó este supuesto al proponer el modelo restless MAB (RMAB), donde el término restless (inquieto) se refiere a que cada proyecto evoluciona continuamente —con dinámicas distintas según esté activo o no. El problema de seguimiento de objetivos móviles mencionado más arriba encaja en este modelo.

Whittle también propuso un índice de prioridad —hoy conocido como índice de Whittle— para el modelo RMAB en el que hay que activar M proyectos de N, con M menor que N, que generaliza el índice de Gittins. También advirtió de tres limitaciones de su propuesta: (1) la existencia de su índice no está garantizada, a diferencia del de Gittins; (2) no indicó cómo calcular el índice; y (3) la política resultante (activar en cada instante los M proyectos con mayor índice) no es, en general, óptima. 

Sin embargo, y dado el amplio abanico de aplicaciones del modelo RMAB, la política basada en el índice de Whittle ha alcanzado gran popularidad. Para solventar las dos primeras limitaciones, investigadores y analistas han recurrido a diversos enfoques ad hoc más o menos rigurosos; en cuanto a la tercera, se ha comprobado que la política basada en el índice de Whittle ofrece un rendimiento casi óptimo, especialmente en modelos de gran escala.

No obstante, algunos modelos de gran relevancia —por ejemplo, el de seguimiento de objetivos móviles mencionado más arriba— resistieron los esfuerzos de los investigadores para demostrar la existencia el índice de Whittle y calcularlo, lo cual puso de manifiesto la necesidad de herramientas metodológicas más eficaces que las tradicionales.

Una metodología alternativa: leyes de conservación parcial

Los enfoques tradicionales para demostrar la existencia y calcular el índice de Whittle se fundamentan en la programación dinámica, introducida en la década de 1950. Sin embargo, ante sus limitaciones, en 2001 propuse las leyes de conservación parcial (PCL, por sus siglas en inglés: partial conservation laws). Este concepto amplía anteriores leyes de conservación o relaciones de invarianza en modelos de priorización de tareas y constituye la base de una metodología alternativa para el análisis de modelos RMAB. Desde entonces, he ampliado esta metodología —denominada PCL-indexabilidad— para abarcar modelos RMAB de complejidad creciente. En una primera fase, la apliqué a proyectos con estado discreto (finito o numerable). En el artículo aquí comentado, publicado en 2020, extendí el enfoque al caso de proyectos con estado continuo real, motivado por aplicaciones como el seguimiento de objetivos móviles y la asignación dinámica de sensores.

Resultado: un teorema de verificación para indexabilidad

El artículo presenta como resultado principal un teorema de verificación que permite tanto demostrar la indexabilidad (es decir, la existencia del índice de Whittle) como calcular dicho índice en modelos RMAB con estado continuo real. Dicho teorema formula tres condiciones suficientes para indexabilidad basadas en PCL; dos de ellas se refieren a un índice definido de manera explícita —el llamado índice de productividad marginal— que, a diferencia del índice de Whittle (implícito), puede calcularse directamente. El cumplimiento de estas condiciones garantiza que el modelo es indexable y que ambos índices coinciden. El artículo ilustra la aplicación de dicho teorema a varios modelos de redes de sensores.

Aunque ya había publicado el teorema como conjetura en 2008, su demostración rigurosa supuso retos técnicos inesperados de considerable dificultad; para solventarlos, el artículo desarrolla como resultados preliminares treinta lemas y siete proposiciones. 

Por otra parte, aunque el artículo se remitió en 2015 a la revista en que fue publicado, su revisión por pares fue tortuosa y se prolongó hasta 2019, evidenciando tanto las debilidades como las fortalezas del sistema. Algunos evaluadores mostraron fuertes sesgos extracientíficos —presumiblemente motivados por rivalidades— e instaron enérgicamente a su rechazo. Frente a ello, el editor en jefe de la revista advirtió indicios de mala praxis y reinició el proceso con un nuevo panel de revisores, lo que condujo finalmente a su aceptación.

Impacto: indexabilidad de modelos de seguimiento de objetivos móviles

Entre las investigaciones que han aplicado con éxito mi teorema de verificación a diversos modelos, sobresale la de Dance y Silander (2019), en la que demuestran por primera vez la existencia del índice de Whittle y lo evalúan en un modelo clásico de seguimiento de objetivos móviles basado en el filtro de Kalman. Su artículo identifica, además, la causa de que el análisis de este modelo mediante métodos tradicionales resultara infructuoso, ya que no satisface las condiciones requeridas. Por otra parte, el artículo introduce importantes novedades para desplegar con éxito las condiciones de PCL-indexabilidad en modelos complejos, en particular la aplicación de la teoría de combinatoria sobre palabras.

Retos pendientes

En investigaciones en curso, el autor continúa extendiendo la metodología de PCL-indexabilidad a modelos más complejos de relevancia en aplicaciones, incluyendo modelos en los que los proyectos presentan múltiples modos de operación, y modelos con estado continuo multidimensional.

Cortesía de Muy Interesante

Dejanos un comentario: