No description available.

Diss. (sammanfattning) Linköping : Linköpings universitet, 2008. / Härtill 6 uppsatser.

[pt] Esta dissertação investiga a aplicação dos métodos de Reinforcement Learning na descoberta de rotas ótimas em uma rede de comunicação. Uma rede de comunicação real possui um comportamento dinâmico, mudando seu estado com o tempo. Os algoritmos de roteamento devem, portanto, oferecer rapidez na resposta às mudanças do estado da rede. O objetivo do trabalho é avaliar a aplicação de técnicas de Reinforcement Learning (RL) como base de algoritmos adaptativos de roteamento de pacotes. O problema de roteamento de pacotes sob a visão de RL consiste na definição de cada nó na rede como um agente RL, sendo que este agente deve definir ações de forma a minimizar uma função objetivo que pode ser o tempo de roteamento dos pacotes. Um dos objetivos do RL é precisamente aprender a tomar as ações que minimizem uma função. O trabalho consistiu de 4 etapas principais: um estudo sobre a área de Reinforcement Learning (RL); um estudo sobre a área de redes de comunicação e roteamento de pacotes; a modelagem do problema de roteamento como um sistema RL e implementação de diferentes métodos de RL para obter algoritmos de roteamento; e o estudo de casos. O estudo na área de Reinforcement Learning abrangeu desde as definições mais fundamentais: suas características, os elementos de um sistema RL e modelagem do ambiente como um Processo de Decisão de Markov, até os métodos básicos de solução: Programação Dinâmica, método de Monte Carlo, e o método de Diferenças Temporais. Neste último método, foram considerados dois algoritmos específicos: TD e Q-Learning. Em seguida, foi avaliado o parâmetro Eligibility Traces como uma alternativa para apressar o processo de aprendizado, obtendo o TD(lambda) e o Q(lambda) respectivamente. O estudo sobre Redes de Comunicação e Roteamento de pacotes envolveu os conceitos básicos de redes de comunicações, comutação por pacotes, a questão do roteamento de pacotes e os algoritmos existentes adaptativos e não adaptativos, que são utilizados na atualidade. Nas redes de comunicação, definidas como um conjunto de nós ligados através de enlaces de comunicação, para se enviar uma mensagem de um nó a outro, geralmente, a mensagem é quebrada em pedaços, chamados pacotes, e enviados através de outros nós, até chegar ao destino. Deste modo surge o problema de escolher os nós que levem o pacote o mais rápido possível até o nó destino. Os algoritmos analisados foram: Shortest Path Routing que procura os caminhos com menor número de nós intermediários, não sendo sensível às mudanças na carga nem na topologia da rede; Weighted Shortest Path Routing, que oferece um melhor desempenho a partir de uma visão global do estado da rede, que nem sempre é fácil de obter em redes reais e o algoritmo de Bellman-Ford, baseado em decisões de roteamento locais e atualizações periódicas, com algumas limitações para obter políticas em altas cargas. Este último é um dos algoritmos mais utilizados na atualidade, sendo base de muitos protocolos de roteamento existentes. A modelagem do problema de roteamento como um sistema RL foi inspirada por uma característica na definição de um sistema RL: um agente que interage com o ambiente e aprende a atingir um objetivo. Assim, a modelagem dos algoritmos tem como objetivo aprender a descobrir as rotas que minimizem o tempo de roteamento de pacotes desde uma origem até um dado destino. A avaliação de uma rota escolhida não pode ser obtida antes que o pacote alcance o seu destino final. Este fato faz com que os processos de aprendizado supervisionado tenham dificuldade de se aplicar a esse problema. Por outro lado, o Reinforcement Learning não necessita de um par entrada-resposta para fazer o aprendizado, permitindo-lhe abordar o problema com relativa facilidade. Na modelagem efetuada, cada nó na rede se comporta como um agente de RL que age na própria rede, a qual é o ambiente. A informação das rotas é armazenada nas funções de valor existentes em todos os nós da rede para / [en] This dissertation investigates the application of Reinforcement Learning methods to the discovery of optimal routes in communication networks. Any current communication network displays dynamic behavior, changing its states over time. Therefore, the routing algorithms must react swiftly to changes in the network status. The objective of this work is to evaluate the application of some Reinforcement Learning techniques to define adaptive packet routing algorithms. The packet routing problem under the RL vision consists in the definition of each node on network as an RL agent. Thus, each agent must take actions in order to minimize an objective function such as end to end packet routing delay. One main objective of the RL is precisely learning to take the actions that minimize a given function. This thesis is consists of 4 main parts: first, a study of Reinforcement Learning (RL); a study of the communication networks and packet routing; the routing problem model as a RL system and the implementation of several RL methods in order to obtain some routing algorithms; e finally, the case study. The study of Reinforcement Learning extends from the more basic definitions, Reinforcement Learning features, elements of a RL system and environment modeling as a Markovian Decision Process, to the basic methods of solution: Dynamic Programming, Monte Carlo methods and Temporal Differences methods. In this last case, two specific algorithms have been considered: TD and Q-Learning, and, finally, the Eligibility Traces are evaluated as a useful tool that permits us to accelerate the learning process leading to the TD(lambda) and the Q(lambda) routing algorithms. The study on communication networks and packet routing involves the foundations of communication networks, packet switching, the packet routing problem, and adaptive and non- adaptive routing algorithms used at the present time. Communication networks are defined as a set of nodes connected through communication links. In order to send a message from a source node to a destination node usually the message is broken into segments called packets, and these are sent through other nodes until arriving at the destination. In this way the problem appears to choose the path which takes the shortest possible time for the packet to reach the destination node. The following algorithms have been analyzed: Shortest Path Routing that looks for paths with minimal hop number, not being sensible to the changes of load level and network topology; Weighted Shortest Path Routing that offers better performance from a global vision of the state of the network, which is not always easy to get in real networks; on the other hand, the Bellman- Ford routing algorithm was studied, this is based on local routing decisions and periodic updates, with some limitations to obtain policies in high load conditions. Bellman-Ford is one of the algorithms most used at the present time, being the basis for many existing routing protocols. The modeling of the routing problem as a RL system was inspired by one of the main features of the definition of an RL system: an agent who interacts with the environment and learns to reach an objective; therefore, the modeling of the routing algorithms has as its objective to learn to discover the paths that minimize packet routing time from an origin to an destination. The evaluation of a chosen route cannot be completed before the package reaches its final destination. This fact implies that supervised learning cannot be applied to the routing problem. On the other hand, Reinforcement Learning does not need a input-output pair for the learning process, allowing it to approach the problem with relative ease. In the modeling, each network node is viewed as a RL agent that acts in the same network; the network is the environment. The routing information is stored in the existing value functions in all nodes in the network, for each node and all another destination node / [es] Esta disertación investiga la aplicación de los métodos de Reinforcement Learning en la determinación de rutas óptimas en una red de comunicación. Una red de comunicación real posee un comportamiento dinámico, donde su estado varia en el tiempo. Los algoritmos de ruta óptima deben, por lo tanto, ofrecer rapidez en la respuesta a las variaciones del estado de la red. El objetivo de este trabajo es evaluar la aplicación de técnicas de Reinforcement Learning (RL) como base de algoritmos adaptativos de problemas de ruteamiento en redes. Este problema consiste en la definición de cada nodo de la red como un agente RL. Este agente debe definir acciones de modo a minimizar una función objetivo que puede ser el tiempo de ruteamiento. El trabajo consta de 4 etapas principais: un estudio sobre el área de Reinforcement Learning (RL); un estudio sobre redes de comunicación y problema de ruteamiento; el modelo de ruta óptima como un sistema RL y la implementación de diferentes métodos de RL para obtener algoritmos de ruta óptima; y un estudio de casos. El estudio en el área de Reinforcement Learning va desde las definiciones fundamentales: características, elementos de un sistema RL y modelaje del ambiente como un Proceso de Decisión de Markov, hasta los métodos básicos de solución: Programación Dinámica, método de Monte Carlo, y método de Diferencias Temporales. En este último método, fueron considerados dos algoritmos específicos: TD e Q-Learning. A seguir, fue evaluado el parámetro Eligibility Traces como una alternativa para agilizar el proceso de aprendizaje, obteniendo el TD(lambda) y el Q(lambda) respectivamente. El estudio sobre Redes de Comunicación y Problema de Transporte incluye los conceptos básicos de redes de comunicaciones, la cuestión de la ruta óptima y los algoritmos adaptativos y no adaptativos existentes, que se utilizan actualmente. Los algoritmos analizados fueron: Shortest Path Routing, que busca los caminos con menor número de nodos intermedios, no siendo sensible a variaciones en la carga ni en la topología de la red; Weighted Shortest Path Routing, que ofrece un mejor desempeño a partir de una visión global del estado de la red, que no siempre es fácil de obtener en redes reales; y el algoritmo de Bellman-Ford, que tiene como base decisiones de rutas locales y actualizaciones periódicas, con algunas limitaciones para obtener políticas en altas cargas. Este último es uno de los algoritmos más utilizados en la actualidad, siendo base de muchos protocolos de trazado de ruta existentes. La solución para modelar el problema de ruteamiento como un sistema RL fue inspirada por una característica en la definición de un sistema RL: un agente que interactúa con el ambiente y aprende a alcanzar un objetivo. Así, el modelo tiene como objetivo aprender a determinar las rutas que minimizen el timpo desde el origen hasta un destino dado. La evaluación de uma ruta seleccionada no puede ser obtenida antes que el paquete alcance su destino final. Esto hace que los procesos de aprendizaje supervisionado tengan dificultades para ser aplicados a este problema. Por otro lado, Reinforcement Learning no necesita de un par entrada-salida para el aprendizaje, permitiendo así, abordar el problema con relativa facilidad. En el modelo establecido, cada nodo en la red se comporta como un agente de RL que actúa en la propria red. La información de las rutas se almacena en las funciones de valor existentes en todos los nodos de la red para cada nodo destino diferente. Esta información contiene un valor estimado del tiempo requerido para un paquete para llegar hasta el nodo destino. La actualización de esos valores se realiza durante la transición del paquete hasta el vecino seleccionado. En este trabajo se implementaron varios algoritmos de ruta óptima. Cada uno de los algoritmos aplica características de las técnicas en Reinforcement Learning: o Q(lambda)-Routing, y el TD-Routing. En el estudio d