Este trabalho propõe uma nova classe de algoritmos que permite o uso de heurísticas para aceleração do aprendizado por reforço. Esta classe de algoritmos, denominada \"Aprendizado Acelerado por Heurísticas\" (\"Heuristically Accelerated Learning\" - HAL), é formalizada por Processos Markovianos de Decisão, introduzindo uma função heurística H para influenciar o agente na escolha de suas ações, durante o aprendizado. A heurística é usada somente para a escolha da ação a ser tomada, não modificando o funcionamento do algoritmo de aprendizado por reforço e preservando muitas de suas propriedades. As heurísticas utilizadas nos HALs podem ser definidas a partir de conhecimento prévio sobre o domínio ou extraídas, em tempo de execução, de indícios que existem no próprio processo de aprendizagem. No primeiro caso, a heurística é definida a partir de casos previamente aprendidos ou definida ad hoc. No segundo caso são utilizados métodos automáticos de extração da função heurística H chamados \"Heurística a partir de X\" (\"Heuristic from X\"). Para validar este trabalho são propostos diversos algoritmos, entre os quais, o \"Q-Learning Acelerado por Heurísticas\" (Heuristically Accelerated Q-Learning - HAQL), que implementa um HAL estendendo o conhecido algoritmo Q-Learning, e métodos de extração da função heurística que podem ser usados por ele. São apresentados experimentos utilizando os algoritmos acelerados por heurísticas para solucionar problemas em diversos domínios - sendo o mais importante o de navegação robótica - e as heurísticas (pré-definidas ou extraídas) que foram usadas. Os resultados experimentais permitem concluir que mesmo uma heurística muito simples resulta em um aumento significativo do desempenho do algoritmo de aprendizado de reforço utilizado. / This work presents a new class of algorithms that allows the use of heuristics to speed up Reinforcement Learning (RL) algorithms. This class of algorithms, called \"Heuristically Accelerated Learning\" (HAL) is modeled using a convenient mathematical formalism known as Markov Decision Processes. To model the HALs a heuristic function that influences the choice of the actions by the agent during its learning is defined. As the heuristic is used only when choosing the action to be taken, the RL algorithm operation is not modified and many proprieties of the RL algorithms are preserved. The heuristic used in the HALs can be defined from previous knowledge about the domain or be extracted from clues that exist in the learning process itself. In the first case, the heuristic is defined from previously learned cases or is defined ad hoc. In the second case, automatic methods for the extraction of the heuristic function H called \"Heuristic from X\" are used. A new algorithm called Heuristically Accelerated Q-Learning is proposed, among others, to validate this work. It implements a HAL by extending the well-known RL algorithm Q-Learning. Experiments that use the heuristically accelerated algorithms to solve problems in a number of domains - including robotic navigation - are presented. The experimental results allow to conclude that even a very simple heuristic results in a significant performance increase in the used reinforcement learning algorithm.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-28062005-191041 |
| Date | 05 April 2004 |
| Creators | Bianchi, Reinaldo Augusto da Costa |
| Contributors | Reali Costa, Anna Helena |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Tese de Doutorado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.1944 seconds