  In the family of Learning Classifier Systems, the classifier system XCS has
been successfully used for many applications. However, the standard XCS has no
memory mechanism and can only learn optimal policy in Markov environments,
where the optimal action is determined solely by the state of current sensory
input. In practice, most environments are partially observable environments on
agent's sensation, which are also known as non-Markov environments. Within
these environments, XCS either fails, or only develops a suboptimal policy,
since it has no memory. In this work, we develop a new classifier system based
on XCS to tackle this problem. It adds an internal message list to XCS as the
memory list to record input sensation history, and extends a small number of
classifiers with memory conditions. The classifier's memory condition, as a
foothold to disambiguate non-Markov states, is used to sense a specified
element in the memory list. Besides, a detection method is employed to
recognize non-Markov states in environments, to avoid these states controlling
over classifiers' memory conditions. Furthermore, four sets of different
complex maze environments have been tested by the proposed method. Experimental
results show that our system is one of the best techniques to solve partially
observable environments, compared with some well-known classifier systems
proposed for these environments.
