Dynamic System Control Using Rule Learning and Genetic Algorithms

DYNAMIC SYSTEM CONTROL USING RULE LEARNING AND GENETIC ALGORITHMS

David E. Goldberg

The University of Alabama, Department of Engineering Mechanics, P. 0. Box 2908, University, Alabama 35486

ABSTRACT

In this paper, recent research results are presented which demonstrate the effectiveness of a rule learning system in two dynamic system control tasks. This system, called a learning classifier system (LCS), learns rules to control a simple inertial object and a simulated natural gas pipeline.

Starting from a randomly generated state of mind, the learning classifier system learns string-rules called classifiers which match strings called messages. Messages are sent by environmental sensors or by previously activated classifiers. Each classifier's effectiveness is evaluated by an internal service economy complete with bidding and auction. Furthermore, new rules are created by an innovative search mechanism called a genetic algorithm. Genetic algorithms are search algorithms based on the mechanics of natural genetics.

Results from computational experiments in both tasks are presented. In the inertial object task, the LCS learns an effective set of rules to center the object repeatedly. In the pipeline task, the LCS learns to control the pipeline under normal summer and winter conditions. It also learns to alarm correctly for the presence or absence of a leak. These results demonstrate the effectiveness of the learning classifier system approach and suggest further refinements which are currently under investigation.

I BACKGROUND

Many industrial tasks and machines that once required human intervention have been all but completely automated. Where once a person tooled a part, a machine tools, senses, and tools again. Where once a person controlled a machine, a computer controls, senses, and continues its task. Repetitive tasks requiring a high degree of precision have been most susceptible to these extreme forms of automated control. Yet despite these successes, there are still many tasks and mechanisms that require the attention of a human operator. P:Uoting an airplane, controlling a pipeline, driving a car, and fixing a machine are just a few examples of ordinary tasks which have resisted a high degree of automation. What is it about these tasks that has prevented more autono­ mous, automated control? Primarily, each of the example tasks requires, not just a single capabil­ ity, but a broad range of skills for successful performance. Furthermore, each task requires performance under circumstances which have never been encountered before. For example, a pilot must take off, navigate, control speed and direc­ tion, operate auxiliary equipment, communicate with tower control, and land the aircraft. He may be required to do any or all of these tasks under extreme weather conditions or with equipment malfunctions which he has never faced before. Clearly, the breadth and perpetual novelty of the piloting task (and similarly complex task environ­ ments) prevents the ordinary algorithmic solution used in more repetitive chores. In other words, difficult environments are difficult because not every possible outcome can be anticipated in ad­ vance, nor can every possible response be prede­ fined. This truth places a premium on adaptation.

This paper describes work done at the University of Michigan. It was partially supported by U. S. Department of Energy Contract DE-FG02-80ER10125, assistance from the MW Goodrich Fund, the H. W. King Fund, the Rackham School of Graduate Studies, and the U. M. Office of Energy Research.

In this paper, we present research results from the application of a learning classifier system (LCS) to the control of two dynamic systems [ 1], an inertial object and a natural gas pipe­ line. A learning classifier system is a rule learning system which combines a computationally complete rule and message system, an apportionment of credit system based on a service economy analogue, and a genetic algorithm to form a system with sufficiently broad adaptability and effi.cien­ cy to learn how to control each dynamic system starting from a random state of mind.

In the remainder of the paper we first examine the origins and structure of learning classifier systems. We examine its application to the control of an inertial object. Finally, we observe its adaptation to normal summer and winter conditions, as well as abnormal leak events, in the control of a simulated natural gas pipeline.

II ORIGINS AND STRUCTURE OF LEARNING CLASSIFIER SYSTEMS

Learning classifier systems are the latest outgrowth of Holland's continuing work on adaptive systems. In 1962, when Holland outlined his theory of adaptive systems [2) he developed a general theory encompassing many adaptive systems, but ultimately he was addressing himself toward programmable machines that could reprogram them­ selves.

With this foundation more concrete sugges­ tions emerged for classes of schemata processors [ 3) which in some limited respects resemble the present day LCS. This work has evolved into the intricately interesting, but as yet unimplemented broadcast language [4). The first practical im­ plementation of a learning system based on these theories appeared in 1978. Holland and Reitman [ 5) describe this first Classifier System wh:l.ch learns a simple maze running task. Though the task is simple, the achievement is remarkable be­ cause of its successful marriage of a rule-based knowledge system and a genetic algorithm for dis­ covery of new rules. Others have continued and extended this work in a variety of areas ranging from visual pattern recognition to draw poker [6-10).

• A learning classifier system (LCS) is an artificial system that learns rules, called classifiers, to guide its interaction in an arbitrary environment. It consists of three main elements:
• Rule and Message System
• Apportionment of Credit System
• Genetic Algorithm

A ~chematic of an LCS is shown in Figure 1. In this schematic, we see that the rule and mes­ sage system receives environmental information through its sensors, called detectors, which de­ code to some standard message format. This envi­ ronmental message is placed on a messag~ list along with a finite number of other internal messages generated from the previous cycle. Mes~ages on the message list may activate classifiers, rules in the classifier store. If activated a classifier may then be chosento send a message to the message list for the next cycle. Additionally, certain messages may call for

ENV I RO NM!::NT

external action through a number of action triggers called effectors. In this way, the rule and message system combines both external and internal data to guide behavior and the state of mind in the next state cycle.

In an LCS, it is important to maintain simple syntax in the primary units of information, messages and classifiers. In the current study messages are ~-bit (binary) strings and classifiers are 3~-position strings over the alphabet { 0, 1, II}. In this alphabet the II is a wild card, matching a 0 or a 1 in a given message. Thus, we mainta:l.n powerful pattern recognition capability with simple structures.

In traditional rule-based expert systems, the value or rating of a rule relative to other rules is fixed by the programmer in conjunction with the expert or group of experts being emulated. In a rule learning system, we don't have this luxury. The relative value of different rules is one of the key pieces of information which must be learned. To facilitate this type of learning, Holland [6) has suggested that rules coexist in a competitive serv:l.ce economy. A competition is held among classifiers where the right to answer relevant messages goes to the highest bidders with this payment serving as a source of income to previously successful message senders. In this way, a chain of middlemen is formed from man­ ufacturer (source message) to message consumer (environmental action and payoff). The competitive nature of the economy insures that the good rules survive and that bad rules die off.

In addition to rating existing rules, we must also have a way of searching for new, possibly better, rules. The primary mechanism for this type of creative learning within an LCS is the genetic algorithm. A genetic algorithm (GA) is a search algorithm based upon the mechanics of natural genetics. It combines a Darwinian survival of the fittest among a population of artificial chromosomes (string rules) and a structured, yet randomized, information exchange among randomly mated pairs of rules. GA simplicity of operation and power of effect have been demonstrated in function optimization, optimal control, as well as LCS domains.

Taken together, the learning classifier system with its computationally complete and convenient rule and message system, an apportionment of credit system modeled after a competitive service economy, and the innovative search of a genetic algorithm, provides a unified framework for investigating the learning control of dynamic systems. In the remainder, we examine the application of the LCS to inertial object and gas pipeline control.

III INERTIAL OBJECT CONTROL

We test the LCS and its ability to control an inertial object in the 1-D space depicted in Figure 2. The object is frictionless and is governed by Newton's second law. As shown, the domain is bounded by inelastic walls, and the LCS receives perfect, yet crude and discrete, know­ ledge of the object's position, velocity, force, and reward in an eight bit environmental message. The LCS has a simple behavioral repertoire: it can apply a force of given magnitude to the right or to the left.

In these tests the LCS is rewarded if the action it has taken j.s consistent with the goal of centering the object (maximum point score = 6). Furthermore, a criterion count is incremented if the obi ect is centered for 10 consecutive time steps. ~ After this, the object is randomly dis­ turbed by a large force to make the system try again.

Starting from a randomly generated set of 30 rules we compare the performance of the LCS with genetic algorithm and without genetic algorithm to a random walk on the basis of time-averaged point count (TOTALEVAL/T) in Figure 3. We note that both the LCS runs are much better than random perfor­ mance. Furthermore, case IOLCS.2 (with GA) even­ tually overtakes and outperforms run IOLCS.l (without GA). In fact, while the differences appear small on this basis, the difference in physical control is much better in the case with genetic algorithm.

To see this we shift the basis of comparison to the more sensitive measure, time-averaged number of criterion achievements displayed as Figure 4. Again, LCS performance is far better than random. Performance with the genetic algo­ rithm is that much better than without. In fact, the run with genetic algorithm has found restora­ tion and braking rules similar to those that might be programmed by a knowledgeable control engineer. The run without genetic . algorithm has ineffective braking rules thereby limiting its capability.

IV GAS PIPELINE CONTROL

A pipeline model, load schedule, and upset conditions are programmed and interfaced to the LCS. We briefly discuss this environmental model and present results of normal operations and upset tests.

A model of a pipeline has been developed which accounts for linepack accumulation and frictional resistance. User demand varies on a daily basis and depends upon the weather. Differ­ ent patterns may be used for winter and summer operation. In addition to normal summer and winter conditions, the pipeline may be subjected to a leak upset. During any given time step, a leak may occur with a specified leak probability. If a leak occurs, the leak flow, a specified value, is extracted from the upstream junction and persists for a specified number of time steps.

The LCS receives a message about the pipeline condition every time step. A template for that message is shown in Figure 5. The system has complete, albeit imperfect and discrete, knowledge of its state including inflow, outflow, inlet pressure, outlet pressure, pressure rate change, season, time of day, time of year, and current temperature reading.

In the pipeline task, the LCS has a larger range of alternatives for actions it may take compared with the inertial object task. It may send out a flow rate chosen from one of four values and it may send a message indicating whether a leak is suspected or not.

The LCS receives reward from its trainer depending upon the quality of its action in relation to the current state of the pipeline. To make the trainer ever-vigilant, a computer subrou­ tine has been written which administers the reward consistently. This is not a necessary step, and reward can come from a human trainer.

Under normal operating conditions we examine the performance of the learning classifier system with and without the genetic algorithm enabled. Without the genetic algorithm, the system is forced to make do with its original set of rules. The results of a normal operating test are presen­ ted in Figure 6. Both runs with the LCS outper­ form a random walk (through the operating alterna­ tives). Furthermore, the run with genetic algo­ rithm enabled is superior to the run without GA. In this figure, we show time-averaged total evaluation versus time of simulation (maximum reward per timestep = 6).

More dramatic performance differences are noted when we have the possibility of leaks on the system. Figure 7 shows the time-averaged total evaluation versus time for several runs with leak upsets. Once again the LCS is ini.tialized with random rules and p~rmitted to learn from external reward. Both LCS runs outperform the random walk and the run with GA clearly beats the run with no new rule learning. To understand this, we take a look at some auxiliary performance measures. In Figure 8 we see the percentage of leaks alarmed correctly versus time. Strangely, the run without GA alarms a higher percentage of leaks than the run with GA. This may seem counterintuitive until we examine the false alarm statistics in Figure 9. The run without GA is only able to alarm a high percentage of leaks correctly because it has so many false alarms. The run with GA decreases its false alarm percentage, while increasing its leaks correct percentage.

V CONCLUSIONS

In this paper, we have applied a learning classifier system to the control of two different dynamic systems, an inertial object and a natural gas pipeline.

In the two applications the LCS learns effective rules in normal and abnormal operating conditions alike. In the inertial object task, the LCS learns to center the object consistently. In the pipeline task, the LCS learns to operate the pipeline under normal summer and winter conditions. It also learns to alarm correctly with increasing accuracy for the presence or absence of a leak.

While the applications of the LCS in this paper have been necessarily specific, this work's implications for other research in artificial intelligence are more far-reaching. The use of ruthlessly spartan syntax and simple, yet powerful learning heuristics drawn from nature may else­ where prove promising in our quest for programs which effectively reprogram themselves with better instructions.