Real World Intelligence Technology Field

Biologically Inspired Adptive System

Shigenobu Kobayashi Professor Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology

Today, I'd like to talk about the project currently underway at our university. This project is rather a mini project or a program in terms of RWC scale. I will try to describe the links with the RWC Project and suggest future directions for both parties.

This project is one of the projects in Research for Future Programs that was started in fiscal 1996 by the Japan Society for the Promotion of Science. Our project is titled "Biologically Inspired Adaptive Systems", and it is scheduled to be completed by fiscal 2000 over a 5-year period. It is currently in its third year, at the mid point (Fig. 1).

Fig.1

The title of this project is "Biologically Inspired Adaptive Systems", abbreviated as BIAS, and it is scheduled to be completed by fiscal 2000, hence its name "BIAS2000". The project is one of the "Bio-information" projects within Research for Future Programs. This "Bio-information" field is expected to have the highest growth rate in the 21st century in software science.

Fig.2

There are many approaches to Bio-information, as summarized in Fig. 2: the approach from computation theory called molecular computing, the approach from information theory called bio-informatics, and our biologically inspired adaptive systems. This may be considered as a software-oriented research focused on engineering methodology in terms of system theory.

Fig.3

Now, let's look at the specific topics. First, I'll explain the characteristics of biologically inspired adaptive systems (Fig. 3). The first characteristic of such systems is "interaction with the environment". The second characteristic is "interaction among components" which constitute this system. "Interaction with the environment" means that the system is evaluated after the event from the environment. This is sometimes called an Evaluative Feedback Loop. On the contrary, "interaction among components" means a generative feedback where a new component is generated or killed through the interaction among components, hence it is also called Generative Feedback Loop. These two types of interaction are linked. The former "interaction with the environment" has very slow dynamics, while the latter "interaction among components" has very fast dynamics. These two characteristics provide a source of power to the third characteristic, "dual dynamics interaction" to create new functions. Creating functions based on the "dual dynamics interaction" is the basic research policy of our project.

These are depicted in Fig. 4.

Fig.4

We would like to develop "biologically inspired adaptive systemsｲ, which create new functions and adapt themselves to unknown or changing environments. To realize such systems, both ｳinteraction among componentsｲ and ｳinteraction with the environmentｲ should have balanced dynamics and cooperate with each other to create functions. These are too abstract, so let me explain some of the specific core technologies: (1) Evolutionary computation also selected by RWC, (2) Reinforcement learning, and (3) Multiagent system which combines the first two. This multiagent system is also biologically inspired, rather than AI inspired. These three technologies are the core of our research.

First, I'll explain about evolutionary computation (Fig. 5).

Fig.5

Our goal is to establish an emergent design theory based on evolutionary computation. The emergent design theory enables machines to automatically search for a structure that satisfies the given design specifications, which means that just by giving the "What", machines then take care of the "How to". To achieve this, two core components of evolutionary computation, "Crossover" and "Generation Alternation" must be established as elementary technologies. The former, "Crossover", has recently reached the stage where its design policy has theoretical support in this project by developing the crossover for each problem domain, while being made theoretical based on the idea of characteristic preserving. The latter, "Generation Alternation Model", is put into practical use by proposing several such models to maintain diversity. The "Crossover" and the "Generation Alternation Model" correspond respectively to the "Interaction among Components" and the "Interaction with the Environment" as explained earlier. By balancing the "Crossover" with the "Generation Alternation Model" appropriately, the potential of evolutionary computation can be utilized, which leads to the emergent design theory.

Fig.6

Another fundamental technology that we're focusing on is Reinforcement Learning (Fig. 6). While the goal of evolutionary computation is emergent design theory, that of reinforcement learning is to establish emergent control theory based on it. The conventional control theory is designed for linear systems in which linearity is assumed, but in reality, the systems to be controlled involve problems of non-linearity and time delays. To control such systems in an emergent manner, reinforcement learning looks promising. There are two methods of reinforcement learning: a method based on a ｳvalue functionｲ and a method based on ｳpolicy makingｲ. The former includes Q-learning or TD (l), based on dynamic programming. This can be considered a technique of identifying the environment. The latter includes Profit Sharing and the stochastic gradient ascent developed by our group. These are effectively an experience reinforcing technique. However, when considering reinforcement learning as a system, any method that specializes either in environment identification or experience reinforcement is insufficient, so the method based on the value function and the method based on policy making should be integrated. We are therefore building the theory of reinforcement learning to integrate them in an Actor/Critic framework and are verifying the effect.

The research organizations involved in this project are so-called intensive, particularly the staff of the Interdisciplinary Graduate School of Science and Engineering at Tokyo Institute of Technology (Fig. 7).

Fig.7

We have no time today to go into details on the respective researches, but Iｹd just like to say that in the evolutionary computation research group, for instance, the staff are conducting research on the problems shown here (Fig. 8), and achieved the results shown here (Fig. 9) during fiscal 1997.

Fig.8

Fig.9

The second, the adaptive learning group, consists of the members shown here (Fig. 10).

Fig.10

The research results in the respective themes during fiscal 1997 are shown in Fig. 11.

Fig.11

The multiagent research group consists of the members shown in Fig. 12 with the research results shown in Fig. 13 during fiscal 1997.

Fig.12

Fig.13

I'd like to explain some of the research results.

First, I'll explain UNDX, which has been developed by our group as a new crossover method of evolutionary computation to optimize functions (Fig. 14). UNDX generates children with a normal distribution in rotational symmetry around the main axis which links parents. The standard deviation of the normal distribution for the components in the direction of the main axis which links parents is made proportional to the distance between the parents. The standard deviation for the components in the direction of other axes is made proportional to the distance between the line which links the parents and the third parent sampled from the group.

Fig.14

UNDX can perform adaptive searches in highly non-linear functions. For example, the Rosenbrock function has a very steep peak along a parabolic line. The conventional method such as BLX-a often moves away from the peak during a search process, but UNDX can execute the search process efficiently by adapting itself to the shape of a peak. In addition, it has been verified that UNDX shows a robust behavior in optimizing multipeak functions.

I will take lens design as an example application of UNDX to design problems. The design of lens optics has a history of more than 100 years, so there is a vast wealth of design know-how. This problem is highly non-linear and has very many peaks with so many local solutions. For 3-lens optics, a structure called a triplet has been empirically known to be the optimum, but it was impossible to find a triplet by using conventional optimizing techniques. Our group succeeded in re-discovering the triplet with UNDX. In addition, even for the 4- and 5-lens optics shown in Fig. 14, we were able to design the structures, considered as reasonable by experts, automatically. The largest one so far designed with UNDX is 30-lens optics, which is an optimization problem in 120 dimensions, often used in steppers.

The design of lens optics using evolutionary computation has a great impact on this field, and is expected to cause a paradigm shift in design in several years. The design of lens optics is thus a "killer application" for emergent design based on evolutionary computation.

Fig.15

Now, I'll take a look at one of the research results on reinforcement learning (Fig. 15). Reinforcement learning is learning that adapts to the environment based solely on a special input called reward. Because the reward has a time delay and perception input usually covers only a part of the environment, there is a problem of incomplete perception. Reinforcement learning has grown around the method based on Dynamic Programming for the discrete Markov decision processes (MDPs), but many real problems should be handled as partially observable Markov dicision processes (POMDPs).

Approaches to the POMDPs are divided into those which exist from an incomplete perception state by using action sequences in the past, and those which use a stochastic policy. We proposed a method called the stochastic gradient ascent, which belongs to the latter category. This method is, like Profit Sharing, an experience reinforcement learning, which is theoretically verified to show reasonable behavior under POMDPs.

Fig. 15 shows the simulation results of crawling robot motion using the stochastic gradient ascent. This robot has two arms, and can move forward by using one arm equivalent to the beak and the other arm equivalent to the neck. When it moves forward, a reward is given. Its goal is to learn how to move forward based solely on this reward with no knowledge given. To move forward, it needs to bring one arm upward, straighten it, and bring it down onto the ground repeatedly, like crawl swimming. Fig. 15 shows an example of the movement acquired with this stochastic gradient ascent and the change in forward movement speed. With incomplete perception, Q-learning would not improve performance, while the stochastic gradient ascent improves the performance gradually.

These were the results of the simulation, so next, let me briefly explain the results using an actual machine with the stochastic gradient ascent. The method was implemented on an actual machine and instructed to learn in real-time. It shows a trial-and-error behavior for the first 5 minutes, and then moves forward based on learning results. There is a slight difference between the simulation and the actual machine. In the actual machine, unexpected behavior is observed, due to complex mechanical conditions like the size and weight of the robot, the friction coefficient of the floor, and vibration caused by movements. Sometimes it crawls forward like in the simulation, but sometimes it moves forward like an inchworm by reaching out two arms as one arm, while placing the ends of the arms and the rear end of the robot body onto the ground and raising the center of the body. The actual machine also experiences difficulties in moving backward, and when moving its arms vigorously, the body vibrates up and down. It can move backward by moving the arms up and down in the air, without placing the ends of the arms on the ground. This behavior was not expected in advance, and it showed an emergent aspect of the reinforcement learning. The actual robot has an awkward structure, but when learning crawling motion with reinforcement learning, it looks like a real insect creeping on the ground, which was very impressive. The application of reinforcement learning to actual systems remains a challenge for the future. Finally, Iｹd like to explain one example of a multiagent reinforcement learning application (Fig. 16). The upper figure shows a tracking problem known as a benchmark in the field of distributed artificial intelligence (DAI). The agent at the center is the animal that is trying to run away, followed by four hunters. With the DAI method, each agent must be given knowledge as a program about how to catch the animal and how to communicate with one another. With multiagent reinforcement learning, no knowledge will be given; each agent performs reinforcement learning independently. One difficulty with multiagent reinforcement learning is that since for one particular agent other agents are part of the environment, the probability of state transition is uncertain during the learning. When the probability of state transition is uncertain, the behavior of Q-learning will be very unstable and will not converge. In such cases, however, Profit Sharing demonstrates a robust behavior, and is able to learn cooperative behavior in order to catch the animal.

Fig.16

Next, I'll explain one example of multiagent reinforcement learning applied to an actual problem. The middle figure in Fig. 16 shows a coil yard in an iron mill. Hot coils, each weighing 30 tons, are fed into the coil yard, where they are stored for cool down. Cooled coils are then carried out from the yard upon request. Three cranes are used to receive and carry the coils, which share the same rails. The problem is to control the cranes so that they can handle coils as fast as possible without colliding with one another. Each crane is considered as an independent agent and performs reinforcement learning with Profit Sharing. The lower left graph in Fig. 16 shows their movements at the initial stage of learning, and the lower right graph shows their movements after learning. At the initial stage of learning, three cranes yielded to each other and so were slow to perform the task. But after learning, useless movements were eliminated, and three cranes moved smoothly. Multiagent reinforcement learning can reduce the process time by approximately 20% from the conventional AI method. Note that knowledge-free learning has better performance than the knowledge-based method.

These are the results of biologically inspired adaptive systems, specifically such applications as lens optics design, crawling robot motion, and the control of cranes.

Fig.17

The final goal of our project is autonomous distributed systems. Fig. 17 shows the relationship between the researches in the priority area in system science up to now and this project. From fiscal 1990 to 1992, there was a project called "Autonomous Distributed Systems" as a priority area research. This project, which I participated in, only produced concepts and focused on ideas and philosophy. It was taken over by the "Emergent System" project from fiscal 1995 to 1997, which in turn was taken over by the "Biologically Inspired Adaptive System" project as pioneering research for the future. In terms of inheritance and creation, we believe that original autonomous distributed systems can now be created based on the results of this series of research. This is summarized in Fig. 18, where one goal is to establish the "Emergent Design Theory" based on evolutionary computation, then establish the "Emergent Control Theory" based on reinforcement learning, and finally create bottom-up "Biologically Inspired Multiagent Systems" by integrating "Evolutionary Computation" and "Reinforcement Learning", and thus build the "Autonomous Distributed System Theory". Once these have been achieved, they will serve as the fundamental technologies for flexible control of rather social systems such as autonomous distributed control of ATM networks and transportation systems. This project will accomplish such objectives.

Fig.18