1 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 1 PROGRAMACIÓN NEURODINAMICA CAPÍTULO 12 Simon Haykin Ing. Danilo Chavez Ing. Jorge A. Sarapura INAUT 2007

2 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 2 ORGANIZACIÓN DEL TEMA

3 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 3 INTRODUCCIÓN

4 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 4 Aprendizaje Supervisado: –Aprendizaje Cognititivo –Necesita un conjunto de elementos representativos de la operación del entorno Aprendizaje Reforzado: –Aprendizaje Conductista –Aprendizaje a través de la interacción entorno-sistema de aprendizaje. –Alcance de objetivos a pesar de incertidumbres. Método Clásico: –Aprendizaje: proceso de Castigo- Recompensa. –Objetivo: Alcanzar un Comportamiento Especializado. Método Moderno: –Basado en Programación Dinámica. –Las decisiones actuales consideran los efectos futuros. –Énfasis en el Planeamiento. Programación Dinámica –Trata con situaciones donde las decisiones se hacen por etapas. –Situaciones donde las decisiones no pueden realizarse en forma aislada. –Problema de asignación de crédito. –Dos características: un Sistema dinámico discreto oculto y una función de costo aditiva todo el tiempo. Programación Neurodinámica –Fundamentos teóricos provistos por la programación dinámica. –Capacidad de aprendizaje provista por las redes neuronales. –Definición (Bertsekas et. al. 1996) La programación neurodinámica posibilita a un sistema a tomar buenas decisiones observando su propio comportamiento y mejorar sus acciones usando un mecanismo incorporado a través del refuerzo.

5 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 5 PROCESO DE DECISIÓN MARKOVIANO Características: –El entorno evoluciona probabilísticamente ocupando un conjunto finito de estados discretos . –Para cada estado del entorno hay un conjunto finito de acciones A i. –El sistema de aprendizaje toma una acción todo el tiempo, un cierto costo ocurre. –Los estados son observados, las acciones tomadas y los costos son incurridos a intervalos discretos. Propiedad de Markov La probabilidad de transición del estado i al estado j depende del estado actual y de la correspondiente acción a. La probabilidad de transición del estado i al estado j depende del estado actual y de la correspondiente acción a ik. Costo incurrido: Factor de descuento mapeo de estados en acciones (estacionario o no) Política: mapeo de estados en acciones (estacionario o no) Secuencia de estados del entorno resultante de las acciones tomadas por el sistema de aprendizaje para un Nº dado de estados y probabilidades de transición. Cadena de Markov: Secuencia de estados del entorno resultante de las acciones tomadas por el sistema de aprendizaje para un Nº dado de estados y probabilidades de transición. (SISTEMA DINÁMICO DISCRETO OCULTO)

6 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 6 Dado un proceso de decisión Markoviano estacionario describiendo la interacción entre un sistema de aprendizaje y su entorno, buscar una política estacionaria que minimice la función de costo por alcanzarpara todo estado inicial i. El Problema Básico Tipos de Problemas en Programación Dinámica: De horizonte finito: el costo es acumulado sobre un número finito de etapas. De horizonte infinito: el costo es acumulado sobre un número infinito de etapas Comienza para un estado inicial X 0 =i y usa una politica  ={  n }. El valor optimo es: (FUNCIÓN DE COSTO) Importante: Durante el aprendizaje el comportamiento del sistema de aprendizaje puede cambiar con el tiempo, pero la política óptima que busca será fija.

7 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 7 PRINCIPIO DE OPTIMALIDAD DE BELLMAN Una política óptima tiene la propiedad de que, cualesquiera sean el estado y las decisiones iniciales tomadas, las restantes decisiones deben constituir una polìtica óptima con independencia del estado resultante de la primera decisión. Una política óptima tiene la propiedad de que, cualesquiera sean el estado y las decisiones iniciales tomadas, las restantes decisiones deben constituir una polìtica óptima con independencia del estado resultante de la primera decisión. Construir una política óptima para el “último subproblema” que implique solamente el último estado Extender la política óptima del último problema implicando los dos últimos estados Continuar hasta que todo el problema esté tratado.

8 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 8 PRINCIPIO DE OPTIMALIDAD DE BELLMAN ALGORITMO DE PROGRAMACIÓN DINAMICA Para cualquier estado inicial X 0, el costo òptimo J*( X 0 ) de problema de horizonte finito es igual a J 0 ( X 0 ), donde la función J 0 es obtenida del paso anterior del algoritmo: El mismo que funciona a traves del tiempo Si µ n * minimiza E, para cada X n y n, entonces la polìtica π* = { µ 0 *, µ 1 *, …, µ K-1 * } es óptima. Costo terminal ( K = horizonte )

9 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 9 PRINCIPIO DE OPTIMALIDAD DE BELLMAN ECUACION DE OPTIMALIDAD DE BELLMAN La conexión entre un problema de horizonte finito y uno infinito utlilizando como polìtica de optimización π = { µ, µ, µ, … }. La conexión entre un problema de horizonte finito y uno infinito utlilizando como polìtica de optimización π = { µ, µ, µ, … }. Si n+1 = K y X 0 = i, entonces: Si n+1 = K y X 0 = i, entonces: Costo inmediato esperado Probabilidad de transición

10 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 10 ITERACIÓN POLÍTICA Factor-Q: es el costo inmediato mas la suma de los costos descontados de todos los estados sucesores tras la política , considerando esta existente y la función J  (i) conocida para todo estado i. Política codiciosa: la política  es codiciosa con respecto a la función, si para todo estado i,  (i) satisface: De esto tenemos que: i, a k i j, b j Nuevo sistema con 2 tipos posibles transiciones

11 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 11 Algoritmo de Iteración Política 1. Se calcula la función de costo por alcanzar para alguna política actual y su correspondiente factor-Q para todos los estados y acciones. 2. La política actual es actualizada para ser codiciosa con respecto a la función costo por alcanzar del paso 1. 1. Empezamos con alguna política inicial  0 y generamos una secuencia de políticas nuevas  1,  2,…. Dada la actual política  n, realizamos el paso 1, calculando J  n (i) y con esto el factor-Q para el par estado-acción (i, a) como: 2. Realizamos el paso de mejora de la política, calculando una nueva política  n+1 : Los dos pasos se repiten (con  n+1 en lugar de  n ) mientras:

12 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 12 VALUE ITERATION Intenta disminuir el costo computacional de la iteración de política. Implica el solucionar de la ecuación de optimalidad para cada uno de una secuencia de los problemas finitos. En el límite la función de costo del problema de horizonte finito converge a la función de costo del problema de horizonte infinito Por tanto podemos aproximar la función de costo

13 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 13 VALUE ITERATION VALUE ITERATION ALGORITHM VALUE ITERATION ALGORITHM 1. Comenzar con un valor arbitrario de J 0 (i) para el estado i = 1,2,…,N. 1. Comenzar con un valor arbitrario de J 0 (i) para el estado i = 1,2,…,N. 2. Para n = 0,1,2,…, calcular: 2. Para n = 0,1,2,…, calcular: 3. Calcular Q - factor: 3. Calcular Q - factor: Por lo tanto, determinar la política óptima como política codiciosa para J* (i): Por lo tanto, determinar la política óptima como política codiciosa para J* (i): Parámetro de tolerancia

14 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 14 VALUE ITERATION

15 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 15 A 3 411 C B EH F DG A I J 1 2 2 3 3 3 3 3 3 4 4 4 4 4 4 1 7 5 6 6 STAGECOACH PROBLEM Stage 1 Stage 2 Stage 3 Stage 4 C B D 1 3 4 4 7 8 711 E F G 3 3 1 6 74 H I J 3 43 4 Tres rutas óptimas: A → C → E → H → J A → D → E → H → J A → D → F → I → J acciones (a) Arriba, abajo, al costado, etc Arriba, abajo, al costado, etc Ocho estados (i) A, B, C, …, J A, B, C, …, J

16 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 16 PROGRAMACIÓN NEURODINÁMICA Objetivo Principal: –Encontrar una política óptima, es decir, una elección óptima de la acción que debería ser tomada por el Sistema de Aprendizaje para cada estado posible del entorno. Interés particular en problemas de grandes dimensiones. Problemas de los Algoritmos de Iteración: –Maldición de la Dimensionalidad: Un problema de programación dinámica que involucra un total de N estados y M posibles acciones por cada estado, cada iteración del algoritmo de Iteración de Valor requiere N 2 M operaciones para una política estacionaria. Ejemplo: juego Backgammon. –Información Incompleta: Los algoritmos de Iteración Política y de Valor requieren conocer las probabilidades de transición de estado y los costos observados (Modelo de Markov del entorno). Solución: –Buscar una política subóptima en vez de una óptima (Aproximar J*(i)). RN (W)  + -

17 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 17 PROGRAMACIÓN NEURODINÁMICA Dos Situaciones Posibles: –El conjunto de datos de entrenamiento {i, J*(i)} esta disponible, entonces se busca la aproximación de la función J*(.) para que el vector W tenga una dimensión pequeña. Representación Compacta, solo se almacena W y la función de aproximación. –El conjunto de datos de entrenamiento no esta disponible, entonces se optimiza en un sentido estadístico usando la simulación de Monte Carlo, para sustituir al modelo Markoviano del sistema (Modo de operación de programación dinámica off-line ). Ventajas: La simulación permite evaluar aproximadamente la función de costo por alcanzar óptima, esta es la principal distinción entre la metodología de programación neurodinámica de los métodos tradicionales de aproximación de la programación dinámica. La simulación permite el uso de métodos de programación neurodinámica para diseñar sistemas para los cuales no se tiene el modelo explicito, porque es engorroso o imposible estimar las probabilidades de transición de estados. A través de la simulación podemos identificar los estados mas importantes como aquellos mas visitados durante la simulación. Por lo tanto, la función de costo aproximada encontrada por la RN puede proveer una buena aproximación de la función J*(i); y el resultado final una buena política subóptima.

18 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 18 Iteración Política Aproximada 1. Dada alguna política actual , se calcula una aproximación de la función de costo por alcanzar para todo estado i. 2. Usando la función costo por alcanzar aproximada del paso 1, se mejora la política  ; esta nueva política se diseña para ser codiciosa con respecto a la función de costo por alcanzar aproximada calculada. Suposición: Se tiene un modelo del sistema, es decir, las probabilidades de transición y los costos observados son conocidos. Se tiene además: Una política estacionaria  como la política inicial. Un conjunto de estados representativos de la operación del entorno. Un conjunto de M(i) muestras de la función de costo por alcanzar J  (i) para cada estado i   (cada muestra se denota por k(i,m), m=1,…,M(i)). Actualización de Política RN para la Evaluación Aproximada de la Políticaw Perceptron Multicapa entrenado con el algoritmo back-propagation

19 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 19 Iteración Política Aproximada Pasos del Algoritmo: 1. Determinar w (y por lo tanto J  (i) aproximada) usando el método de mínimos cuadrados, es decir, minimizando: 2. Determinar el factor-Q aproximado con: 3. Determinar una política mejorada usando: Fuentes de Error: 1º- La RN usada para calcular la función de costo por alcanzar aproximada puede no ser adecuada calculando potencias. 2º- La aproximación hecha por la RN se basa en respuestas deseadas provistas por el simulador. Convergencia: Asumiendo que toda evaluación y mejora de la política se realiza con ciertas tolerancias de error  y , respectivamente. Puede probarse que el algoritmo producirá políticas cuyas perfomance difieren de las políticas óptimas en un factor que decrece a cero conforme  y  se reducen. Simulador Generador de acciones AproximadorCost-to-go Resol. Mínimo Cuadrado Construye un modelo sustituto del entorno (Genera estados y muestras de la función cost-to-go) Genera una política mejorada Genera la función cost-to-go aprox.

20 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 20 Q-LEARNING Q-Learning se define como una forma de aprender modelo-libre del aprendizaje reforzado[Watkins, 1989; Watkins y Dayan, 1992; Jang, et. Todos, 1997]. Es utilizado para un problema donde se tiene información incompleta DEL MODELO, pero se necesita que el modelo sea absolutamente observable. Podría ser vista como versión incremental de Programación Dinámica que mejora sucesivamente sus evaluaciones de acciones específicas en los estados específicos. El objetivo es encontrar la política óptima y el valor de su estado se estima mientras que se valora el mejor par de estado-acción del estado

21 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 21 Q-LEARNING La convergencia asintótica del algoritmo Q-learning al valor óptimo Q* (i, a) para todos los pares posibles de la estado-acción (i, a) se asegura con la condición de que todos los pares de la estado-acción sean visitados infinitamente a menudo.

22 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 22 Se puede reemplazar una pate de la ecuaciòn por el valor Q-factor deseado Para el estado n-esimo tenemos que el Q-factor está definido por: donde “i n ” y “ a n ” son el estado actual y la acción actual, respectivamente. Q-Learning Aproximado El “Q-valor estimado” es el “actual Q-valor” de tomar la acción “a” en el estado “i” y después de usar las acciones óptimas en todos los estados futuros. En un proceso repetitivo para intentar todas las acciones en todos los estados, el agente aprende cuáles son las mejores, juzgando por la recompensa descontada a largo plazo.

23 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 23Q-Learning Flowchart of the One-step Q-learning Algorithm using NN approximators INICIO Observar el estado Actual in Escoger una acción an, de Forma estocástica Para la acción seleccionada Calcular Q-valor con la red 1 1 Ejecutar la acción an Observar el siguiente Estado j, y calcular el refuerzo Calcular Q(j,b), con la red Q-net 1 1 Calcular el Q deseado Ajustar los valores de la red Q-net Utilizando backpropagation FIN

24 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 24 El algoritmo es aplicado a una red neuronal de la siguiente manera Q-Learning Q-net arquitectura RN (W)  + -

25 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 25 Aplicación de la NPD al Control Óptimo de Sistemas Sistema de control óptimo: sistema en el cual se optimiza un índice de desempeño. Problema de control óptimo: dado un estado inicial del sistema, buscar una secuencia de acciones de control de manera tal de llevar al sistema a una región deseada del espacio de estado minimizando un índice de desempeño predeterminado. –El enfoque tradicional de resolver un problema de control óptimo se basa en el principio de optimalidad de Bellman, el cual aplicado a sistemas continuos conduce a la ecuación de Hamilton, Jacobi, Bellman. Estas ecuaciones no siempre tienen una solución analítica, se encuentran soluciones para sistemas lineales, variantes y con índices de desempeño cuadráticos como el (LQR) que lleva a la ecuación de Riccati. El mismo principio aplicado a sistemas discretos conduce a algoritmos de programación dinámica. Solución de Problemas de Control Óptimo: debido a los problemas inherentes de la programación dinámica (dimensionalidad,...) para resolver ciertos problemas, se han desarrollado sistemas de control óptimo basados en métodos avanzados de la PD, como la Programación Dinámica Iterativa y la Programación Neurodinámica. Esta última en vez de evaluar el índice de desempeño para todos los estados posibles, emplea RN para aproximarlo. Diseños Críticos Adaptables: existen básicamente 3 tipos de métodos de PD aproximada o NPD: PD Heurística (HDP), PD Heurística Dual (DHP) y PD Heurística Dual Globalizada (GDHP); estos métodos en conjunto son llamados Diseños Críticos Adaptables.

26 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 26 Aplicación de la NPD al Control Óptimo de Sistemas Modelo en espacio de estado (en gral. no lineal, variante y discreto): Índice de desempeño o función costo de trayectoria del estado x(i) Principio de Optimalidad para sistemas de tiempo discreto: Modelo Markoviano (basado en la propiedad de Markov): Función costo por alcanzar: Principio de Optimalidad para sistemas no determinísticos: Modelo del sistema Funcional a Minimizar Principio de Optimalidad de Bellman Sistemas Determinísticos y Estocásticos. Una comparación:

27 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 27 Diseño Adaptable Crítico Red Crítica (W C ) Red Acción (Controlador) (W A ) Modelo (W M ) Planta (Entorno) Error: Leyesde ajuste: Leyes de ajuste: Estructura de Diseño Crítico Adaptable con el método HDP de Programación Neurodinámica Predice el estado Permite calcular Estima la función Minimiza la función

28 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 28 Aplicación a la Navegación de Barcos Modelo Dinámico de un Barco de Mediano Porte (Anderson & Miller, 1990) Tiempo de Convergencia de la velocidad de giro Velocidad ctte. del barco Ctte. Periodo de muestreo Velocidad de giro Ángulo Timón Objetivo del Control: Dada una serie de puntos ordenados de referencia y conociendo el modelo dinámico, se desea obtener autónomamente una secuencia óptima de acciones de control de manera de conducir el barco a través de dichos puntos tan rápido como sea posible. Sistema de control  Sistema de piloto automático (lazo directo), el cual manipula directamente el ángulo del timón.  Operador, que cierra el lazo de control y da las consignas angulares deseadas.

29 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 29 Implementación: Los tres módulos (crítico, acción y modelo) son implementados usando RN estáticas, cada una con 6 entradas, las cuales son: Los datos para entrenar la red crítica se obtienen de muestrear una trayectoria que comienza en una determinada posición y que pasa por unos puntos especificados. Función de utilidad: Factor de Descuento: Aplicación a la Navegación de Barcos Posiciones de referencia del barco

30 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 30 Aplicación a la Navegación de Barcos Trayectoria para el pasaje por una compuerta, luego de 20 iteraciones. Resultado de Simulación:

31 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 31 Aplicación a la Navegación de Barcos Resultado de Simulación: Trayectoria para el pasaje a través de 4 compuertas, luego de 6000 iteraciones.

32 26/06/2017 PROGRAMACIÓN NEURODINÁMICA 32 BIBLIOGRAFÍA Simon Haykin, 1999, Neural Networks: A Comprehensive Foundation. Bertsekas and Tsitsiklis, 1996, Neuro-Dynamic Programming. Patiño, Fullana and Schugurensky, 2004, Programación Dinámica.