Proyecto de tesis Intranet - iri.upc.edu · descuento. Sin embargo si el entorno es no determinista, como suele ser el caso, no existirá un único valor para la ecuación (1), sino

ÍNDICE

1. RESUMEN DEL PROYECTO ..................................................................................................... 1

2. OBJETIVOS ................................................................................................................................... 3

2.1. OBJETIVOS TEÓRICOS ................................................................................................................. 3 2.2. OBJETIVOS PRÁCTICOS ............................................................................................................... 3

3. ESTADO DEL ARTE .................................................................................................................... 4

3.1. APRENDIZAJE POR REFUERZO ................................................................................................... 4 3.2. APRENDIZAJE POR REFUERZO EN DOMINIOS CONTINUOS ....................................................... 5 3.2.1. TÉCNICAS DE APROXIMACIÓN DE FUNCIONES .......................................................................... 6 3.2.2. TÉCNICAS DE RESOLUCIÓN VARIABLE .....................................................................................13 3.2.3. GENERALIZACIÓN EN EL ESPACIO DE ACCIONES ......................................................................16 3.3. APRENDIZAJE EN ENTORNOS CATEGORIZABLES .....................................................................16 3.3.1. DESCRIPCIÓN DEL ALGORITMO ................................................................................................17

4. TRABAJO PREVIO .....................................................................................................................20

4.1. EVALUACIÓN DEL ALGORITMO CL ..........................................................................................20 4.1.1. RESULTADOS .............................................................................................................................21 4.2. CONTROL DE MOTOR CON EL ALGORITMO CL .......................................................................22 4.2.1. MODELADO DEL MOTOR ...........................................................................................................22 4.2.2. GENERACIÓN DE TRAYECTORIAS DE REFERENCIA ...................................................................23 4.2.3. FORMULACIÓN DEL PROBLEMA PARA EL ALGORITMO CL .......................................................23 4.2.4. FUNCIÓN DE RECOMPENSA ........................................................................................................24 4.2.5. NUEVOS CAMBIOS DEL ALGORITMO ........................................................................................24 4.2.6. CONTROL PID ...........................................................................................................................25 4.2.7. RESULTADOS .............................................................................................................................25 4.3. CONTROL DE UN MANIPULADOR CON EL ALGORITMO CL .....................................................28 4.3.1. MODELO DEL MANIPULADOR ...................................................................................................28 4.3.2. FORMULACIÓN DEL PROBLEMA PARA EL ALGORITMO CL .......................................................29 4.3.3. RESULTADOS .............................................................................................................................29 4.4. NUEVA FORMULACIÓN MATEMÁTICA DEL ALGORITMO ........................................................30 4.4.1. INFERENCIA ESTADÍSTICA ........................................................................................................31 4.4.2. ESTIMACIÓN EN EL Q-LEARNING ..............................................................................................35 4.4.3. ESTIMACIÓN EN EL APRENDIZAJE CON CATEGORIZACIÓN ........................................................37

5. PROYECTO DE TESIS ...............................................................................................................42

5.1. MEJORA DEL ALGORITMO CL. GESTIÓN DE VISIONES PARCIALES. ......................................42 5.2. ADAPTACIÓN DEL ALGORITMO CL PARA APRENDIZAJE EN DOMINIO CONTINUO ...............42 5.2.1. RESOLUCIÓN VARIABLE EN APRENDIZAJE EN ENTORNOS CATEGORIZABLES .........................42 5.2.2. APROXIMACIÓN DE FUNCIONES EN APRENDIZAJE EN ENTONOS CATEGORIZABLES ................42 5.2.3. APROXIMACIÓN DE FUNCIONES CON RESOLUCIÓN VARIABLE EN APRENDIZAJE EN ENTORNOS CATEGORIZABLES ..................................................................................................................................42 5.2.4. GENERALIZACIÓN EN EL ESPACIO DE ACCIONES ......................................................................43 5.3. EVALUACIÓN DEL ALGORITMO CL PARA DOMINIOS CONTINUOS USANDO UN SIMULADOR 43

5.4. APLICACIÓN DEL ALGORITMO A UN PROBLEMA REAL COMPLEJO .......................................43 5.4.1. EL ROBOT ARGOS ......................................................................................................................43

6. PLAN DE TRABAJO ...................................................................................................................45

7. REFERENCIAS ............................................................................................................................46

8. PUBLICACIONES REALIZADAS ............................................................................................49

Proyecto de Tesis RESUMEN

1

1. Resumen del Proyecto Muchos de los problemas que se pretenden resolver con la inteligencia artificial tienen como dominio el mundo real. Estos dominios poseen generalmente características continuas. La mayoría de los problemas planteados en estos entornos requieren para su resolución una gran cantidad de conocimiento específico. Este conocimiento usualmente no está disponible y es necesario extraerlo. El aprendizaje por refuerzo es un paradigma en el cual un agente autónomo mejora su comportamiento extrayendo este conocimiento del entorno basándose solo en la propia experiencia. El aprendizaje por refuerzo asume dominios discretos para su formulación teórica. Si el dominio del problema es continuo la técnica más comúnmente utilizada es la discretización de las variables continuas que se utilizarán en el aprendizaje. Pero la discretización de las variables genera algunos inconvenientes. Si se utilizan segmentos muy anchos para la discretización no será posible extraer la toda información del dominio necesaria para lograr un aprendizaje adecuado. Por otro lado, si la discretización es muy fina la cantidad de experiencia necesaria en el aprendizaje crece considerablemente. Este problema se conoce como la maldición de la dimensionalidad. Por este motivo la aplicación de aprendizaje por refuerzo en problemas complejos de dominio continuo solo es viable si se puede realizar algún tipo de generalización que disminuya la cantidad de experiencia necesaria. Se han propuesto diversas técnicas de generalización. En general se pueden clasificar en dos grupos: Las técnicas de aproximación de funciones y las técnicas de resolución variable. Las técnicas de aproximación de funciones intentan solucionar el problema de la maldición de la dimensionalidad aproximando una función sobre las variables del dominio usando la información extraída de las zonas donde hubo experimentación para estimar la información contenida en las zonas no experimentadas. Las técnicas de resolución variable en cambio pretenden solucionar el problema de la maldición de la dimensionalidad evitando hacer una discretización fina en todo el dominio de las variables, con el consiguiente incremento explosivo de la cantidad de experiencia necesaria, realizándola solamente en las zonas que concentran mayor información útil para la resolución del problema y realizando una discretización más gruesa en las zonas donde la información es más irrelevante. No obstante algunos problemas puntuales donde se obtuvieron muy buenos resultados, las técnicas de generalización para dominios continuos aún están en fase de experimentación y todavía quedan muchos problemas por resolver. Uno de los inconvenientes principales que tienen actualmente estas técnicas es que, a pesar de realizar generalización, no pueden resolver el problema de la maldición de la dimensionalidad en problemas de mediana complejidad que utilizan un número mayor a 5 o 6 variables continuas. Este inconveniente podría solucionarse si se aprovecha una propiedad del entorno, que la contendrá en mayor o menor medida, denominada categorizabilidad. Categorizabilidad significa que de todas las variables del entorno que se deben observar para obtener información útil en cualquier región del dominio, solo un reducido número de ellas será relevante para obtener la información útil de una región en particular. Se ha desarrollado un algoritmo que procura aprovechar esta propiedad para el aprendizaje. Este algoritmo, llamado algoritmo de aprendizaje en entornos categorizables, también está en fase de experimentación, y al igual que las técnicas de aprendizaje por refuerzo, fue diseñado asumiendo un dominio discreto. En este proyecto se pretende mejorar los resultados hasta ahora obtenidos con las técnicas de aprendizaje en dominios continuos aprovechando la propiedad de categorizabilidad. Para ello se propone diseñar una técnica que combine los métodos de generalización en dominios continuos con la técnica de aprendizaje en entornos categorizables. Posteriormente se aplicará la nueva técnica de aprendizaje para dominio continuo a un problema real complejo, el problema de control de locomoción de un robot caminante hexápodo.

Proyecto de Tesis RESUMEN

2

El presente trabajo se estructura como sigue. Primero se establecen los objetivos del proyecto. Luego se desarrolla el estado del arte para las técnicas de aprendizaje y métodos de generalización en dominio continuo, y el estado del arte de la técnica de aprendizaje en entornos categorizables. Continúa con una descripción del trabajo previo realizado referido a los objetivos del proyecto y el estado actual de la investigación. Finalmente se describe el enfoque que se utilizará para alcanzar los objetivos y un calendario tentativo para cada una de las tareas propuestas.

Proyecto de Tesis OBJETIVOS

3

2. Objetivos 2.1. OBJETIVOS TEÓRICOS El objetivo general del proyecto es desarrollar una técnica de aprendizaje para dominios continuos que mejore los resultados hasta ahora obtenidos aprovechando la propiedad de categorizabilidad. Para ello nos planteamos los siguientes objetivos intermedios:

Mejorar la técnica de aprendizaje en entornos categorizables que existe actualmente. Desarrollar una técnica de resolución variable que pueda aplicarse al aprendizaje en

entornos categorizables. Desarrollar una técnica de aproximación de funciones que pueda aplicarse al

aprendizaje en entornos categorizables. Combinar técnicas de aproximación de funciones con técnicas de resolución variable

para mejorar la aproximación en el aprendizaje en entornos categorizables.

2.2. OBJETIVOS PRÁCTICOS Aplicar la técnica desarrollada de aprendizaje para dominios continuos al problema de

control de locomoción de un robot hexápodo. Mejorar los resultados de aplicar una técnica de control proporcional-integral-

derivativo para la misma tarea.

Proyecto de Tesis ESTADO DEL ARTE

4

3. Estado del arte 3.1. APRENDIZAJE POR REFUERZO En esta sección se realizará una breve introducción de los conceptos que utilizaremos más adelante. El aprendizaje por refuerzo (RL) [36], [22] es un paradigma en el cual un agente aprende una política de acción para alcanzar su objetivo en base a la interacción con el entorno. Con cada interacción recibe una recompensa en base al objetivo planteado. En el RL se busca que el agente aprenda la política de acción con la que obtenga una mayor recompensa acumulada a lo largo de ella. El agente percibe el entorno a través de sus detectores. Con las lecturas de los detectores genera un estado s del entorno. Para cada estado existirá un conjunto de acciones posibles y seleccionará una acción a para su ejecución. La ejecución de a cuando se observa s resultará en una recompensa r y en un nuevo estado s’. El RL supone que la información contenida en s es suficiente para aprender a estimar el resultado de ejecutar a y con que probabilidad se realizará la transición a un estado s’. Si s contiene esta información entonces se dice que tiene la propiedad de Markov. Los procesos cuyos estados cumplen con esta propiedad se llaman Procesos de Decisión de Markov (MDP) [36]. Uno de los algoritmos de RL más utilizados para encontrar la política con la que se maximiza la recompensa acumulada es el Q-Learning [41]. Este algoritmo estima el valor de recompensa acumulada, Q(s,a), para la política óptima que sigue de ejecutar a en el estado s. Si el entrono es determinista el valor real de Q(s,a) se obtiene de la siguiente ecuación,

)','(max),('

asQrasQa

γ+= (1)

donde s’ es el estado resultante de ejecutar la acción a en el estado s y γ es el coeficiente de descuento. Sin embargo si el entorno es no determinista, como suele ser el caso, no existirá un único valor para la ecuación (1), sino que se obtendrán diferentes valores a lo largo del aprendizaje. Llamaremos a estos valores q(s,a). Esto se produce por que el valor de recompensa r se obtendrá ahora de acuerdo a una distribución de probabilidad y la transición al estado s´ estará también sujeta a una probabilidad de transición. La distribución de probabilidades sobre el conjunto de estados s’ que pueden resultar de ejecutar a en el estado s es,

aassssP ttta

ss ==== + ,|'Pr 1' (2)

Asimismo, el valor esperado de la distribución de probabilidad para el valor de recompensa r obtenido luego de ejecutar la acción a en el estado s y que resulte en cualquier estado s’ es,

',,| 1' ssaassrER tttass ==== + (3)

La política óptima en este caso será aquella que maximice el valor esperado la recompensa acumulada, ),()','(max),(

'asqEasQrEasQ

a=+= γ (4)


5

[ ]∑ +=' ''' )','(max

s a

ass

ass asQRP γ (5)

La ecuación (5) es conocida como ecuación de Bellman [9]. En casi totalidad de los problemas donde se aplica RL el modelo del entorno es desconocido, y por lo tanto, es desconocida la distribución (2) y el valor (3). Por este motivo el valor de Q(s, a) es desconocido y debe estimarse. En el caso de entornos no deterministas esta estimación se realiza de forma iterativa utilizando un promedio ponderado de las observaciones individuales,

)','(ˆmax'

asQrqa

γ+= (6)

qasQasQ .),(ˆ)1(),(ˆ αα +−← (7) donde ),(ˆ asQ es el valor estimado de Q(s, a) y α el coeficiente de aprendizaje. Cuando se trata de problemas episódicos el valor estimado converge al valor real para n→∞ siempre que α sea pequeño y decrezca a lo largo del tiempo de forma adecuada, cumpliendo con los enunciados de la teoría de aproximaciones estocásticas [36]. En el caso de que el entorno sea también no estacionario, entonces no es posible converger al valor Q(s, a) pero sí a una buena aproximación de él, y el valor de α deberá tener un valor constante pequeño cuando n→∞ para que la estimación se adapte suavemente a los cambios de Q(s,a) producidos por la no estacionariedad. En los problemas no episódicos no es posible lograr esta convergencia pero el algoritmo de Q-Learning siempre adapta los valores estimados en la dirección de la política óptima [36].

3.2. APRENDIZAJE POR REFUERZO EN DOMINIOS CONTINUOS Los algoritmos de RL asumen que el entorno cumple con la propiedad de Markov, y las políticas aprendidas corresponden a procesos markovianos (MDP). En estos procesos se consideran estados discretos. Así, los algoritmos RL convencionales necesitan que el entorno esté representado por estados y acciones discretos. Muchas de las aplicaciones importantes en RL se realizan en entornos reales con variables continuas. Para poder aplicar RL en estos entornos, la técnica más comúnmente utilizada es la discretización del tiempo, de las variables continuas que componen el estado, y de las acciones a ejecutar. Luego, para encontrar la política óptima, el algoritmo deberá experimentar todos los estados varias veces para que el valor aprendido sea una buena estimación de la recompensa acumulada. En general existen dos problemas ocasionados por la discretización:

• Si la discretización se realiza considerando segmentos muy anchos la función de estimación de recompensa acumulada tendrá grandes discontinuidades y además la estimación será poco precisa, resultando en un desempeño bajo del algoritmo.

• Si en cambio se realiza una discretización fina, el número de estados y el número de iteraciones necesarias para experimentarlos, se hace demasiado grande. El aprendizaje será muy lento y con grandes requerimientos de memoria. Este problema es conocido como “maldición de la dimensionalidad” (“curse of dimensionality”) [36].

Así, la aplicación de técnicas de RL en entornos reales solo tendrá sentido si se puede conseguir algún tipo de generalización que permita un aprendizaje eficiente disminuyendo la cantidad de experimentación necesaria. Se pretende entonces que con la generalización se utilice la experiencia de aquellos estados visitados para los estados que nunca se han visto con


6

anterioridad. Describiremos a continuación las técnicas de generalización más utilizadas en RL.

3.2.1. Técnicas de Aproximación de Funciones Las técnicas de aproximación de funciones (AF) intentan aproximar una función desconocida f(x) usando ejemplos [xi, f(xi)] obtenidos de la misma. Ya que estas técnicas utilizan ejemplos que contienen la salida deseada f(xi) para las entradas xi, han sido extensamente aplicadas en aprendizaje supervisado para aproximar la función valor (FV). En general en RL no se dispone de la salida deseada de la función de recompensa acumulada de los puntos ejemplos, pero si de una estimación de la misma. Con estas estimaciones podemos crear los ejemplos que usaremos para aproximar la FV. Existen muchas técnicas de AF que se aplican en el aprendizaje supervisado y en principio cualquiera de ellas podría ser aplicada a RL. Sin embargo no todas las técnicas son igualmente adecuadas. Las técnicas de AF que se apliquen a RL deben se robustas ante la aproximación de funciones no estacionarias. Por ejemplo, en el caso del Q-Learning, que realiza estimaciones usando otras estimaciones (bootstrapping), los valores estimados de la FV cambian constantemente. Incluso pueden existir cambios en la propia FV si el entorno es no estacionario. Por esto, los métodos que pueden manejar mejor las características no estacionarias del sistema son más adecuados para ser aplicados en el RL. Generalmente se utilizan métodos de AF de bajo costo computacional así se puede crear nuevas aproximaciones rápidamente ante el dinamismo del sistema. Por otro lado, algunas de las técnicas de aprendizaje que se explicarán más adelante, agregan nuevos ejemplos durante el aprendizaje para mejorar la aproximación. Así, las técnicas de AF utilizadas en esos casos deberán ser robustas frente al aumento del número de ejemplos. En aprendizaje supervisado, el aprendizaje basado en el agregado de nuevos ejemplos se conoce con el nombre de aprendizaje basado en memoria [26]. Con estas técnicas los ejemplos observados son simplemente almacenados en memoria y la aproximación de la FV no se realiza hasta que no se requiere estimar el valor de la FV para un nuevo estado observado. Cuando esto ocurre se recuperan de la memoria los ejemplos cercanos al nuevo estado observado y se aproxima la VF solo considerando estos ejemplos. De esta manera la aproximación es local en vez de global consiguiéndose muy buenos resultados aunque la función global sea muy compleja ya que localmente se puede aproximar con un modelo simple.

3.2.1.1. Aproximación de Funciones en Q-Learning En el aprendizaje por refuerzo las técnicas de AF sustituyen los valores tabulados de Q(s, a) por una función parametrizada con un conjunto de parámetros θ. Usualmente la cantidad de parámetros es mucho menor que la cantidad de estados utilizados en el Q-Learning convencional. Para evaluar la aproximación de la función Q(s,a) se utiliza generalmente el error cuadrático medio (ECM) de estimación. Se busca un conjunto de parámetros θ que minimice este error sobre los puntos del espacio estado-acción que se experimenten con mayor frecuencia y probablemente correspondan a políticas deseadas. Para ello, se utiliza una distribución de probabilidad sobre estos puntos, P(s,a), la cual se tomará en cuenta para la minimización ECM. Para formalizar el problema de la AF, supongamos primero que conocemos la función de recompensa acumulada al seguir una política π luego de ejecutar la acción a en el estado s. Llamaremos a esta función Qπ(s,a). Sea Qt(s,a) una función parametrizada con parámetros θπ que aproxima Qπ(s,a). El ECM de la aproximación teniendo en cuenta la distribución P(s,a) es,


7

ECM(θπ) [ ]∑

∈

−=)(,,

2),(),(),(sASas

t asQasQasP π (8)

donde S es el espacio de estados y A(s) el espacio de acciones. En un problema real los valores de la función Qπ(s,a) son desconocidos pero podemos considerar los valores observado qπ(s,a) como una aproximación de ellos (solo a modo ilustrativo, la estimación de valores Q que corresponden una política determinada π se hace usando el algoritmo Sarsa [36]). Usaremos estos valores en la ecuación (8) en lugar de Qπ(s,a) para encontrar un conjunto de parámetros θ. Usando RL y AF se busca que θ→θπ. Para encontrar los parámetros θπ, la distribución P(s, a) deberá corresponderse con la política π, por lo que a esta distribución se la llama distribución on-policy. Para el caso de que la política π sea la óptima no es posible determinar la distribución P(s,a) y los ejemplos deberán presentarse cuidadosamente para converger a una buena aproximación [35], [36]. Se han propuesto diferentes formas de presentar los ejemplos para lograr convergencia en el aprendizaje utilizando el algoritmo de Q-Learning y FA, pero en general se debe especificar a priori posibles trayectorias en el espacio de estado cercanas a la trayectoria de la política óptima [35], [12], [36]. Adicionalmente, para realizar AF utilizando el algoritmo de Q-Learning es necesario combinar las técnicas de actualización del valor estimado de Q(s,a) y de selección de acción con las técnicas de AF. Las técnicas de selección de acción para acciones continuas es todavía un área abierta de investigación [35], [21]. Sin embargo, si las acciones son pocas y discretas, la actualización y la selección de acción se realizan de igual manera que en el Q-Learning convencional, pero con la precaución de que la selección de acción se realizará de acuerdo a una política suave que se corresponda con las trayectorias seleccionadas en el espacio de estados para lograr la convergencia.

3.2.1.2. Métodos Globales de Aproximación de Funciones Los métodos globales de AF mantienen y actualizan los conjuntos de parámetros θ en todas las regiones del espacio de estado. Ya que almacenan en memoria el valor ajustado de éstos parámetros la actualización de los mismos hasta los valores óptimos posibles en un instante determinado se realiza rápidamente. Gracias a esto, en el caso de los métodos globales es posible aplicar técnicas de AF que tengan más precisión en la aproximación aunque resulten más costosas desde el punto de vista computacional, como por ejemplo las redes neuronales y algunos casos de métodos lineales.

3.2.1.2.1. Redes Neuronales Existen diferentes opiniones acerca del uso de redes neuronales como AF en RL. Aunque se han obtenido resultados sorprendentes al usar redes neuronales como método de AF en RL [37], generalmente no tienen un buen desempeño aún en problemas relativamente simples. Los principales problemas asociados al uso de redes neuronales en RL son:

• Aproximación global de la VF mientras que el RL requiere que se realicen ajustes locales durante el entrenamiento.

• Debido a la naturaleza de las redes neuronales y a las características no estacionarias de los valores que estima el RL durante el aprendizaje, la red es susceptible a sobrestimar la utilidad de un ejemplo [38]. Este hecho se conoce como over-fitting.

• La cantidad de cómputo necesaria para el ajuste de los pesos es elevada lo cual dificulta su aplicación on-line.

• No existen criterios establecidos bajo los cuales se asegure convergencia hacia una buena aproximación de la VF [39], [33].


8

No obstante los problemas enumerados, las redes neuronales siguen siendo motivo de investigación como método de AF en RL ya que pueden manejar entradas de muchas dimensiones más fácilmente que otros métodos de AF [15]. Se han propuesto diversas técnicas para solucionar estos inconvenientes [13], [15], [23]. Si bien estos métodos han demostrado buenos resultados en algunos problemas puntuales, la cantidad de cómputo sigue siendo elevada y aún persisten los problemas de convergencia.

3.2.1.2.2. Métodos lineales Globales En los métodos lineales la función parametrizada Qt(s,a) es lineal con respecto a los parámetros θ,

Qt(s,a) = ∑=

n

ias iFi

1, )().(θ (9)

donde n es el número de parámetros que se utiliza para la aproximación, y Fs,a es un conjunto de características del espacio estado-acción y son funciones creadas a partir de los elementos de los ejemplos considerados en este espacio. El vector Fs,a tiene las mismas dimensiones que θ,

Fs,a = (Fs,a(1),…,Fs,a(n))T (10) Una ventaja importante del caso lineal es que solo existe un mínimo para el ECM en donde el vector de parámetros θ es el óptimo θ*. Por ello cualquier método de AF que garantice una convergencia a un mínimo del ECM o a un valor cercano de este, y que utilice el caso lineal, convergerá al vector θ* o a un punto cercano de θ*. Para que pueda ocurrir esta convergencia es muy importante que los ejemplos se correspondan a una distribución on-policy, de lo contrario el método diverge. Una explicación más detallada sobre las condiciones técnicas para la convergencia de los métodos de FA que utilizan el caso lineal puede encontrarse en [36], [37]. Los métodos lineales son muy utilizados en la práctica no solo por que tienen mejores características de convergencia que otros métodos, sino también por su bajo requerimiento de cómputo. No obstante, la elección de las características Fs,a es crítica para lograr esta eficiencia. Esta elección deberá hacerse en base al problema y utilizando algún conocimiento del entorno lo cual es una desventaja en muchos problemas donde no se tiene ningún conocimiento previo.

Elección de las características Fs,a Las Fs,a se pueden construir de muchas maneras y utilizando diferentes técnicas. Dos de las técnicas más utilizadas son la codificación por grupos y la técnica de mosaicos. En la figura 1 se muestran las estructuras de las Fs,a para estas técnicas en un espacio de ejemplos de dos dimensiones,

a) b)

Figura 1. Creación de características Fs,a en un espacio de ejemplos de dos dimensiones. a) codificación por grupos utilizando círculos. b) codificación por mosaicos con una discretización uniforme y con dos grillas superpuestas. Se puede

considerar como un caso de codificación por grupo. Se muestran en ambos casos los elementos que se activan con un ejemplo “x”.

x


9

En la figura 1 se muestra un nuevo ejemplo “x” y las características que lo contienen. En la figura 1a) tres características contienen al nuevo ejemplo. Ellas constituirán los elementos del vector Fs,a. La estimación se realizará en este caso con un vector de parámetros θ de tres elementos, cada uno de ellos correspondiente a una característica. En el caso de la figura 1b) la cantidad de elementos del vector θ será de dos. En la codificación por mosaicos los mosaicos pueden ser de cualquier forma y tamaño, usando las formas más convenientes de acuerdo al problema considerado [36]. La precisión final de la aproximación luego del ajuste de los parámetros no dependerá del ancho de la región cubierta por cada característica en el espacio de estado, sino de la cantidad de características que se activan en una zona determinada. Cuanto mayor es la cantidad de características en una región, mayor precisión se conseguirá en la aproximación. Las características pueden ser binarias o no binarias. Las binarias solo toman valores 1 o 0 dependiendo si el ejemplo está o no dentro de su zona de cobertura. Por otro lado, las características no binarias pueden tomar más de dos valores distintos, dependiendo de la posición del nuevo ejemplo.

Radial Basis Functions La técnica “Radial Basis Functions” (RBF) se utiliza para crear características que tomen valores en el intervalo [0,1] dependiendo de una función de la distancia del centro de la misma al nuevo ejemplo. La función de la distancia más utilizada para definir estas características es la gaussiana y la distancia se calcula habitualmente como la distancia euclidea. Así el valor de la característica i del vector de características Fs,a será,

2

2

2, )( i

icx

as eiF σ

−−

= (11) donde ci es el centro de la característica y σi es la desviación estándar de la función gaussiana, la cual es considerada como el ancho de la característica.

Método iterativo para Calcular θ. Gradiente descendente. Se describe a continuación un método iterativo para calcular el valor de θ. Este método también se utiliza en redes neuronales para la actualización de los pesos de la red.

Gradiente Descendente Los métodos de gradiente descendente realizan un ajuste iterativo de los parámetros θ en la dirección donde el ECM decrece más rápidamente. Estos métodos son aplicables cuando la función Qt(s,a) es suave y diferenciable con respecto a θ. El ajuste de los parámetros se realiza de la siguiente manera,

[ ]21 ),(),(21

ttttttt asQasQt

−∇−=+ θαθθ

(12) [ ] ),(),(),( ttttttttt asQasQasQ

tθαθ ∇−+=

donde α es el coeficiente de ajuste y,

T

t

tt

t

tt

t

ttttt n

QQQasQ

t ⎟⎟⎠

⎞⎜⎜⎝

⎛∂∂

∂∂

∂∂

=∇)()(

,....,)2()(

,)1()(

),(θ

θθθ

θθ

θ (13)


10

Para garantizar la convergencia a un mínimo local del ECM el coeficiente α tiene que cumplir con las condiciones de la teoría de aproximaciones estocásticas [36].

Métodos de Gradiente Descendente para el Caso Lineal Lo interesante del caso lineal es que el gradiente con respecto a θ es,

=∇ ),( asQtθ Fs,a (14) Así la ecuación (12) para el caso lineal es,

[ ]tt asttttttt FasQasQ ,1 ),(),( −+=+ αθθ (15)

3.2.1.3. Métodos Locales de Aproximación de Funciones Los métodos locales de AF aproximan la función alrededor del nuevo ejemplo usando solo los vecinos de este. Cada nuevo ejemplo tendrá una nueva aproximación, por lo tanto los métodos locales de AF no memorizan los parámetros θ. Las aproximaciones se realizan recuperando de la memoria los ejemplos cercanos al nuevo estado y aproximando localmente la FV usando estos ejemplos. La técnica de AF utilizada generalmente es muy sencilla ya que se asume que la FV, que globalmente puede ser muy compleja, localmente se puede considerar con un modelo simple. Esto representa una importante ventaja con respecto a otros métodos cuando el problema considerado es complejo, como sucede en muchas aplicaciones de RL en entornos reales.

3.2.1.3.1. Aprendizaje Basado en Memoria Las técnicas de aprendizaje basado en memoria (ABM) simplemente aprenden almacenando cada ejemplo observado en memoria. Las técnicas de ABM en RL más utilizadas son k-Nearest Neighbor (k-NN) [26] y aprendizaje con regresión local pesada (LWR) [6]. Esta última es la preferida para problemas complejos en entornos reales y de muchas dimensiones, ya que consigue rápidamente una buena aproximación y funciona muy bien en aprendizaje on-line [6], [7], [35].

3.2.1.3.2. Regresión Local Pesada El método de LWR aproxima localmente un modelo de la FV utilizando los ejemplos vecinos a una nueva instancia ponderando la influencia de cada ejemplo de acuerdo a la distancia del mismo a la nueva instancia. El modelo aproximado puede ser lineal o no lineal. Generalmente se usa una aproximación lineal ya que se espera que localmente el modelo sea sencillo. En esta sección se explicará brevemente los aspectos más relevantes de LWR considerando solo el caso lineal. Para una explicación más detalla de LWR ver [6]. Sea [xi, yi] un ejemplo del conjunto de ejemplos. Se considera primero una aproximación lineal de la FV con igual influencia para todos los ejemplos recuperados de la memoria. Un modelo lineal en los parámetros θ puede expresarse como,

iTi yx =θ (16)

En la aproximación lineal a cada vector de entrada se le agrega un 1 para el factor constante en la regresión. Considerando todos los ejemplos usados en la regresión, se puede escribir la ecuación (16) de forma matricial,


11

X θ = y (17) Con la regresión lineal buscaremos encontrar un mínimo del ECM en el vector de parámetros θ,

( )∑=

−=k

ii

T yxECMi

1

2)( θθ (18)

donde k es el número de ejemplos vecinos considerados para la regresión. El valor de θ para los cuales el ECM es mínimo se consigue diferenciando la ecuación (18) con respecto a θ e igualando el resultado a 0. El valor de θ obtenido es,

θ =(XT X)-1 XT y (19) Se puede resolver esta ecuación de forma matricial o aplicar cualquier método iterativo de ajuste de pesos, con el criterio de minimizar el ECM (18). En la ecuación (18) se asigna a cada ejemplo considerado en la regresión un mismo peso. No obstante se consiguen mejores resultados si la aproximación se realiza permitiendo una mayor influencia de los ejemplos más cercanos al nuevo vector de entradas xq. Esto se consigue ponderando la influencia de cada ejemplo en el criterio del ECM con una función decreciente de la distancia de cada ejemplo al xq,

( ) ( )( )[ ]∑=

−=k

iqii

Tq xxdKyxxECM

i1

2 ,),( θθ (20)

En este caso el ECM no solo dependerá del vector de parámetros θ sino también de la posición de xq. La función K( ) se denomina comúnmente Kernel. En el caso lineal también se pueden ponderar directamente los ejemplos según su distancia a xq, usando la función kernel K( ) [6],

zi = wi xi (21) donde,

)),(( qii xxdKw = (22) y

vi = wi yi (23) En este caso, los valores del vector de parámetros θ dependerá de la ubicación del nuevo ejemplo xq,

θ(xq) =(ZT Z)-1 ZT v (24)

Función de Distancia Generalmente la función de distancia utilizada es la distancia euclidea,


12

( ) ( ) ( )qiT

qi

n

jqiqi xxxxjxjxxxd −−=−= ∑

=

2

1

)()(),( (25)

Se puede utilizar un factor de escala mj que pondera la influencia del elemento j del vector xi en el cálculo de la distancia. En forma matricial este factor de escala se coloca en una matriz diagonal M en la posición (j,j),

( ) ( ) ( )qiTT

qi

n

jqijqi xxMMxxjxjxmMxMxd −−=−= ∑

=

2

1

)()(),( (26)

Si el factor de escala es 0 para alguna dimensión del vector de entradas, entonces la influencia en la distancia al punto xq en esa dimensión será la misma para todos los ejemplos que se utilizan en la aproximación, y por lo tanto, todos los ejemplos tendrán la misma importancia a lo largo de esa dimensión. Cabe mencionar que la matriz de escala M también puede tener valores distintos de 0 fuera de la diagonal produciendo efectos de traslación y rotación en los ejes de coordenadas, lo cual puede resultar de utilidad para algunos problemas [6].

Kernel La función Kernel puede ser cualquier función decreciente de la distancia d. En general se utilizan funciones suaves de la distancia para conseguir una aproximación suave de la FV. Generalmente se utiliza como Kernel una función gaussiana de la forma,

2

)( dedK −= (27) También se puede utilizar un parámetro h, llamado parámetro de suavizado, o ancho de banda, para regular la influencia de la distancia en el Kernel,

⎟⎠⎞

⎜⎝⎛

hdK (28)

Valores pequeños de h producen un efecto de alejamiento de los ejemplos al punto xq, suavizando su efecto. También h puede tomar valores distintos para cada ejemplo xi ajustando individualmente la influencia de un punto en la aproximación.

Recuperación de Ejemplos para la Aproximación Hasta ahora mencionamos como realizar la regresión lineal utilizando un conjunto de ejemplos del espacio de ejemplos pero no mencionamos cuales ejemplos utilizar y como recuperarlos de la memoria eficientemente. Generalmente los ejemplos que se utilizarán en la aproximación quedan determinados por el ancho de banda h considerado, descartándose aquellos ejemplos con valores de peso despreciables. También se puede especificar el número k de vecinos más cercanos a xq que se quiere utilizar en la aproximación. Un estructura de almacenamiento que permite una recuperación rápida de los ejemplos vecinos a un nuevo punto xq, y un almacenamiento compacto de los mismos, es la estructura kd-tree [10], [19].


13

Kd-Tree El kd-tree es una estructura de árbol binaria para almacenar puntos de un espacio n-dimensional. Subdivide recursivamente este espacio en subregiones hiperrectangulares más pequeñas. En cada nodo se almacena los límites del hiperrectángulo que representa y los parámetros de nueva partición que se realiza dentro de este hiperrectángulo en dos nuevas subregiones (partición binaria). Las particiones se realizan siempre a lo largo de una dimensión en un punto determinado. La división binaria continúa hasta llegar a subregiones que contengan un ejemplo, o un número previamente especificado de ejemplos (buckets). En la versión optimizada del kd-tree [19] la partición se realiza a lo largo de la dimensión con valores más dispersos. Luego se considera la mediana de estos valores como el valor de partición para que cada nueva instancia tenga igual probabilidad de estar en cualquier lado de la misma.

3.2.1.3.3. LWR en Q-Learning En la aplicación de técnicas de AF usando LWR en Q-Learning cada ejemplo almacenado tiene como vector de entrada un punto en el espacio estado-acción y como salida el valor estimado de Q(s,a). Cada punto en el espacio estado acción puede ser cualquier combinación del vector de estado s y el vector de acción a. Generalmente se crea este punto concatenando ambos vectores. Con cada nuevo estado observado y para cada acción posible se predice el valor estimado de Q(s,a) haciendo LWR. Luego se ejecuta una acción según una política determinada. Generalmente se utiliza la política ε-greedy [36], que selecciona la acción con mayor valor estimado de Q con una probabilidad 1-ε, y una exploración aleatoria con probabilidad ε. Así se obtiene un nuevo estado s’. Se realiza nuevamente LWR para cada acción posible en s’ buscando el valor máximo de Q, y se aplica la técnica de Q-Learning convencional utilizando los valores mencionados para encontrar el nuevo valor de estimación de Q(s,a). El estado observado s, la acción ejecutada a, y este nuevo valor de estimación de Q(s,a) se almacenan como un nuevo ejemplo (ABM). Luego se ajustan los valores de estimación de Q para cada uno de los ejemplos utilizados en la LWR, y según la influencia que tuvieron en ella, en la dirección del nuevo valor estimado de Q(s,a) [35]. Existen algunos problemas en la aplicación de esta técnica de AF. Se deben definir muchos parámetros empíricamente, como por ejemplo el ancho de banda y el número de ejemplos considerados para la aproximación. Por otro lado, aún no existe un criterio de almacenamiento de ejemplos que evite una proliferación innecesaria de ejemplos en memoria [35].

3.2.2. Técnicas de Resolución Variable Otra manera de enfrentar el problema de la maldición de la dimensionalidad es a través de una exploración no uniforme en el espacio de estados usando una representación con pocos estados en aquellas zonas irrelevantes para el aprendizaje. Esto se consigue variando la granularidad de las regiones del espacio de estado a través de una discretización no uniforme. Las técnicas que usan una discretización no uniforme en el espacio de estados se conocen como técnicas de resolución variable [40] [28]. Sin un conocimiento previo del dominio no es posible saber cual será la granularidad más adecuada. Este problema es el que intenta resolver los métodos de resolución variable particionando dinámicamente el espacio de estados mientras encuentra al mismo tiempo una política adecuada para resolver el problema planteado [22].

3.2.2.1. Parti-Game El algoritmo Parti-Game [27] pretende encontrar una partición que le permita alcanzar el estado objetivo por un camino aceptablemente corto. Para ello particiona dinámicamente del


14

espacio de estados en hiperrectángulos (celdas) que almacena en una estructura kd-tree. Asume que tiene un controlador que le permite realizar las acciones de forma controlada y evaluar las transiciones que consigue con ellas. Utiliza la técnica minimax de la teoría de juegos para evaluar si una celda es muy ancha para evitar convergencia a comportamientos oscilatorios. Las celdas que produzcan estos problemas son particionadas. El algoritmo demostró buenos resultados en problemas concretos, pero requiere que se especifique un estado objetivo, y la tarea se define en base a este objetivo y no a una función de recompensa. También asume que tiene un controlador para ejecutar las acciones y asume un entorno determinista, lo cual difícilmente ocurre en problemas en entornos reales. Si bien posteriormente en [5] se realizó optimización del algoritmo y se propuso un esquema general para eliminar la necesidad de un controlador, todavía quedan por superar el resto de los inconvenientes.

3.2.2.2. Programación Dinámica con Resolución Variable (VRDP) El algoritmo de VRDP [28] permite aplicar algoritmos de Programación Dinámica (DP) en un entorno real con muchas dimensiones. Las particiones del especio de estados son almacenadas en una estructura kd-tree. Estas particiones son refinadas solo en las regiones potencialmente importantes para el aprendizaje. Para ello utiliza trayectorias predefinidas y evalúa la importancia de las regiones a lo largo de la misma, en base a la recompensa obtenida. La resolución en las particiones importantes del espacio de estados es incrementada subsecuentemente. El criterio de parada de la partición depende del desempeño del agente. La partición se detiene si las tres recompensas más recientes obtenidas en una celda tienen una variación de menos de un 5% con respecto a la mayor recompensa alguna vez observada en esa celda. En [29] se optimiza el algoritmo de VRDP usando en la estructura de almacenamiento una triangulación Kuhn [17] dentro del kd-tree. Además optimiza el criterio de partición a través de dos mediciones globales introducidas, la influencia y la varianza. La influencia mide como cambios en la VF de una celda influye en las VF de otras celdas. La varianza mide en cuanto cumple la celda la propiedad de Markov. Si la varianza es baja entonces se confía en que el estado cumple con la propiedad de Markov. No obstante los buenos resultados obtenidos en problemas concretos, los algoritmos de VRDP tienen dos grandes desventajas que limitan su aplicación en el mundo real. Se deben especificar trayectorias predefinidas y se debe conocer el modelo del sistema para aplicar los algoritmos de programación dinámica.

3.2.2.2.1. Técnicas de Resolución Variable Independientes del Modelo En [34] se propone un algoritmo de resolución variable utilizando una heurística similar a VRDP para el refinamiento de los estados, realizándose el mismo en aquellas áreas donde existen mayores variaciones en la FV y almacenando los estados en una estructura kd-tree. No obstante en el algoritmo de Reynolds [34] no se requiere un modelo del entorno. El proceso de partición considera dos regiones adyacentes a la vez. Si los mayores valores estimados de la FV en ambas regiones son similares entonces no se realiza la partición. También las estimaciones de la FV deben tener la suficiente confianza de que son buenas estimaciones para que la partición tenga lugar. El nivel de confianza se determina de acuerdo al número de veces que se ejecutó cada acción en la partición. Si el menor número de veces para todas las acciones supera un umbral prefijado entonces se considera que el valor estimado de la FV es una buena estimación. Luego de verificar que se cumplan los dos requerimientos citados anteriormente se realizará la partición si al ejecutar la acción con mayor valor estimado de la FV de una región en la región adyacente resulta significativamente peor que ejecutar la mejor acción de la región adyacente.


15

Una de las cuestiones abiertas de este método es encontrar un mejor criterio para calcular la confianza en la estimación de la FV.

3.2.2.3. Árboles de decisión La idea principal de usar árboles de decisión es que la misma estructura de árbol usada para diferenciar estados en la memoria, puede ser también usada para diferenciar estados basándose en la percepción de los atributos. Los árboles de decisión también pueden considerar métodos de AF ya que construyen una representación de la FV usando una estructura más compacta que los métodos tabulados convencionales. No obstante se engloban dentro de los métodos de resolución variable ya que permiten representar el espacio de estados con una resolución no uniforme. En general las técnicas de árboles de decisión en RL tienen un buen desempeño en el aprendizaje y tiene mejores condiciones de convergencia que algunas técnicas de AF como las redes neuronales.

3.2.2.3.1. U-Tree El algoritmo U-tree [25] mantiene una historia de las transiciones T entre estados. Utiliza una discretización de las variables continuas del entorno pero no constituye el espacio de estado con esta discretización sino que lo crea dinámicamente usando los valores discretos de las variables. Cada nodo del árbol representa una de éstas variables con los valores discretos que son relevantes para el problema. Cada transición T está compuesta del estado actual observado st, la acción previa ejecutada at-

1, la recompensa obtenida r, y la transición anterior Tt-1. Cada nueva transición T se coloca en una hoja del árbol de forma ordenada de acuerdo a sus componentes. Para cada hoja del árbol el algoritmo almacena los valores de Q asociados a cada acción posible y mide la utilidad de esta hoja como el mayor valor de Q entre las acciones. El algoritmo también almacena para cada hoja un estimado de la distribución de probabilidad de transición hacia las hojas adyacentes y un estimado de la media de la distribución de la recompensa inmediata para cada acción, con esto calcula el valor de Q para una acción usando la fórmula de Bellman (5) y programación dinámica. El espacio de estados se crea dinámicamente a través del agregado periódico de nuevos nodos, o nuevas ramas en los nodos ya existentes correspondientes a una nueva distinción de una dimensión. Luego verifica si este agregado mejora las capacidades de predicción del U-tree, comparando los resultados obtenidos con y sin el nuevo agregado. La comparación se realiza utilizando la prueba de comparación de hipótesis Kolmogorov-Smirnov [18]. Si la comparación resulta en una diferencia significativa en la predicción entonces el nuevo agregado se mantiene, sino se lo descarta.

U-Tree continuo El algoritmo de U-tree continuo [40] difiere del U-Tree en que no requiere de una discretización previa de las variables continuas consideradas [40]. Además puede realizar la actualización del valor de Q utilizando el algoritmo de Q-Learning, y no tiene necesidad de aplicar programación dinámica. El árbol usado en este caso es binario. Cada nodo del árbol hace una partición binaria en una dimensión. Para encontrar la mejor partición se ordenan las instancias de acuerdo a los valores de las particiones realizadas hasta el momento para una dimensión. Luego se realiza una evaluación de los resultados que se obtendrían si se considera una partición entre cada par de valores consecutivos. La evaluación se realiza a través de pruebas estadísticas de significancia sobre las predicciones que se obtienen antes y después de considerar cada partición. En [40] se proponen dos métodos para medir la significancia. Uno es el mismo que se utiliza para el


16

U-tree convencional, la prueba Kolmogorov-Smirnov, y el otro método es utilizando el error cuadrático medio (ECM).

3.2.2.3.2. Algoritmo G El algoritmo G [14] también utiliza una discretización previa de las variables y un árbol de decisión para representar de forma compacta la estimación de la FV. Pero en este caso se consideran estados con componentes binarios que solo tomarán valor 0 o 1. Comienza considerando todos los estados en un solo nodo y recursivamente particiona el espacio de estados cuando es necesario. El criterio de partición se realiza utilizando la prueba t de significancia sobre datos históricos. Evalúa la significancia sobre la diferencia de la predicción al considerar un componente (dimensión) del vector de estado como 0 o como 1. Si existe una diferencia significativa en las predicciones entonces particiona el espacio en dos en el rango que abarca el componente evaluado. En las hojas del árbol se representan cada uno de los estados, y el valor de Q para cada acción se calcula utilizando Q-Learning convencional.

Algoritmo G continuo En [33] se desarrolla una técnica que usa el algoritmo G pero sin necesidad de una discretización previa de las variables consideradas. El árbol de decisión es aprendido a lo largo de políticas predefinidas. Realiza las particiones de forma oblicua, no paralela a los ejes de las dimensiones del espacio de estados. Particiones oblicuas forman árboles de decisión más pequeños permitiendo a cada nodo almacenar más de una característica de la entrada. Se obtienen resultados similares a los del algoritmo G convencional pero con una representación más compacta de los estados.

3.2.3. Generalización en el Espacio de Acciones La mayoría de las técnicas de generalización mencionadas utiliza un conjunto de acciones discretas. No obstante existen problemas en los que considerar las acciones como discretas puede resultar un inconveniente. Por ejemplo, en los casos donde las posibles acciones son combinaciones de acciones elementales es importante generalizar para evitar mantener valores de estimación separados para todas las posibles combinaciones de acciones elementales. No existen muchas técnicas de generalización en el espacio de acciones y sigue siendo un área abierta de investigación [35]. No obstante se han desarrollado algunas técnicas de generalización considerando un espacio de acciones continuo. En [8] se desarrolló una red neuronal que considera la acción como una dimensión continua que se agrega al conjunto de entrada y usa un método de gradiente ascendente hasta encontrar un máximo local de la FV estimada. En [21] se desarrollo un algoritmo que también utiliza una red neuronal para espacios de acciones continuos de muchas dimensiones en entornos estocásticos. El algoritmo considera una distribución normal de probabilidades inicial en el espacio de las acciones y ejecuta acciones a partir de esta probabilidad. Luego ajusta la media de esta distribución en la dirección donde se obtuvieron mejores resultados concentrando la mayor probabilidad en la zona donde se encuentra la acción que maximiza la estimación de la FV.

3.3. APRENDIZAJE EN ENTORNOS CATEGORIZABLES El aprendizaje en entornos categorizables trata de solucionar el problema de la maldición de la dimensionalidad aprovechando un tipo de generalización del entorno que denomina categorizabilidad. Categorizabilidad significa que de todas las características del entorno que son relevantes para predecir el valor de recompensa acumulada en cualquier situación, solo un reducido número de ellas será relevante para predecir este valor en una situación particular.


17

Este tipo de generalización no se aprovecha con las técnicas de generalización descriptas anteriormente ya que dos estados iguales, o grupos de características iguales, se consideran por separado si el valor de estimación de la recompensa acumulada es diferente para al menos una acción [31].

3.3.1. Descripción del Algoritmo En esta sección resumiremos los aspectos fundamentales del algoritmo de aprendizaje en entornos categorizables (algoritmo CL). Para una explicación más detallada del funcionamiento del algoritmo ver [31]. Se asume que el mundo se percibe por un número n de detectores binarios de características fi, i=1...n. Se define una visión parcial v de orden m, v(fi1,…, fim), como un detector virtual que se activa cuando sus m detectores de características que lo componen están simultáneamente activos. Para cada visión parcial v y para cada acción a ejecutable cuando v está activa, asociamos tres valores:

• qv(a) valor estimado de recompensa acumulada. • ev(a) error absoluto promedio de la estimación de recompensa acumulada qv(a). Con

los valores de qv(a) y ev(a) se define un intervalo de confianza Iv(a)=[qv(a) - 2 ev(a), qv(a) + 2 ev(a)].

• iv(a) índice de confianza. Contabiliza el número de veces que la acción a se ha ejecutado cuando v estaba activa con un valor de predicción qv(a) cercano al valor observado q(v,a) de recompensa acumulada. Este índice se utiliza para calcular el valor de confianza en la estimación qv(a). La confianza de la estimación se calcula utilizando una función monotónica creciente de iv(a), que toma valores entre 0 y un valor de saturación β<1 definido por el usuario,

cv(a) = minβ, function_confianza(iv(a)) (29)

El valor del índice de confianza para el cual la función de confianza alcanza el parámetro β se controla por otro parámetro definido por el usuario η.

El proceso de categorización comienza considerando solamente detectores de características de orden 1, y progresivamente se combinarán para dar origen a nuevos detectores de orden mayor de acuerdo a los requerimientos del aprendizaje.

3.3.1.1.1. Selección de acción En cada situación se tiene un conjunto de visiones parciales activas. Cada acción posible tiene asociada tres valores relacionados a la estimación de la recompensa acumulada. Por lo tanto, para la selección de la acción a ejecutar se deberá tener en cuenta estos valores. Con este fin se define un nuevo parámetro, la relevancia de una visión parcial v para la acción a,

)(11)(

aea

vv +

=ρ (30)

Se utiliza esta relevancia como un indicador de la precisión de la estimación del valor de q de la visión parcial v para la acción a. Este parámetro tomará valores en el intervalo (0,1]. Además de la relevancia se desea predecir el valor de q con una estimación confiable, es decir con valor de confianza cv(a) alto. Así, el criterio para seleccionar la visión parcial que se utilizará para estimar el valor de q al ejecutar la acción a será,


18

)()(maxarg),( acaaVganadoraw vvVv⋅==

∈∀ρ (31)

donde V es el conjunto de visiones parciales activas y w es la visión parcial utilizada para la predicción. Para obtener el valor de predicción de q se tienen en cuenta dos fuentes de incertidumbre. La primera está relacionada a la precisión en la estimación y dependerá del ev(a). Se obtiene un valor de predicción en el intervalo de confianza Iv(a) según una distribución uniforme,

i_guess(a) = rand(qw(a) - 2 ew(a), qw(a) + 2 ew(a)) (32) La segunda fuente de incertidumbre está relacionada al nivel de confianza que se tiene en la estimación, cv(a). Se utiliza un término de ruido que afectará al valor de predicción en mayor medida a aquellas predicciones realizadas en base a estimaciones de poca confianza. El valor de ruido se obtiene de acuerdo a una distribución uniforme en el intervalo determinado por los valores mínimos y máximos de q alguna vez observados,

guess(a) = cw(a) i_guess(a) + (1- cw(a) ) rand(qmin, qmax) (33) Luego, la acción seleccionada para su ejecución es aquella con mayor valor de predicción. Este método de selección de acción intenta establecer un balance entre exploración y explotación de acuerdo a las propiedades de la estimación. Las acciones con estimaciones de baja confianza siempre tendrán una oportunidad de ejecutarse aún con valores bajos en la estimación de q, mientras que cuando la confianza en el valor estimado de q es alta la exploración es menor.

3.3.1.1.2. Actualización Estadística Con la ejecución de la acción seleccionada se obtiene una recompensa r, y se realiza la transición a una nueva situación donde se activan un nuevo conjunto de visiones parciales V’. El valor obtenido de recompensa acumulada se calcula usando una modificación de la fórmula de Bellman,

),'(|)(max. aVganadoravaqrq va=+=

∀γ (34)

Este valor se utiliza para actualizar los valores estadísticos de estimación para la acción ejecutada en cada una de las visiones parciales de V. Para la actualización se utiliza como coeficiente de aprendizaje el valor (1-cv(a)). Esto permite un ajuste más rápido en aquellas visiones parciales con estimaciones de baja confianza.

qv(a) = cv(a) qv(a) + (1- cv(a) ) q (35)

ev(a) = cv(a) ev(a) + (1- cv(a) ) |q-qv(a)|

Finalmente, el índice de confianza iv(a) se incrementa en uno si el valor obtenido de q está dentro del intervalo de confianza Iv(a) y se disminuye en uno en el caso contrario.

3.3.1.1.3. Gestión de Visiones Parciales Si la predicción realizada difiere del valor obtenido q en una cantidad δ, entonces se generan τ nuevas visiones parciales con el objetivo de mejorar la predicción.


19

Las nuevas visiones parciales se crean combinando dos existentes. Se seleccionan dos visiones parciales de V de acuerdo a una distribución de probabilidad que favorece la selección de visiones parciales con mayor confianza cv(a) y mayor valor estimado de recompensa qv(a). Para evitar una indeseada proliferación de visiones parciales se limita el número de las mismas en un valor μ. Este valor se establece de acuerdo al nivel de categorización que se desea alcanzar. Si se alcanza este valor y la predicción de q sigue siendo mala entonces será necesario eliminar visiones parciales existentes para generar nuevas. Se utilizan dos criterios de eliminación de visiones parciales: criterio de redundancia y criterio del error de creación.

Redundancia Una visión parcial se considera redundante cuando la estimación del valor esperado de recompensa acumulada para todas las acciones es similar a la estimación de alguna de las visiones parciales, v1 o v2, que la originaron. Las estimaciones realizadas se compararan midiendo la superposición de los intervalos de confianza a través de una función de similaridad,

)(,)(max)()(

))(),(('

'' aIaI

aIaIaIaIsim

vv

vvvv

∩= (36)

Así, la redundancia de una visión parcial v es,

))(),(()),(),((maxmin)(21

aIaIsimaIaIsimvaredundanci vvvva∀= (37)

Las visiones parciales con redundancia mayor a un valor λ son eliminadas.

Error de Creación Cada vez que una visión parcial se genera, se almacena con ella el error absoluto de predicción del valor de q. Una mala predicción se produce cuando la categorización del entorno no es buena, haciendo que el error de predicción sea alto. Por esto, se considera que el error de predicción es un indicador de la necesidad de mejorar la categorización. Si el error de predicción cuando se genera una visión parcial es grande entonces la necesidad de mejorar la categorización también lo es, y por lo tanto la visión parcial creada resulta más útil al sistema. Por el contrario si este error es menor, entonces la necesidad de mejorar la categorización es menor, y la utilidad de la visión parcial es más baja. Se eliminan así las τ visiones parciales con menor error de creación, siempre que este error no sea mayor al error de predicción de la situación actual.

Proyecto de Tesis TRABAJO PREVIO

20

4. Trabajo Previo El objetivo del proyecto es utilizar categorización de entornos para desarrollar un método eficiente de aprendizaje en dominios continuos complejos. Es fundamental disponer de una técnica capaz de realizar categorización de forma eficiente en dominios complejos para luego volcarnos al aprendizaje en dominios continuos. El concepto de categorización de entornos se planteó por primera vez en [31]. Es ahí donde nace la primera técnica que procura utilizar la categorización de entornos para el aprendizaje, el algoritmo CL. Si bien el planteo original del algoritmo refleja los conceptos de la categorización, el mismo carece de un sustento teórico matemático adecuado. En [32] se enumeran algunos aspectos que se deberían considerar como trabajos futuros sobre el algoritmo CL. Entre ellos figura la necesidad de mejorar las técnicas para medir la confianza que se tiene en la estimación de q, la necesidad de reducir el número de parámetros de aprendizaje que debe predefinir el usuario, y la necesidad de una formulación teórica matemática de los conceptos que utiliza el algoritmo. El trabajo previo realizado consistió entonces en superar estos inconvenientes para mejorar la técnica de aprendizaje en entornos categorizables. La secuencia de trabajos realizado fue la siguiente. Nuestro primer experimento fue verificar si realmente el aprendizaje con categorización era posible y si el algoritmo CL era capaz de categorizar el entorno y aprovechar esta categorización en el aprendizaje [1], [2]. Posteriormente se aplicó el algoritmo CL al problema de control de un motor de corriente continua [3], [4] y luego al control de un manipulador con carga variable y de alta inercia para verificar su desempeño en problemas más complejos, de dominio continuo y de varias dimensiones. Se identificaron inconvenientes en el aprendizaje que reflejaban la necesidad de una formalización teórica matemática. De esta manera nuestro siguiente paso fue replantear el algoritmo usando una formalización matemática de los conceptos utilizados para el aprendizaje y la categorización. Con este nuevo replanteo teórico del algoritmo se solucionaron en gran medida los problemas citados en [32].

4.1. EVALUACIÓN DEL ALGORITMO CL Para evaluar la capacidad de categorización del algoritmo utilizamos un problema en el cual resulte sencillo evaluar la categorización conseguida con el algoritmo, y como se utiliza la misma para el aprendizaje. Un problema que cumple con estos requerimientos es el tres en línea, conocido también como TIC-TAC-TOE. Solo se describirán brevemente los resultados obtenidos. Para un mayor detalle de los experimentos realizados ver [1]. En la figura 2 se observan dos situaciones del juego en las que el jugador que utiliza la ficha X podrá ganar la partida si tiene en cuenta las celdas marcadas en gris para decidir su jugada. En ambos casos la acción ganadora consiste en colocar una X en la celda inferior derecha. En este caso la hipótesis de categorización se cumple en ambas situaciones ya que solo existe un número reducido de características relevantes, y las características son las mismas para dos situaciones diferentes desde el punto de vista de los estados pero iguales desde el punto de vista de la categorización.

X O O X

O X X O

X O Figura 2. Ejemplo de categorización para dos partidas diferentes

del Tres en Línea.


21

Para la aplicación del algoritmo CL para el juego del Tres en Línea se utilizó una recompensa de 100 para una partida ganada, -100 para una perdida y 50 para un empate. Se utilizó un oponente con política de juego fija, entrenado previamente utilizando la técnica de TD con actualización de valores de estado [36]. Los parámetros del algoritmo CL utilizados para el aprendizaje fueron, β=0.99, η=50, δ= 50, λ=0.90, μ=500, γ=0.90 y τ=3. Los primeros experimentos revelaron problemas en la convergencia del aprendizaje. Estos problemas estaban relacionados a los criterios de eliminación de las visiones parciales que utilizaba el algoritmo CL. El criterio de Error de Creación no era un buen indicador de la utilidad de una visión parcial ya que no contemplaba que esta utilidad cambie con la evolución del aprendizaje. Debido a esto se eliminaban visiones parciales útiles para el sistema provocando inestabilidades en la convergencia de la recompensa. Así, se creo un nuevo criterio para medir la utilidad de una visión parcial basado en sus valores estadísticos de estimación. Si el error absoluto promedio de predicción era grande para cada acción y las confianzas correspondientes también lo eran entonces la visión parcial se consideraba poco útil para el sistema y podía eliminarse. Con este criterio, el cálculo de la utilidad se realizaba de la siguiente manera,

⎭⎬⎫

⎩⎨⎧

=∀ )(

)(max)(

aca

vuv

v

a

ρ (38)

Con este nuevo criterio se solucionó los problemas de convergencia del aprendizaje. Por otro lado, analizando las visiones parciales generadas observamos que existían visiones parciales redundantes con otras visiones parciales distintas de sus progenitoras. Se calculó entonces la redundancia de una visión parcial v con respecto a todas las visiones parciales cuyas características constituían un subgrupo de las características de v,

))(),((maxmin)( ''

aIaIsimvaredundanci vvvva ⊂∀∀= (39)

4.1.1. Resultados En la figura 3 se presentan tres de las visiones parciales generadas por el algoritmo CL junto con los valores estadísticos de la estimación asociados a cada acción.

a) b) c) - - -

- X X

- - -

- - -

- X -

X - -

- O -

- O -

- - -

a qv(a) ev(a) iv(a) (1,1) 52,8 7,9 50 (1,2) 49,6 0,4 20 (1,3) 89,2 8,4 50 (2,1) 100,0 0,0 50 (2,2) - - - (2,3) - - - (3,1) 84,3 19,3 50 (3,2) 47,9 13,1 50 (3,3) 75,7 27,5 50

a qv(a) ev(a) iv(a) (1,1) 75,7 41,9 50 (1,2) 61,2 25,5 50 (1,3) 100,0 0,0 50 (2,1) 78,3 24,3 49 (2,2) - - - (2,3) 24,7 69,9 50 (3,1) - - - (3,2) 11,9 50,6 50 (3,3) 71,6 15,5 49

a qv(a) ev(a) iv(a) (1,1) -100 0,0 21 (1,2) - - - (1,3) -100 0,0 16 (2,1) -100 0,0 48 (2,2) - - - (2,3) -100 0,0 25 (3,1) -100 0,0 50 (3,2) 56,6 22,7 50 (3,3) -100 0,0 30

Figura 3. Ejemplo de tres visiones parciales generadas por el algoritmo CL para el juego de Tres en Línea, junto con los valores estadísticos de la estimación de cada acción.


22

Observamos que tanto en a) como en b) las acciones cuyos valores estadísticos de estimación eran mejores son las acciones que ganan el juego. Por otro lado de c) se observa que la única acción que posee una recompensa acumulada positiva es la que evita perder la partida. Por otro lado, en la figura 4 se muestran dos partidas completas en donde se marca con gris la visión parcial activa en cada situación. La estructura de las visiones parciales se corresponden con la política de juego del oponente usado para el entrenamiento, y el algoritmo descubre cuales son las características relevantes para tener una victoria final. Como se puede observar las dos situaciones finales son diferentes desde el punto de vista de los estados pero iguales para la misma visión parcial ganadora.

a)

O O O O O O X O O

X X X O X X O X X O X X O X X

X X X

b)

O O X O X O X O X X O X

O X O X O X O

X X X X O X O X Figura 4. Dos partidas completas entre el oponente y el algoritmo CL luego del entrenamiento.

Finalmente se evaluó el aprendizaje del algoritmo CL comparando los resultados con aquellos obtenidos por el Q-Learning bajo el mismo número de iteraciones de entrenamiento. El algoritmo CL ganó el 100% de las partidas de prueba realizadas contra el 85% de victorias conseguidas con el Q-learning. Por otro lado el Q-learning necesitó memorizar 6000 estados para el aprendizaje mientras que el algoritmo CL solo memorizó 500 visiones parciales.

4.2. CONTROL DE MOTOR CON EL ALGORITMO CL Luego de verificar que el algoritmo CL podía categorizar entornos discretos sencillos y realizar un aprendizaje eficiente en ellos, se planteó como siguiente problema una aplicación más compleja y en un entorno continuo. Para ello se seleccionó el problema de control de seguimiento de trayectoria de un motor de corriente continua bajo los requerimientos de un actuador rotacional de una articulación en un robot caminante [3]. Se utilizaron en este problema los modelos de dos motores de diferente potencia y se les aplicó el mismo planteo del algoritmo para evaluar la capacidad del algoritmo de adaptarse a las variaciones de los parámetros. Para evaluar el desempeño del algoritmo se compararon los resultados obtenidos con el control realizado por un sistema de control de procesos convencional aunque muy robusto, el control proporcional-integral-derivativo (PID) [30] especialmente sintonizado para cada caso. También se evaluó el desempeño del algoritmo en el control del motor cuando existen perturbaciones externas y cuando se considera una inercia de carga mayor.

4.2.1. Modelado del motor Se modelaron dos motores de corriente continua que se usan en aplicaciones robóticas, el Maxon 118800 de 70 (Watt) de potencia y el Maxon 118769 de 18 (Watt) [24]. Los modelos se realizaron de acuerdo a las especificaciones del manual [24] que considera el momento de fricción como un valor constante independiente de la velocidad. También se considera despreciable la inductancia del rotor. Las ecuaciones del modelo son,

DMRR MiKMsignJ −=+ ).(θθ (40)

θMKVRi −=


23

donde V (volts) es el voltaje de entrada y θ (rad) es la posición angular del eje del motor. La tabla 1 muestra los valores utilizados para ambos modelos,

Tabla 1. Valores de parámetros de los modelos

Parámetro Modelo 118800 118769

JR (kg.m2) inercia del rotor 65 E-4 10.8 E-4 MR (mNm) momento de fricción 3.98 1.082 KM (mNm/A) constante del rotor 56 21.3 R (Ω) resistencia en los terminales 2,75 2.27 Momento de frendado (mNm) 865 226

La simulación de la dinámica del motor se realizó utilizando el siguiente sistema de ecuaciones,

dtttdtt .θθθ +=+ (41)

2.21. dtdtttdtt θθθθ ++=+

donde el diferencial de tiempo considerado es de 1 milisegundo. Este valor es suficientemente pequeño para obtener buenos resultados en la simulación de acuerdo a las constantes de tiempo del sistema [24].

4.2.2. Generación de Trayectorias de Referencia Para el entrenamiento se generaron trayectorias de referencia compuestas por subtrayectorias con un perfil de velocidades con valor constante para la aceleración y deceleración calculado de la siguiente manera [16],

2

)(5t

if θθθ

−= (42)

donde θi y θf son las posiciones angulares iniciales y finales de la subtrayectoria y t es la duración de la misma. Las subtrayectorias fueron generadas al azar con valores de duración y posición final seleccionados aleatoriamente dentro de los intervalos [2,5] (seg) y [-100π, 100π] (rad) respectivamente. Cada trayectoria de referencia se formaba uniendo el final de una subtrayectoria con el comienzo de la otra.

4.2.3. Formulación del Problema para el Algoritmo CL Las características del entorno consideradas para el aprendizaje son: la velocidad y aceleración angular, la diferencia entre la posición angular actual del motor y la siguiente de la trayectoria, y la diferencia entre la velocidad angular actual del motor y la siguiente de la trayectoria. Para lograr mayor resolución en el espacio de estados en aquellas zonas cercanas a los estados objetivos, las características que representan la diferencia de valores con respecto a la trayectoria de referencia se discretizaron utilizando escala logarítmica. De esta manera a medida que esta diferencia tiende a cero aumenta la resolución de las características relacionadas. Para disminuir el tiempo de convergencia y evitar una exploración excesiva al comienzo del aprendizaje se utilizó otra característica de diferencia de posición con respecto a


24

la trayectoria pero con intervalos de discretización mayores. La Tabla 2 enumera las características mencionadas y los intervalos de discretización considerados. Cabe mencionar que el número de segmentos considerados en la discretización está definido para evitar acentuar el efecto de la maldición de la dimensionalidad.

Tabla 2. características consideradas para el control de motor

feature Min Max no seg

Escala log

Velocidad angular (rad/s) -1000 1000 40 No Aceleración angular (rad/s2) -200 200 40 No Δ posición trayectoria (rad) -800π 800π 40 Si Δ posición trayectoria (rad) -80π 80π 8 Si

Δ velocidad trayectoria (rad/s) -1000 1000 40 Si Las acciones usadas para la tarea de control son los voltajes aplicados al motor y el rango de las mismas se determinó de acuerdo a los voltajes nominales. Así, se utilizaron 16 segmentos discretos para las acciones en un rango de [-48..48] (volt) para el motor 118800 y en un rango de [-30..30] (volt) para el motor 118769. El período de muestreo para los valores de los detectores se estableció de acuerdo al teorema de Nyquist [30] que establece una frecuencia de muestreo superior al doble de la componente de mayor frecuencia de la señal muestreada. En este caso y de acuerdo a las características de las trayectorias de referencia generadas, la frecuencia máxima de las trayectorias de referencia es de aproximadamente 5 Hz. La frecuencia de muestreo debe ser por lo menos de 10 [Hz] por lo que se consideró una frecuencia de muestreo de 20 (Hz), lo que corresponde a un período de 50 (ms) para lectura de sensores y para la ejecución de las acciones. La función de confianza que se utilizó era lineal con respecto al índice de confianza y los parámetros de aprendizaje del algoritmo fueron: η=20, β=0.95, δ=50, γ=0.5, λ=0.9 and μ=500.

4.2.4. Función de recompensa La función de recompensa utilizada es el negativo de la distancia angular en valor absoluto del motor con respecto a la trayectoria:

)()()( tttr TYM θθ −−= (43) donde, θTY es la posición angular de la trayectoria y θM es la posición angular del motor.

4.2.5. Nuevos Cambios del Algoritmo En el problema de dominio continuo seleccionado aparecieron nuevos inconvenientes. El primero de ellos está relacionado a la gran cantidad de prueba empíricas que se debe realizar para ajustar para la función de confianza, el valor de η y el valor de β. Tuvimos muchas dificultades para encontrar un conjunto de estos valores que brinde resultados aceptables. Otro problema detectado con esta nueva aplicación es en el cálculo de la relevancia. La ecuación (30) converge asintóticamente a cero con el aumento del error absoluto promedio. La relevancia para valores medianamente grandes de este error presenta pocas variaciones. Los errores alcanzados con la función de recompensa considerada hacen que la relevancia según (30) presente pocas diferencias entre las visiones parciales. Por este motivo, y ya que la relevancia se utiliza para comparar solo las visiones parciales activas se consideró una


25

relevancia relativa para cada grupo de visiones parciales activa obtenida de la siguiente manera,

1)()(

)()()(maxmin

min +−−

=aeae

aeaea vvρ (44)

donde emin(a) y emax(a) son los errores absolutos promedios mínimo y máximo para la acción a en todas las visiones parciales activas. Con esta nueva relevancia mejoraron los resultados pero también se podría haber utilizado otras funciones para calcularla sin un criterio claro para saber cual es la función apropiada. Otra vez quedaba en evidencia la falta de una formulación teórica. Finalmente, otro ajuste fue necesario relacionado al índice de confianza iv(a). Anteriormente cuando el valor observado q caía fuera de Iv(a) el índice de confianza se disminuía en 1 sin tener en cuenta la confianza la visión parcial. En realidad se espera que la predicción de las visiones parciales de mayor confianza sea mucho mejor que las de menor confianza. El decremento de iv(a) se hizo proporcional a su valor.

4.2.6. Control PID Para comparar y evaluar los resultados obtenidos con el algoritmo de aprendizaje se implementó un control PID y sus ganancias proporcionales Kd, tiempos integrales Ti y tiempo derivativos Td se sintonizaron para cada motor utilizando el segundo método de la regla de Ziegler-Nichols [30]. En la tabla 3 se muestran los valores sintonizados.

Tabla 3. valores sintonizados para los controles PID Modelo Kcr Tcr Kp Td Ti 118800 3 2Δt 0.5Kcr 0.05Tcr Tcr 118769 0.97 2Δt 0.6Kcr 0.01Tcr Tcr

Se utilizaron los mismos valores discretos de voltajes como salidas del sistema de control y el período de muestreo también fue de Δt =50 (ms).

4.2.7. Resultados Los resultados del aprendizaje con el algoritmo CL se evaluaron sobre una trayectoria compuesta de 5 subtrayectorias generadas al azar. En la figura 5 se presentan los resultados de control del motor 118800 para el algoritmo CL luego de 25000 iteraciones de entrenamiento y para el control PID sintonizado. En ambos casos se muestra el error cuadrático de control.


26

0 2 4 6 8 10 12 14 16 18 20

-250

-200

-150

-100

-50

0

50

100

150

200

250

Trayectoria de Referencia

tiempo [s]

posicion

ang

ular [r

ad]

-250

-200

-150

-100

-50

0

50

100

150

200

250

posicion

ang

ular

[rad

]

Control con PID

ECM = 6.83

0 2 4 6 8 10 12 14 16 18 20-10

0

10

tiempo [s]

Erro

r [ra

d]

-250

-200

-150

-100

-50

0

50

100

150

200

250

posicion

ang

ular [r

ad]

Control con algoritmo CL

ECM = 10.98

0 2 4 6 8 10 12 14 16 18 20-10

0

10

tiempo [s]

Erro

r [rad]

Figura 5. Resultados de control del motor 118800 para el algoritmo CL luego de 25000 iteraciones y para el control PID sintonizado.

Por otro lado en la figura 6 se presentan los resultados de control sobre el motor 118769. En la primera gráfica se muestra los resultados del control PID del motor 118769 utilizando los parámetros sintonizados para el 118800. Con esta gráfica se quiere destacar la capacidad del algoritmo CL de adaptarse a los cambios de parámetros del sistema ya que no fue necesaria ninguna reformulación del algoritmo para el entrenamiento con el motor 118769, mientras que con el PID fue necesaria una resintonización.


27

0 2 4 6 8 10 12 14 16 18 20

-250

-200

-150

-100

-50

0

50

100

150

200

250

time (s)

angu

lar p

osition

[rad]

Control PID del motor 118769 con los parametros sintonizados para el motor 118800

-250

-200

-150

-100

-50

0

50

100

150

200

250

time (s)

posicion

ang

ular [r

ad]

Control PID sintonizado del motor 118769

ECM = 8.03

0 2 4 6 8 10 12 14 16 18 20-10

0

10

tiempo [s]

Erro

r [rad]

-250

-200

-150

-100

-50

0

50

100

150

200

250

posicion

ang

ular [r

ad]

Control del motor 118769 con el algoritmo CL

ECM = 6.51

0 2 4 6 8 10 12 14 16 18 20-10

0

10

tiempo [s]

Erro

r [rad]

Figura 6. Resultados de control del motor 118769 para el algoritmo CL luego de 25000 iteraciones y para el control PID antes y después de la resintonización.

Como puede observarse de las gráficas los resultados son buenos considerando que el algoritmo CL tiene el mismo desempeño que un control PID sintonizado. No obstante, cabe mencionar que periódicamente la trayectoria del motor se alejaba levemente de la trayectoria de referencia para volver a converger mas tarde. Esto se producía por que durante estos alejamientos ganaban visiones parciales que no eran las más adecuadas para predecir el resultado de ejecutar una acción. Con respecto a la categorización conseguida, la poca inercia del sistema y la falta de perturbaciones externas hacían que las características de aceleración y velocidad angular sean irrelevantes para determinar la acción a ejecutar dada la elevada velocidad de respuesta del sistema. Se observó que en general ganaban las visiones parciales de orden 1 con la diferencia


28

de posición como característica. Por otro lado se generaron muchas visiones parciales que no se utilizaron en ningún momento para la predicción. No obstante los buenos resultados obtenidos, sospechábamos que los problemas que se pusieron de manifiesto en esta aplicación sencilla podrían volverse mucho más evidentes en un sistema más complejo, e incluso se podrían detectar nuevos problemas. Por esto aplicamos el algoritmo a un problema de control de un manipulador con carga de perturbación y una inercia de carga de gran magnitud.

4.3. CONTROL DE UN MANIPULADOR CON EL ALGORITMO CL Para el aprendizaje de la tarea de control de un manipulador se desarrolló un modelo de manipulador que utiliza el motor Maxon 118800 como actuador. En este caso se utilizó un planteo similar al realizado para la tarea de control del motor con algunas diferencias que mencionaremos oportunamente. También se sintonizó un control PID para la comparación de los resultados obtenidos.

4.3.1. Modelo del Manipulador Para la tarea de control se implementó un modelo de un manipulador de una sola articulación con el motor Maxon 118800 como actuador rotacional. Toda la masa se considera ubicada en el extremo distal del brazo. La figura 7 muestra un esquema del manipulador.

Figura 7. Manipulador Las ecuaciones del modelo son,

iKmlGsignnMmlJn MRR =+++ )cos()()( 22 θθθ (45)

θMnKVRi −= donde V es el voltaje de entrada y θ es la posición angular en radianes. La tabla 4 enumera los parámetros del modelo y los valores considerados.

Tabla 4. Parámetros del modelo del manipulador

Parámetro Valor JR (g.m2) inercia del rotor 65 E-4 MR (mNm) momento de fricción 3.98 KM (mNm/A) constante de momento 56 R (Ω) resistencia en las terminales del motor 2,75 m masa del manipulador (g) 1E4 l longitud del brazo (m) 0,5 G constante de gravedad (m / s2) 9,8 n relación de reducción 100 Momento de Frenado (mNm) 864

Gl

τ θ

m

M n=100


29

El cálculo de la masa y la longitud del manipulador de modo que la perturbación de carga variable producida por la componente de la gravedad tenga como valor máximo un valor similar al momento máximo que puede realizar el motor (momento de frenado). La simulación se realizó considerando los mismos intervalos de tiempo y las mismas ecuaciones de la dinámica. Las trayectorias se generaron de igual manera que en el caso del control pero considerando es espacio de trabajo del manipulador.

4.3.2. Formulación del Problema para el Algoritmo CL Las características utilizadas para la creación de visiones parciales fueron el coseno de la posición angular, la aceleración angular, la diferencia de posición angular del manipulador y del la trayectoria de referencia, la diferencia de velocidades del manipulador y de la trayectoria de referencia. La tabla 5 muestra los rangos considerados en este problema.

Tabla 5. características consideradas para el control de motor

Feature Min Max no seg

Escala log

cos(θ) -1 1 12 No Aceleración angular (rad/s2) -20 20 40 No Δ posición trayectoria (rad) -0.125π 0.125π 40 Si Δ posición trayectoria (rad) -π/2 π/2 40 Si

Δ velocidad trayectoria (rad/s) -5 5 40 Si Los parámetros de aprendizaje del algoritmo fueron: η=20, β=0.95, δ=0.2, γ=0.7, λ=0.9 and μ=1500.

4.3.3. Resultados La figura 8 muestra los resultados obtenidos luego de 150000 iteraciones. La mayor complejidad del sistema y una velocidad de respuesta mucho menor que en el caso anterior hacía que la exploración necesaria para que los valores estadísticos del aprendizaje sean confiables aumentara considerablemente, haciéndose evidente el problema de la maldición de la dimensionalidad. Para disminuir este efecto disminuimos los números de segmentos en la discretización pero a costa de empeorar la predicción de la recompensa acumulada.


30

0 2 4 6 8 10 12

-1.5

-1

-0.5

0

0.5

1

1.5


tiempo [s]

posicion angular [rad]

-1.5

-1

-0.5

0

0.5

1

1.5

posicion

ang

ular [rad

]

Control con PID

ECM = 0.016

0 2 4 6 8 10 12-0.5

0

0.5

tiempo [s]

Error [rad]

-1.5

-1

-0.5

0

0.5

1

1.5

posicion

ang

ular [r

ad]


ECM = 0.089

0 2 4 6 8 10 12-0.5

0

0.5

tiempo [s]

Error [

rad]

Figura 8. Resultados de control del manipulador para el algoritmo CL luego de 150000 iteraciones y para el control PID sintonizado.

Analizando las visiones parciales generadas nos encontramos con visiones parciales que contenían características redundantes como por ejemplo las diferencias de posición angular de alta resolución y de baja resolución al mismo tiempo. Fueron necesarias muchas pruebas empíricas para determinar un conjunto de parámetros que brinden los mejores resultados posibles. Sin embargo, como se observa en la figura, el algoritmo no estaba realizando el aprendizaje adecuadamente.

4.4. NUEVA FORMULACIÓN MATEMÁTICA DEL ALGORITMO Los experimentos realizados anteriormente pusieron de manifiesto la necesidad de una formalización matemática del algoritmo. Por ejemplo solo para determinar la confianza que tendrá una visión parcial para una acción determinada, es necesario definir empíricamente tres componentes: la función de confianza, el η y el β. Además existen muchos otros elementos que utiliza el algoritmo que carecen de un fundamento teórico claro. Por ejemplo, la función de relevancia definida arbitrariamente, un intervalo de confianza definido intuitivamente sin


31

establecer el porcentaje de confianza que tendremos en que el verdadero valor de recompensa acumulada esté dentro del mismo. Todos estos aspectos ya fueron contemplados en [32]. Era evidente que si deseábamos utilizar el algoritmo CL para aplicaciones en problemas complejos reales, tal como se plantea en el objetivo del proyecto, necesitábamos realizar una formalización teórica que respalde cada uno de los conceptos que intuitivamente se usan en el algoritmo. Esta formalización se realizó teniendo en cuenta que tanto en el aprendizaje por refuerzo en general como en el aprendizaje en entornos cotegorizables en particular, se desea obtener una buena estimación del valor esperado de la recompensa acumulada en base a observaciones en una experimentación. Las herramientas que se aplican para evaluar las estimaciones realizadas en base a observaciones de una experimentación son las herramientas de Probabilidad e Inferencia Estadística [18].

4.4.1. Inferencia Estadística Un problema de inferencia estadística consiste en analizar datos que han sido generados de acuerdo a una distribución de probabilidad desconocida y hacer algún tipo de inferencia acerca de esta distribución. Podemos querer inferir cual es la forma general de la misma, cual es su valor medio, cual es su mediana, o cualquier otro parámetro que nos brinde alguna información que la caracterice. Se resumirán en esta sección los conceptos fundamentales de inferencia estadística que aplicaremos luego en el algoritmo CL para su formulación matemática. Para una explicación teórica más detallado ver [11], [18].

4.4.1.1. Estimación Para inferir el valor de un parámetro desconocido de una distribución de probabilidad se usa un estimador del parámetro, el cual es una función que utiliza como argumento los datos generados de acuerdo a esta distribución de probabilidad, y que da como resultado un valor estimado de este parámetro. El conjunto que contiene todos los valores posibles del parámetro a estimar se denomina espacio muestral del experimento. Cualquier función con valores reales definida en este espacio es una variable aleatoria. Si tenemos una distribución de probabilidad f, se dice que n variables aleatorias X1,…,Xn constituyen una muestra aleatoria de esta distribución si éstas variables son independientes y con idéntica distribución de probabilidad f. El valor de n se denomina tamaño muestral. Es deseable que la estimación de un estimador cambie con el valor del parámetro a estimar de manera que la distribución de probabilidad de este estimador siempre esté concentrada alrededor del verdadero valor del parámetro. Un estimador que cumple con esta propiedad es un estimador insesgado. Existen diferentes tipos de estimadores que se pueden utilizar dependiendo del tipo de estimación que se desea realizar y de la información que se tiene acerca de la distribución. Algunos estimadores se aplican para estimar el valor de un parámetro desconocido de una distribución con forma conocida. Otros estiman el valor de un parámetro desconocido pero de distribuciones cuya forma general también es desconocida. De este último caso, el estimador más utilizado es el estimador máximo verosímil (EMV). Un EMV es el valor para el parámetro estimado que maximiza la probabilidad de obtener los datos observados en la muestra aleatoria. Por ejemplo, dada una distribución con media μ desconocida y varianza σ2 desconocida, sus EMVs son la media y la varianza muestral [18],

∑=n

i nXX1

/ y ∑ −=n

i XXn 1

22 )(1σ (46)


32

respectivamente. Sin embargo, a pesar de que la media muestral X es un estimador insesgado de μ, la varianza muestral 2σ no es un estimador insesgado de σ2. Se puede demostrar [18] que un estimador insesgado de la varianza σ2 es,

∑ −−

=n

i XXn

S1

22 )(1

1 (47)

por lo que en adelante se usará esta estimación de la varianza.

4.4.1.2. Teorema central del límite El teorema central de límite establece que si las variables aleatorias X1,…,Xn constituyen una muestra aleatoria de una distribución con media μ y varianza σ2 desconocidas, entonces para cualquier valor x se cumple,

)()(Prlim xxXnn

Φ=⎥⎦

⎤⎢⎣

⎡≤

−∞→ σ

μ (48)

donde Φ es la distribución normal tipificada acumulada. Esto significa que si se selecciona una muestra aleatoria suficientemente grande de una distribución cualquiera con media μ y varianza σ2 desconocidas, la variable aleatoria X tendrá aproximadamente una distribución normal con media μ y varianza σ2/n.

4.4.1.3. Intervalos de Confianza No solo podemos estimar un valor de un parámetro desconocido sino también estimar un intervalo en el cual podría encontrarse este parámetro con una confianza determinada. En general un intervalo de confianza para un parámetro θ cuyo valor se quiere estimar se obtiene encontrando dos funciones reales de la muestra aleatoria A(X1,…,Xn) y B(X1,…,Xn) tales que,

Pr[A(X1,…,Xn) < θ < B(X1,…,Xn)] = γ (49) Ya que A y B son funciones reales tomarán valores específicos para cada conjunto de valores observados de la muestra aleatoria. Llamemos a y b a estos valores, entonces el intervalo (a, b) es un intervalo de confianza para la media μ con una confianza γ. En esta sección definiremos como se crea un intervalo de confianza para la estimación de la media μ de una distribución usando solo los valores de la muestra aleatoria.

4.4.1.3.1. Distribuciones muestrales Para la creación de un intervalo de confianza utilizaremos unas distribuciones especiales muy usadas en inferencia estadística, las distribuciones muestrales. En general una distribución muestral es la distribución de cualquier función real de una muestra aleatoria. Esta distribución puede ser deducida usando la distribución de cada una de las variables Xi, i=1,…,n, de la muestra. La distribución de probabilidad de un estimador es una distribución muestral. Si tenemos un parámetro desconocido de una distribución de probabilidad de una variable aleatoria podemos evaluar un estimador de este parámetro encontrando, a partir de su distribución muestral, la probabilidad de que el valor estimado esté cerca del parámetro desconocido. Si esta probabilidad es alta para todo valor posible de este parámetro entonces el estimador evaluado es un buen estimador del mismo.


33

4.4.1.3.2. Distribución χ2 La distribución χ2 es una distribución estrechamente relacionada con muestras aleatorias de una distribución normal. La distribución muestral χ2 de n grados de libertad de una variable aleatoria X se define como,

2/12/ xn ekx −− con x≥0 (50)

Donde k es una constante arbitraria. Esta distribución es importante por la aplicación de los enunciados del siguiente teorema para definir un intervalo de confianza. Esta aplicación se mostrará más adelante.

Teorema 1, Si Xi, i=1,…,n, son variables aleatorias independientes y cada una de ellas tiene una distribución normal N(μ,σ2), entonces

∑ ≈−n

i nX1

222 )()(1 χμ

σ (51)

y

∑ −≈−n

i nXX1

222 )1()(1 χ

σ (52)

Además es importante mencionar que por propiedades de las distribuciones normales [18] la media muestral X tendrá una distribución normal con media μ y varianza σ2/n.

4.4.1.3.3. Distribución t Al igual que la distribución χ2 la distribución t también tiene una estrecha relación con muestras aleatorias de una distribución normal. Esta distribución es la que al final utilizaremos para derivar los intervalos de confianza. La distribución t con n grados de libertad de una variable aleatoria X es,

2/)1(2

1+−

⎟⎟⎠

⎞⎜⎜⎝

⎛+

n

nxk -∞< x < ∞, (53)

La distribución t es simétrica con respecto a x = 0 y tiende a una distribución normal tipificada cuando n → ∞. Luego de haber definido las dos distribuciones muestrales enunciamos un nuevo teorema que las contempla y que es fundamental para la creación de intervalos de confianza.

Teorema 2, Si Y es una variable aleatoria con distribución normal tipificada N(0,1), y Z es una variable aleatoria con una distribución χ2 con n grados de libertad entonces la variable aleatoria U definida de la siguiente manera,

2/1

⎟⎠⎞

⎜⎝⎛

=

nZYU (54)

tiene una distribución t con n grados de libertad [11].


34

4.4.1.3.4. Creación de un intervalo de confianza Supongamos ahora que tenemos una muestra aleatoria Xi, i=1,…,n de una distribución normal con media μ y varianza σ2 desconocidas. Definimos a partir de esta muestra dos variables aleatorias Y y Z de la siguiente manera,

σμ /)(2/1 −= XnY ∑ −=n

i XXZ1

22 )(1

σ (55)

Dado que cada Xi tiene una distribución normal N(μ,σ2), la media muestral X tendrá una distribución normal con media μ y varianza σ2/n, y la variable aleatoria Y una distribución normal tipificada. Por otro lado por el teorema 1, la variable aleatoria Z tendrá una distribución χ2 con n-1 grados de libertad. Si definimos ahora la variable aleatoria U como,

SXn

n

XX

Xn

nZYU

n

i

)(

1

)(

)(

1

2/1

2/1

1

2/1

2/1

μμ −=

⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜

⎝

⎛

−

−

−=

⎟⎠⎞

⎜⎝⎛

−

=

∑ (56)

por el teorema 2 esta variable tendrá una distribución t con n-1 grados de libertad. Es importante destacar que tanto la variable aleatoria U como su distribución no dependen de la varianza σ2 la cual es desconocida. Utilizaremos esta definición de U para encontrar ahora un intervalo en el cual tengamos una confianza γ de que la media μ de la distribución normal de la cual se obtuvo la muestra aleatoria se encuentre en dicho intervalo. Para ello solo utilizaremos datos obtenidos de la muestra aleatoria, en particular la estimación a partir de los datos de la muestra de la media y de la varianza, X y S respectivamente. Partiendo de que U tiene una distribución t con n-1 grados de libertad podemos encontrar un valor c de las tabla para la distribución t, tal que se cumpla,

γ=<<− )Pr( cUc (57) y de la ecuación de U (56) y luego de algunas operaciones matemáticas tenemos que,

γμ =⎟⎟⎠

⎞⎜⎜⎝

⎛+<<−=<<−

ncSX

ncSXcUc Pr)Pr( (58)

Este resultado establece que independientemente del valor desconocido de la varianza σ2, la probabilidad de que μ esté entre las variables aleatorias,

A=n

cSX − y B=n

cSX + (59)


35

es γ. De esta manera, para cada conjunto de valores observados de la muestra aleatoria, las variables aleatorias A y B tomarán valores específicos a y b, y tendremos un intervalo de confianza (a, b) para la media μ con una confianza γ.

4.4.1.3.5. Intervalo de confianza para una muestra aleatoria de una distribución no normal No obstante la suposición inicial de una distribución normal de probabilidad de la variable aleatoria X para la creación de un intervalo de confianza para μ, toda la teoría expuesta a este respecto también puede aplicarse con buenos resultados cuando X posee cualquier otra distribución distinta a la normal [11]. Esto se debe a que de no tratarse de una distribución normal tendremos que la variable Y definida en (55), por el teorema central del límite [11], tendrá una distribución aproximada a la normal tipificada y convergerá a esta cuando el número de muestras n→∞. De esta manera, se podrá utilizar los mismos enunciados que para muestras de distribución normal pero ahora la confianza de que la media esté en el intervalo (a, b) será aproximadamente γ, mejorando los resultados para valores mayores de n.

4.4.1.4. Tamaño muestral No existe un método directo para calcular el tamaño muestral sin conocer la varianza de la distribución de probabilidad por la cual se generaron los datos de la muestra. En la mayoría de los experimentos esta varianza es desconocida. No obstante, podemos encontrar un valor del tamaño muestral para la estimación de la media μ con una muestra aleatoria de una distribución con varianza σ2 desconocida, especificando una precisión deseada en la estimación en términos de una proporción k de esta varianza y un nivel de confianza γ en que el error absoluto de estimación será menor a esta proporción,

[ ] γσμ >≤− kXPr (60) Esta probabilidad se puede escribir como,

[ ] γσ

μσμ >

⎥⎥⎦

⎤

⎢⎢⎣

⎡≤

−=≤− nk

nXnknX PrPr (61)

La expresión σμ nX )( − es una variable aleatoria con distribución normal tipificada para

muestras aleatorias de una distribución normal, y, por el teorema central del límite, aproximadamente una distribución normal tipificada para cualquier otra distribución distinta a la normal. Por lo tanto,

[ ]nkY ≤Pr >γ (62)

El valor de n se puede obtener de tablas o utilizando la ecuación de la distribución normal tipificada acumulada. Generalmente el valor de n para el cual se obtienen buenos resultados es de 20 [11].

4.4.2. Estimación en el Q-Learning El objetivo del aprendizaje por refuerzo es encontrar el valor de recompensa acumulada a lo largo de una política de acción. Si el entorno es determinista entonces tendremos un solo valor de recompensa acumulada. Si el entorno es no determinista, no existirá un valor específico de recompensa acumulada sino tendremos una distribución de probabilidades de la misma. En


36

este caso se busca una estimación del valor medio de esta distribución a través del aprendizaje [36]. En particular, el algoritmo de Q-Learning para entornos no deterministas pretende encontrar el valor medio de recompensa acumulada de la política para la cual esta recompensa es máxima. Con un completo conocimiento del modelo del entorno este valor medio se puede obtener de la fórmula de Bellman. Recordando la ecuación de Bellman, [ ]∑ +=

' ''' )','(max),(s a

ass

ass asQRPasQ γ

Ya que este modelo es desconocido casi la totalidad de las veces el valor de Q(s, a) debe estimarse. La estimación se realiza a través del promedio ponderado. Recordamos la ecuación de estimación,

)','(ˆmax 1'

asQrq na

−+= γ

qasQasQ nn .),(ˆ)1(),(ˆ1 αα +−← −

Cuando se trata de problemas episódicos estacionarios el valor estimado converge al valor real para n→∞ y cuando α cumple con los enunciados de la teoría de aproximaciones estocásticas [36]. Bajo estas características ),(ˆ asQn es un EMV de Q(s, a) para problemas episódicos y para problemas no episódicos puede considerarse como una buena aproximación de un EMV [36]. Como se expuso anteriormente un EMV es el valor del parámetro estimado que maximiza la probabilidad de obtener los datos observados. En este caso el parámetro estimado es sobre la distribución de recompensa acumulada, la cual es desconocida, y estimamos el valor medio de esta distribución. Los valores observados que constituyen la muestra aleatoria son cada uno de los valores de q observados durante el experimento. En este caso como el ),(ˆ asQn es un EMV de un valor medio también esta estimación minimiza el error cuadrático medio (ECM) [18],

[ ]2)),(( asQqEECM −= (63)

4.4.2.1. Intervalo de confianza Si n representa el número de veces que se ejecutó la acción a cuando se observa s entonces por (47) podemos considerar la estimación insesgada de la varianza de la distribución de q como [40],

∑ −−

=n

n asQqn

S1

22 )),(ˆ(1

1 (64)

y el intervalo de confianza para el valor de Q(s, a) estará definido por las variables aleatorias,

A=n

cSasQn −),(ˆ y B=n

cSasQn +),(ˆ (65)

donde el valor de c se calcula como en (58) para el valor de n y una confianza deseada.


37

4.4.3. Estimación en el aprendizaje con categorización Para aplicar los conceptos enunciados de inferencia estadística al algoritmo CL consideramos de nuevo que q es una variable aleatoria con una distribución de probabilidad. En el caso del Q-Learning como se considera un único estado por situación, solo existe una distribución de q para ese estado y una acción determinada. En el caso del algoritmo CL se consideran muchas visiones parciales por situación y tendremos una distribución de q para cada una de ellas y para cada acción. El algoritmo CL procura encontrar una visión parcial para cada situación en la que la distribución de q sea similar a la distribución que obtendríamos de considerar el estado completo s para esa situación y para la misma acción. Se describe a continuación la formulación teórica realizada en cada una de las fases del algoritmo.

4.4.3.1. Visiones Parciales y Valores de Aprendizaje Se asume nuevamente que el mundo se percibe por un número k de detectores binarios de características fi, i=1...k y se define una visión parcial de orden m, v(fi1,…, fim), como un detector virtual que se activa cuando sus m detectores de características que lo componen están simultáneamente activos. Para cada visión parcial v para cada acción posible a cuando v está activa se asocian tres valores:

• qv(a) estimación de la esperanza de la recompensa acumulada. • nv(a) Número de veces que la acción a se ejecutó estando activa v. Corresponde al

tamaño muestral. • ev(a) acumulado del error cuadrático de la predicción. Cabe notar que anteriormente se

utilizaba el error absoluto promedio de la predicción. Para crear el intervalo de confianza utilizaremos un nivel de confianza del 95%. El intervalo de confianza está determinado por las variables aleatorias,

)()(

)(anacS

aqAv

vv −= y

)()(

)(anacS

aqBv

vv += (66)

donde el valor de c se puede encontrar usando la distribución t con nv(a) grados de libertad y para una probabilidad del 95%, y el valor de Sv(a) está determinado por,

)(1)(

1)( aean

aS vv

v −= (67)

y se considera la estimación insesgada de la desviación estándar de la distribución de q.

4.4.3.2. Tamaño Muestral Para aproximar un número de muestras a partir del cual esperamos que el estimador haya alcanzado un buen nivel de estimación, siempre relativo a sus posibilidades, utilizamos la fórmula,

[ ]cnkY ≤Pr > γ (68)


38

a partir de los valores de la distribución normal tipificada obtenemos el valor de nc. De ahora en más consideramos este valor como el mínimo número de muestras para el cual los valores estadísticos de qv(a) y Sv(a) de una visión parcial para una acción se consideren como buenas estimaciones de la media de la distribución de q de esa visión parcial y de su desviación estándar σ.

4.4.3.3. Selección de Acción Debemos seleccionar cual será la acción a ejecutar más adecuada en cada situación. Para ello primero buscamos las mejores estimaciones del valor esperado para cada acción. La mejor estimación para cada acción será la de la visión parcial con el intervalo de confianza más pequeño,

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

=∈∀ )(

)(2minarg),(

anacS

aVganadorav

v

Vv (69)

donde V es el conjunto de visiones parciales activas. Una vez que se encuentra la visión parcial ganadora w el valor de predicción de la media de la distribución de q (que llamaremos Q(w,a)) se obtiene utilizando una variable aleatoria auxiliar U con distribución t de nw(a) grados de libertad. Esta variable aleatoria se define como,

)()),()(()(

aSawQaqan

Uw

ww −= (70)

Cabe mencionar que la variable aleatoria U es la que se utilizó para crear el intervalo de confianza para la media Q(w,a). Para encontrar un valor de predicción de la media primero obtenemos un punto c’ de U según la distribución t con nw(a) grados de libertad. Luego utilizando la ecuación de U (70) obtenemos un valor de predicción para Q(w,a) de la siguiente manera,

)()('

)()(anaSc

aqapredicciónw

ww += (71)

Como puede verse la predicción será más precisa para aquellas acciones cuya visión parcial ganadora presente un intervalo de confianza más estrecho ya que la predicción de Q(w,a) tiene un 95% de probabilidad de estar dentro de ese intervalo.

4.4.3.4. Actualización Estadística Para la actualización estadística utilizamos cada nuevo valor observado q como una nueva muestra del experimento. Sea r el valor de recompensa obtenido de ejecutar a cuando se observa el conjunto de visiones parciales V. El valor observado de q se obtiene como antes,

),'(|)(max. aVganadoravaqrq va=+=

∀γ (72)

donde V’ es el conjunto de visiones parciales activas de la situación siguiente. Con el valor observado de q actualizamos los valores asociados a cada visión parcial en V y para cada acción.


39

Para cada nuevo valor observado incrementamos en 1 el tamaño muestral asociado a cada visión parcial activa y para la acción a,

nv(a) = nv(a) + 1 (73) Para la actualización de qv(a) usamos la fórmula de actualización del Q-Learning para entornos estocásticos,

qv(a) = (1- αv(a)) qv(a) + αv(a) q (74) donde αv(a) es el coeficiente de aprendizaje. Un valor de coeficiente de aprendizaje adecuado para este fin es,

)(11)(

ana

vv +

=α (75)

El valor αv(n) definido en (75) cumple con los requerimientos de la teoría de aproximaciones estocásticas [36]. Para procesos estacionarios el valor estimado qv(a) convergerá a Q(v,a) con probabilidad 1. Pero generalmente los entornos de los problemas considerados son no estacionarios y necesitaremos mantener un valor de coeficiente de aprendizaje mínimo para reflejar los cambios del sistema en los valores estadísticos. Para ello seguiremos utilizando la función αv(n) pero con valor de saturación mínimo de αv(nc) para valores de n ≥ nc , siendo este el valor de n para el cual se espera que el valor de qv(a) sea una buena estimación de Q(v,a). Para poder estimar la desviación estándar de la distribución de q (67) utilizamos el error cuadrático de predicción. La esperanza de este error es el EMV el cual es la varianza de la distribución de q, y se minimiza cuando el estimador del valor observado es la media muestral [18]. Anteriormente se utilizaba la función de pérdida del error absoluto cuya esperanza se minimiza cuando el estimador del valor observado es la mediana [18] de la distribución, y no la media como nos interesa en RL. El cálculo del estimador insesgado de la desviación estándar utiliza el valor acumulado del error cuadrático. Este valor acumulado se almacena en ev(a),

ev(a) = ev(a) + (q – qv(a))2 (76)

4.4.3.5. Gestión de Visiones Parciales El propósito de este bloque sigue siendo mejorar la predicción de q cuando sea necesario a través de la generación de nuevas visiones parciales. La precisión de la predicción depende del ancho del intervalo de confianza de la visión parcial ganadora w. Para determinar el ancho del intervalo de confianza de w que indique una buena categorización es necesario conocer la varianza de la distribución de q para el estado s [11], la cual desconocemos. Este hecho constituye uno de los principales problemas pendientes de resolver para evaluar la necesidad de mejorar la categorización. No obstante, podemos adoptar diferentes criterios para la generación de visiones parciales. Describiremos el criterio que hasta el momento nos parece mas conveniente.

4.4.3.5.1. Generación de Visiones Parciales Ya que desconocemos el nivel de categorización que podemos alcanzar y en cuanto podemos mejorar la predicción, se utiliza una generación de visiones parciales a una tasa constante y


40

variaremos el ancho del intervalo máximo permitido para w para mantener esta tasa en un valor predefinido. Se inicializa el ancho crítico para el intervalo de confianza en un valor aleatorio. Esto produce el efecto de mantener un nivel de generación mayor en aquellas situaciones en donde es posible mejorar la categorización de forma adaptativa y de acuerdo a los requerimientos del problema.

Combinación de Visiones Parciales Las nuevas visiones parciales se crean combinando dos existentes. Debido a que se desea mejorar la categorización para predecir mejor el valor de q en una situación consideramos adecuado favorecer la combinación de aquellas visiones parciales que no sean redundantes. Es decir, si dos visiones parciales poseen características similares de predicción su combinación posiblemente no aporte más información de la existente para mejorar la predicción, mientras que si combinamos dos visiones parciales que posean estimaciones diferentes entonces su combinación podría aportar más información al sistema para predecir el resultado de una acción. Así, la combinación se realiza comparando las distribuciones del valor estimado de las visiones parciales activas tomadas de a pares y favoreciendo la combinación de aquellas que presenten mayor diferencia en sus distribuciones. La comparación se puede realizar con cualquier método de contraste de hipótesis como la prueba t o la prueba de Kolmogorov-Smirnov.

4.4.3.5.2. Eliminación de visiones parciales La eliminación de visiones parciales solo se realizará sobre visiones parciales redundantes. Como antes, se calcula la redundancia de una visión parcial activa con respecto al resto de visiones parciales activas en una situación, pero ahora se calcula la similaridad entre dos visiones parciales usando un método de contraste de hipótesis sobre las distribuciones de sus estimaciones. Cabe mencionar que no se eliminan visiones parciales según el criterio de utilidad debido a que la utilidad real de una visión parcial es desconocida por que si bien puede resultar poco útil en una situación, su combinación con otra visión parcial existente puede resultar en una utilidad mayor para el sistema y esto no es posible conocerlo con anterioridad.

4.4.3.6. Evaluación de la Formalización Teórica Con la formalización teórica del algoritmo CL logramos reducir considerablemente el número de parámetros y elementos definidos por el usuario, y dimos sustento teórico a muchos conceptos utilizados para la categorización. Por ejemplo, la confianza y la relevancia de una visión parcial quedan concentradas en el valor del ancho del intervalo de confianza definido a partir de la distribución muestral del estimador qv(a). Podemos seleccionar el nivel de confianza en un porcentaje. En este caso trabajamos con un nivel de confianza del 95% de que el verdadero valor estimado estará dentro del intervalo de confianza. Esto nos permite comparar las características como estimador de las diferentes visiones parciales basándonos en herramientas teóricas. Además desaparecen los parámetros η y β. La actualización estadística simplemente se hace en función de los valores que luego utilizaremos para analizar las propiedades de estimación de una visión parcial. Queda pendiente aún una formalización teórica más sólida para el bloque de gestión de visiones parciales.

4.4.3.7. Aplicación al Control del Manipulador La figura 9 muestra los resultados de aplicar el algoritmo luego de la formalización teórica.


41

0 2 4 6 8 10 12

-1.5

-1

-0.5

0

0.5

1

1.5


tiempo [s]

posicion

ang

ular [rad]

-1.5

-1

-0.5

0

0.5

1

1.5

posicion

ang

ular [r

ad]

Control con PID

ECM = 0.016

0 2 4 6 8 10 12-0.5

0

0.5

tiempo [s]

Error [

rad]

-1.5

-1

-0.5

0

0.5

1

1.5

posicion

ang

ular [r

ad]


ECM = 0.027

0 2 4 6 8 10 12-0.5

0

0.5

tiempo [s]

Error [

rad]

Figura 9. Resultados de control del manipulador para el algoritmo CL con la formalización teórica luego de 60000 iteraciones y resultados de control con un PID sintonizado.

El primer punto a destacar es que el algoritmo con la formalización matemática necesitó mucho menos iteraciones que antes de ella, 60000 contra 150000 iteraciones para la convergencia. Otro aspecto es que el error cuadrático es mucho menor en este caso, presenta menos varianza y en algunas zonas es cercano a cero. También es importante mencionar que en el caso anterior se invirtió una cantidad considerable de tiempo para encontrar empíricamente valores de parámetros que dieran resultados aceptables. En este caso muchos de estos parámetros han desaparecido y el desempeño es aún mejor mostrando la solidez teórica que se agregó al algoritmo. No obstante, quedan aspectos por resolver relacionados a la continuidad del dominio y al propio algoritmo.

Proyecto de Tesis PROYECTO DE TESIS

42

5. Proyecto de Tesis Como trabajo a realizar nos planteamos desarrollar un método de aprendizaje en dominios continuos aprovechando la categorizabilidad del entorno. Cabe mencionar que la técnica de aprendizaje en entornos categorizable, los métodos de aproximación de funciones aplicados a aprendizaje por refuerzo y los métodos de resolución variable, siguen constituyendo áreas abiertas de investigación. No obstante, creemos que la combinación de estos tres métodos mejorarán los resultados hasta ahora obtenidos en el campo del aprendizaje en dominios continuos. Describiremos ahora las tareas a realizar en relación a los objetivos planteados.

5.1. MEJORA DEL ALGORITMO CL. GESTIÓN DE VISIONES PARCIALES. Uno de los problemas que quedaron pendientes de resolver en la formalización teórica del algoritmo CL está referido a la gestión de visiones parciales. Como primer paso del trabajo investigaremos sobre otros posibles criterios para evaluar la categorización de una situación y buscar una base teórica más sólida para el criterio de combinación de visiones parciales.

5.2. ADAPTACIÓN DEL ALGORITMO CL PARA APRENDIZAJE EN DOMINIO CONTINUO Para poder aplicar las técnicas de resolución variable y aproximación de funciones en el algoritmo CL se considerará primero la aplicación de cada una de ellas por separado para facilitar la evaluación de los resultados. Luego, una vez que se encuentren los métodos adecuados para cada caso, se investigará sobre la combinación de ambas.

5.2.1. Resolución Variable en Aprendizaje en Entornos Categorizables Para aplicar técnicas de resolución variable en el aprendizaje en entornos categorizables debemos tener en cuenta que: un grupo de visiones parciales se activa por cada punto considerado del espacio de estados, que las visiones parciales contemplan diferentes dimensiones, y que la visión parcial ganadora para cada acción puede ser diferente en la misma región. Además, una mala predicción sobre el resultado de una acción puede deberse no solo a la necesidad de mejorar la resolución, sino también a que la visión parcial ganadora no posee la información suficiente como para realizar una buena predicción. Todo lo mencionado puede representar una dificultad importante para encontrar un método de resolución variable en el aprendizaje en entornos categorizables. Investigaremos sobre cuales características o grupo de característica del entorno se debe variar la resolución para mejorar el aprendizaje, como se puede realizar esta variación y en que momento es necesario hacerlo.

5.2.2. Aproximación de Funciones en Aprendizaje en Entonos Categorizables Para aproximar la función valor en el aprendizaje en entornos categorizables es necesario tener en cuenta que para cada punto del espacio de estados, y para una acción determinada, se tendrá una visión parcial ganadora diferente. Así, la función valor para una acción tendrá un dominio de dimensión variable según la región del espacio de estados que se considere. Investigaremos cuales técnicas serán las más adecuadas para aplicar en este caso y como se realiza la aproximación de la función valor.

5.2.3. Aproximación de Funciones con Resolución Variable en Aprendizaje en Entornos Categorizables Muy poco se ha investigado sobre la combinación de métodos de resolución variable con métodos de aproximación de funciones, aunque si se ha mencionado la posibilidad de combinar ambos métodos para mejorar la aproximación de la función valor [15]. El concepto


43

general es utilizar las técnicas de resolución variable para aumentar la cantidad de ejemplos en aquellas regiones donde se necesite mayor precisión en la aproximación. Investigaremos como combinar ambos métodos en el aprendizaje en entornos categorizables.

5.2.4. Generalización en el Espacio de Acciones Existen tareas complejas que requieren predecir para una sola situación el resultado de ejecutar varias acciones simultáneamente. En estos casos las posibles combinaciones de acciones que se pueden ejecutar de forma simultánea puede ser muy grande. Es por ello que a veces es también necesario generalizar en el espacio de acciones. La generalización en el espacio de acciones aún es un área abierta de investigación [8]. El objetivo práctico del trabajo es aplicar el algoritmo a un problema real de control de locomoción de un robot caminante en donde puede ocurrir la ejecución de varias acciones simultáneamente. Investigaremos como aplicar estos métodos en aprendizaje en entornos categorizables para generalizar en el espacio de las acciones.

5.3. EVALUACIÓN DEL ALGORITMO CL PARA DOMINIOS CONTINUOS USANDO UN SIMULADOR Antes de aplicar el algoritmo CL para dominios continuos a un problema real, se evaluará su desempeño sobre el problema de control de trayectoria en el espacio cartesiano de su actuador final. En este modelo tendremos inercias variables, cargas variables dadas por las componentes de gravedad, y un espacio de acciones de tres dimensiones.

5.4. APLICACIÓN DEL ALGORITMO A UN PROBLEMA REAL COMPLEJO La mayoría de los algoritmos de aprendizaje que fueron desarrollados para problemas reales complejos se evalúan sobre simulaciones en un ordenador. Estas simulaciones resultan mucho más sencillas que el problema real que simulan. En el mundo real existen muchos otros factores que no se tienen en cuenta en la simulación que pueden afectar el desempeño del algoritmo.

5.4.1. El robot Argos Argos es el nombre de un robot caminante de 6 patas con 3 grados de libertad en cada una de ellas. Posee actuadotes rotacionales con motores de corriente continua marca Maxon modelo 118800 (ver Sección 4.2.1. para las características del motor). Por cada dos grados de libertad posee una placa controladora con un controlador PIC 16F87. El controlador está conectado a un ordenador a través de un bus CAN. La transmisión de movimiento y esfuerzo se realiza a través de engranajes dentados.

Figura 10. El robot Argos.


44

En este momento el control de trayectoria de cada actuador se realiza con un sistema de control proporcional integral (PI). Las características de diseño del robot dificultan el control de cada actuador y en consecuencia afectan a la marcha. Evaluaremos el algoritmo CL para dominios continuos aplicándolo al control de seguimiento de trayectoria de las patas del robot Argos en el espacio cartesiano.

Proyecto de Tesis PLAN DE TRABAJO

45

6. Plan de trabajo

A continuación se describe el plan de trabajo a realizar.

A. Mejora del bloque de gestión de visiones parciales del algoritmo CL. B. Desarrollo de técnica de resolución variable para el aprendizaje en entornos

categorizables. C. Desarrollo de técnica de aproximación de funciones para el aprendizaje en entornos

categorizables. D. Aplicación de técnica de aproximación de funciones utilizando un dominio de

resolución variable en el aprendizaje en entornos categorizables. E. Aplicación de técnicas de generalización en el espacio de acciones en el aprendizaje

en entornos categorizables. F. Desarrollo de un simulador de un brazo robótico de tres grados de libertad con

actuadotes rotacionales. Aplicación del algoritmo CL para dominios continuos al problema de control de trayectoria en el espacio cartesiano del actuador final. Evaluación de resultados e implementación de los cambios necesarios para mejorar el desempeño del algoritmo.

G. Puesta en funcionamiento del robot Argos. El robot Argos lleva un tiempo considerable sin funcionar. Será necesario un chequeo completo del estado de sus componentes electrónicos y de los mecanismos en general.

H. Implementación del algoritmo CL para dominios continuos en el sistema del robot Argos.

I. Aplicación del algoritmo CL para dominios continuos al problema real de control de movimiento de las patas del robot Argos. Evaluación de los resultados. Sospechamos que nos encontraremos con muchas nuevas dificultades cuando apliquemos el algoritmo a este problema real complejo. Consideramos que será necesario revisar y replantear algunos de los métodos usados para el aprendizaje en dominio continuo y para el aprendizaje en entornos categorizables. Tenemos la esperanza de poder superar estas dificultades y realizar un control adecuado de las patas usando aprendizaje en dominio continuo con categorización de entornos mejorando el rendimiento de un sistema de control convencional PID que suele ser el más robusto y simple de implementar y por ende el más usado [16], [30].

J. Elaboración del informe de tesis.

En la figura 11 se especifica la estimación del calendario para las tareas a realizar. Año 2004 2005 2006 Mes 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7

A B C D E F G H I J

Figura 11. Calendario tentativo de tareas.

Proyecto de Tesis REFERENCIAS

46

7. Referencias [1] Agostini A, Celaya E, Applying Categorization to Improve Learning in Complex

Environment. In Proceedings I Jornadas de Recerca en Automàtica, Visiò i Robòtica. UPC, Barcelona, Spain 2004, pp. 263-268.

[2] Agostini A, Celaya E. Learning in Complex Environments with Feature-Based

Categorization. In Proceedings of The 8th Conference on Intelligent Autonomous Systems. Amsterdam, The Netherland. 2004, pp. 446-455.

[3] Agostini A, Celaya E. Learning Model Free Motor Control. In Proceedings of the 16th

European Conference on Artificial Intelligence. Valencia, España. Agosto, 2004 (accepted).

[4] Agostini A, Celaya E. Trajectory Tracking Control of a Rotational Joint using Feature

Based Categorization Learning. IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan. 2004 (submitted).

[5] Al-Ansari M. Efficient Reinforcement Learning in Continuous Environments. PhD

Thesis. College of Computer and Information Science (CCIS). Northeastern University, Boston, MA, 2001.

[6] Atkeson C, Moore A, and Schaal S. Locally Weighted Learning. Artificial Intelligence

Review, 11:(1-5), pp. 11-73, 1997. [7] Atkeson C, Moore A, and Schaal S. Locally weighted learning for control. Artificial

Intelligence Review, vol. 11, pp. 75-113, 1997. [8] Baird L and Klopf A. Reinforcement learning with high-dimensional, continuous actions.

Tech. Rep. WL-TR93 -1147, Wright Laboratory, 1993. [9] Bellman R. Dynamic Programming. NJ: Princeton University Press, 1957. [10] Bentley J. Multidimensional binary search trees used for associative searching.

Communications of the ACM, 18(9):509--517, September, 1975. [11] Blom G. Probability and Statistics: Theory and Applications. Springer Texts in Statistics.

Springer-Verlag, 1989. [12] Boyan J and Moore A. Generalization in reinforcement learning: Safely approximating the

value function. In Tesauro, G.; Touretzky, D. S.; and Leen, T. K., eds., Advances in Neural Information Processing Systems, volume 7. Cambridge, MA: The MIT Press, 1995.

[13] Buck S, Beetz M, and Schmitt T. Approximating the Value Function for Continuous

Space Reinforcement Learning in Robot Control. Proceedings of the IEEE/RSJ IROS 2002, Lausanne, Switzerland.


47

[14] Chapman D. and Kaebling L. Input Generalization in Delayed Reinforcement Learning: An Algorithm and Performance Comparisons. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91), 726-731, 1991.

[15] Coulom R. Feedforward Neural Networks in Reinforcement Learning Applied to High-

Dimensional Motor Control. ALT 2002: 403-414.

[16] Craig J. Introduction to Robotics. 2nd Ed. Addison-Wesley Publishing Company, 1989. [17] Davies S. Multidimensional Triangulation and Interpolation for Reinforcement Learning.

In Neural Information Processing Systems 9. Morgan Kaufmann. 1996. [18] DeGroot M. Probabilidad y Estadística. Segunda Edición. Addison-Wesley

Iberoamericana, 1988. [19] Friedman J, Bentley J, Finkel R. An Algorithm for Finding Best Matches in Logarithmic

Expected Time. ACM Transactions on Mathematical Software, Vol. 3, 3, 209/226, Septiembre, 1977.

[20] Großmann A. Continual learning for mobile robots. School of Computer Science, PhD

Thesis, The University of Birmingham, Birmingham, UK, February 2001.

[21] Gullapalli V. A Stochastic Reinforcement Learning Algorithm for Learning Real-Valued Functions. Neural Netwoks, 3:671:692, 1990.

[22] Kaelbling L, Littman M. and Moore A. Reinforcement learning: A survey. Journal of

Artificial Intelligence Research 4:237–285, 1996. [23] Lin W, Prasanna V, Przytula K. Algorithmic Mapping of Neural Network Models onto

Parallel SIMD Machines. IEEE Trans. Computers 40(12): 1390-1401, 1991. [24] Maxon Motor, High Precision Drives and Systems, Maxon Interelectric AG, Switzerland. [25] McCallum A. Reinforcement Learning with Selective Perception and Hidden State. Phd.

thesis, Department of Computer Science, University of Rochester, Rochester, NY, 1995. [26] Mitchel T. Machine Learning. McGraw-Hill, 1997. [27] Moore A. The parti-game algorithm for variable resolution reinforcement learning in

multidimensional state-spaces. In Cowan, J. D.; Tesauro, G.; and Alspector, J., eds., Advances in Neural Information Processing Systems 6, 711–718. Morgan Kaufmann, 1994.

[28] Moore A. Variable resolution dynamic programming: Efficiently learning action maps in

multivariate real-valued spaces. In Proceedings Eighth International Machine Learning Workshop, 1991.

[29] Munos R, Moore A. Variable Resolution Discretization in Optimal Control. Machine

Learning 49(2-3): 291-323, 2001.


48

[30] Ogata K. Modern Control Engineering. 4th ed., Prentice Hall, New Jersey, United State, 2002.

[31] Porta J, Celaya E. Learning in Categorizable Environments. Sixth International

Conference on Simulation of Adaptive Behaviour: From Animals to Animats, Paris, September, 2000.

[32] Porta J. Behaviour-Based Robots and Reinforcement Learning: A Case Study on Legged

Robots. PhD Thesis, Departament de LLenguatges I Sistemes Informàtics. UPC. Catalunya, Spain, 2001.

[33] Pyeatt L and Howe A. Decision Tree Function Approximation in Reinforcement

Learning. In Proceedings of the Third International Symposium on Adaptive Systems: Evolutionary Computation & Probabilistic Graphical Models, pages 70 77, Havana, Cuba, March 2001.

[34] Reynolds S. Adaptive Resolution Model-Free Reinforcement Learning: Decision

Boundary Partitioning. ICML 2000: 783-790. [35] Smart W and Kaelbling L. Practical reinforcement learning in continuous spaces. In

Proceedings of the Seventeenth International Conference on Machine Learning (ICML) 2000.

[36] Sutton R, Barto A. Reinforcement Learning: An Introduction, "A Bradford Book", MIT

Press, 1998.

[37] Tesauro G. Temporal Difference Learning and TD-Gammon. Communications of the ACM 38(3):58-68, March 1995.

[38] Thrun S. and Schwartz A. Issues in Using Function Approximation for Reinforcement

Learning. In M. Mozer, P. Smolensky, D. Touretzky, J. Elman, and A. Weigend, editors, Proceedings of the Connectionist Models Summer School, pp. 255-263, Hillsdale, NJ, 1993.

[39] Tsitsikilis J. and Van Roy B. An Analysis of Temporal Difference Learning with Function

Approximation. IEEE Transactions on Automatic Control, 42(5):674--690, 1997. [40] Uther W, Veloso M. Tree Based Discretization for Continuous State Space Reinforcement

Learning. En Proceedings of AAAI-98, Madison, WI, Julio, 1998. [41] Watkins C, Dayan P. Q-Learning. Machine Learning, 8:279-292, 1992.

Proyecto de Tesis PUBLICACIONES

49

8. Publicaciones Realizadas

RELACIONADAS AL PROYECTO DE TESIS

Agostini A, Celaya E, Applying Categorization to Improve Learning in Complex Environment. In Proceedings I Jornadas de Recerca en Automàtica, Visiò i Robòtica. UPC, Barcelona, Spain 2004, pp. 263-268.

Agostini A, Celaya E. Learning in Complex Environments with Feature-Based

Categorization. In Proceedings of The 8th Conference on Intelligent Autonomous Systems. Amsterdam, The Netherland. 2004, pp. 446-455.

Agostini A, Celaya E. Learning Model Free Motor Control. In Proceedings of the 16th

European Conference on Artificial Intelligence. Valencia, España. Agosto, 2004 (accepted).

Agostini A, Celaya E. Trajectory Tracking Control of a Rotational Joint using Feature

Based Categorization Learning. IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan. 2004 (submitted).

OTRAS PUBLICACIONES RELACIONADAS AL DOCTORADO

Agostini A. Sistema Multiagente para Monitorización Inteligente Domiciliaria de Pacientes con Patologías Cardiovasculares. In Open Discussion Track Proceedings of the VIII Iberoamerican Conference on Artificial Intelligence. F. Garijo, J.C. Riquelme, M. Toro (editors). Sevilla, España, Noviembre 2002. pp. 205-210.

Rollón E, Isern D, Agostini A, Cortés U. Towards the Distributed Management of

Emergencies: Forest Fires Case Study. Eighteenth International Joint Conference on Artificial Intelligence. Acapulco, México, Agosto 2003.

Documents

Proyecto de tesis Intranet - iri.upc.edu · descuento. Sin embargo si el entorno es no determinista, como suele ser el caso, no existirá un único valor para la ecuación (1), sino