Learning Mazes with Aliasing States: An LCS Algorithm with Associative Perception

Zatuchna, Zhanna V. and Bagnall, Anthony (2009) Learning Mazes with Aliasing States: An LCS Algorithm with Associative Perception. Adaptive Behavior, 17 (1). pp. 28-25. ISSN 1059-7123

[img]
Preview
PDF - Published Version
Download (402kB) | Preview

Abstract

Learning classifier systems (LCSs) belong to a class of algorithms based on the principle of self-organization and have frequently been applied to the task of solving mazes, an important type of reinforcement learning (RL) problem. Maze problems represent a simplified virtual model of real environments that can be used for developing core algorithms of many real-world applications related to the problem of navigation. However, the best achievements of LCSs in maze problems are still mostly bounded to non-aliasing environments, while LCS complexity seems to obstruct a proper analysis of the reasons of failure. We construct a new LCS agent that has a simpler and more transparent performance mechanism, but that can still solve mazes better than existing algorithms. We use the structure of a predictive LCS model, strip out the evolutionary mechanism, simplify the reinforcement learning procedure and equip the agent with the ability of associative perception, adopted from psychology. To improve our understanding of the nature and structure of maze environments, we analyze mazes used in research for the last two decades, introduce a set of maze complexity characteristics, and develop a set of new maze environments. We then run our new LCS with associative perception through the old and new aliasing mazes, which represent partially observable Markov decision problems (POMDP) and demonstrate that it performs at least as well as, and in some cases better than, other published systems.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Depositing User: Vishal Gautam
Date Deposited: 11 Mar 2011 16:04
Last Modified: 27 Sep 2020 23:31
URI: https://ueaeprints.uea.ac.uk/id/eprint/23596
DOI: 10.1177/1059712308099230

Actions (login required)

View Item View Item