Topological reinforcement learning agent

Author(s)

Arthur Plínio de Souza Braga

• Document type: Doctoral Thesis
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Escola de Engenharia de São Carlos (EESC/SBD)
• Defense date: 2004-04-07

Examining board members

Aluizio Fausto Ribeiro Araujo; Felipe Maia Galvão França; Carlos Henrique Costa Ribeiro; José Demisio Simões da Silva; Marco Henrique Terra

• Advisor: Aluizio Fausto Ribeiro Araujo

Abstract

Reinforcement Learning (RL) methods have shown to be a good choice for decision-making problems due to their flexible and adaptive characteristics. Despite such promising features, RL methods often have their practical application restricted to small or medium size (at state, or state-action, space) problems mainly because of their standard strategies for value function estimation. In this thesis, a new RL approach, called \"Topological Reinforcement Learning Agent\" - TRLA, is proposed to accelerate learning through an alternative mechanism to update the state-action value function. TRLA is inspired in latent learning, which refers to animal learning that occurs in the absence of reinforcements and that is not visible until an environmental reinforcement is perceived. This concept considers that part of a task can be learned even before the agent receives any indication of how to perform such a task. Cognitive Maps are usually used to encode information about the environment where the agent is immersed. Thus, the TRLA uses a topological map, based on Self-Organized Maps, to implement cognitive map functions and permit a new simple mechanism to execute the propagation of state-action updates. The chosen problem to test TRLA is the simulation of a mobile robot navigation in some initially unknown and unstructured environments. Performance comparisons of the TRLA with six other RL algorithms were carried out to the execution of the navigation task. The obtained results are very promising and comparable with some of faster RL algorithms simulated. In some experiments, the TRLA\'s performance overcomes the others especially in simulations with unstructured environments. Three characteristics of the original TRLA were modified to make it more suitable for real implementations: (i) changes in the topological map construction to reduce the vertices number, (ii) changes in the agents heuristic for action selection, and (iii) variations on the TRLAs strategy for exploration of the state-action space. In (i), a new procedure to construct topological maps was proposed and implemented, the Incremental Classifier Topological Map ICTM, which generates the vertices for a Watsons triangulation from the classification of the input states. In (ii), it was proposed a method to optimize trajectory planning problems based on graphs, denoted \"trajectory improvement from inner point detection\". The third point considers directed exploration strategies as an option for TRLA\'s learning acceleration. (AU)