A hierarchical XCS for long path environments

Abstract

It has been noted (Lanzi, 1997, Butz et al, 2000) that XCS (Wilson, 1998) is unable to identify an adequate solution to the Maze14 problem (Cliff and Ross, 1994) without the introduction of alternative exploration strategies. The simple expedient of allowing exploration to start at any position in the Maze will allow XCS to learn in such `difficult' environments (Barry, 2000b), and Lanzi (1997) has demonstrated that his `teletransportation' mechanism achieves similar results. However, these approaches are in truth a re-formulation of the problem. In many `real' robotic learning tasks there are no opportunities available to `leapfrog' to a new state. This paper describes an initial investigation of the use of a pre-specified hierarchical XCS architecture. It is shown that the use of internal rewards allows XCS to learn optimal local routes to each internal reward, and that a higher-level XCS can select over internal sub-goal states to find the optimum route across sub-goals to a global reward. It is hypothesised that the method can be expanded to operate within larger environments, and that an emergent approach using similar techniques is also possible.