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

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
UEA Research Groups:	Faculty of Science > Research Groups > Data Science and Statistics
Depositing User:	Vishal Gautam
Date Deposited:	11 Mar 2011 16:04
Last Modified:	10 Jan 2024 01:21
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23596
DOI:	10.1177/1059712308099230

Downloads

Actions (login required)

View Item