Hiroshi Kawakami
Co-evolution of Sensors and Controllers
Komei Sugiura? Takayuki Shiose? Hiroshi Kawakami? Osamu Katai?
Animal species have adapted their morphology (the placement of sensors and actuators, speci?c characteristics, etc.) to their ecological niche. However, so far very little is known about the relationship between the morphology of an evolutionary system such as self-organizing robot and its adaptive behavior in the environment. In this paper we investigate the evolutionary development of embodied agents that are allowed to evolve not only control mechanisms but also the sensitivity and temporal resolution of their sensors. The experimental results indicate that the sensors and controller co-evolve in an agents through interacting with the environments.
Keywords: sensor evolution, evolutionary robotics, embodiment, time resolution
1. Introduction Arti?cial Intelligence (AI) has exhibited its ability to solve problems under very limited conditions such as playing chess. In these cases, human programmers have to design limited and digitized input information for the AI. Robots equipped with AI, however, are not capable of pick out meaningful inputs from the environment according to the problem to be solved. As a result of this situation, the Frame Problem [6, 16] arises. How do animals cope with this Frame Problem? Uexk¨ ll insisted that animals have their own worlds (Die u Umwelten) in which they are surrounded information that is meaningful to them [21]. Namely, animal species have evolved their sensory systems to pick out information that is meaningful only to them, so that each of them ’sees’ the world di?erently. Animals’ behavior and their Umwelten are closely related. The sensitivity and resolution of insects’ sensors depend on their feeding behavior, mating behavior, velocity and so on [7]. For instance, the human visual system has high spatial resolution and low temporal resolution, whereas the ?y visual system has low spatial resolution and high temporal resolution. Critical Fusion Frequency (CFF) is an indicator of time resolution. Generally, insects that move at high speed have a high CFF, while insects that move slowly have a low CFF. The sensitivity and resolution of sensors di?er not only among animal species but also in a single species. For example, the fovea/periphery in the visual systems of both humans and mantes have high/low spatial resolution. In this case, the diversi?cation of the ability of sensors is determined by the animals’ physical characteristics.
?
Inspired by these biological facts, researchers have tried to arti?cially evolve the morphology and behavior of an agent in the ?eld of Arti?cial Life and Evolutionary Robotics [18]. Sims and Lipson et al. realized a system that evolves the morphology and neural system of robots inside a computer [13, 19]. Other research e?orts have been made on Sensor Evolution [1,5,12,14,15,20]. Kortmann et al. studied the evolution spatial and temporal resolution in populations of simulated visuo-motor systems and showed that two factors are responsible for the trade-o? between spatial and temporal resolution [9–11]. In this paper, we investigated the evolution of the sensors and controller of embodied agents. We developed simulated sensory-motor systems that can change the sensitivity and temporal resolution of their sensors. Then, we carried out two kinds of experiments in which populations of the sensory-motor systems perform tasks. Finally, we describe how the physical characteristics of agents a?ect the diversi?cation of their sensors through interaction with the environment. 2. Sensory-Motor System and Task Envi-
ronments
We constructed sensory-motor systems that can change sensitivity of the sensors, temporal resolution of sensors and connection weights in their neural network controllers. To investigate how embodied agents adapt their sensors and controllers to the task environment, we prepared two kinds of environments in which populations of sensory-motor systems perform di?erent tasks. The individuals and environments were built using the robot simulator Webots? . Below we give the details of the sensory-motor system and the task environments. 2.1 Sensory-Motor System A top view of the sensory-motor system is shown in Fig. 1.
?
Graduate School of Informatics, Kyoto University Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan sugiura@sys.i.kyoto-u.ac.jp {shiose, kawakami, katai}@i.kyoto-u.ac.jp
https://www.wendangku.net/doc/5e446394.html,
1
Proximity Sensors: 1-8 2, 10 1, 9 Light Sensors: 9-16 6, 14
Left Wheel Right Wheel
8, 16
7, 15
Wheels
Proximity Sensors
Light Sensors
Fig. 1. Left: Top view of the structure of the simulated sensory-motor system (agent). The system is based on the Khepera robot; 28 mm in radius, and equipped with 8 infrared sensors used as both proximity sensors (1-8) and light sensors (9-16). Right: Schematic view of Braitenberg’s Vehicle-like controller [2]. It has 16 input units, half of which receive information from the proximity sensors and the other half receive information from the light sensors, with two output units controlling the speed of the wheels.
Sensors This Khepera-like agent has eight infrared sensors that are used as both proximity sensors and light sensors. The two kinds of sensors are physically one uni?ed device, but the simulator models it as two di?erent devices by applying di?erent computing algorithms. Each sensor has di?erent sensitivity and resolution values. Here, the sensitivity si stands for a radix used to digitize the ith sensor’s input. The bigger si becomes, the more the sensor is able to detect slight changes. The temporal resolution ?ti stands for the interval that the ith sensor’s input is updated. Consequently, the sensor cannot detect changes occurring within ?ti . Therefore, CFF is modeled by 1/?ti . We put a restriction on si and ?ti in order to hold the amount of acquired information I constant. Here, I is de?ned as information that an agent can acquire from all of its sensor in a unit of time. si and ?ti must ful?ll the following equation. si =I (1) ?ti Controller The system is controlled by a simple neural network, which has only inputs, outputs, and multiplying connections. The right-hand side ?gure of Fig. 1 shows a schematic view of the controller. The rotation of each wheel is stimulated or inhibited in proportion to the normalized signal strength that each sensor senses. The connection weights are encoded in the individual’s genotype, so they are ?xed during one generation. Actuators Wheels are driven by two independent motors. The maximum angular speed ωmax and the maximum angular acceleration αmax can be varied. Agents with high ωmax and αmax simulates light insects that move at high speed.
2
2.2 Task Environments We carried out the following two kinds of experiments. (I) Phototaxis One individual is put in an arena (100 mm × 100 mm) and performs a phototaxis task. Individuals acquire ?tness if they arrive at the circle in which a light source exists (see Fig. 2). At each generation, an individual is given one trial. The position and direction of each individual is initialized randomly at the start of each trial. A trial ends either when the individual arrives at the goal or when 300 time steps (approximately 20 seconds in real time) are performed. (II) Predator-Prey Pursuit Two species of agents (predator and prey) are used in this experiment. Several researchers have investigated predator-prey co-evolution in both simulated [3, 4] and real robotic experiments [8, 17]. Cli? and Miller also showed that task-dependent morphological parameters (view range) are evolved in co-evolving predator and prey agents [3, 4]. In this experiment, we investigated dependencies on the ecological niche and the sensitivity and resolution of agents’ sensors. The same arena as (I) is used, but there is no light source. Instead, each predator and prey agent is equipped with a light source on it. They are also provided with sensors having the same range. At each generation, all couples of randomly chosen predator and prey agents perform tournaments. In each tournament, both the predator and the prey are put randomly in the arena. Once the tournament has started, it continues until the individuals collide or 300 time steps are performed. We examined several cases in which the prey has di?erent maximum speed. 3. Evolution of Sensors and Controllers Genetic algorithms (GAs) are used in order to make simulated embodied agents adapt both their sensor
Co-evolution of Sensors and Controllers
Light source
100mm
Prey
Predator
100mm
100mm
Fig. 2. Left: Schematic View of the arena used in (I). Agents are asked to perform phototactic behavior. Right: Prey evades from the predator in the arena. Sensors equipped on the two species have the same range. A light source is also put on each agent.
properties and behaviors to their morphologies and tasks. The GA is allowed to optimize four kinds of parameters of each sensor: sensitivity si , time resolution ?ti , left wheel input multiplier li , and right wheel input multiplier ri . 3.1 Genetic Representation The genotype of an individual has the following form: G = (s1 , t1 , l1 , r1 , s2 , t2 , l2 , r2 , . . . , s16 , t16 , l16 , r16 ), where si and ti are the ratios of spatial and temporal resolution. Each of the parameters (si , ti , li , ri ) is binary encoded by four bits in the genotype. An individual has 16 sensors altogether, therefore the length of a genome is 256 bits. The weights (li , ri ) are decoded into real values ranging from ?1 to 1. On the other hand, si and ?ti are calculated as follows to ful?ll the equation (1): si = si I
sj tj sj tj
where t is the time to arrive at the goal and Tmax is the maximum time steps performed in the experiment. For (II), We adopted a ?tness function similar to that of [8]. Namely, both Φpr for a predator and Φpy for a prey are based on the time to contact: Φpr = 1 ? Φpy = t Tmax
t Tmax
where t is the time the predator needs to contact the prey. 4. Results and Discussion 4.1 Performance We carried out experiments in ?ve populations for both (I) and (II). We kept I = 32 and αmax ?xed. The factor ωmax varied between the populations, but was kept ?xed within a population in (I). In the experiments (II), we kept the predators’ ωmax = 60, but varied the preys’ ωmax between the prey populations. In Fig. 3, the average ?tness of the individuals (left) and the predators (right) is plotted against the number of generations. All populations converged within 300 generations in (I), while the predators’ ?tness values stay unsteady in (II). Fig. 3 shows that the ?tness of the agents (ωmax = 100) reaches lower values than that of the agents (ωmax = 20). This result can be explained by the fact that the range of the sensors is not enough for the agents with high ωmax to avoid the wall. 4.2 Diversi?cation of Sensors We also studied the variation of the degree of dependence on each sensor. Here, the degree of dependence on the ith sensor is calculated as follows: di =
si ?ti
?ti = ti
I
3.2 Genetic Algorithm Each genotype of an individual in the ?rst generation is a random combination of 0 or 1. In each generation, the GA assesses the ?tness of all individuals. Roulette selection is used to select individuals that participate in mating. The GA then generates new children from selected individuals to replace the 10% worst individuals of the population. Each population consists of 100 individuals in (I). In (II), 100 predators and 100 preys compose independent populations. We made the cross-over rate 50% and the probability of mutation per bit 0.002%. 3.3 Fitness Function The ?tness function Φ for individuals in (I) is calculated as follows: Φ=1? t Tmax
3
I
In Fig. 4, the average degree of dependence on each sensor is plotted against the number of generations. The
100mm
1
1
0.8
0.8
Fitness
Fitness
0.6
0.6
0.4
ωmax ωmax ωmax ωmax ωmax
0.4
ωmax ωmax ωmax ωmax ωmax
0.2
= 100 = 80 = 60 = 40 = 20 250 300
0.2
= 100 = 80 = 60 = 40 = 20 250 300
0
0
50
100
150 Generation
200
0
0
50
100
150 200 Generation
Fig. 3. Left: Each curve represents the average ?tness of the ?ve di?erent populations between which ωmax is varied. Right: Experiment on predator-prey pursuit problem showing the average ?tness of the predators’ performance. Each curve represents the average ?tness of the ?ve di?erent populations between which the preys’ ωmax is varied.
Fig. 4. The average degree of dependence on each sensor (S1-S16) in (I). Left: ωmax = 100. Right: ωmax = 20.
left-hand side ?gure shows that the agents (ωmax = 100) after 300 generations acquire information from both proximity sensors and light sensors. On the other hand, the agents with low ωmax acquire almost all information from one light sensor (see the left-hand side ?gure). This result can be explained by the fact that agents with high ωmax need more information from the proximity sensors so as not to hit the wall. In Fig. 5 and Fig. 6, average degree of dependence on each sensor is plotted against the number of generations (Left: predators, Right: preys). Fig. 5 shows that the predators concentrate attention on two light sensors to catch the relatively quick preys (cf. Fig. 6). Fig. 3 and Fig. 5 show that the ?tness of the predators drastically increases with the increase in the degree of dependence on the ?fteenth sensor. This clearly indicate that both the sensor morphologies (sensitivity and resolution) and control mechanisms evolved in these sensory-motor systems.
5. Conclusions In this paper, we investigated the dependencies on the behaviors and morphologies in populations of sensorymotor systems. Genetic algorithms (GAs) were used to make simulated embodied agents adapt both their sensor properties and behaviors to their morphologies and tasks. We carried out two kinds of experiments in which agents were asked to perform phototactic and pursuit/evading behaviors. The experimental results show that the physical characteristics of an agent and the task environment a?ect the sensitivities and the resolution of its sensors, and thus task-dependent morphologies are evolved. Future work will include the evolution of sensor morphology including placement, resolution, and sensitivity in agents performing tasks in noisy environments.
4
Co-evolution of Sensors and Controllers
Fig. 5. The average degree of dependence on each sensor (S1-S16) in (II). The predators’ ωmax = 60, and the preys’ ωmax = 100. Left: In the predators. Right: In the preys.
Fig. 6. The average degree of dependence on each sensor (S1-S16) in (II). The predators’ ωmax = 60, and the preys’ ωmax = 20. Left: In the population of predators. Right: In the population of preys.
and respond to information, W. H. Freeman & Co. (1992). Floreano, D., Nol?, S. and Mondada, F.: Competitive CoEvolutionary Robotics: From Theory to Practice, Proceedings of the Fifth International Conference of the Society for Adaptive Behavior (Pfeifer, R., Blumberg, B. and Kobayashi, H.(eds.)), Cambridge, MA., MIT Press, pp. 515–524 (1998). Kortmann, R., Postma, E. and van den Herik, J.: The tradeo? between spatial and temporal resolution in visual systems, Proceedings of the eleventh Belgian-Dutch conference on arti?cial intelligence (Postma, E. O. and Gyssens, M.(eds.)), pp. 219 – 226 (1999). Kortmann, R., Postma, E. and van den Herik, J.: Visual resolution evolving to a trade-o? curve, From animals to animats 6, proceedings of the sixth international conference on simulation of adaptive behavior (Meyer, J.-A., Berthoz, A., Floreano, D., Roitblat, H. and Wilson, S.(eds.)), Cambridge, MA., MIT Press, pp. 405 – 412 (2000). Kortmann, R., Postma, E. and van den Herik, J.: Evolution of visual resolution constrained by a trade-o?, Arti?cial Life, Vol. 7, No. 2, pp. 125 – 145 (2001). Lightensteiger, L. and Pfeifer, R.: An Optimal Sensor Morphology Improves Adaptability of Neural Network Controllers, ICANN (Dorronsoro, J. R.(ed.)), Springer, pp. 850–855 (2002). Lipson, H. and Pollack, J. B.: Automatic design and manufacture of robotic lifeforms, Nature, Vol. 406, No. 6799, pp. 974–978 (2000). Lund, H. H., Hallam, J. and Lee, W.-P.: Evolving Robot Mor-
References
(1) Balakrishnan, K. and Honavar, V.: On Sensor Evolution in Robotics, Proceedings of the First International Conference on Genetic Programming, Stanford University, CA., pp. 455– 460 (1996). Braitenberg, V.: Vehicles: Experiments in Synthetic Psychology, MIT Press, Cambridge, MA. (1984). Cli?, D. and Miller, G. F.: Tracking the Red Queen: Measurements of adaptive progress in co-evolutionary simulations, Advances in Arti?cial Life: Proceedings of the Third European Conference on Arti?cial Life (Mor′n, F., Moreno, A., a Merelo, J. J. and Chac′n, P.(eds.)), Berlin, Springer Verlag, o pp. 200–218 (1995). Cli?, D. and Miller, G. F.: Co-evolution of Pursuit and Evasion II: Simulation Methods and Results, From animals to animats 4 (Maes, P., Mataric, M. J., Meyer, J.-A., Pollack, J. B. and Wilson, S. W.(eds.)), Cambridge, MA., MIT Press, pp. 506–515 (1996). Dautenhahn, K., Polani, D. and Uthmann, T.: Special Issue on Sensor Evolution, Arti?cial Life, Vol. 7, No. 2, pp. 95–98 (2001). Dennett, D. C.: Cognitive wheels: The frame problem of AI, Minds, Machines and Evolution: Philosophical Studies (Hookaway, C.(ed.)), Cambridge University Press, Cambridge, pp. 129–151 (1984). Dusenbery, D. B.: Sensory ecology: how organisms acquire
(8)
(9)
(2) (3)
(10)
(4)
(11)
(5)
(12)
(6)
(13)
(7)
(14)
5
(15)
(16)
(17)
(18)
(19)
(20)
(21)
phology, Proceedings of IEEE 4th International Conference on Evolutionary Computation, IEEE Press, p. Invited paper (1997). Mark, A., Polani, D. and Uthmann, T.: A Framework for Sensor Evolution in a Population of Braitenberg Vehicle-like Agents, Arti?cial Life VI: Proceedings of the Sixth International Conference on Arti?cial Life (Adami, C., Belew, R., Kitano, H. and Taylor, C.(eds.)), Cambridge, MA., MIT Press, pp. 428–432 (1998). McCarthy, J. and Hayes, P. J.: Some Philosophical Problems from the Standpoint of Arti?cial Intelligence, Machine Intelligence 4 (Meltzer, B. and Michie, D.(eds.)), Edinburgh University Press, pp. 463–502 (1969). Nol?, S. and Floreano, D.: Co-evolving predator and prey robots: Do ‘arms races’ arise in arti?cial evolution?, Arti?cial Life, Vol. 4, No. 4, pp. 311 – 335 (1999). Nol?, S. and Floreano, D.: Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines, MIT Press, Cambridge, MA. (2000). Sims, K.: Evolving 3D Morphology and Behavior by Competition, Arti?cial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems (Brooks, R. and Maes, P.(eds.)), Cambridge, MA., MIT Press, pp. 28–39 (1994). Vaario, J. and Shimohara, K.: On Formation of Structures, Advances in Arti?cial Life: Proceedings of the Third European Conference on Arti?cial Life (Mor′n, F., Moreno, A., a Merelo, J. J. and Chac′n, P.(eds.)), Berlin, Springer Verlag, o pp. 421–435 (1995). von Uexk¨ ll, J.: A stroll through the worlds of animals and u men, Instinctive Behavior: The Development of a Modern Concept (Shiller, C. H.(ed.)), International University Press, pp. 5–80 (1957).
6