Terzo weekend in quel di Losanna e terzo weekend che devo passare di fronte al computer per via di una qualche deadline. Non e’ esattamente un grande inizio. Questa e’ la volta del paper da sottomettere entro domani sera per TAROS 2010 (che, lo so, se non fosse stato per l’estensione della deadline avrei dovuto averlo gia’ finito un mese fa, ma tant’e'). Al momento sto aspettando i risultati delle ultimissime simulazioni in esecuzione sui server di Plymouth (che avevo trovato un po’ trafficati e la cosa ha quindi richiesto piu’ tempo del previsto), ma il paper e’ ormai pronto. Ieri e oggi li ho passati a mettere a posto la parte introduttiva e di literature review, attingendo da una marea di papers. Il risultato, una volta tanto, mi sembra molto soddisfacente. Al punto che lo condivido qui con voi, nel caso in cui abbiate commenti da fare o suggerimenti da consigliarmi (pregasi considerare che manca ancora una revisione linguistica e che, quello che trovate qui sotto, e’ tutto scritto a sentimento).
Introduction
Focusing on the domain of evolutionary computation, for ‘incremental evolution’ – as concisely stated by Barlow [1] – we refer to “the process of evolving a population on a simple problem and then using the resulting evolved population as a seed to evolve a solution to a related problem of greater complexity”.
The inspiration for this approach clearly comes from biological evolution. Animal species (and this is particularly true for humans) have acquired over the time the ability to perform extremely complex tasks. These abilities have not appeared from the middle of nowhere at a certain stage during the evolution, rather they have been progressively built up on top of simpler behaviours. If it is true that these simple behaviours have been sometimes quite evident in their manifestations (e.g., in order to learn how to run, the humans have gone through a complex series of sequential steps involving standing on their legs, walking, etc.) this is not always the case. Sometimes, in fact, these underlying capabilities needed as prerequisites for the development of more complex behaviours remained ‘silent’ over the time, i.e. not expressed in form of explicit behaviours before abruptly appearing. This is what has been demonstrated by Gould introducing the concept of ‘punctuated equilibrium’ [2], a phenomena that later on has been easily identified among many others areas outside the biological evolution domain, such as the introduction of government policies [3], the diffusion of technological innovations [4], etc. Both continuous/progressive evolution and punctuated equilibrium dynamics (see for example the classic work by Lindgren [5] can be seen as result of computer-simulated evolutionary processes.
In the work presented herein we propose the application of an incremental approach to evolution for an Evolutionary Robotics [6] model, aimed to the development of autonomous controllers for MAVs (Micro-unmanned Aerial Vehicles). Incremental evolution can be seen as a way to force the evolutionary algorithm used to generate a continuous evolutionary dynamics, thus better directing the evolution toward the desired goal, At the same time it allows avoiding the long periods of stasis typical of punctuated equilibrium-like dynamics that might make complicated evaluating the intermediate solutions emerged for a complex problem.
The remainder of this paper is structured as follows. In the opening section we provide a brief introduction about the usage of incremental approaches within the robotics and, more specifically, Evolutionary Robotics (ER) fields. Section II describes the functioning of the ER model employed as basis for the work presented herein and show the results obtained by non-incremental evolutionary runs of the corresponding computer simulator. Section III illustrates the characteristics of the incremental approach adopted and illustrates the results it has generated, performing a comparison with those obtained through direct evolution. The results are then discussed in details in Section IV, and the following conclusions are drawn in Section V.
Incremental evolution in autonomous robotics
The idea of using an incremental approach to evolution is very well known in the autonomous robotics and evolutionary computation fields. Gomez and Miikkulainen [7] describe the advantages of incremental evolution already back in 1997, mentioning among others the possibility offered by this approach for evolving behaviours otherwise not obtainable, as well as the better generalisation capabilities exhibited by controllers designed following this paradigm. But the origin of incremental evolution can be dated back even further. Rodney Brooks, for example, taking inspiration from his previous work on behavior-based robotics, was among the firsts to propose an incremental approach to be used within the genetic programming domain in 1992 [8]. This should not be surprising taking into account the fact that Brook’s subsumption architecture itself [9] could be easily seen as a way to mimic incremental evolution, building increasingly complex behavioural modules on top of simpler ones. A tribute must then be payed to Inman Harvey’s and his research group in Sussex for their studies on the SAGA (Species Adaptation GAs) framework [10]. Thanks to its work, Harvey’s group – that could be considered the ‘father’ of the incremental approach to evolution in autonomous robotics – has provided a coherent theoretical framework for incremental evolution. Framework that has been used by a significant number of researchers all over the world as basis for their works.
During more recent times, Mouret and Doncieux [11] have attempted to make order into the field, providing a classification of the possible approaches to incremental evolution in autonomous robotics in four categories: (1) ‘staged evolution’, (2) ‘environmental complexification’, (3) ‘behavioural decomposition’, and (4) ‘fitness shaping’. Staged evolution employs multiple fitness functions that correspond to multiple sub-tasks of increasingly difficulty: the population is initially evolved to perform the simplest task, then the fitness function is modified leading to the solution of the second task, and so on. Environmental complexification is similar to staged evolution, but the complexity of the task can be modified continuously operating on certain parameters. Behavioural decomposition (also called modular evolution) relies on the decomposition of a neural controller into separate task-based sub-controllers, each of these is evolved independently from the others. An evolutionary algorithm then combine all of these modules into a master neurocontroller. Finally, fitness shaping uses a weighted sum of multiple evaluation criteria in order to create a fitness gradient that evolution tries to follow.
As from the above classification, incremental evolution does not necessarily involve a progressive complexification of the controller architecture, although this is frequently the case especially when neural network are employed. Usages of this approach are abundant in literature. A good example consists in Stanley and Miikkulainen’s work [12], where they present the NEAT (NeuroEvolution of Augmenting Topologies) method, a framework for evolving neural network topologies along with synaptic weights. The results they have obtained applying NEAT on a reinforcement learning task used as benchmark demonstrate how this approach can outperform those based on fixed neural networks topologies. In Stanley’s case, the topology of the network changes over time following evolutionary dynamics. But it is also common the case in which is the experimenter who decides the topology the ‘global’ controller must have, manually joining various sub-modules dedicated to different functions. Togelius [13] (also reviewed in [14]) provides a further classification based on the possible ways in which different neural modules could be incrementally attached to an existing controller. He defines ‘incremental evolution’ as the evolution of a one layer network using multiple fitness functions, ‘modularised evolution’ as the evolution of multiple layers or multiple networks with a single fitness function, and ‘layered evolution’ as the evolution of a multi-layered network using multiple fitness functions, specific for each layer. On this basis, Tomko and Harvey [14] have pointed out that it is also of fundamental importance to consider how new units/modules are connected to the main controller during incremental evolution. Their findings highlight the detrimental effect generated by the use of random large connection weights, rather suggesting the linkage of additional neural modules using connection weights with zero values.
As reviewed by recent researches carried out by Petrovic [15][16], many works that can be found within the abundant Evolutionary Robotics literature have employed, to different extents, an incremental approach to evolution. The topics are as differentiate as possible: from the control of unmanned aerial vehicles [1] to 6-legged robots [17], passing through artificial vision systems [18] and autonomous learning [19]. Though, most of the published works simply justify the reason for using an evolutionary approach as consequence of non-better specified ‘issues’ in evolving the desired behaviour through direct evolution. Rarely a quantitative analysis of the advantages coming from the adoption of an incremental approach is provided. One of the few exceptions to this trend consists in the work carried out by Walker [20], who performs an accurate comparison between the performances generated by a direct and an incremental methods for a multi-variable symbolic regression problem. Walker interestingly takes into account the full ‘computational costs’ of both approaches, intended as the number of evaluations of the fitness formula required by the two alternatives. The results he collected demonstrate that no significant advantages in terms of full computational costs are guaranteed by the adoption of an incremental approach. Another recent interesting study, leading to similar evidences, is the one carried out by Christensen and Dorigo [21] comparing the performances generated by two popular approaches to incremental evolution (behavioral decomposiition and environmental complexity increase) against the results obtained through several non-incremental evolutionary algorithms. According to their results none of the incremental evolutionary strategies performs any better than the non-incremental approach. This stream of criticisms seems to have had an effect also on a fierce supporter of the incremental approach as Harvey, that in his already mentioned work states how – according to the analysis carried out – incremental evolution seems to outperform direct evolution only under specific conditions.
In conclusion literature presents results supporting both the arguments, with a recent increase in the number of works that look at the phenomena with a skeptical eye. Anyway, the impression is that it is still extremely difficult to provide a definitive answer to the dilemma whether incremental evolution is ‘better’ or not than direct evolution. The study presented herein aims to give an additional contribute to the topic, with the awareness of not being able to provide any conclusive answer.
References
[1] G. Barlow, C. Oh, and E. Grant, “Incremental evolution of autonomous controllers for unmanned aerial vehicles using multi-objective genetic programming,” Proceedings of the 2004 IEEE Conference on Cyber- netics and Intelligent Systems, 2004.
[2] S. Gould, The Structure of Evolutionary Theory. Belknap Press of Harvard University Press, 2002.
[3] F. Baumgartner and B. Jones, Agendas and Instability in American Politics. The University of Chicago Press, 1993.
[4] C. Loch and B. Huberman, “A punctuated-equilibrium model of technology diffusion,” Management Science, vol. 45, no. 2, pp. 160– 177, 1999.
[5] K. Lindgren, “Evolutionary phenomena in simple dynamics,” Artificial Life II, pp. 295–312, 1991.
[6] S. Nolfi and D. Floreano, Evolutionary Robotics. The Biology, Intel- ligence, and Technology of Self-Organizing Machines. Cambridge, MA: MIT Press, 2000.
[7] F. Gomez and R. Miikkulainen, “Incremental evolution of complex general behavior,” Adaptive Behavior, no. 5, pp. 317–342, 1997.
[8] R. Brooks, “Artificial life and real robots,” Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, pp. 3–10, 1992.
[9] R. Brooks, “A robust layered control system for a mobile robot,” IEEE Journal of Robotics and Automation, vol. 2, no. 1, pp. 14–23, 1986.
[10] I. Harvey, “Artificial evolution: A continuing saga,” Evolutionary Robotics. From Intelligent Robotics to Artificial Life, vol. 2217, pp. 94–109, 2001.
[11] J.-B. Mouret, S. Doncieux, and J.-A. Meyer, “Incremental evolution of target-following neuro-controllers for flapping-wing animats,” From Animals to Animats 9. Proceedings of SAB 2006, the 9th International Conference on Simulation of Adaptive Behavior, pp. 606–618, 2006.
[12] K. Stanley and R. Miikkulainen, “Evolving neural networks through augmenting topologies,” Evolutionary Computation, vol. 10, no. 2, pp. 99–127, 2002.
[13] J.Togelius,“Evolution of a subsumption architecture neurocontroller,” Journal of Intelligent and Fuzzy Systems, vol. 15, no. 1, pp. 15–20, 2004.
[14] N. Tomko and I.Harvey, “Do not disturb: Recommendations for incremental evolution,” Proceedings of ALIFE XII, the 12th International Conference on the Synthesis and Simulation of Living Systems, 2010.
[15] P. Petrovic, “Overview of incremental approaches to evolutionary robotics,” Proceedings of the 1999 Norwegian Conference on Com- puter Science, pp. 151–162, 1999.
[16] P. Petrovic, “A step towards incremental on-board evolutionary robotics,” Proceedings of SCAI’01, the Seventh Scandinavian Conference on Artificial Intelligence, pp. 3–12, 2001.
[17] D. Filliat, J. Kodjabachian, and J.-A. Meyer, “Incremental evolution of neural controllers for navigation in a 6-legged robot,” Proceedings of the Fourth International Symposium on Artificial Life and Robotics, 1999.
[18] I. Harvey, P. Husbands, and D. Cliff, “Seeing the light: Artificial evolution, real vision,” From Animals to Animats 3, Proceedings of SAB 1994, the 3rd International Conference on Simulation of Adaptive Behaviour, pp. 392–401, 1994.
[19] E. Tuci, M. Quinn, and I. Harvey, “An evolutionary ecological approach to the study of learning behavior using a robot-based model,” Adaptive Behavior, vol. 10, no. 3-4, pp. 201–221, 2002.
[20] M. Walker, “Comparing the performance of incremental evolution to direct evolution,” Proceedings of the 2nd International Conference on Autonomous Robots and Agents, pp. 119–124, 2004.
[21] A. Christensen and M. Dorigo, “Incremental evolution of robot controllers for a highly integrated task,” From Animals to Animats 9, pp. 473–484, 2006.
Comments(3)