Story Transcript
UNIVERSIDAD POLITÈCNICA DE CATALUÑA TELECOM BCN
Ingeniería de Telecomunicaciones Departamento de telemática
Aprendizaje por refuerzo multi-nivel para sistemas RRM PROYECTO FINAL DE CARRERA Febrero 2014
Autor Kevin Collados Zamora
Director Juan Luis Gorricho Moreno
Abstracto Este estudio se centra en la problemática de la gestión de recursos en el ámbito de los sistemas RRM (Radio Resource Management) con más de un objetivo a maximizar. En concreto se centra en maximizar simultáneamente la calidad de servicio que se ofrece al usuario y el beneficio adquirido para el operador. Para tal fin se evaluará el rendimiento de los sistemas RRM basados en la utilización de la metodología RL (Reinforcement Learning). Esta evaluación se realizará mediante la modificación y evolución de las características propias del sistema a fin de incrementar su rendimiento. Finalmente se realiza una propuesta de resolución, basándose en un sistema de cooperación entre dos agentes. Ambos agentes utilizan la metodología FRL (Fuzzy Reinforcement Learning). Cada agente se centra en maximizar un objetivo, de forma que la colaboración conjunta entre agentes proporcionará una optimización global del sistema.
Índice general 1. Introducción 1.1. Entorno de trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Sistema EDC 2.1. Sistema inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. Resultados del sistema . . . . . . . . . . . . . . . . . . 2.2. División de estados y consideración de la calidad de servicio 2.2.1. Metodología de división . . . . . . . . . . . . . . . . . . 2.2.2. Incorporación de la calidad de servicio . . . . . . . . . 2.2.3. Resultados del sistema . . . . . . . . . . . . . . . . . . 2.3. Sistema distribuido . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Gestión de carga . . . . . . . . . . . . . . . . . . . . . . 2.3.2. Resultados del sistema . . . . . . . . . . . . . . . . . . 2.4. Análisis del sistema EDC . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
3. Sistema ARMUN 3.1. Nivel de calidad de servicio . . . . . . . . . . . . . . . . . . . . . . . 3.2. Nivel de beneficio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Resultados de un único operador funcionando en el entorno . . . . 3.3.1. Análisis de los resultados individuales . . . . . . . . . . . . . 3.4. Comparativa entre dos operadores . . . . . . . . . . . . . . . . . . . 3.4.1. Comparativa AA-AA . . . . . . . . . . . . . . . . . . . . . . . 3.4.2. Comparativa AA-QQ . . . . . . . . . . . . . . . . . . . . . . . 3.4.3. Comparativa QQ-AA . . . . . . . . . . . . . . . . . . . . . . . 3.4.4. Comparativa QQ-QQ . . . . . . . . . . . . . . . . . . . . . . . 3.4.5. Análisis de los resultados con competición entre operadores 4. Conclusiones
. . . . . . . . . .
. . . . . . . . . .
1 2 3
. . . . . . . . . .
5 5 6 7 7 9 10 11 12 12 13
. . . . . . . . . .
15 17 21 27 34 35 36 40 44 48 52 54
5. Estado del arte 57 I. Tipos de Estructuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 I.1. Estructura Centralizada . . . . . . . . . . . . . . . . . . . . . . . 57
I.2. Estructura Distribuida . . . . . . . . . . . . Aprendizaje por refuerzo . . . . . . . . . . . . . . . II.1. Actor-Critic . . . . . . . . . . . . . . . . . . . II.2. Q-Learning . . . . . . . . . . . . . . . . . . . II.3. Procedimiento Actor-Critic . . . . . . . . . . II.4. Procedimiento Q-Learning . . . . . . . . . . III. Lógica difusa . . . . . . . . . . . . . . . . . . . . . . III.1. Función de membresía . . . . . . . . . . . . III.2. Reglas del sistema . . . . . . . . . . . . . . III.3. Procedimiento general de implementación . IV. Fuzzy reinforcement Learning . . . . . . . . . . . . IV.1. Estructura de la lógica difusa . . . . . . . . IV.2. Fuzzy Actor-Critic . . . . . . . . . . . . . . . IV.3. Fuzzy Q-Learning . . . . . . . . . . . . . . . IV.4. Procedimiento FAC . . . . . . . . . . . . . . IV.5. Procedimiento FQL . . . . . . . . . . . . . . II.
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
6. Anexos I. Pseudo-Código movimiento de los usuarios . . . . . . II. Pseudo-Código Recompensa en el sistema EDC inicial III. Parámetros de simulación: EDC sistema inicial . . . IV. Parámetros de simulación: EDC sistema divisible . . V. Parámetros de simulación: EDC distribuido . . . . . . VI. Parámetros de simulación: ARMUN 1 operador . . . . VII. Parámetros de simulación: ARMUN 2 operadores . . 7. Nomenclatura
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
58 59 60 61 62 62 62 64 65 66 67 67 68 72 75 75
. . . . . . .
77 77 79 80 82 84 86 88 90
8. Bibliografía 92 I. Publicaciones Realizadas . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Índice de figuras 1.1. Ejemplo de un escenario con interactuación de 9 estaciones . . . . . . .
2
2.1. Esquema estado acción sistema EDC estático . . . . . . . . . . . . . . . 5 2.2. Esquema de divisionamiento de estados . . . . . . . . . . . . . . . . . . 8 2.3. Esquema de gestión de las llamadas según la carga . . . . . . . . . . . 12 3.1. Relación agentes-entorno . . . . . . . . . . . . . . . . . . . . . . 3.2. Relación agentes-entorno utilizando aprendizaje por refuerzo 3.3. Categorización del nivel de dropping . . . . . . . . . . . . . . . 3.4. Categorización del nivel de blocking . . . . . . . . . . . . . . . 3.5. Matriz de reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6. Pesos de las acciones asociadas a las reglas . . . . . . . . . . . 3.7. Clasificación de la carga del sistema . . . . . . . . . . . . . . . 3.8. Clasificación del vector de decisión: Coverage area . . . . . . . 3.9. Clasificación del vector de decisión: Demanda de canal . . . . 3.10.Clasificación del vector de decisión: Threshold . . . . . . . . . 3.11.Reglas del nivel de beneficio . . . . . . . . . . . . . . . . . . . . 3.12.Ejemplos de ventanas deslizantes . . . . . . . . . . . . . . . . . 3.13.Entorno del sistema a simular . . . . . . . . . . . . . . . . . . . 3.14.Carga de los canales en posesión . . . . . . . . . . . . . . . . . 3.15.Adquisición porcentual del número de canales disponibles . . 3.16.Threshold promedio de los canales en posesión . . . . . . . . . 3.17.Incremento porcentual del área de cobertura . . . . . . . . . . 3.18.Porcentaje de Blocking y Dropping . . . . . . . . . . . . . . . . 3.19.Calidad de servicio ofrecida al usuario . . . . . . . . . . . . . . 3.20.Relación beneficio-coste del operador . . . . . . . . . . . . . . . 3.21.Comparativa AA-AA: cobertura . . . . . . . . . . . . . . . . . . 3.22.Comparativa AA-AA: porcentaje de canales en posesión . . . . 3.23.Comparativa AA-AA: carga promedio del sistema . . . . . . . 3.24.Comparativa AA-AA: comparativa threshold . . . . . . . . . . 3.25.Comparativa AA-AA: comparativa dropping y blocking . . . . 3.26.Comparativa AA-AA: QoS . . . . . . . . . . . . . . . . . . . . . 3.27.Comparativa AA-QQ: cobertura . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
16 16 19 19 20 20 22 23 23 24 25 27 28 29 30 31 31 32 33 34 37 38 38 39 39 40 41
3.28.Comparativa AA-QQ: porcentaje de canales en posesión . 3.29.Comparativa AA-QQ: carga promedio del sistema . . . . 3.30.Comparativa AA-QQ: comparativa threshold . . . . . . . 3.31.Comparativa AA-QQ: comparativa dropping y blocking . 3.32.Comparativa AA-QQ: QoS . . . . . . . . . . . . . . . . . . 3.33.Comparativa QQ-AA: cobertura . . . . . . . . . . . . . . . 3.34.Comparativa QQ-AA: porcentaje de canales en posesión . 3.35.Comparativa QQ-AA: carga promedio del sistema . . . . 3.36.Comparativa QQ-AA: comparativa threshold . . . . . . . 3.37.Comparativa QQ-AA: comparativa dropping y blocking . 3.38.Comparativa QQ-AA: QoS . . . . . . . . . . . . . . . . . . 3.39.Comparativa QQ-QQ: cobertura . . . . . . . . . . . . . . . 3.40.Comparativa QQ-QQ: porcentaje de canales en posesión 3.41.Comparativa QQ-QQ: carga promedio del sistema . . . . 3.42.Comparativa QQ-QQ: comparativa threshold . . . . . . . 3.43.Comparativa QQ-QQ: comparativa dropping y blocking . 3.44.Comparativa QQ-QQ: QoS . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
42 42 43 43 44 45 46 46 47 47 48 49 50 50 51 51 52
5.1. 5.2. 5.3. 5.4. 5.5. 5.6. 5.7. 5.8.
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
57 58 63 65 66 68 72 74
Esquema de una estructura centralizada . . . . Esquema de una estructura distribuida . . . . . Diagrama de un sistema básico de lógica difusa Diagrama función de membresía . . . . . . . . . Ejemplo matriz de regla . . . . . . . . . . . . . . Esquema de lógica difusa utilizado . . . . . . . . Esquema FACL . . . . . . . . . . . . . . . . . . . Esquema FQL . . . . . . . . . . . . . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
1. Introducción Las redes diseñadas para planificar, configurar, administrar, optimizar y recuperar los radio-accesos de la son denominadas SON (Self Organisation Networks) [1]. Estos sistemas comprenden todos aquellos algoritmos y metodologías definidas para realizar una adaptación de los parámetros controlados por los sistemas. En el caso especifico de los sistemas RRM (Radio Resource Management) se gestionan las características de los sistemas inalámbricos. La capacidad de reconfiguración de los sistemas RRM proporciona nuevas vías en la manera de utilizar los recursos disponibles [2], [3]. Mediante el uso de una política más adecuada para la administración de los recursos puede alcanzarse una mayor eficiencia a partir del desarrollo de mecanismos más apropiados para afrontar la demanda de los usuarios de la red. La gestión de los recursos tradicionalmente ha seguido un enfoque estático en como se realiza la distribución y especificación de los recursos disponibles, entre otros la gestión de los recursos reservados para el traspaso de servicios en curso [4], [5], [6]. La posibilidad de realizar un ajuste automático de estos parámetro supone una adaptación más rápida y eficiente. Esta capacidad de adaptación del sistema [7] a las necesidades de los usuarios determina, en un grado muy elevado, la habilidad del operador tanto en responder a la demanda de los usuarios como en la adaptación a las condiciones del entorno. Los sistemas existentes se clasifican en dos grupos: el primer grupo consiste en aquellos algoritmos que basa su funcionamiento en el aprendizaje del sistema; el segundo grupo se centra en optimizar la probabilidad de distribución del escenario. Este estudio propone la utilización de los algoritmos RL1 . Estos algoritmos permiten una adaptación del sistema basada en la experiencia obtenida, y por consiguiente, mecanismos adaptados según la demanda de los usuarios [8].
1
Véase apartado II de la sección 5
Aprendizaje por refuerzo multi-nivel para sistemas RRM
1.1.
2
Entorno de trabajo
El estudio se desarrolla en un entorno de programación Java. A partir de este entorno se simula el comportamiento, la operativa y el rendimiento de las estaciones consideradas en la simulación, así como el escenario dónde actúan. El escenario está basado en una cuadrícula. El tamaño de la cuadrícula depende en relación al número de estaciones a considerar en la simulación. De esta forma el entorno está adaptado al radio de actuación del conjunto de estaciones. En la Fig. 1.1 se muestra el efecto producido en un escenario con la participación de un conjunto de 9 estaciones. En la figura también se muestra la definición realizada de los ejes del escenario. Se observa que parte del área de cobertura, que es cubierta por las estaciones situadas al margen de la cuadrícula, se encuentra fuera del área dónde el movimiento de los usuarios es permitido. Deshabilitando estas zonas de conflicto se asegura que en cualquier punto un usuario es capaz de establecer una conexión con al menos una estación. El entorno a simular es un escenario ideal. Utilizando un escenario ideal se asegura que el comportamiento del sistema no se ve influenciado por las características del entorno. Cada estación puede estar bajo el control de más de un operador, compitiendo entre ellos por los recursos disponibles en la estación.
Figura 1.1: Ejemplo de un escenario con interactuación de 9 estaciones El comportamiento de los usuarios también es programado. Los usuarios siguen una trayectoria lineal, cuya velocidad es aleatoria al inicio de la simulación2 . Una vez iniciada la simulación la velocidad se mantiene constante. Los usuarios al llegar al extremo del escenario rebotan, cambiando el sentido de la velocidad respecto al 2
Existen dos componentes en la definición de la velocidad, Vx y Vy . Ambas componentes son aleatorias inicialmente.
Introducción
3
eje donde rebotan. Después siguen su trayectoria lineal con su nueva dirección3 . Respecto a la estadística de llamadas, todas las llamadas siguen una distribución de Poisson, tanto en la duración de la llamada como en el tiempo entre llamadas. De esta forma se consigue una estadística en las llamadas más parecida a la que se obtendría en un entorno real. Otro aspecto a tener en consideración es la estación a realizar la conexión. En los sistemas RRM implementados, se ha priorizado la conexión del usuario en las estaciones disponibles más próximas respecto a la posición actual de móvil.
1.2.
Objetivos
Entre los principales objetivos de este proyecto se encuentra crear un sistema capaz de aprender, sin ningún conocimiento previo, el comportamiento más óptimo para un operador. Estos sistemas actúan y aprenden sin la necesidad de intervención humana, convirtiéndose en sistemas completamente capaces de auto-ajustarse a las necesidades de la red. Crear un sistema de aprendizaje que no posea ninguna base de inicial sobre el caso de estudio, sugiere implementar un sistema de aprendizaje por refuerzo. Decidir los parámetros utilizados para la composición de estados o los parámetros modificables mediante acciones, determina el comportamiento del sistema completamente. Implementando una estructura diferente se obtendría un comportamiento totalmente distinto. El número de variables a considerar en un entorno de estas características es bastante amplio, aumentando su complejidad si no se consideran algunas de estas características de carácter no variable o despreciables para el estudio a realizar. En consecuencia, otro objetivo a tener en cuenta son las variables a ser consideradas como objetivo de aprendizaje por el algoritmo, y cuáles son consideradas constantes o despreciables4 . Para un operador, dos de las características más distintivas para gestionar un sistema RRM son la calidad ofrecida al usuario y el beneficio que obtiene el operador. Por ello el sistema se focalizará en obtener el máximo beneficio para el operador y ofrecer la máxima calidad posible al usuario. 3
El código que ejecuta esta rutina esta adjuntada en el apartado I de la sección 6 Al implementar un entorno ideal, las características especiales de los escenario reales no se consideran. 4
Aprendizaje por refuerzo multi-nivel para sistemas RRM
4
El estudio parte de un sistema EDC (Estados de División de Carga). Este sistema se basa en la utilización de un modelo RL. En la sección 2 el sistema EDC es evaluado y modificado para observar y analizar las variaciones producidas en su rendimiento. A partir de la observación de las incapacidades del algoritmo en el momento de maximizar los objetivos, la sección 3 propone el uso del sistema ARMUN (Aprendizaje por Refuerzo Multinivel). El sistema ARMUN mediante el uso del algoritmo FRL (Fuzzy Reinforcement Learning)5 en un sistema multinivel [9] mejora y solventa aquellas características que el sistema EDC no es capaz.
5
FRL surge de la combinación de los algoritmos RL y FL (Fuzzy Logic)
2. Sistema EDC 2.1.
Sistema inicial
El sistema EDC inicial se basa en una estructura centralizada1 . Esta estructura está compuesta de un conjunto de estaciones base a cargo de un agente controlador. Este agente implementa un algoritmo RL, Actor-Critic o Q-Learning2 . Cada operador dispone de un agente propio, de modo que las estaciones pueden llegar a ser controladas por múltiples operadores simultáneamente. Cada operador gestionará los parámetros controlados de la estación acorde a sus necesidades. Los estados del sistema EDC están referidos al nivel de carga del sistema, dada su estructuración centralizada los estados son referidos al sistema global, definiendo la carga del sistema como la media de la carga individual de todas las estaciones bajo el control del operador. En la Fig. 2.1 se relatan los estados de carga definidos para el sistema.
Figura 2.1: Esquema estado acción sistema EDC estático Baja Carga (carga inferior al 33 %): El sistema reduce el precio ofrecido a los usuarios. 1 2
Véase apartado I en la sección 5 Ambos algoritmos están formulados en el apartado II de la sección 6
Aprendizaje por refuerzo multi-nivel para sistemas RRM
6
Media Carga (carga entre el 33 % y el 66 %): El sistema escoge de forma aleatoria entre incrementar o reducir el precio. Alta Carga (carga superior al 66 %): El sistema incrementa el precio ofrecido a los usuarios. Con independencia del estado del sistema se realizará una modificación en el precio ofrecido. Reducir el importe en los estados de baja carga del sistema supone un reclamo para incrementar el número de clientes que solicitan un servicio. Análogamente detectando el sistema en alta carga no hay disponibles suficientes recursos para la demanda de los usuarios, lo que permite aumentar el precio ofrecido. En los usuarios se ha implementado un algoritmo de preferencia aleatorio. Este algoritmo dota a los usuarios con la capacidad de elegir de forma aleatoria el operador a conectarse. La probabilidad de conexión a un operador decrece proporcional al incremento de precio, de esta forma las estaciones que ofrecen un precio menor tienden a recibir más peticiones de servicios. Para que el sistema interactúe adecuadamente con el entorno, es indispensable definir una correcta función de refuerzo. La función de refuerzo debe incentivar un nivel de carga alto, lo que supondrá un mayor beneficio para el operador. Considerando la estructura definida para los estado del sistema, es equivalente a incentivar al sistema a conseguir situarse en el estado de alta carga3 .
2.1.1.
Resultados del sistema
El sistema ha sido probado para un entorno ideal donde existen dos estaciones. Dos operadores compiten entre ellos para dar servicio a los usuarios, uno de los operadores implementa el algoritmo Actor-Critic , el otro utiliza la metodología QLearning . Los resultados obtenidos4 para ambos operadores son mostrados en la siguiente tabla5 : Carga del Sistema Blocking Dropping QoS 3
Q-Learning Actor-Critic 36.4 % 29.2 % 29.8 % 40.4 % 69.6 % 69.4 % 3.082 3.18
El código de esta función de recompensa se encuentra en el apartado II de la sección 6 En los resultados no se considera ninguna función de beneficio, en su lugar se intenta obtener un nivel de carga alto. 5 La parámetros de configuración de la simulación son adjuntados en el apartado III de la sección 6 4
Sistema EDC
7
A partir de estos resultados se observa que la precisión del sistema es demasiado baja, resultando en un rendimiento excesivamente bajo del sistema. El rendimiento del operador utilizando una metodología Q-Learning es ligeramente superior al operador utilizando algorítmica Actor-Critic. El sistema Q-Learning, en estas condiciones, consigue un nivel de carga mayor, y por consiguiente un bloqueo del sistema inferior. No obstante, aun considerando las diferencias establecidas, ambos operadores consiguen un nivel de carga mucho menor de lo esperado. Considerando la definición de recompensa definido, un nivel de carga bajo significa un escaso beneficio para el operador. Mantener un nivel de carga más elevado requiere realizar acciones más precisas, esto sugiere una definición de estados del sistema más exhaustiva, suficientes como para mantener unos estándares de carga elevados. Por otra parte, al no existir ningún tipo de restricción para asegurar un mínimo de calidad, la calidad de servicio global6 es demasiado baja, esto supone que es necesario una incorporación de restricciones respecto a la calidad ofrecida para poder incrementarla.
2.2.
División de estados y consideración de la calidad de servicio
Partiendo de los resultados obtenidos en el apartado anterior, se realizan modificaciones acorde con las observaciones realizadas. En primera instancia se tratará la precisión de los estados, después se incorporará las restricciones para la mejora de la calidad de servicio.
2.2.1.
Metodología de división
Aumentar la precisión del sistema conlleva definir un mayor número de estados. A mayor número de estado definidos más precisa es la acción que se puede realizar. No obstante, para implementar un sistema RL es necesario un cierto tiempo de procesado, a mayor número de estados definidos mayor es el tiempo y capacidad de procesado requerido. Para poder observar la mejora al realizar una división de estados, el sistema se inicializará con la configuración de estados definida en el apartado anterior. Al 6
La calidad de servicio se rige por la ec. 2.2
Aprendizaje por refuerzo multi-nivel para sistemas RRM
8
transcurrir un cierto tiempo, el sistema se divide formando dos nuevos estados de cada estado ya existente. Cada nuevo estado dispondrá de la experiencia obtenida por su estado generador. Al mismo tiempo, cada nuevo estado podrá realizar una acción diferente a la que realizaba su predecesor. Este esquema de división puede ser observado en la Fig. 2.2. Aunque la acotación para generar cada estado es diferente a la de su predecesor, y las acciones disponibles pueden ser distintas, el objetivo global no varía. Este hecho facilita la inserción y cohesión del aprendizaje de la estructura antigua en la nueva. Una vez este conocimiento es adquirido por la nueva estructura, mediante entrenamiento los parámetros de su aprendizaje se van adaptando a la nueva estructura. En contrapartida, un número muy elevado de estados puede inducir al sistema a oscilar entre dos o más estados similares7 , incitando un aprendizaje erróneo del sistema respecto a la situación real.
Figura 2.2: Esquema de divisionamiento de estados En una división, el rango de activación de un nuevo estado es la mitad de su progenitor, de forma que el conjunto de nuevos estados deben abarcar el mismo rango que su predecesor. Un inconveniente de realizar una división de estados, radica en como definir las acciones a realizar en cada uno de los nuevos estados. Una acción no acorde con las características de su estado puede provocar un desajuste entre sistema y entorno, y por consiguiente una aprendizaje erróneo. La metodología de actuación del estado dividido es la misma que su predecesor, por consiguiente, el proceso de decisión de acciones se puede automatizar aplicando 7
Estados similares son aquellos que su rango de definición difiere mínimamente
Sistema EDC
9
una acción acorde al estado actual. En el sistema de estudio se automatiza la modificación que sufre el precio referente al estado actual del sistema, el incremento proporcionado por cada estado es el mostrado en la ec. 2.1. ∆estado = ∆nominal ∗ (
num_estados 2 ) num_estados 2
estado −
= ∆nominal ∗ (
2 ∗ estado − 1) num_estados
(2.1)
∆estado es la variación producida por estar en el estado actual8 . ∆nominal es la variación de base, definida por el operador, indicando el incremento o decremento en el precio permitido por el sistema en una sola iteración. Automatizar las acciones a realizar provoca que una división de estados demasiado extensa, además de posibilitar estados similares, posibilita la existencia de acciones similares. De modo que dos estados consecutivos pueden producir el mismo efecto sobre el entorno. Por este motivo, y para poder comparar las ventajas que provoca una división de estados automatizada, solo se permitirá una división durante la simulación.
2.2.2.
Incorporación de la calidad de servicio
Para poder realizar una priorización correcta del tipo de servicio sería necesario incluir como variables de creación de estados los valores de blocking9 y dropping10 del sistema. Para un sistema RL el hecho de definir tres entradas como variables de creación supondría un número de estados bastante más elevado incrementando así la complejidad del algoritmo. Además de analizar la complejidad adicional que supone incrementar el número de variables de entrada, realizar un aumento en la precisión requiere considerar que efecto produciría definir de una forma más exhaustiva cada variable sobre las otras, y finalmente el impacto que provocaría la nueva definición de las acciones sobre el entorno al realizar la división. La definición de calidad de servicio (QoS) de una estación base se relaciona con su porcentaje de blocking y dropping. Actualmente ningún estándar regula como determinar rigurosamente la calidad de servicio para un sistema RRM, por consiguiente, cada operador puede realizar una interpretación diferente dependiendo del carácter de su gestión. 8
Los estados son numerados incrementando su número a medida que crece la carga, este efecto es indicado en la Fig. 2.2 9 Blocking: incapacidad de establecer una llamada de nueva entrada 10 Dropping: incapacidad de gestionar una llamada traspasada entre estaciones
Aprendizaje por refuerzo multi-nivel para sistemas RRM
10
En las interpretaciones de la QoS usualmente se considera que produce un mayor deterioro la incapacidad de la gestión del traspaso de un servicio entre estaciones comparado con el hecho de no poder establecer un nuevo servicio. Para facilitar el análisis del conjunto, se considera que todos los operadores y estaciones se rigen bajo la definición descrita en la ec. 2.2 . QoS = 4 · Dropping + Blocking
(2.2)
Esta interpretación de la función de calidad debe incorporarse en la función de refuerzo. Adicionalmente para facilitar la comparación del sistema se propone que esta función cumpla las siguientes premisas: Cuando el sistema detecte un óptimo de calidad (QoS = 0), la recompensa obtenida es idéntica a la obtenida en el caso del sistema inicial11 . Ofreciendo la mínima calidad posible (PBLOCKIN G = 1; PDROP P IN G = 1 → QoS = 11), la recompensa es nula. Siguiendo las premisas anteriores es propuesta la función de recompensa expuesta en la ec. 2.312 .
revenue = −
2.2.3.
revenueinicial QoS + revenueinicial 11
(2.3)
Resultados del sistema
Se realiza nuevamente el estudio incorporando las modificaciones propuestas para el sistema. De la simulación se han obtenido los siguientes resultados13 : Q-Learning Actor-Critic Carga del Sistema 85.6 % 87.4 % Blocking 56.5 % 57.4 % Dropping 3.47 % 3.85 % QoS 0.7238 0.728 Aplicando una división de estados conjuntamente con una función de refuerzo considerando la calidad de servicio, se logra alcanzar una carga en el sistema mucho más elevada, y por ende un mayor beneficio para el operador. 11
Esto es posible dada la estructura de la función de calidad, cuán menor su valor numérico mejor es la calidad ofrecida. 12 La nomenclatura utilizada en la ec. 2.3 es la expuesta en el apartado II de la sección 6. 13 La parámetros de configuración de la simulación son adjuntados en el apartado IV de la sección 6
Sistema EDC
11
Por otra parte, aunque el ratio de blocking se mantiene en un valor elevado, obtener un bajo ratio de dropping supone una gran mejora en términos de calidad comparado con la obtenida en la estructura anterior. Con este hecho se demuestra la efectividad que produce considerar el parámetro QoS en la función de refuerzo. Aunque los resultados empiezan a mostrar indicios de un correcto funcionamiento del sistema, en entornos RRM reales no se puede permitir una carga del sistema superior al 80 % de su capacidad. Al sobrepasar el 80 % de la carga empiezan a aparecer efectos de saturación debidos a la congestión del sistema. Por otra parte, es necesario considerar la existencia de canales especializados o reservados para ciertos servicios, de esta forma se pueden realizar estrategias más óptimas mejorando tanto el comportamiento del sistema como la calidad ofrecida al usuario. Para realizar un análisis de la carga es necesario conocer los niveles en cada estación de forma individual. Utilizando un sistema centralizado no es posible controlar de forma individual la carga del sistema para que no supere un umbral, puesto que los datos del sistema corresponden a la media del conjunto de estaciones. Para realizar los cambios necesarios en cada una de las estaciones es preciso implementar un sistema distribuido14 .
2.3.
Sistema distribuido
Se implementará el sistema realizado con anterioridad para la estructura centralizada en cada una de las estaciones. El agente encargado de realizar el algoritmo deja de controlar un conjunto de estaciones simultáneamente, en su lugar controla únicamente una estación [10]. La actuación de cada agente continuará basándose en la modificación del precio ofrecido, puesto que existe un agente en cada una de las estaciones disponibles, cada estación podrá ofrecer un precio diferente aunque sea del mismo operador. El hecho de que cada estación ofrezca un precio diferente no produce ningún conflicto. Aun existiendo la preferencia de conexión a estaciones con el menor precio, es más prioritario para el usuario la conexión a estaciones más próximas. De este modo el terminal del usuario en el momento de realizar una conexión ordena las estaciones por orden de proximidad. Una vez decidida la estación más cercana, aplica el algoritmo de preferencia por coste15 . En caso de no existir recursos disponibles en la estación se repite el proceso decidiendo la siguiente estación más próxima. 14 15
Véase apartado I de la sección 5. Algoritmo explicado en el apartado 2.1
Aprendizaje por refuerzo multi-nivel para sistemas RRM
2.3.1.
12
Gestión de carga
A partir del análisis realizado con anterioridad se ha propuesto un sistema de gestión de carga. Esta gestión solo permite utilizar hasta un 80 % de la capacidad disponible. De la carga útil, un cierto número de canales deben ser reservados para servicios especiales. En la Fig. 2.3 se observa gráficamente la gestión de carga realizada en cada una de las estaciones. Sobrepasar el 60 % de la carga imposibilita establecer nuevos servicios, por tanto estos serán bloqueados. El nivel de carga a partir del cual se empieza a hacer distinción entre los diferentes tipos de servicio se denomina threshold (señalado en la Fig. 2.3). Este nivel puede realizarse de manera dinámica para una mejor adaptación al entorno, sin embargo, para realizar una correcta comparación entre sistemas se ha mantenido constante al 60 % de la capacidad.
Figura 2.3: Esquema de gestión de las llamadas según la carga
2.3.2.
Resultados del sistema
De forma similar a los casos anteriores es comparado el funcionamiento de los algoritmos en un entorno ideal con dos estaciones en funcionamiento y dos operadores en cada una de las estaciones. A diferencia de los casos anteriores, en este caso se muestran los resultados obtenidos en ambas estaciones16 : 16
La parámetros de configuración de la simulación son adjuntados en el apartado V de la sección 6
Sistema EDC
13
Q-Learning Actor-Critic estación 1 estación 2 estación 1 estación 2 Carga del Sistema 60.1 % 55.7 % 63 % 62.9 % Blocking 53.64 % 62.5 % 61.5 % 45 % Dropping 7.02 % 6.51 % 6.51 % 6.85 % QoS 0.8172 0.8854 0.8757 0.725 Con el uso del sistema distribuido, se confirma que la calidad de servicio ofrecida, así como la carga, es diferente en cada una de las estaciones controladas. Si se compara los resultados con el sistema del apartado 2.2 se observa que la carga del sistema ha disminuido aproximadamente un 20 %, un hecho aceptable dado que su carga útil se ha visto reducida en ese mismo porcentaje. Respecto a la calidad ofrecida, el ratio de llamadas bloqueadas se mantiene, pero a consecuencia de un ligero aumento en la tasa pérdidas. Mantener constante la tasa de bloqueo a costa de aumentar la tasa de pérdidas indica que el sistema no prioriza adecuadamente.
2.4.
Análisis del sistema EDC
Realizar una correcta optimización de una función depende del número de parámetros a maximizar en la función. A mayor número de parámetros existentes en una función, menor es el grado de optimización que se puede conseguir en estos parámetros. A fin de conseguir una priorización más adecuada, y en consecuencia maximizar más apropiadamente los parámetros relacionados con la función de refuerzo, es conveniente dividir los parámetros en varias funciones. La solución propuesta para dividir los parámetros son dos funciones de refuerzo. Para ello es requerido un sistema de cooperación entre dos agentes [11]. Cada agente está a cargo de maximizar uno de los siguientes objetivos: beneficio del operador o calidad de servicio ofrecida. En la sección 3 se explica en profundidad el funcionamiento del sistema realizado para realizar un sistema de cooperación entre agentes. Por otra parte, aplicar divisiones de los estados de forma continuada para aumentar su precisión requiere cada vez más capacidad de procesamiento. Además, cada división realizada precisa un reaprendizaje para la nueva parametrización del sistema aún incorporando el aprendizaje adquirido por la estructura progenitora. Por ello se propone sustituir la metodología de división de estados por el uso del algoritmo FRL17 [12], [13]. 17
Véase el apartado IV de la sección 5
Aprendizaje por refuerzo multi-nivel para sistemas RRM
14
Un algoritmo FRL dota al sistema de una precisión mayor sin necesidad de dividir los estados, dado que el sistema FRL no requiere de una discretización de las entradas previa, sino que la propia categorización de las variables de entrada está considerado dentro del algoritmo. El hecho de realizar la clasificación de las variables de entrada como parte del algoritmo, permite a este trabajar con variables de carácter continuo. Trabajar con variables continuas en lugar de variables discretas proporciona un grado de precisión mucho más elevado en el sistema.
3. Sistema ARMUN La cooperación entre ambos agentes se realiza mediante una estructura multinivel. En esta estructura ambos agentes están interconectados de forma que solo uno de ellos es capaz de realizar modificaciones en el entorno, el agente restante está limitado a modificar las variables de entrada del primer agente. Permitiendo que solo un agente sea capaz de actuar sobre el entorno evita que se produzcan modificaciones incompatibles o contradictorias y por tanto que no se produzcan desajusten en el entorno. Una de las motivaciones más importantes para que el sistema sea implementado en un entorno real se basa en que el sistema sea rentable para el operador. Por este motivo, el agente a cargo de realizar las modificaciones en los parámetros del entorno es el agente que su función de refuerzo maximiza el beneficio del operador. De esta forma se pretende que la decisión final tomada asegure la rentabilidad del sistema. En consecuencia, el agente a cargo de maximizar la calidad no es capaz de modificar el entorno. Sus decisiones son limitadas a modificar las variables de entrada del agente de beneficio. Similar a la estructura EDC, las variables a considerar en el entorno serán la carga del sistema, y la calidad. Para una mayor exactitud en el momento de determinar la calidad, en lugar de considerar directamente como entrada una definición de calidad, se utilizarán como entrada los valores de blocking y dropping de la estación. El nivel de carga, por sí solo, no tiene relación con la calidad ofrecida, en cambio, es un factor muy importante a tener en cuenta para el cálculo del beneficio. Por todo ello, el nivel de carga de la estación se incorpora como una variable de entrada en el agente encargado de optimizar el beneficio. Resultando en dos fuentes de información para el agente de beneficio, por una parte, desde el entorno se recibe la información de la carga del sistema. Por otro se reciben las decisiones de la capa de calidad. En la Fig. 3.1 se muestra gráficamente la relación entre agentes y entorno.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
16
Figura 3.1: Relación agentes-entorno El funcionamiento de ambos algoritmos está basado en los modelos de aprendizaje por refuerzo, lo que supone que la información recibida como entradas no es suficiente. Los algoritmos de aprendizaje por refuerzo requieren de información adicional referente al entorno para computar la función de refuerzo, y así calcular la recompensa obtenida por las acciones tomadas. Cada agente tiene su propia función de refuerzo, en la que ha de maximizar su objetivo. Con la interconexión se intentan maximizar ambos objetivos simultáneamente. En la Fig. 3.2 se observa el esquema de relación agentes-entorno considerando que los agentes utilizan algoritmos basados en aprendizaje por refuerzo.
Figura 3.2: Relación agentes-entorno utilizando aprendizaje por refuerzo En la sección anterior se ha comprobado que la modificación del precio ofrecido en un estructura distribuida es una acción poco coherente. Realizar esta acción permite en estaciones adyacentes del mismo operador ofrecer precios diferentes.
Sistema ARMUN
17
Permitir una modificación del precio ofrecido global implica crear una estructura diferente, la cual tenga en cuenta no solo la relación entre capas sino también la relación entre estaciones [14]. Incorporar una estructura global en el modelo, incrementaría notablemente la complejidad del sistema y supondría una modificación completa de la estructura realizada hasta ahora, por lo cual no se permitirá a los operadores la modificación del precio ofrecido en ninguna estación bajo su control. Puesto que la modificación del precio ofrecido no es permitida, se dota al operador con la capacidad de alterar la potencia de emisión [15]. Mediante la modificación de la potencia de emisión se consigue variar el radio de cobertura de la estación bajo control. Controlando el alcance de la estación se puede aumentar o disminuir el número de usuarios capaces de acceder a la estación. Adicionalmente se dota a la estación base con un conjunto de canales1 [16], [17]. Estos canales están a disposición de los operadores que actúan en la estación, permitiendo su adquisición para uso del operador en caso de necesidad. Siguiendo la definición realizada en el apartado 2.3.1, existen diferentes tipos de servicio que pueden ser tratados de forma diferente. Esta separación de los canales en distintos tipos de servicios se realiza mediante un nivel denominado threshold2 . A partir de este nivel se indica el porcentaje de canales reservados para cada tipo de servicio. A continuación se procede a explicar los distintos niveles implementados en el sistema, en el apartado 3.1 se explica el funcionamiento del nivel de calidad, en el apartado 3.2 se detalla el funcionamiento del nivel de beneficio. Por último en los apartados 3.3 y 3.4 se detallan los resultados obtenidos por el algoritmo.
3.1.
Nivel de calidad de servicio
Este nivel recibe la información directamente del entorno, en concreto, recibe como variables de entrada los ratios de blocking y el dropping de la estación. Estos datos son procesados por un algoritmo FRL para maximizar la calidad de servicio ofrecida al usuario. Dedicando el nivel exclusivamente a maximizar la calidad ofrecida al usuario, puede incorporarse una función de calidad más exhaustiva que la realizada en el apartado 2.2. La nueva relación puede establecerse según unos márgenes de calidad 1
Los canales son los recursos disponibles por la estación base para realizar la comunicación (time slots, frecuencias asignadas,...) 2 Este nivel es mostrado en la Fig. 2.3.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
18
determinados, de forma que el algoritmo es incentivado a cumplir esos objetivos, denominados target, mostrados en la ec. 3.1.
fobj = (targetblocking − Blocking) + β ∗ (targetdropping − Dropping).
(3.1)
Las entradas no son únicamente tratadas como variables a optimizar en la función de refuerzo. Estas entradas también son utilizadas como variables para la creación de estados. Ambas entradas son evaluadas siguiendo el esquema de la Fig. 5.6, una vez adquiridas deben ser catalogadas, cada entrada debe ser clasificada de forma individual. La clasificación realizada divide cada parámetro de entrada (blocking y dropping) en seis categorías. Las categorizaciones de las entradas son mostradas en las Figs. 3.4 y 3.3. Acorde con el modelo definido en la Fig. 5.6, la cual detalla el funcionamiento de la lógica difusa, una vez realizada la clasificación de la entradas es necesario evaluar cada una de las categorías disponibles según una serie de reglas. Las 36 posibles categorías resultantes3 son evaluadas siguiendo 5 reglas4 .El esquema de evaluación seguido es mostrado en la Fig. 3.5. En esta figura se muestra la procedencia de cada una de las categorías resultantes. El conjunto de reglas esta realizado de modo que observando los valores que obtienen cada una de estas reglas se obtenga una idea de la calidad de servicio que se ofrece al usuario.
3 4
En la Fig. 3.5 las 36 categorías son mostradas en color gris En la Fig. 3.5 las 5 reglas son mostradas en color negro
Sistema ARMUN
19
Figura 3.3: Categorización del nivel de dropping
Figura 3.4: Categorización del nivel de blocking
Aprendizaje por refuerzo multi-nivel para sistemas RRM
20
Figura 3.5: Matriz de reglas Una vez realizada la evaluación en las categorías, el resultado es procesado por el algoritmo RL5 . Una vez realizado el procesado, se combinan los pesos de las acciones con las reglas obtenidas, consiguiendo un nuevo vector denominado action elegibility. Este nuevo parámetro determina la elegibilidad de cada regla respecto a las entradas actuales. Existen tres acciones asociadas a cada parámetro del vector: incrementar o reducir handover (HO); incrementar o reducir el área de cobertura (CA) y adquirir o liberar un canal (CH). Cada una de las acciones tiene su propio peso en cada una de las acciones, esta relación entre acciones y reglas se observa en la Fig. 3.6.
Figura 3.6: Pesos de las acciones asociadas a las reglas 5
Véase apartado IV de la sección 6
Sistema ARMUN
21
Los valores mostrados en la Fig. 3.6 son elegidos experimentalmente, buscados para forzar al sistema a tomar la mayor diversidad de acciones posibles. Los valores obtenidos se suman obteniendo un único vector de tres componentes, denominado vector de decisión. Este vector contiene los parámetros finales decididos por la capa de calidad. El vector de decisión es enviado al siguiente nivel, la etapa de beneficio, formando parte de sus parámetros de entrada. De este modo, la decisión obtenida por el agente de calidad es reevaluada por el nivel de beneficio determinando las acciones que puede tomar la capa de beneficio.
3.2.
Nivel de beneficio
Este nivel maximiza el beneficio para el operador captando la información necesaria de dos fuentes. La primera fuente de información procede directamente del entorno, el cual proporciona información sobre el nivel de carga del sistema. La otra fuente de información proviene del nivel de calidad de servicio, recibiendo como entradas el vector tridimensional de conclusiones que ha realizado. Centrándose exclusivamente en maximizar el beneficio del operador, permite que la función de refuerzo tenga relación con las variables que aporten más beneficio. Los factores que más destacan en el momento de calcular el beneficio de un operador son: los canales en posesión; carga en el sistema; precio ofrecido, coste de mantenimiento por canal y duración de la llamada. Con el fin de evitar complicaciones adicionales en la función de refuerzo se considera que el usuario no paga un coste adicional proporcional a la duración de la llamada, tampoco existe un coste adicional en el momento de adquirir o liberar un canal. En la ec. 3.2 se observa la función de refuerzo propuesta a partir de los factores nombrados con anterioridad. Carga x P recio x Canales en posesi´ on − Coste x Canales en posesi´ on (3.2) Duraci´ on de la llamada Siguiendo la metodología explicada en el nivel de calidad, se sigue aplicando el modelo estructural mostrado en la Fig. 5.6. El primer paso de esta estructura se basa en categorización de las entradas. fobj =
La categorización de la carga del sistema determina el nivel de saturación de la estación base. En la Fig. 3.7 se observa que el nivel de carga se divide en tres niveles: baja carga, media carga y alta carga.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
22
Figura 3.7: Clasificación de la carga del sistema Teniendo en consideración las características comentadas en el apartado 2.3.1 si la carga del sistema supera el 80 % puede ocasionar un malfuncionamiento de la estación. Por ello se intentará que el nivel de carga se encuentre prioritariamente en el nivel denominado “media carga”. Respecto al vector tridimensional proporcionado por el nivel de calidad cada componente se clasifica individualmente. De modo que cada componente del vector proporciona sus propias categorías. Para facilitar el futuro uso de estas categorías en las reglas, el nombre de las categorías es el mismo que la regla destino. La componente del área de cobertura (CA) del vector de decisión se clasifica en dos categorías, mostradas en la Fig. 3.8. Estas categorías son: Reducir área de cobertura y aumentar el área de cobertura. Entre ambas categorías se determina el grado de modificación necesario del área de cobertura que es requerido según la etapa del nivel de calidad.
Sistema ARMUN
23
Figura 3.8: Clasificación del vector de decisión: Coverage area La componente adquisición de canales (CH) del vector de decisión es clasificado en una única categoría: adquirir un canal. En la Fig. 3.9 se observa como esta categoría es directamente proporcional al valor de la entrada. Este hecho se debe a que la adquisición de canal no tiene ninguna otra acción substituible.
Figura 3.9: Clasificación del vector de decisión: Demanda de canal La componente threshold (HO) del vector de decisión es la entrada que más se diversifica. Como es mostrado en la Fig. 3.10 se clasifica en cinco clases: Reducir reserva de canal, incrementar reserva de canal, adquirir un canal, reducir área de cobertura y aumentar área de cobertura.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
24
Reducir y aumentar threshold son proporcionales a la entrada de la variable, este parámetro no es contemplado en el momento de computar el beneficio del operador y son variables necesarias para el control de calidad. No obstante, la reserva de canal indica las necesidades del operador para satisfacer las demandas de los usuarios. Puesto que se incita al sistema a realizar modificaciones de forma continuada en el entorno, si no se requiere de modificaciones del valor del threshold supone una situación de poca exigencia en el sistema, por consiguiente es posible dar servicio a un mayor número de clientes, lo que supone aumentar la cobertura. En caso de que el valor de este threshold necesite ser aumentado en mayor medida significa que el sistema tiene muchas peticiones de servicios nuevos, aumentando este nivel puede ser insuficiente para satisfacer la demanda, por ello también se intenta adquirir un canal nuevo. En caso contrario, si este nivel es muy bajo significa que hay muchas llamada provenientes de handover, para disminuir el número de llamadas de handover se reduce el área de cobertura activa6 de la estación base.
Figura 3.10: Clasificación del vector de decisión: Threshold Siguiendo el esquema propuesto en la Fig. 5.6, una vez las entradas han sido clasificadas se procede a su evaluación mediante reglas. A partir del esquema de la Fig. 3.11 se observa que el número total de reglas existentes en el nivel de beneficio son 6. Como se ha mencionado anteriormente, para facilitar la implementación del sistema, el nombre de las categorías coincide con el de la reglas, y cada regla tendrá una única acción aplicable, siendo la acción aplicable definida por el nombre de la regla. 6
Al reducir el área de cobertura se consigue que el solapamiento entre estaciones sea menor, lo que reduce y retrasa el traspaso de servicios entre estaciones.
Sistema ARMUN
25
En cada una de las 6 reglas será añadido el valor de las categorías cuyo nombre coincide. Sin embargo, existen categorías complementarías, lo que provoca una anulación entre ellas. Para conseguir que todas las acciones tengan probabilidad de realizarse, las reglas que tienen solo una categoría no se les aplica la política de anulación, puesto que su ritmo de crecimiento es más lento que las demás reglas.
Figura 3.11: Reglas del nivel de beneficio Dado que estas reglas tienen asociada una única acción se ha implementado un mecanismo basado en parámetros de control. Este mecanismo desactiva aquellas reglas que su acción no puede realizarse en el entorno. Los parámetros de control son las siguientes: Activar regla “incrementar threshold”: Si el valor del threshold es inferior al 80 %. Este valor viene dado por el 20 % de carga libre necesario para evitar saturaciones en el sistema. Activar regla “disminuir threshold”: Si el valor del threshold es superior a 20 %. Se debe disponer de un mínimo número de canales para establecer llamadas de nuevo servicio. Activar regla “incrementar área de cobertura”: El área de cobertura es inferior a la distancia entre estaciones.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
26
Activar regla “reducir el área de cobertura”: El área de cobertura es superior al 75 % de la distancia entre estaciones. Se debe garantizar un solapamiento entre áreas de cobertura de las estaciones para asegurar que en cualquier punto del escenario un usuario tiene acceso como mínimo a una estación. Activar regla “adquirir un canal”: Existe un canal disponible en la estación base. Activar regla “liberar un canal”: El operador dispone de un mínimo de 3 canales. El operador debe ofrecer unos servicios mínimos. El valor mínimo de una regla no puede ser menor que 0: Asegurar que todas las acciones pueden llegar a realizarse. Una vez realizada la evaluación y categorización de las entradas mediante lógica difusa representado por el esquema de la Fig. 3.11, los valores de estas reglas son procesados por el algoritmo RL para obtener la acción a ser tomada. Para evitar realizar sobre acciones en el entorno se implementa un tiempo entre acciones. Este tiempo entre acciones prohíbe al sistema actuar si no se cumple unos ciertos requisitos de tiempo definidos por el operador, permitiendo que el algoritmo determine correctamente que efecto produce sobre el entorno las acciones tomadas y no provoque un mal funcionamiento del sistema debido a estas sobreactuaciones. Por último, los valores de entrada procedentes del entorno (blocking, dropping y carga del sistema), por definición, son resultado de realizar una media. El intervalo de tiempo considerado para realizar esta media está relacionada con una ventana temporal deslizante. El tamaño de esta ventana determina la respuesta del sistema. En la Fig. 3.12 se muestra el efecto de la anchura de las ventanas deslizantes sobre una entrada periódica7 . A partir de la Fig. 3.12 se observa que, para la señal de ejemplo, una ventana de anchura de 100 muestras produce una perdida en la estadística de la señal, obteniendo como resultado una señal prácticamente uniforme. Una distribución uniforme en la entrada induce al sistema a realizar pocas modificaciones. Utilizando una ventana con anchura de 1 muestra (input) se obtiene una señal cuyos picos son bastante pronunciados, pudiendo provocar acciones contradictorias, provocado por estar en estados contradictorios, en los instantes que la señal de entrada toma valores de picos complementarios, dificultando así el aprendizaje del sistema. 7
El valor de la entrada está fijado a modo de ejemplo. Sus valores no están relacionados con el trabajo.
Sistema ARMUN
27
Dado este efecto, y teniendo en consideración los objetivos del sistema, encontrar una correcta relación anchura de ventana y tiempo entre acciones es fundamental para un óptimo funcionamiento del sistema.
Figura 3.12: Ejemplos de ventanas deslizantes
3.3.
Resultados de un único operador funcionando en el entorno
Para probar el funcionamiento del sistema se implementa un entorno con un conjunto de 9 estaciones como se muestra en la Fig. 3.13. Las 9 estaciones están bajo el dominio de un único operador, de esta forma el comportamiento del sistema no se ve alterado por la intervención de ningún otro sistema en el entorno, posibilitando observar su comportamiento ideal. Dada la estructura del entorno, se centralizará el estudio del sistema sobre la estación central de la cuadrícula de 9 estaciones diseñada. La estación central es de especial interés debido a que es la única que no tiene parte de su área de cobertura mermada8 , y adicionalmente esta estación es la que tiende a sufrir más tránsito, tanto debido por servicios de nueva creación y/o debido a servicios procedentes de otras estaciones base. 8
Se merma el área de cobertura para garantizar en todo momento un usuario puede establecer conexión, deshabilitando las áreas de conflicto no se permite el movimiento de usuarios.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
28
Puesto que el entorno es modificado dependiendo de la actuación del sistema global entraña una complicación añadida. El comportamiento de los usuarios varia en dependencia de las acciones tomadas por cada estación10 . La incierta modificación del comportamiento de los usuarios comporta que las estaciones no sufran la misma carga dependiendo del comportamiento del sistema global. Para realizar una correcta comparación, se utilizan simulaciones equivalentes. Se consideran equivalentes cuando la estación central sufre aproximadamente la misma demanda de todos los tipos de servicios en todos los sistemas a testar. 9
Figura 3.13: Entorno del sistema a simular Para facilitar la notación en los gráficos, a la combinación de algoritmos de aprendizaje se le denota con dos letras correlativas. La letra situada a la izquierda representa el algoritmo de aprendizaje asociado al nivel de beneficio, la letra situada a la derecha representa el algoritmo asociado al nivel de calidad. El significado de las letras es el siguiente: la letra “A” corresponde a que el nivel en cuestión utiliza un algoritmo basado en la metodología Actor-Critic; la letra “Q” significa que el nivel en cuestión implementa un algoritmo basado en la metodología Q-Learning; por último la letra “N” se refiere a que el nivel asignado implementa un algoritmo basado en una metodología Non-Learning, es decir, de no aprendizaje. 9
Sistema global se refiere al conjunto de las 9 estaciones e.g. El bloqueo de una llamada en una estación provoca una estadística diferente en el entorno y estaciones a la que produciría la misma llamada siendo aceptada por la estación 10
Sistema ARMUN
29
La metodología Non-Learning consiste en utilizar la estructura relatada en la Fig. 5.6, una vez realizada la evaluación en lugar de disponer de un algoritmo RL para decidir la acción más conveniente a realizar se selecciona la acción mediante la algorítmica ε -Greedy11 . Los parámetros del sistema12 están calibrados para conseguir que los operadores requieran los canales disponibles en la estación base obteniendo una carga media del 40 % aproximadamente13 . Teniendo en consideración el esquema detallado por la Fig. 3.7, se observa en la Fig. 3.14 que todos los sistemas implementados son capaces de mantener un nivel de carga medio. No obstante, se puede determinar que los sistemas que emplean una metodología Actor-Critic en el nivel de calidad tienden a disminuir ligeramente su nivel de carga respecto a los otros sistemas, mientras que los que utilizan un algoritmo Q-Learning en el nivel de calidad mantienen un nivel de carga más elevado.
Figura 3.14: Carga de los canales en posesión En la Fig. 3.15 se observa el porcentaje de canales adquiridos de la estación base. Los sistemas adquieren prácticamente en su totalidad los canales a su disposición a excepción de los algoritmos “NN” y “AN”, los cuáles adquieren un número bastante 11
Aplicar el algoritmo Non-Learning es equivalente a aplicar un proceso basado únicamente en lógica difusa 12 La parámetros de configuración de la simulación son adjuntados en el apartado VI de la sección 6 13 El valor del 40 % corresponde al valor de pico de la categoría “media carga” correspondiente a la entrada “carga del sistema”
Aprendizaje por refuerzo multi-nivel para sistemas RRM
30
inferior de canales comparado con los otros sistemas.
Figura 3.15: Adquisición porcentual del número de canales disponibles Parte de los canales obtenidos son dedicados a servicios especiales. La Fig. 3.16 muestra el porcentaje de canales dedicado a estos servicios. Todos los sistemas empiezan con un valor inicial de este threshold del 60 %, su límite viene dado por las reglas de control. Estas reglas de control imponen que el valor de este umbral no pueda sobrepasar el 80 % ni ser inferior al 20 %. Cabe destacar que en los sistemas cuyo nivel de calidad opera con la metodología Non-Learning, el valor del umbral no es modificado. Indicando que estos sistemas no consideran necesario adaptar su estructura a los diferentes tipos de servicios existentes. En el caso de estudio estos servicios son: llamadas de nuevo servicio y traspasos de servicios entre estaciones (handover). Los algoritmos restantes modifican este valor, manteniendo el umbral alrededor del 50 %, suponiendo una reserva del mismo número de canales para los dos tipos de servicio.
Sistema ARMUN
31
Figura 3.16: Threshold promedio de los canales en posesión En el área de cobertura se permite un máximo aumento del 25 % respecto su radio inicial. En la Fig. 3.17 se representa el incremento porcentual del área de cobertura. Se observa que los algoritmos que implementan un sistema “Non-learning” en el nivel de calidad no consideran prioritario el aumento del área de cobertura. Los algoritmos restantes permiten un cierto aumento de su área de cobertura, no obstante, los sistema cuyo nivel de calidad implementan un algoritmo Actor-Critic tienden a aumentar más este área comparándolo con los sistemas que utilizan la metodología Q-Learning en ese mismo nivel.
Figura 3.17: Incremento porcentual del área de cobertura
Aprendizaje por refuerzo multi-nivel para sistemas RRM
32
Para realizar una medición de la calidad de servicio al usuario se detallan tres parámetros: ratio de blocking, ratio de dropping y QoS mediante la definición de la función de refuerzo mostrada en la ec. 3.1. El ratio de blocking y dropping mostrados conjuntamente en la Fig. 3.18 detalla que los únicos algoritmos que permiten un cierto porcentaje de dropping14 son aquellos que implementan un algoritmo Actor-Critic en el nivel de calidad. A excepción de la combinación “‘QA”, esta combinación sobrepasa el limite de blocking dado que no es capaz de gestionar correctamente los recursos, en un intento de mantener la mejor calidad de servicio posible prioriza el bloqueo de llamadas frente a la perdida de llamadas. Los demás algoritmos no permiten que exista dropping en su sistema, incluso a coste de rebasar la tasa de bloqueo objetivo.
Figura 3.18: Porcentaje de Blocking y Dropping Según la medida de QoS mostrada en la Fig. 3.19, los sistemas que superan los objetivos de blocking ofrecen una calidad de servicio peor que los sistemas que se mantienen fieles a los objetivos.
14
En la función de refuerzo del nivel de calidad se penaliza cuádruple el dropping al blocking
Sistema ARMUN
33
Figura 3.19: Calidad de servicio ofrecida al usuario El beneficio obtenido por el operador es observado en la Fig. 3.20. Similar a la gráfica de QoS es considerado como definición de beneficio la descripción realizada en la función de refuerzo mostrada en la ec. 3.2. A partir de estos resultados se comprueba que la combinación “QQ” consigue un mayor beneficio para el operador, debido en gran medida a la adquisición de un nivel de carga mayor con un número de canales ligeramente superior a los otros sistemas. Puesto que los sistemas adquieren prácticamente la totalidad de los canales disponibles, el coste de mantenimiento de estos es muy similar para todos, provocando que el beneficio repercuta en la carga del sistema y el número de canales obtenidos.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
34
Figura 3.20: Relación beneficio-coste del operador
3.3.1.
Análisis de los resultados individuales
De este apartado se puede determinar que el nivel de calidad de servicio produce un gran efecto en el comportamiento de la combinación de los algoritmos, aún estando limitada su actuación a la modificación de las variables de entrada del nivel de beneficio. Variando el algoritmo implementado en este nivel se puede conseguir un comportamiento totalmente diferente del conjunto. Si se utiliza un algoritmo basado en una metodología Non-Learning en el nivel de calidad, las acciones finales sobre el sistema no supondrá ningún efecto sobre el threshold ni sobre el radio de cobertura. Este hecho se debe a que las reglas que producen estos efectos en el entorno son completamente dependientes de la salida proporcionada por el nivel de calidad. Por otra parte se denota que el uso de un algoritmo Actor-Critic en el nivel de calidad produce un efecto de priorización de la calidad ofrecida respecto al beneficio del sistema. Los algoritmos que cumplen esta característica no sobrepasan en ningún momento los objetivos de blocking y dropping fijados, en contrapartida el beneficio que obtienen es inferior a los demás algoritmos. Si en su lugar se implementa un algoritmo Q-Learning en el nivel de calidad, los estándares de calidad no son tan prioritarios como el beneficio, incluso permitiendo excederse de los objetivos fijados. En contraposición a este efecto, esta metodología obtiene en general un beneficio mayor para el operador. Sin embargo, la alta implicación del nivel de calidad no significa que el agente
Sistema ARMUN
35
de beneficio tenga una baja implicación. De hecho la carga del sistema, mostrada en la Fig. 3.14, es un parámetro controlable únicamente por el nivel de beneficio, esto demuestra la alta implicación de este nivel en la decisión final del sistema. Por último, cabe destacar las combinaciones “QQ” y “AA”. La combinación “QQ” aunque no se ajusta a los márgenes establecidos en la función de refuerzo del nivel de calidad consigue un beneficio mucho mayor que ninguna otra combinación de algoritmos. En el caso contrario se encuentra la combinación “AA”, esta combinación no consigue un beneficio tan elevado para el operador, en su lugar es el sistema que consigue ofrecer una mayor calidad final al usuario.
3.4.
Comparativa entre dos operadores
El estudio se sigue centrando sobre la estación central situada en la cuadrícula. Las causas de la centralización del estudio son las mismas explicadas en el caso individual. A continuación se muestra el desarrollo de dos operadores actuando en el mismo entorno compitiendo por el control de los canales de las estaciones. Se ha elegido los sistemas compuesto por las combinaciones “AA‘” y “QQ”. El sistema “AA” es escogido por su capacidad para ofrecer una calidad de servicio menor que el resto de sistemas. El sistema “QQ”, en cambio, proporciona un mayor beneficio al operador. En este caso los operadores tendrán diferentes funciones de refuerzo. En un operador, denominado operador 2 (op2 en las gráficas), se rebajan los estándares de calidad, incorporando un objetivo de dropping aumentado a un 5 % y su objetivo de blocking aumentado a un 15 % mientras que el beneficio por usuario15 se mantiene. El otro operador, denominado operador 1 (op1 en las gráficas), mantendrá los objetivos de calidad fijados con anterioridad a doblando el beneficio por usuario. La operativa implementada en este entorno se basa en un ámbito de competición, de modo que los operadores requieran los canales disponibles en la estación base16 . Por otra parte, los usuarios son fieles al operador, por consiguiente, no pueden cambiar de operador durante la simulación, consiguiendo así un nivel de peticiones de servicio similar en ambos operadores. Para esta configuración, comparar el beneficio entre operadores no es coherente dada la diferencia de precios ofrecida entre ellos. Un hecho similar sucede en la 15
El beneficio por usuario es el coste que tiene este para establecer la comunicación (precio). El número mínimo de canales que debe poseer el operador es 3 según las reglas de control expuestas en el apartado 3.2. 16
Aprendizaje por refuerzo multi-nivel para sistemas RRM
36
calidad de servicio ofrecida, en este caso para realizar una medida de la calidad de servicio ofrecida al usuario se utiliza la definición mostrada por la ec. 3.3. Esta definición de calidad de servicio es equivalente a considerar unos objetivos de blocking y dropping nulos en la ecuación de refuerzo implementada en el nivel de calidad (ec. 3.1). Convirtiéndose en un medición idéntica a la realizada en el apartado 2.2, con lo cual a menor valor de QoS obtenido mejor es la calidad de servicio ofrecida al usuario.
QoS = 4 · Dropping + Blocking
(3.3)
Por último, al realizar la comparación entre dos operadores de forma simultánea en el mismo entorno no hay necesidad de realizar simulaciones equivalentes. A continuación se muestran los resultados obtenidos para cada una de las posibles combinaciones de los algoritmos17 .
3.4.1.
Comparativa AA-AA
En este apartado se muestra el comportamiento de dos operadores compitiendo en un entorno real. Ambos operadores utilizan un algoritmo Actor-Critic tanto en el nivel de beneficio como en el nivel de calidad. El incremento porcentual sufrido en el área de cobertura es mostrado en la Fig. 3.21. El área de cobertura en ambos operadores se ve reducido comparado con el incremento obtenido en el caso individual. Se destaca que el operador 2 permite un incremento del área de cobertura menor que el operador 1, ocasionando una reducción en el número de usuarios que desean establecer una conexión a este operador con menos cobertura. En la Fig. 3.22 se observa la distribución de los canales. Los operadores agotan cerca de la totalidad de los canales disponibles. Según la figura se puede considerar que los canales no se distribuyen de forma equitativa entre ambos operadores. El porcentaje de canales adquiridos por el operador 1, cuyo incremento en el área de cobertura es mayor y por consiguiente atiende a más peticiones de los usuarios, es ligeramente superior al del otro operador. Considerando lo mostrado en la Fig. 3.23, los canales a disposición de ambos operadores obtienen una carga promedio sostenida alrededor del 40 %, un valor esperado según la calibración realizada en el sistema. Sin embargo, comparando el 17
6
La parámetros de configuración de la simulación son adjuntados en el apartado VII de la sección
Sistema ARMUN
37
porcentaje de carga obtenida con el caso individual, mostrado en la Fig. 3.14, la carga promedio en un escenario con dos operadores se ve aumentada en ambos operadores. Al no disponer de recursos en la estación base, el operador debe optimizar de una forma más eficiente la carga útil de la estación, provocando un aumento en esta, pero en ningún momento debe exceder el valor de carga objetivo. Los limites fijados como carga objetivo son definidos por la categoría “‘media carga” referente a la entrada “carga del sistema” en el nivel de beneficio. La Fig. 3.24 muestra los resultados obtenidos para el valor del umbral denominado threshold. Incluso con un número de canales inferior al obtenido en el estudio individual, el valor de este umbral no es variado en gran medida. Los sistemas mantienen un reserva para servicios especiales de aproximadamente la mitad de los canales disponibles. La falta de recursos disponibles provoca un incremento notable en el bloqueo del sistema. La Fig. 3.25 relaciona las estadísticas de los dos operadores. Se observa que el operador 1 no produce perdidas en el sistema a coste de aumentar el bloqueo en el sistema. Este comportamiento se debe a un intento por parte del algoritmo para mantener la máxima calidad posible, la Fig. 3.26 muestra la eficacia de la política tomada resultando en una calidad mayor a la obtenida para el otro operador.
Figura 3.21: Comparativa AA-AA: cobertura
Aprendizaje por refuerzo multi-nivel para sistemas RRM
Figura 3.22: Comparativa AA-AA: porcentaje de canales en posesión
Figura 3.23: Comparativa AA-AA: carga promedio del sistema
38
Sistema ARMUN
Figura 3.24: Comparativa AA-AA: comparativa threshold
Figura 3.25: Comparativa AA-AA: comparativa dropping y blocking
39
Aprendizaje por refuerzo multi-nivel para sistemas RRM
40
Figura 3.26: Comparativa AA-AA: QoS
3.4.2.
Comparativa AA-QQ
En este apartado dos operadores están compitiendo en un entorno real por el control de los canales disponibles en la estación base. El operador con mayor beneficio y que debe ofrecer una calidad mayor implementa un algoritmo Actor-Critic en sus dos niveles, el otro operador implementa un algoritmo Q-Learning en ambos de sus niveles. La Fig. 3.27 muestra que el incremento porcentual del área de cobertura en ambos sistemas se ve reducido de una forma muy acentuada cuando es comparada con el caso de de un único operador en el entorno. En la Fig. 3.28 se muestra la proporción de canales disponibles en la estación base adquiridos por los operadores. Similar al caso anterior, el operador que cubre un área de cobertura inferior obtiene un número de canales levemente menor al obtenido por el otro operador. La carga del sistema mostrada en la Fig. 3.29 expone que ambos operadores mantienen un nivel de carga medio. Respecto al caso individual, ambos operadores han aumentado la carga del sistema. Similar al caso anterior dada la inexistencia de recursos disponibles en la estación se consigue mejorar la eficiencia de estos canales. Semejante al caso de un operador individual, el valor del threshold mostrado en la Fig. 3.30 se mantiene en bornes del 50 %. El número de canales reservados para servicios especiales sigue manteniéndose en la mitad de los canales totales del operador.
Sistema ARMUN
41
Los ratios de bloqueo y pérdidas mostrados en la Fig. 3.31 dan a observar el bajo porcentaje de dropping en ambos operadores, en su defecto los porcentajes de bloqueo son más elevados. Dada la estructura de los objetivos fijados para los operadores, el operador 1 sobrepasa el objetivo de bloqueo fijado, mientras el operador 2 mantiene los márgenes establecidos, puesto que estos son más elevados. Como resultado, según los valores de calidad mostrados en la Fig.3.32, aun manteniendo el operador 2 dentro de los objetivos, ambos operadores mantienen unos niveles de calidad muy similares siendo la calidad obtenida levemente mejor en el operador 1.
Figura 3.27: Comparativa AA-QQ: cobertura
Aprendizaje por refuerzo multi-nivel para sistemas RRM
Figura 3.28: Comparativa AA-QQ: porcentaje de canales en posesión
Figura 3.29: Comparativa AA-QQ: carga promedio del sistema
42
Sistema ARMUN
Figura 3.30: Comparativa AA-QQ: comparativa threshold
Figura 3.31: Comparativa AA-QQ: comparativa dropping y blocking
43
Aprendizaje por refuerzo multi-nivel para sistemas RRM
44
Figura 3.32: Comparativa AA-QQ: QoS
3.4.3.
Comparativa QQ-AA
El comportamiento de dos operadores compitiendo por el control de los canales en la estación base es mostrado en este apartado. El operador cuyos objetivos de calidad son más estrictos implementa una algorítmica Q-Learning en sus dos niveles. El otro operador implementa el algoritmo Actor-Critic en ambos de sus niveles. El radio de cobertura en ambos operadores se ve reducido. La Fig. 3.33 indica que el radio de cobertura del operador 2 permite un incremento en su área de cobertura ligeramente superior a la del operador 1. En la Fig. 3.34, el operador 2 consigue un número porcentual de canales bastante inferior al porcentaje adquirido por el operador 1. Parecido a lo sucedido en los apartados anteriores, el operador con un área de cobertura mayor obtiene un porcentaje superior de los canales. La carga del sistema se mantiene en el rango donde predomina la categoría “‘media carga” de la entrada “carga del sistema”. Similar a los casos anteriores, la carga promedio del sistema es ligeramente superior a la obtenida en el caso de un operador individual. Este hecho se debe a una optimización más eficiente de la carga del sistema frente a la falta de adquisición de recursos. El valor del umbral threshold, mostrado en la Fig. 3.36, refleja que este se mantiene alrededor del valor medio, indicando que la mitad de los canales obtenidos son reservados para servicios especiales.
Sistema ARMUN
45
Respecto al ratio de blocking i dropping en la Fig. 3.37. En el operador 1 se dispara el número de llamadas bloqueadas mientras que ninguna llamada es perdida. Un porcentaje de llamadas bloqueadas tan alto es debido a la carencia de recursos para este operador, en concreto su porcentaje de recursos obtenidos es un 15 % inferior al del otro operador. El operador 2 al adquirir un porcentaje de canales superior su ratio de llamadas bloqueadas es menor. Al no existir dropping en el sistema, la medida de QoS realizada en la Fig. 3.38 es aproximadamente el valor del ratio de blocking obtenido. Por las mismas razones nombradas en el párrafo anterior, la calidad en el operador 1 es inferior a la calidad del operador 2.
Figura 3.33: Comparativa QQ-AA: cobertura
Aprendizaje por refuerzo multi-nivel para sistemas RRM
Figura 3.34: Comparativa QQ-AA: porcentaje de canales en posesión
Figura 3.35: Comparativa QQ-AA: carga promedio del sistema
46
Sistema ARMUN
Figura 3.36: Comparativa QQ-AA: comparativa threshold
Figura 3.37: Comparativa QQ-AA: comparativa dropping y blocking
47
Aprendizaje por refuerzo multi-nivel para sistemas RRM
48
Figura 3.38: Comparativa QQ-AA: QoS
3.4.4.
Comparativa QQ-QQ
Por último se muestra la comparativa entre dos operadores, ambos operadores utilizando la algorítmica Q-Learning en sus dos niveles, compitiendo por el control de los canales disponibles en la estación base. La Fig. 3.39 muestra el incremento porcentual del área de cobertura. Trabajando de forma competitiva entre dos sistemas, ambos implementando la combinación “QQ’,’ permiten un incremento en el área de cobertura muy inferior al obtenido en el caso individual. La Fig. 3.40 relata la estadística de posesión de canales en ambos operadores. Los operadores han repartido los canales disponibles de modo que puede ser considerada como equitativa. Respecto la carga promedio en el sistema, la Fig. 3.41 relata el establecimiento de esta alrededor del 40 %, el cual hace referencia al valor de pico en la categoría “media carga” de la entrada “carga del sistema”. Idéntico a los casos anteriores, la carga obtenida en los sistemas es ligeramente superior a lo obtenido en el caso del estudio con operadores actuando individualmente en el entorno. El valor del umbral threshold para los canales en posesión, mostrado en la Fig. 3.42 se aproxima a los valores obtenidos en los casos anteriores del 50 %, manteniendo una reserva para canales específicos de la mitad de los canales en posesión. Los valores del ratio de blocking y dropping mostrados en la Fig. 3.43 muestran
Sistema ARMUN
49
la poca tolerancia del operador 1 a la perdida de llamadas, aumentando así su ratio de llamadas bloqueadas. Por otra parte, el operador 2 adquiere una mayor tolerancia a la perdida de llamadas disminuyendo así el número de llamadas bloqueadas. El comportamiento de los operadores en este aspecto concuerda con los objetivos de calidad fijados, teniendo un objetivo de dropping mas elevado provoca una tolerancia mayor a este. Observando la gráfica de QoS de la Fig. 3.44, la calidad ofrecida en ambos sistemas es muy similar, aún siendo su comportamiento respecto a la perdida de llamadas bastante diferente.
Figura 3.39: Comparativa QQ-QQ: cobertura
Aprendizaje por refuerzo multi-nivel para sistemas RRM
Figura 3.40: Comparativa QQ-QQ: porcentaje de canales en posesión
Figura 3.41: Comparativa QQ-QQ: carga promedio del sistema
50
Sistema ARMUN
Figura 3.42: Comparativa QQ-QQ: comparativa threshold
Figura 3.43: Comparativa QQ-QQ: comparativa dropping y blocking
51
Aprendizaje por refuerzo multi-nivel para sistemas RRM
52
Figura 3.44: Comparativa QQ-QQ: QoS
3.4.5.
Análisis de los resultados con competición entre operadores
Todas las combinaciones posibles han resultado con una disminución del área de cobertura por parte de ambos operadores. Así como la conservación de un nivel de “carga medio”. Confirmando que los sistemas realizan una adaptación en relación al entorno. El efecto de no permitir un incremento del área de cobertura tan grande como el caso de un solo operador radica en el número de usuarios que pueden acceder a la estación. Reduciendo el número de usuarios con acceso a la estación base adapta la carga del sistema al número de canales disponibles. El principal inconveniente de los operadores es la falta de recursos disponibles en la estación. Teniendo otro operador en el entorno, da una importancia muy significante a la rapidez y priorización del algoritmo. Un algoritmo con un tiempo de respuesta lento provoca que el operador no tenga disponibles los recursos cuando sean necesarios. Un efecto similar parece suceder al comparar las combinaciones “AA” y “QQ”. La combinación “AA” suele conseguir un mayor número de canales de la estación de estudio que los operadores que implementan la combinación “QQ’. Este hecho supone que la algorítmica “AA” tiende a dar prioridad a la adquisición de un canal. Por ora parte, la carga de los sistemas con algorítmica Q-Learning en ambos niveles consiguen una carga en el sistema más elevada, priorizando así una optimización de la carga antes de la adquisición de un canal.
Sistema ARMUN
53
La política de la combinación QQ sigue con una tendencia de conseguir una tasa de dropping ínfima a costa de aumentar su tasa de blocking. La combinación AA continua con tendencia a permitir una cierta tasa de dropping, intentando mantenerse dentro de los margenes establecidos por los objetivos definidos en la función de refuerzo incorporada en el nivel de calidad. Esta política se ve distorsionada en algunos casos, especialmente en los casos que los objetivos de calidad son más restrictivos, por un porcentaje de llamadas bloqueadas aumentado. Este hecho es debido al intento del algoritmo a minimizar el impacto sobre la calidad final, dado que el bloqueo de llamadas penaliza menos que la pérdida. Considerando el efecto explicado en el caso individual, la metodología Q-Learning aplicada en ambos niveles conseguía un beneficio mayor que el resto de sistemas. Valorando la definición de beneficio realizada en la ec. 3.2 se puede inferir, aún siendo inviable una comparación directa del beneficio entre operadores, que se realiza una maximización del beneficio por parte de los operadores con esta metodología, puesto que en los canales en posesión se adquiere una carga superior al del otro operador con diferente metodología. Cabe destacar que en cualquier comparativa realizada entre estos algoritmos el valor del threshold es mantenido alrededor del 50 % de los canales disponibles. Esto indica que la mitad de los canales son reservados para servicios de handover, mientras que la otra mitad son reservados para todo tipo de servicio. Indicando que la priorización de servicios implementada en el nivel de calidad es realmente considerada por el nivel de beneficio. Dada la calibración realizada en el sistema y la escasez de recursos para satisfacer la demanda de los usuarios, la calidad total en el sistema es inferior a la obtenida en el caso de un sistema operando individualmente en el entorno. Las preferencias de los algoritmos con los objetivos de calidad idénticos al del caso individual varían la operativa respecto a bloquear o perder llamadas, ambas combinaciones priorizan el hecho de realizar un mayor bloqueo de las llamadas entrantes ante la pérdida de llamadas, hecho coherente dado que se penaliza de una forma más severa la pérdida de llamadas en la función de refuerzo. En el caso del operador con unos objetivos de calidad más tolerantes, ambos sistemas llegan a permitir un ratio de dropping más elevado, en base a que los objetivos del nivel de calidad son mucho menos restrictivos.
4. Conclusiones Los resultados obtenidos en el apartado EDC muestran la ineficiencia de un solo agente en el momento de maximizar un sistema con diversas variables a considerar, resultando en una incapacidad del sistema en el momento de optimizar los parámetros. La propuesta de resolución mediante el sistema ARMUN muestra una forma de dividir los objetivos en diversos agentes cooperando entre ellos. Los resultados obtenidos son dependientes de la estructura dispuesta en cada nivel, de modo que el resultado del sistema varía en función de que algoritmo sea implementado en el nivel. Ante un sistema RL o FRL se tiende a considerar que los resultados de los sistemas han de ser los mismos. La base de este razonamiento proviene del hecho de que los algoritmos RL y FRL están basados en buscar un máximo de una función objetivo. No obstante, en secciones anteriores se ha mencionado que cada función objetivo tiene más de un parámetro a maximizar, siendo algunos de estos parámetros propiamente modificables por el sistema, resultando en una configuración diferente de los parámetros que componen la función dependiendo de la metodología implementada. En el modelo implementado de cooperación entre agentes, solo el agente de beneficio ha sido capacitado para modificar el entorno, mientras que el agente de calidad está limitado a controlar las variables de entrada del agente de beneficio. Todo y con esta limitación el agente de calidad consigue que sus decisiones tengan un gran efecto sobre la decisión final del sistema1 . A partir de los resultados obtenidos en el caso individual se observa que hay combinaciones de agentes que se centran en proporcionar un beneficio elevado mientras que otros se centran en conseguir un mayor nivel de calidad. Esto demuestra que existe un elevado grado de cooperación entre algoritmos, y el efecto de incorporar algoritmos diferentes en los distintos niveles existentes. Cuando diferentes operadores compiten entre ellos por el control de la estación 1
En [18] se muestra el rendimiento de un sistema utilizando FL y MCDM (Multi-criteria decision making) para optimizar la calidad de servicio ofrecida al usuario.
Conclusiones
55
base. Sus comportamientos se ven modificados, teniéndose que adaptar a las nuevas características del entorno. Los resultados de las comparativas entre operadores proporcionan una idea del grado de conocimiento de los sistemas sobre el entorno. Al disminuir los recursos disponibles del operador, los operadores reducen su área de influencia para poder dar unos ciertos niveles de calidad a los usuarios y continuar obteniendo beneficio para el operador. El sistema ha sido diseñado sobre un entorno ideal. En un entorno ideal muchos fenómenos no se tienen en consideración, por ejemplo efectos de fading2 o shadowing3 . Estos efectos provocan que el área de cobertura obtenido no coincida con el área de cobertura que se obtendría en un entorno real. Para comprobar el desarrollo de los sistemas en entornos reales, es de interés realizar un estudio de los sistemas en un entorno más real. Otra vía de desarrollo futuro del proyecto se basa en realizar un tratamiento más exhaustivo de los parámetros a controlar por el operador. Además de las características contempladas en el estudio existen otros parámetros que pueden ser de interés para el operador, gestionándolos de una forma eficiente y autónoma. Por ejemplo, en [17] se produce una optimización del ángulo de inclinación de las estaciones controladas. Este ángulo se diseña para maximizar la potencia de emisión mientras se minimiza la potencia recibida de las estaciones adyacentes a fin de reducir la interferencia intra-celular (ICI). Otro parámetro a considerar es la variación dinámica de la máscara utilizada en el ancho de banda, como se muestra en [11] la relación señal-ruido varía en relación a este parámetro. La consideración del precio como un factor variable en el sistema ARMUN, similar a lo realizado en sistema EDC, también es un factor a tener en consideración. Para realizar una modificación del precio no es suficiente con la estructura diseñada hasta el momento, para ello es necesario crear una “‘conciencia global” del sistema. Una conciencia global significa tener en consideración todas las estaciones donde el operador actúa, de modo que todas o gran parte de las estaciones tienen que permitir la acción a tomar. Esto implica crear una estructura que no considere únicamente una estación, sino que considere un conjunto de estaciones trabajando conjuntamente a fin de lograr un objetivo determinado. Realizar el estudio en un entorno de programación Java ha permitido definir el proyecto sin ninguna base previa. Constituir un proyecto completamente nuevo permite no estar ligado a unos módulos predefinidos por el sistema de simulación, 2 3
Fading: atenuación de la señal producida por la propagación en el medio. Shadowing: atenuación producida en la señal debido obstrucciones en el trayecto.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
56
pudiendo adaptar íntegramente el sistema y el entorno a los criterios deseados. No obstante, realizar un proyecto que incluya todas las características a tener en consideración tanto del entorno como del algoritmo no permite calcular el tiempo de ejecución de este, lo que supone realizar otro estudio diferente para calcular el tiempo de ejecución del algoritmo.
5. Estado del arte I.
Tipos de Estructuras
La tipología estructural determina el comportamiento del sistema, un sistema con una correcta parametrización pero una estructuración errónea comportaría un malfuncionamiento del sistema. Si además la metodología del sistema es de aprendizaje, la problemática no vendría únicamente dada por el malfuncionamiento del sistema sino que el aprendizaje realizado sería erróneo. En este trabajo se diferencian dos tipos de estructuras: estructura centralizada y estructura distribuida.
I.1.
Estructura Centralizada
La autoridad para la toma de decisiones se concentra en un sólo organismo, de tal forma que las estaciones que están bajo su responsabilidad operan de la misma forma.
Figura 5.1: Esquema de una estructura centralizada
Aprendizaje por refuerzo multi-nivel para sistemas RRM
58
Características de la estructura centralizada Dado que la toma de decisiones depende de un único organismo, facilita el uso de un conjunto de políticas más uniformes. Poder realizar un conjunto de políticas más uniforme tiende a no diversificar tanto la operativa. Existe poca ambigüedad entre operaciones. La toma de decisiones se puede ralentizar, debido a las comunicaciones entre estaciones.
I.2.
Estructura Distribuida
Cada estación tiene autoridad para la toma de decisiones en su estación base, el hecho de que una exista una estructura organizativa distribuida no implica obligatoriamente que exista una comunicación activa entre estaciones.
Figura 5.2: Esquema de una estructura distribuida Características de la estructura distribuida La toma de decisiones se puede realizar de un forma más rápida, no existen comunicaciones externas que lo ralentizan. Existe una mejor capacidad de adaptación. Pueden existir ineficacias de carácter global que individualmente no se observan. La definición de las políticas se debe realizar de forma más exhaustiva, no es obligatorio recibir información exterior en la toma de decisiones.
Estado del arte
II.
59
Aprendizaje por refuerzo
El algoritmo de aprendizaje por refuerzo [19] se basa en el aprendizaje a partir de la experiencia obtenida, dirigiéndolo mediante objetivos expresados por un valor de recompensa que es devuelto por el entorno en el momento de realizar una acción sobre él. Inicialmente se desconoce cuál es la acción más adecuada para el sistema, solo se conoce el efecto que la acción a realizar produce sobre el entorno, de tal forma que el conjunto de acciones debe maximizar la recompensa recibida a largo plazo. El comportamiento del entorno usualmente es desconocido y en ciertos casos puede ser estocástico, posibilitando que su función de recompensa obedezca una cierta función de probabilidad. No obstante, el comportamiento del entorno sigue siendo desconocido, lo que provoca una fuerte carga de ensayo y error, añadido al hecho que la recompensa puede tener un cierto retardo, produce que no se refleje la bondad de la acción realizada por el sistema hasta una evaluación posterior. Por otra parte, existe el dilema de exploración-explotación, este dilema trata de evaluar si es más conveniente explorar el entorno para aumentar el conocimiento del problema, empeorando a corto plazo la recompensa obtenida a cambio de conseguir un mejor conocimiento del problema. En oposición de explotar el conocimiento acumulado intentando maximizar la recompensa hasta el momento dificultando la adquisición de nuevo conocimiento sobre el entorno. Todo sistema de aprendizaje por refuerzo debe tener en consideración los siguientes elementos: Agente: Sujeto del aprendizaje por refuerzo. Su funcionamiento consiste en obtener información sobre el estado del entorno, realizar acciones sobre este y interpretar las reacciones que producen. Entorno: Objeto sobre el que opera el agente, recibe las acciones del agente y evoluciona dependiendo de ellas. Es responsable de generar las recompensas asociadas a las acciones y cambios de estado. Política: Define el comportamiento del agente. Puede verse como un listado de relaciones entre estados y acciones, estableciendo reglas de asociación entre el estado del entorno y la acción a tomar. Función de refuerzo: Establece la recompensa a generar en función del estado actual del entorno y la acción realizada sobre él. El objetivo del aprendizaje por refuerzo es maximizar la recompensa total obtenida a largo plazo.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
60
Función de evaluación: Refleja una estimación de la recompensa que se va a recibir partiendo de un cierto estado y siguiendo cierta política, permitiendo escoger la acción a realizar (aquella que conduce a una recompensa mayor). Construir esta función es el objetivo de este tipo de algoritmos.
II.1.
Actor-Critic
Este método dispone de dos memorias separadas en la estructura, de esta forma se consigue separar la política a seguir de la función de evaluación. La estructura que se encarga de la política es conocida como actuador, seleccionando las acciones a aplicar. La estructura que se encarga de estimar los valores de la función de evaluación es conocido como crítico, criticando las decisiones tomadas por el actuador. Después de cada acción, el agente crítico evalúa el nuevo estado y realiza un balance de la situación, esta evaluación se realiza mediante la metodología de predicción TD1 calculando el error según la ecuación: δt = rt+1 + γVt (st+1 ) − Vt (st )
(5.1)
Donde V (st )2 es la función de evaluación, rt+1 el resultado de la función de refuerzo, γ es una variable definida por el usuario que indica el grado de implicación del estado futuro dentro de la función de evaluación, la actualización de esta función se define: Vt+1 (st ) = Vt (st ) + αδt et (st ) (5.2) Dónde el parámetro α es elegido por el usuario e indica el grado de implicación de la función e(s, a) y del error, δt , en la función de evaluación. Si el error definido en la ec. 5.1 es positivo la acción ha sido beneficiosa, con lo cual se fortalecerá la probabilidad de ejecutarla en un futuro, en caso contrario, si es negativo significa que esta acción ha sido contraproducente, entonces la probabilidad de realizar esta acción en un futuro disminuirá. Se puede evaluar esta probabilidad p(st , at ) 3 de elección mediante: pt+1 (st , at ) = pt (st , at ) + βδt et (st , at )
(5.3)
Siendo β una variable definida por el usuario, mediante este valor se puede adaptar el grado de implicación de la función error sobre la probabilidad de escoger una 1
La metodología de aprendizaje TD o time difference consiste en predecir un valor que depende de valores futuros de la función de estudio. 2 St hace referencia al estado actual del sistema en el instante t. 3 at es la acción tomada, el conjunto (st , at ) hace referencia a la acción tomada at en el estado st
Estado del arte
61
acción en un estado concreto. Por otra parte es necesario tener en cuenta la elegibilidad de una acción dentro de un estado, e(s, a), de esta forma se obtiene un registro temporal del suceso del evento, mediante la siguiente estructura: ( γλet (s, a) + γλ s = st , a = at et+1 (s, a) = (5.4) γλet (s, a) s 6= st , a 6= at Donde γ y λ son parámetros elegidos por el usuario que indican el grado de deterioro de la elegibilidad por cada iteración realizada.
II.2.
Q-Learning
Se basa en utilizar las cadenas de Markov como base para definir estados, de los cuales se deduce una función de acción-valor (función de evaluación), que intenta optimizar la utilidad de coger la acción. Al igual que el caso del algoritmo actor-critic, se realiza un balance de la situación mediante el cálculo del TD error: δt = rt+1 + γQt (st+1 , a∗t+1 ) − Qt (st , at )
(5.5)
Similar al algoritmo anterior, γ determina el grado de implicación del estado futuro, pero en este caso, se tiene en cuenta la acción que maximizará la función de evaluación, a∗t+1 , en el estado de la siguiente iteración. En este caso se observa que la función de evaluación, Q(st , at ), depende tanto del estado del entorno como de la acción tomada, a diferencia de la función de evaluación del caso actor-critic, V (st ), que solamente tiene en consideración el estado del sistema, permitiendo al algoritmo Q-Learning manejar problemáticas relacionadas con las transiciones estocásticas y recompensas sin necesidad de adaptaciones. La actualización de la función de evaluación se actualiza de forma similar al del algoritmo Actor-Critic. Qt+1 (st , at ) = Qt (st , at ) + αδt et (st , at ) (5.6) Como en el algoritmo anterior α es una variable escogida por el usuario. Este parámetro determina el grado de implicación del error y la elegibilidad en el cálculo del nuevo valor. El hecho de que la función de evaluación tenga los parámetros acción, at , y estado, st , indica que ya incorpora en sí misma una valoración de la probabilidad de escoger una acción en un estado, con lo cual no es necesario calcular una función de
Aprendizaje por refuerzo multi-nivel para sistemas RRM
62
probabilidad adicional como se realiza en el caso del algoritmo Actor-Critic. Sin embargo, esta función no tiene en cuenta la elegibilidad de una acción dentro del estado, por eso se utiliza la función adicional e(s, a), realizando el registro temporal del suceso del evento, mediante la siguiente estructura: ( γλet (s, a) + γλ s = st , a = at et+1 (s, a) = (5.7) γλet (s, a) s 6= st , a 6= at Los valores de γ y λ son elegidos por el usuario, y al igual que en el algoritmo anterior, indican el deterioro de la elegibilidad en cada iteración.
II.3.
Procedimiento Actor-Critic
1. Calcular el error para el estado actual y recompensa obtenida (ec. 5.1 ) 2. Actualizar la función de evaluación (ec. 5.2) 3. Actualizar la elegibilidad según el estado (ec. 5.4) 4. Calcular la nueva probabilidad de elección (ec. 5.3)
II.4.
Procedimiento Q-Learning
1. Calcular el error para el estado actual y recompensa obtenida (ec. 5.5) 2. Actualizar la función de evaluación (ec. 5.6) 3. Actualizar la elegibilidad según el estado (ec. 5.7)
III.
Lógica difusa
La lógica difusa o fuzzy logic (FL) [20] es un sistema de control que proporciona una manera simple de llegar a una conclusión precisa basado en una información poco precisa, ruidosa o ambigua. Utiliza un lenguaje impreciso pero muy descriptivo para analizar la información semejante al de la mente humana. Sus características más distintivas son:
Estado del arte
63
Es inherentemente robusto por su funcionamiento con entradas poco precisas y/o ruidosa. El procesado de la salida puede ser una función sencilla a pesar de tener un rango de variación amplio de las entradas. Dado que el controlador de la lógica utiliza reglas definidas por el usuario, pueden ser modificadas de forma sencilla para mejorar o modificar el sistema. No está limitado en número de entradas y salidas definidas, ni es necesario una correspondencia entre el número de entradas y de salidas. No necesita medir o calcular la variación de los parámetros para ser implementado. La formulación de las reglas define la complejidad del sistema, se suele fragmentar el sistema en espacios pequeños para obtener controladores lógicos más pequeños. Puede controlar sistemas no lineales, difíciles o imposibles de modelar matemáticamente. Procedimiento general de la lógica difusa:
Figura 5.3: Diagrama de un sistema básico de lógica difusa El elemento denominado Control analiza, clasifica y evalúa las entradas para realizar la acción más correspondiente sobre el entorno respecto a las entradas actuales. dependiendo de la programación de una acción puede ser aplicada al mismo tiempo.
Aprendizaje por refuerzo multi-nivel para sistemas RRM
64
El control suele trabajar con dos niveles de programación, el primero divide cada entrada en categorías según su nivel de pertenencia determinado por una función de membresía. El segundo evalúa las categorías realizadas según una estructura definida por el usuario. Puede existir una comunicación entre el Control y el entorno, considerando la información recibida respecto al entorno en el momento de generar las acciones. No obstante, esta comunicación no es imprescindible en este tipo de sistemas.
III.1.
Función de membresía
La función de membresía es la representación de la magnitud de participación de cada entrada respecto a unas categorías definidas por el usuario, asociando un peso a cada entrada procesada para finalmente determinar la respuesta de salida. Las reglas utilizan los valores de membresía como factores determinantes en la influencia de los conjuntos de salida4 (o categorías) para decidir la conclusión final. Una vez las categorías son inferidas, escaladas y combinadas son transformadas en salidas nítidas capaces de modificar y guiar al sistema. Es común que la forma de estas funciones sea triangular, no obstante, no tienen una forma definida y puede ser cualquier tipo de función, no obstante si la función es muy compleja entonces requerirá una capacidad computacional adicional para hacer este cálculo. Para definir una correcta función de membresía se han de considerar las siguientes características: Altura: Indica el grado máximo de membresía respecto de una entrada. Normalmente es normalizada. Anchura: Indica el rango de pertenencia de los valores de la entrada en una categoría. Solape: Rango de valores de una entrada pertenecientes a dos o más categorías simultáneamente. Centro: Se considera el centro el punto o puntos de la función donde una categoría alcanza su mayor valor. Guarda: Fija un valor a una categoría para aquellos valores de entrada que no están definidos con una función de membresía. 4
Los conjuntos de salida es la clasificación de las entradas en una serie de categorías definidas por el usuario
Estado del arte
65
En la Fig. 5.4 se observa una representación de una función de membresía para una sola entrada con funciones triangulares definiendo tres categorías (denominadas A,B y C) dónde se señalan las características de esta función. En ocasiones se define la función de membresía gráficamente y se implementa únicamente aplicando reglas. Esto sucede cuando el número de variables de entrada es bajo y se pueden evaluar de una forma sencilla.
Figura 5.4: Diagrama función de membresía
III.2.
Reglas del sistema
Las reglas son definiciones lógicas de cómo actuar con el conjunto de categorías activas respecto a las entradas actuales, la actuación del sistema vendrá determinada por la definición de estas reglas y por el valor obtenido en la función de membresía. Para más de una variable se puede utilizar una matriz de reglas que indica la interacción entre entradas. La matriz de reglas normalmente tiene un número de columnas y filas impares para acomodar una región de sistema estable5 . Esto puede no ser necesario tan pronto como las funciones de cada lado se solapen de alguna manera y se tengan 5
Sistema estable es aquel que no es necesario modificar ningún parámetro del sistema dado que la entradas recibidas son aceptables
Aprendizaje por refuerzo multi-nivel para sistemas RRM
66
continuas dudas de si la salida obtenida es aceptable. La falta de la región de sistema estable provoca que el sistema continuamente busque por esta región. También es posible tener un número diferente de filas que de columnas, el número máximo de reglas posibles es simplemente el producto del número de filas y columnas. No obstante, la definición de todas estas reglas puede ser innecesaria dado que algunas de ellas pueden no suceder en la práctica. El principal objetivo de este mapa de construcción es relacionar todas las posibles entradas mientras el sistema se mantiene bajo control. Un posible ejemplo de sistema sería el caso de dos entradas de dos sistemas diferentes, en los cuales su función de membresía sea idéntica a la mostrada en la Fig. 5.4, con esta estructura se puede definir la matriz de reglas mostrada en la Fig. 5.5, en el cuál cada combinación de entradas resulta en una acción diferente. En el supuesto de que exista un solapamiento entre categorías, y por tanto diversas acciones estén activas simultáneamente la actuación del sistema dependerá de la estructuración de las reglas, dada la definición realizada en la Fig. 5.5 se realizarían todas las acciones que fueran activadas por sus respectivas categorías.
Figura 5.5: Ejemplo matriz de regla
III.3.
Procedimiento general de implementación
1. Definir los objetivos de control y el criterio de actuación y clasificación. 2. Determinar la relación entrada/salida y seleccionar un mínimo numero de variables para la entrada. 3. Crear las funciones de membresía que define la relación entrada/salida utilizadas en las reglas.
Estado del arte
67
4. Programar las reglas. 5. Probar el sistema, evaluar los resultados y modificar la parametrización acorde a las necesidades.
IV.
Fuzzy reinforcement Learning
La lógica difusa combinada con el aprendizaje por refuerzo o Fuzzy Reinforcement Learning [21] permite a los algoritmos de aprendizaje por refuerzo el manejo de entradas como variables continuas. Además permite trabajar con gran variedad de estados tanto respecto a la entrada como respecto a la salida, proporcionando una dimensionalidad elevada al sistema lo que permite implementar un sistema de generación continua de acciones. Proporcionando así una adaptación rápida a las condiciones del entorno.
IV.1.
Estructura de la lógica difusa
En el apartado III se explica el funcionamiento general de un sistema basado el lógica difusa. Seguidamente se profundiza en el sistema FL utilizado para su posterior unión con los algoritmos de aprendizaje. Siguiendo la estructura de la Fig. 5.6, la primera etapa denominada input layer, donde son definidas las entradas del sistema xi . Como se ha nombrado en la sección anterior no existe un número máximo ni un número mínimo de entradas en el sistema. La segunda etapa es la de difusión, fuzzyfication layer, en la cual se realiza la clasificación de las entradas según el patrón definido por el usuario, cada categoría Li obtendrá un valor µi dependiendo del valor de la entrada y la función de membresía aplicada. La última etapa es la de evaluación, rule evaluation layer, en esta etapa cada valor µi calculado en la etapa anterior es procesado según una serie de reglas definidas por el usuario, cada regla tendrá su propio valor o peso αRi el cual se obtiene aplicando multiplicaciones sucesivas de los valores obtenidos en la etapa de difusión µi tal como se muestra en la ec. 5.8.
αRi = Πnj=1 µLij (xj )
(5.8)
Aprendizaje por refuerzo multi-nivel para sistemas RRM
68
Por tanto para cada conjunto de entradas Xt se activarán una serie de reglas definidas por el conjunto A(Xt ), y por consiguiente cada una de las reglas activas tendrá asociado un peso αRi , formando el conjunto de peso de las reglas activas αRi (Xt )
Figura 5.6: Esquema de lógica difusa utilizado
IV.2.
Fuzzy Actor-Critic
La estructura del sistema Actor-Critic6 conjuntamente con lógica difusa o fuzzy actor-critic (FAC), tiene las siguientes características básicas: Cada regla,Ri , está asociada a una serie de acciones denotadas por el vector U i Cada acción asociada a cada regla tiene asociado un factor de calidad (un peso) wi que será ajustado mediante las fases de aprendizaje del sistema. Cada regla tiene una parte de conclusión oi (vector de un único valor) que será ajustado por el critico para estimar el valor de la función. 6
La estructura del algoritmo Actor -Critic esta explicada en el apartado II.3
Estado del arte
69
La estructura general del sistema sigue el esquema dibujado en la Fig. 5.7. En conjunto con la lógica difusa, el cálculo de la función de evaluación del algoritmo actor-Critic es modificado, provocando una independencia del valor nuevo respecto al antiguo. En su lugar se consideran las reglas activadas por la entrada actual y sus pesos tal y como se indica en la ec. 5.9. ΣRi ∈A(Xi ) αRi (Xt )oit V˜t (Xt ) = ΣRi ∈A(Xi ) αRi (Xt )
(5.9)
Esta ecuación se puede simplificar mediante notación vectorial, definiendo el vector Φ, mostrado en la ec. 5.10, cuyos valores son los pesos de la regla normalizados. Φt (Xt ) =
αRi (Xt ) ΣRi ∈A(Xi ) αRi (Xt )
(5.10)
Mediante notación vectorial se puede redefinir el cálculo de la función de evaluación aplicando un producto matricial mostrado en la ec. 5.11. V˜t (Xt ) = ot Φt (Xt )T
(5.11)
Así mismo, es necesario realizar un balance de la situación después de cada acción, el modo de funcionamiento del algoritmo Actor-Critic indica que esta evaluación se realice utilizando la metodología TD error mostrado en la ec 5.12. ε˜t+1 = rt+1 + γ V˜t (Xt+1 ) + V˜t (Xt )
0≤γ≤1
(5.12)
γ es el factor de descuento definido por el usuario que indica el grado de implicación del estado en el error. El vector de conclusión, ot , necesita ser actualizado en cada iteración. En este vector se almacenan las reglas que provocan un mayor beneficio para el sistema, de tal forma que al calcular el nuevo valor de la función de evaluación se considere la evolución del sistema. oit+1 = oit + α˜ εt+1
∂ V˜t (Xt ) → ot+1 = ot + α˜ εt+1 Φt ∂oit
0