Solving Non-Markovian Control Tasks with Neuro-Evolution

1 Introduction

The pole-balancing or inverted pendulum problem has been established as a standard benchmark for artificial learning systems. For over 30 years researchers in fields rang­ ing from control engineering to reinforcement learning have tested their systems on this task [Schaffer and Cannon, 1966; Michie and Chambers, 1968; Anderson, 1989]. There are two primary reasons for this longevity: (l) Pole balancing has in­ tuitive appeal. It is a real-world task that is easy to understand and visualize. It can be performed manually by humans and implemented on a physical robot. (2) It embodies many es­ sential aspects of a whole class of learning tasks that involve temporal credit assignment [Sutton, 1984]. In short, it is an elegant environment that is a good surrogate for more general problems.

Despite this long history, the relatively recent success of modern reinforcement learning methods on control learning tasks has rendered the basic pole balancing problem obso­ lete. It can now be solved so easily that it provides little or no insight about a system's ability. Neuroevolution (NE)

systems (i.e. systems that evolve neural networks using ge­ netic algorithms), for example, often find solutions in the ini­ tial random population [Moriarty and Miikkulainen, 1996; Gomez and Miikkulainen, 1997]. In response to this need for a new benchmark, the basic pole-balancing task has been extended in a variety of ways.

Wieland[1991] presented several variations to the standard single pole task that can be grouped into two categories: (1) modifications to the mechanical system itself such as adding a second pole either next to or on top of the other. (2) re­ stricting the amount of state information that is given to the controller; for example, only providing the cart position and the pole angle. The most challenging of these is a double pole configuration where two poles of unequal length must be bal­ anced simultaneously. Even with complete state information this problem is very difficult requiring extremely precise con­ trol to solve. In this paper, we demonstrate a neuroevolution method, Enforced Sub-populations (ESP; Gomez and Miikku­ lainen 1997), on an even harder version of this task in which the two poles must be balanced without velocity information. This task represents a significant leap in terms of difficulty. We show that ESP can solve this task, and can do so more efficiently than other methods have been able to solve it even with velocity information.

An interesting aspect of the double pole system is that it is more difficult to control as the poles assume similar lengths. When the poles are very close in length, solutions to this sys­ tem cannot be evolved directly by current methods. In order to control the system under these conditions, shaping (or in­ cremental learning) techniques can be employed that increase the length of the shorter pole very gradually [Wieland, 1991; Saravanan and Fogel, 1995]. This kind of approach is effec­ tive but can be extremely slow due to the limitations of the un­ derlying evolutionary search method-many generations are required to recover from minute changes to the environment. Using an incremental approach in conjunction with a local search technique (Delta-Coding; Whitley et al. 1991) to sus­ tain diversity, we demonstrate that ESP can cope with more significant changes to the environment. Instead of evolving on the goal task directly, ESP evolves on a sequence of in­ creasingly difficult tasks.

The paper is organized as follows. Section 2 describes the ESP and Delta-Coding algorithms. In section 3 we describe incremental evolution in detail. In Section 4 we show the results for three different tasks: (1) the double pole with ve­ locities, (2) double pole without velocities, and (3) double pole without velocities demonstrating incremental evolution to almost equal pole lengths. The last two sections contain a discussion of the results and the conclusion.

2 Neuro-Evolution Method: Enforced Sub-Populations +Delta-Coding.

The Neuroevolution method used is based on Symbiotic, Adaptive Neuro-Evolution (SANE; Moriarty, 1997; Moriarty and Miikkulainen, 1996). SANE has been shown to be a pow­ erful reinforcement learning method for tasks with sparse re­ inforcement.

2.1 SANE

SANE differs from other NE systems in that it evolves a pop­ ulation of neurons instead of complete networks (figure 1). These neurons are combined to forni hidden layers of feed­ forward networks that are then evaluated on a given problem. Evolution in SANE proceeds as follows:

1. Initialization. The number of hidden units u in the net­ works that will be formed is specified and a population of neuron chromosomes is created. Each chromosome encodes the input and output connection weights of a neuron with a random string of binary numbers.
2. Evaluation. A set of u neurons is selected randomly from the population to form a hidden layer of a feed­ forward network. The network is submitted to a trial in which it is evaluated on the task and awarded a fitness score. The score is added to the cumulative fitness of each neuron that participated in the network. This pro­ cess is repeated until each neuron has participated in an average of e.g. 10 trials.
3. Recombination. The average fitness of each neuron is calculated by dividing its cumulative fitness by the num­ ber of trials in which it participated. Neurons are then ranked by average fitness. Each neuron in the top quar­ tile is recombined with a higher-ranking neuron using !-point crossover and mutation at low levels to create

l

Figure 2: The Enforced Sub-Populations Method (ESP). The population of neurons is segregated into sub-populations shown here as clusters of circles. The network is formed by randomly selecting one neuron from each sub-population.

• the offspring to replace the lowest-ranking half of the population.
• The Evaluation-Recombination cycle is repeated until a network that performs sufficiently well in the task is found.

In SANE, neurons compete on the basis of how well , on av­ erage, the networks in which they participate perform. A high average fitness means that the neuron contributes to forming successful networks and, consequently, suggests a good abil­ ity to cooperate with other neurons. Over time, neurons will evolve that result in good networks.

The SANE approach has proven faster and more efficient than other reinforcement learning methods such as Adaptive Heuristic Critic, Q-Learning, and standard neuroevolution, in, for example, the basic pole balancing task and in the robot arm control task [Moriarty, 1997; Moriarty and Miikkulainen, 1996].

2.2 Enforced Sub-Populations (ESP)

In Enforced Sub-Populations, as in SANE, the population consists of individual neurons instead of full networks, and a subset of neurons are put together to form a complete net­ work. However, ESP allocates a separate population for each of the u units in the network, and a neuron can only be re­ combined with members of its own sub-population (figure 2).

ESP speeds up SANE evolution for two reasons: The sub­ populations that gradually form in SANE are already circum­ scribed by design in ESP. The "species" do not have to or­ ganize themselves out of a $ingle large population, and their progressive specialization is not hindered by recombination across specializations that usually fulfill relatively orthogonal roles in the network. Second, because the networks formed by ESP always consist of a representative from each evolv­ ing specialization, a neuron is always evaluated on how well it performs its role in the context of all the other players. In SANE, networks can contain multiple members of some spe­ cializations and omit members of others, and its evaluations are therefore less consistent.

The main contribution of ESP, however, is that it allows evolution of recurrent networks. Since SANE forms networks by randomly selecting neurons from a single population, a neuron cannot rely on being combined with similar neurons in any two trials. A neuron that behaves one way in one trial may behave very differently in another, resulting in evalua­ tions of neuron fitness that are very noisy. The sup-population architecture of ESP makes the evaluation of the neurons more consistent. A neuron's recurrent connection weight r, will al­ ways be associated with neurons from sub-populationS;. As the sub-populations specialize, neurons evolve to expect, with increasing certainty, the kinds of neurons to which they will be connected. Therefore, the recurrent connections to those neurons can be adapted reliably.

As evolution progresses, each sub-population will decline in diversity. This is a problem, especially in incremental evo­ lution, because a converged population cannot easily adapt to a new task. To accomplish task transfer despite convergence, ESP is combined with an iterative search technique known as Delta-Coding.

2.3 Delta-Coding

The idea of Delta-Coding [Whitley et al., 1991] is to search for optimal modifications of the current best solution. In a conventional single-population GA, when the population of candidate solutions has converged, Delta-Coding is invoked by first saving the best solution and then initializing a pop­ ulation of new individuals called 6.-chromosomes. The 6.­ chromosomes have the same length (number of genes) as the best solution and they consist of values (6.-values) that rep­ resent differences from the best solution. The new popula­ tion is evolved by selecting 6.-chromosomes, adding their 6.­ values to the best solution, and evaluating the result. Those 6.-chromosomes that improve the solution are selected for reproduction. Therefore, Delta-Coding explores the hyper­ space in a "neighborhood" around the best previous solution. Delta-Coding can be applied multiple times, with successive 6.-populations representing differences to the previous best solution.

In the experiments presented in this paper, Delta-Coding is implemented with the ESP sub-population architecture. Once the neuron sub-populations have reached minimal di­ versity, the best solution (i.e. the best network specifica­ tion) is saved. New sub-populations are then initialized with 6.-chromosomes so that each neuron in the best solu­ tion has a dedicated sub-population of 6.-chromosomes that will be evolved to improve it specifically. ESP selects a 6.-chromosome from each sub-population and adds the 6.­ values to the connection weights of the neurons in the best­ solution. When these sub-populations converge the best 6.­ chromosomes are added to the best solution to form the new best solution for the next iteration of the Delta phase.

Delta-Coding was originally developed to enhance the fine local tuning capability of Genetic Algorithms for numerical optimization by Whitley et al. [1991]. Gomez and Miik­ kulainen [ 1997], showed how Delta-Coding can be used to facilitate incremental evolution. When a task was completed the best solution was saved and 6.-populations initialized be­ fore evolution was begun on the next task. A more general approach has been taken in the experiments described in this paper. Delta-Coding is activated whenever the system's per­ formance ceases to improve over a predefined number of gen­ erations. This strategy limits the disruption of genetic build­ ing blocks when the population is still adjusting well to task changes by only introducing additional variation when neces­ sary.

3 Incremental Evolution

Evolutionary search methods can be ineffective if the task is too demanding to exert significant selective pressure on the population during the early stages of evolution. In such a case, all individuals perform poorly and the GA gets trapped in an unfruitful region of the solution space. One remedy is to enlarge the population size so that a more diverse set of phe­ notypes is sampled. However, prohibitively large populations may be required to discover individuals with sufficient com­ petence to direct the search. Another approach is to view the goal task as one of many possible instances of a more general parameterized task. The system then learns by evolving on a sequence of increasingly difficult evaluation tasks culminat­ ing in the intended goal task.

A number of researchers have applied task decomposi­ tion, or shaping, to make learning complex tasks tractable [Colombetti and Dorigo, 1992; Perkins and Hayes, 1996; Singh, 1992]. Typically, in these approaches the complex task is broken into simpler components or subtasks that are each learned by separate systems (e.g. GAs or rule-bases) and then combined to achieve the goal task. In contrast, in incremental evolution as proposed in this paper (and also used by Wieland [1991] and Saravanan and Fogel [1995]), a single system learns a succession of tasks. Such an adaptation process is similar to continual (or lifelong) learning [Elman, 1991; Ring, 1994], and motivated by staged learning in real life.

4 Pole Balancing Experiments

The starting point for our experiments is the more challenging double pole problem in which a second pole is placed next to the first (figure 3). The objective is to apply force to the cart at regular time intervals such that the poles are balanced in­ definitely and the cart stays within the track boundaries. The state of this system is defined by six state variables: the an­ gle of each pole from vertical B;, the angular velocity of each pole 0;, the position of the cart on the track x, and the ve­ locity of the cart ::i:, where i E (1, 2) (see Wieland[1991] for the equations of motion and parameters used in this task). We adopt the notation et to denote the evaluation-task where f is the length of the short pole in meters. The long pole is always set to 1 meter. Three different experiments were conducted using this configuration with the following three goal tasks:

1. eo.1 with velocity information.
2. eo.1 without velocity information.
3. eo.s without velocity information.

All of the pole balancing experiments were implemented using the Runge-Kutta fourth-order method with a step size of0.01s. The state variables were scaled to [-1.0, 1.0] before being input to the network. During simulation the networks output a force value every 0.02 seconds (i.e. time step) in the range [ -10, 1 O]N. For tasks 1 and 3, the initial angle for the long pole was set to 1° (so that the networks could not control the system by simply outputting values close to zero), and fitness was determined by the number of time steps a net­ work could keep both poles within ±36 degrees from vertical and keep the cart between ends of a 4.8 meter track. A task was considered solved if a network could balance the poles for 100,000 time steps, which is equal to over 30 minutes in simulated time. For task 2, the fitness function and start­ ing state are described in section 4.3. Neuron chromosomes were encoded as strings of floating point numbers. Arithmetic crossover was used to generate new neurons. Each chromo­ some was mutated with probability 0.2, replacing a randomly chosen weight value with a random value within the range [- 6.0, 6.0]. The techniques and parameters were found effective experimentally; small deviations from them produce roughly equivalent results.

4.1 Related Work

We compared the performance of ESP with SANE and the published results of three other evolutionary methods. The first two [Wieland, 1991; Saravanan and Fogel, 1995] have been applied to the double pole problem with velocities. Wieland used an NE approach which we have termed Con­ ventional NE. This is a single population method for evolving neural networks in which each individual represents a com­ plete network. Fogel and Saravanan use Evolutionary Pro­ gramming, a general mutation-based approach that generates offspring by perturbing the best individuals with Gaussian noise. For the case without velocities, Gruau et al. [1996] is the only study we know that has addressed this problem with some success. Therefore, for this task, we compare ESP only to the Cellular Encoding (CE) method. CE uses a graph trans­ formation language to evolve the network topology as well as its weights. We did not compare ESP with conventional Rein­ forcement Learning methods (e.g. Q-learning, TD(>.)) in this study, because NE methods have already been shown more efficient on easier versions of these tasks [Moriarty and Miik­ kulainen, 1996].

4.2 2 Poles with Velocities( eo.!)

Table 1 shows the results for the 2 pole configuration with velocities. As in Wieland [1991] and Saravanan and Fogel [ 1995], the networks were composed of 10 hidden units. Fo­ gel and Saravanan used feed-forward networks, and Wieland used a fully recurrent architecture. It is clear that NE methods based on partial solutions are superior to other neuroevolution methods in terms of learning speed. Although CPU time was unavailable for the other methods, it can be estimated from the number of evaluations required (i.e. Generationsx#Nets)

that they are considerably slower. Also, ESP is faster than SANE by a factor of 2.

To verify the robustness of SANE and ESP we also per­ formed experiments in which the long pole was started with an angle chosen randomly from a fixed range. Table 2 shows the results for two ranges, one of ±5 degrees and the other ± 10 degrees. This has the effect of varying the difficulty of the task from trial to trial thereby introducing noise into the fitness evaluation. Evaluation noise is a real problem in non-deterministic domains because it limits a GAs abil­ ity to determine the underlying fitness of a population. Even though SANE has been shown robust against noisy evalua­ tions in general [Moriarty, 1997], it could not handle it in this more difficult task, most of the time failing to find a solution at all. In contrast, ESP was largely unaffected by such vari­ ation solving this task every time even when the range was extended ±10 degrees. These results demonstrate that ESP is highly resistant to evaluation noise.

4.3 2 Poles without Velocities (eo.I)

This task is identical to the one in the previous section ex­ cept that the networks do not receive any velocity informa­ tion. Therefore, the networks need to be recurrent so that the velocities can be computed internally using feedback connec­ tions. This makes the task significantly harder in two ways: (1) It is simply more difficult to control such a delicate sys­ tem when the concomitant problem of velocity calculation must also be solved. (2) The number of connections in the networks is necessarily larger, thereby expanding the size of the search space.

For these simulations we compare ESP to CE using the same fitness function as Gruau et al. [1996]. The function F is the weighted sum of two separate fitness measurements

(O.lh + 0.9/2) taken over a simulation of 1000 time steps:

where t is the number of time steps the pole was balanced, K is a constant (set to 0. 75), and the denominator in (2) is the sum of the absolute·values of the cart and the large pole state variables, summed over the last 100 time steps of the run. This complex fitness is intended to force the network to com­ pute the pole velocities by penalizing swinging, and thereby making the GA favor controllers with the ability to return the poles to the upright position and damp oscillations. This kind of fitness measure is necessary because otherwise networks can balance the poles by merely swinging them back and forth (i .e. without calculating the velocities) [Gruau et at., 1996].

Gruau et al. claimed that the decidedly large number of evaluations required by CE to solve this task, compared to direct encoding (table 3), is offset by the number of evalua­ tions saved by not having to search for an effective network architecture to solve the problem. Also, they were unable to solve this problem using direct encoding. CE does not as­ sume an a priori network topology, and is therefore able to optimize it to suit a particular problem. While such methods are an important area of research, we found that they are not necessary nor advantageous for this problem. To demonstrate this we designed an experiment that minimizes the amount of human intervention in the determination of network topology that ESP evolves. In this experiment, the number of hidden units H is still fixed for each evolution, but instead of being prescribed by the user it is chosen at random by the system in a range from [ 1- i 0]. For each simulation, the system be­ gins evolving with the randomly selected H. If it does not solve the task (for whatever reason), it will restart with a new H . This occurs repeatedly until the task is solved. The total number of evaluations over all of the restarts is then counted.

Table 3 compares the performance of ESP and CE in this task. The ESP experiments are the aforementioned where H is selected randomly. The initial angle for the long pole was set to 4.5° for all simulations. To determine if the task had been solved, we tested the most fit individual from each gen­ eration to see if it could balance the pole for 100,000 time steps and score at least 200 on the generalization test describe below. The latter was necessary because we found that fitness :F did not correlate well with the ability to generalize to novel initial states.

In addition to learning speed, the robustness of the solu­ tions was also tested. The column labeled "Generalization" refers to each method's average score on a test where a suc­ cessful controller is awarded a point for each of 625 different initial states from which it is able to control the system for I 000 time steps. The test cases were generated by allowing the state variables x, x, 81, and 01 to take on the values: -0.9, -0.5, 0.0, 0.5, 0.9, (5 4 = 625) . This test, first introduced in [Dominic et al., 1991 ], has become a standard for evaluating the generality of solutions in pole balancing. A high score indicates that a solution has competence in a wide area of the state space.

The main result is that ESP is roughly 5 times faster than CE without significantly compromising generalization, show­ ing that the search for an appropriate architecture for this task can be automated by a simple stochastic mechanism. The ESP simulations had a restart rate of 4.06. That means that, on average, the system had to start over with a new random H about 4 times per run.

4.4 Incremental Evolution of 2 Poles without Velocities (eo.s)

This section compares the results of incremental versus direct evolution. For the incremental experiments, the following method was used the determine the sequence of tasks: The evolution begins with the pole balancing system described in the previous section eo.1 as the initial evaluation task t1. When this task is solved, the shorter pole is lengthened by a predefined increment (P). P can change from task to task according to a simple rule. If ESP is unable to solve the next task after two Delta phases, Pis halved and ESP then tries to solve the problem where the shorter pole has a length halfway between t1 and the new, "unachieved" task t2. Once this in­ termediate task t~ is solved, ESP will move on to the next task t2. So instead going from h to t2 in a single step, the system does it in two steps t1 ---+ t~ ---+ t2. If after completing t~, task t2 can still not be achieved, P is halved again and added to t~ yielding t~ which is halfway between t~ and t2. Tasks are therefore repeatedly simplified, with P decreasing mono­ tonically, until either a transition occurs or a lower bound on P is reached.

The incremental evolution can be illustrated best with an example. Normally with this method the task differences are quite large at first. As the networks move on to harder tasks, P tends to shrink, and more task transitions are required for a given increase in the length of the short pole. For the initial value of P used in these experiments (0.1 ), a typical evolution schedule might look like:

In each of the direct evolution simulations, the evaluation task was fixed . Four different tasks were chosen to test this approach: e0 .3, e0 .5 , e0 .7, eo.s. Each task was attempted 50 times evaluating 1000 networks per generation. Note that the direct simulations were given a population size over two times larger than that of the incremental (1000 vs.400). This was done to see if the harder tasks could be solved by simply increasing the number of search points.

Table 4 compares the two methods on different tasks. P was started with a value of 0.1. This means that after solving the initial task e0 .1 the short pole will be increased by 100% to eo.2· This is a significant change to the environ­ ment. Other approaches that have applied shaping to the eas­ ier double pole task (with velocities) have incremented the short pole by only I% [Wieland, 1991; Saravanan and Fo­ gel, 1995]. ESP was almost always able to complete the first three tasks (eo.l, eo.2, e0.3) without having to decrement P, and the first two tasks were always achieved in less than 70 generations.

Even with a larger population, Direct evolution was inca­ pable of solving e0.5 . When the task is this hard ESP cannot discover a good region of the search space before converg­ ing. No individual does well enough to guide the search. ESP selects genotypes that are slightly better than others in terms of the fitness scalar but are not necessarily any closer to the goal. The incremental approach, on the other hand, was able to solve the hardest task (e0.8 ) within 3000 generations 80% of the time, making an average of 30 task transitions per run.

5 Conclusions

The results show that ESP with Delta-Coding can be an ef­ ficient method for controlling unstable systems. It was able to solve a Markovian version of the double pole balancing problem much faster than other methods, and also a much more difficult non-Markovian version. Incremental evolution was found to be an effective way to scale up the approach to even more difficult tasks. The non-Markovian control task is an important benchmark not only because is it presents non­ linear dynamical environment, but also because it requires memory. Many tasks in varied domains from game-playing to robotics require memory to overcome perceptual aliasing.

In the future, we plan to apply ESP to real-world robot nav­ igation tasks. Tasks of this kind are often naturally decompos­ able into a hierarchy of sub tasks amenable to the incremental paradigm. They also pose the challenge of changing environ­ ments, which we believe can also be solved effectively by the same approach.

Acknowledgments

Special thanks to Oliver Gomez for help in preparing the il­ lustrations. This research was supported in part by National Science Foundation under grant #IRI-9504317.