Publication: Restless bandit index policies for dynamic sensor scheduling optimization
Loading...
Identifiers
Publication date
2012-04
Defense date
2012-07-17
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
This dissertation addresses two complex stochastic and dynamic resource allocation problems, with application in modern sensor systems: (i) hunting multiple elusive hiding targets and (ii) tracking multiple moving targets. These problems are naturally formulated as Multi-armed Restless Bandit Problems (MARBPs) with real-state variables, which introduces technical difficulties that cause its optimal solution to be intractable. Hence, in this thesis we focus on designing tractable and well-performing heuristic policies of priority-index type. We consider the above MARBPs as Markov Decision Processess (MDPs) with special structure, and we deploy recent extensions to the unifying principle to design a dynamic priority index policy based on a Lagrangian relaxation and decomposition approach. This approach allows to design an index rule based on a structural property of the optimal solution to the decomposed parametric-optimization subproblems. The resulting index is a measure of the Marginal Productivity (MP) of resources invested in the subproblems, and it is then used to define a heuristic priority rule for the original intractable problems. For each of the problems under consideration we perform such a decomposition, to analyze the conditions under which the index recovering the optimal policies for the subproblems exists. We further obtain formulae for the indices which do not admit a closed form expression, but which are approximately computed by a tractable evaluation method. Apart from the practical contribution of deriving the tractable sensor scheduling polices which improve on existing heuristics, the main contributions of this thesis are the following: (i) deploying the recent extensions of Sufficient Indexability Conditions (SIC) to the real state case, for two problems in which direct verification of the SIC and obtaining a closed-form index formula are not possible, (ii) addressing the technical difficulties to analyze PCL-indexability introduced by the uncountable state space of the MARBPs of concern, and the state evolution over it given by non-linear dynamics by exploiting the special structure of the trajectories of the state and the action processes under a threshold policy using properties of M¨obius Transformations, and (iii) providing with a tractable approximate evaluation method for the resulting index policies._________________________________________________________________________________________________________________________________Esta tesis estudia dos problemas dinámicos y estocásticos de asignación de recursos, con aplicación a sistemas modernos de sensores: (i) localización de múltiples objetivos evasivos que se ocultan y (ii) el rastreo de múltiples objetivos que se mueven. Estos problemas son modelizados naturalmente como problemas de “Multi-armed Restless Bandit” con variable de estado real, lo que introduce dificultades técnicas que causan que su solción óptima no sea computacionalmente tratable. Debido a esto, en esta tesis nos concentramos en cambio en diseñar políticas heurísticas de prioridad que sean computacionalmente tratables y cuyo rendimento sea casi óptimo. Modelizamos los problemas arriba mencionados como problemas de decisión Markovianos con estructura especial y les aplicamos resultados existentes en la literatura, los que constituyen un principio unificador para el diseño de políticas de índices de prioridad basadas en la relajación Lagrangiana y la descomposición de esos problemas. Este enfoque nos permite considerar una propiedad de los subproblemas: la indexabilidad, por la cual podemos resolverlos de manera óptima mediante una política índice. El índice resultante es una medida de productividad de los recursos invertidos en los subproblemas, y es usado luego como medidad de la prioridad dinámica para los problemas originales intratables. Para cada uno de los problemas bajo estudio realizamos tal descomposición, y analizamos las condiciones bajo las que una política índice que recupere la solución óptima de los subproblemas existe. Además obtenemos fórmulas para los índices, las que a pesar de no admitir una expresión cerrada, son calculadas aproximadamente de manera eficiente meadiante un método tratable. Aparte de la contribución práctica de obtener reglas heurísticas de índices de prioridad para el funcionamiento de sistemas de múltiples sensores en el contexto de los dos problemas analizados, las principales contribuciones teóricas son las siguientes: (i) la aplicación de las extensiones recientes de las condiciones suficientes de indexabilidad para el caso de variable de estado real, para dos problemas en los que tanto la verificación directa de ellas como la obtención de fórmulas cerradas no son posibles, (ii) el tratamiento de las dificultades técnicas para establecer la indexabilidad introducidas por el espacio de estado infinito de los problemas bajo consideración, y por la evolución sobre este estado dada por dinámicas no lineales, explotando propiedades estructurales de los procesos de la variable de estado y trabajo bajo políticas de umbral como recursiones de Transformaciones de Möbius, and (iii) un método aproximado de evaluación de las políticas de índices resultantes.
Description
Keywords
Instrumentación, Procesos estocásticos, Análisis dinámico