7 Conclusion

Future developments in robotic hardware technology will soon yield low-cost autonomous robots for various kinds of private and professional applications. The control of such robots in every-day situations, and even more under critical circumstances such as those given by medical applications, will require a profound understanding of the complex interactions of robots with each other and with humans. This understanding firstly includes knowledge about the generation of algorithms in the first place that allow for complex robotic activities to be executed. In many cases this generation is highly complex even for a single robot, and gets harder when a swarm of robots is involved or when heterogeneous robots interact with each other. Secondly, dependable validation methods will be needed that go beyond mere algorithmic analysis and are capable of proving complex real-world properties of robot behaviors. For example, Isaac Asimov’s famous Three Laws of Robotics are such complex properties that are undeniably desirable, but by today’s techniques extremely hard to accomplish in a real robotic system, and hardly ever provable for all circumstances. The field of ER provides promising ideas that might bring forth methods to treat these issues in the future.

The contributions of this thesis to the field of ER can be arranged along the axes of (a) trustworthiness of both the behavior generation process and the resulting behaviors (mainly items 2., 3. and 4. in the chapter-wise listing below), and (b) generation of complex behaviors for autonomous robots (mainly item 3. below). Further contributions concern the field of ABS (item 1.). Following the chapter structure of the thesis, the major contributions can be summarized as follows:

1. Proposal, implementation and evaluation of a programming pattern for agent-based simulations intended to improve structuredness and code reusability in implementations by non-expert programmers (Chap. 3). Experiments with student test persons suggest that the proposed architecture implemented within the simulation program EAS yields more structured and reusable implementations than the state-of-the-art simulation programs MASON and NetLogo.
2. Proposal of a novel FSM-based control model for robots (Moore Automaton for Robot Behavior; MARB) and a corresponding decentralized online-evolutionary framework, both applicable to various types of robots (Chap. 4). A comprehensive evaluation shows that robot behaviors of complexities comparable to the current state-of-the-art from literature can be evolved, by yielding fairly analyzable robot programs, thus, contributing to the trustworthiness of evolved behaviors in ER.
3. Proposal of a highly flexible genotype-phenotype mapping based on FSMs (Moore Automaton for Protected Translation; MAPT) which, by mimicking the process of DNA to protein translation in nature, can be evolved along with robot behavior, leading to an automatic adaptation of the evolutionary operators to a given search space structure (Chap. 5). It is shown by extensive evaluation that the approach can lead to the desired adaptation and furthermore to a significant improvement of the evolutionary outcomes. The question of the extent, to which the approach can support the evolution of truly complex behavior, has to be finally resolved in future work. Nevertheless, the flexibility of the genotype-phenotype mapping and the system’s capability to control essential aspects of its own evolution in a highly recursive manner build a foundation for a broad range of applications and further research options (see below).
4. Proposal and evaluation of a formal framework for the prediction of success in evolutionary approaches involving complex environments (Chap. 6). By measuring the qualities of both fitness-based (explicit) and environmental (implicit) selection in variable states of abstractions from an intended real-world scenario (purely probabilistic estimations – simulation runs – laboratory experiments etc.), a probability of successful behavior evolution in the real environment can be estimated. Experiments with so far rather artificial simulation scenarios show that the model prediction matches the experimental outcome with a high precision.

In the following, a more detailed summary of the main topics of the thesis and an outlook to future work are given, according to the structure given by the two ER axes as well as the distinct ABS axis.

Agent-based simulation. There exists a large body of simulation frameworks, each of which provides different levels of complexity, various types of features and different matureness of documentation while requiring different degrees of user skills. This situation makes it difficult for non-expert users to choose an appropriate simulation framework and quickly begin programming individual simulations. The Simulation Plugin Interface (SPI) proposed in Chap. 3 is an architectural concept intended to provide programmers with a coherent interface which can be utilized to make existing simulations extendable in an inherently well-structured way. The SPI enforces users to program within these structures whatever type of simulation they are implementing, from simple extensions of existing simulations to complex simulation toolkits. In this way, errors and misconceptions can be found at an early stage, often at compilation time. Furthermore, by using the SPI, the software automatically gets reusable in a hierarchical way meaning that users can easily program extensions to simulations without having to alter any parts of the existing code. Additional implementations can be plugged in or out as desired and remain completely distinct from the core implementation. From this perspective, any implementation within the SPI architecture provides a new shell around the existing simulation core which, in turn, can be reused without being altered from “outside”. Experiments with student test persons imply that implementations made by unskilled programmers, using the SPI as part of the presented ABS Framework EAS, are better-structured and more reusable than the according reference implementations using NetLogo and MASON. On the other hand, the time required by the test persons for implementing their simulation programs is comparable to the time required with MASON or NetLogo (for this statement, however, implementation parts have to be ignored which clearly rely on MASON’s or NetLogo’s far-developed auxiliary tools which have lacked a counterpart in the early EAS version used for the experiments).

To provide more specific insights in the advantages offered by the SPI architecture, more experiments with a larger group of test persons are required. There, particularly more comprehensive methods for measuring the implementation quality, as known from software engineering, are desirable to allow for a more detailed analysis and to possibly find further improvement possibilities. Furthermore, due to the universality of the SPI architecture, an implementation within most existing simulation programs is possible (Chap. 3 gives some clues to how this can be done). An integration in a simulation program such as MASON could yield insights about the accomplishments of the SPI architecture unbiased by the particular implementation given by EAS.

Trustworthiness. Most currently published successful approaches in ER are basing controllers on ANNs or similarly complex structures that, being Turing-complete in the most general case, provide for the greatest possible behavioral flexibility. However, Turing-completeness by itself implies that even from a solely algorithmic point of view arbitrary controllers cannot be automatically tested for any non-trivial properties. Moreover, even for the several constrained classes of ANNs commonly used in ER no analyzing methods for arbitrary controllers are known, neither automatic nor manual – using “common sense”. Rather, behavioral properties are usually graded by observation and fitness measurement ^{[86], [139]}, both of which methods provide statistic evidence only, and lack even a statement of confidence as it is unknown which untested situations might cause failures.

Chapters 4 and 5 show that much simpler controllers, namely MARB controllers which are completely representable by FSMs, can be used to evolve behaviors of comparable complexity as known from current literature (limited to completely evolutionary methods; cf. discussion in Chap. 2). For that purpose, an Embodied Evolution (EE) approach has been proposed and studied in simulation as well as with real robots. FSMs are both intuitively understandable for humans and provide a large body of theory including analyzing methods at an algorithmic level. Chap. 4 provides examples of how basic behavioral properties can be proven by simply testing the reachability of states. Therefore, particularly for critical applications where failures may cause unforeseeable harm, MARBs can be used to generate trustworthy controllers. Recently, this has been done in a medical application by Jung et al. using MARBs to generate controllers for a robotic exoskeleton walking assistant with crutches for paraplegic patients ^[88], cf. Fig. 7.1.

Fig. 7.1. MARB-controlled walk intention detection algorithm in a robotic exoskeleton with crutches. The figure shows a walking experiment with a paraplegic patient performed by a group of researchers from South Korea and the ETH Zurich.

However, the potentials of automatically analyzing MARBs have been discussed rather briefly in this thesis. Beyond mere state reachability more complex properties might be of interest such as “which sensor input sequences can lead to a certain state or operation”. Such properties include the calculation of condition satisfiability which is in its essence equivalent to the NP complete propositional satisfiability (SAT) problem. Nevertheless, due to the small size and inherent structuredness of most conditions, this problem is expected to be treatable fairly easily, for example using SAT solvers which are, on average, highly efficient today. Classic FSM techniques such as minimization of automata can also be considered when analyzing MARBs. Future work should involve studying these issues to enhance the trustworthiness of the model. However, looking one step further, these aspects of trustworthiness still cover the algorithmic level only. The equally important question of how an algorithmic analysis can be transferred into real-world behavioral assertions remains, to a great extent, an open issue and another major subject for future research.

A different aspect of trustworthiness is addressed in Chap. 6, where the question is treated, how successful an evolutionary run will be when performed in a real-world environment. As real-world experiments can be very expensive, providing an accurate success prediction before the actual run can be of great importance. There has been a lot of theoretical work aiming at the calculation of the expected success of an evolutionary run in the fields of classic EC, spatially structured evolutionary algorithms, evolutionary optimization under uncertainty or in noisy environments and ER; on the other hand, great effort has been made by evolutionary biologists to understand population dynamics in nature (cf. discussion in Sec. 2.1.9 of Chap. 2). However, to the knowledge of the author, there exists so far no theoretical model including both implicit (environmental) and explicit (fitness-based in terms of classic EC) selection in the calculation of success. The combination of these two types of selection is considered typical to ESR and occurs neither in classic EC nor in evolutionary biology. The proposed model provides a prediction method based on Markov chains driven by data from previous simulation or laboratory runs. It bridges the reality gap by abstraction from scenario details and focussing on variables expected to be of major importance to the success of a run. Results show that the model is well applicable to several example scenarios.

However, so far experiments have been performed solely in simple simulated environments and by using selection methods designed to closely suit the model requirements. It remains to be shown that the model is applicable to more realistic real-robot scenarios, too. Furthermore, mutation is not yet explicitly considered by the model meaning that the prediction is constrained to periods without mutation. As different chains of mutation can lead to greatly differing results in terms of behavioral quality, including mutation into the model is another major concern for future work.

Complex behavior generation. One of the great open problems in ER is the question of weather or not it is possible to evolve truly complex behavior. More precisely, for behaviors exceeding a certain complexity, no purely evolutionary experiment so far has been capable to manage the bootstrap from an initial population of robots with trivial or random controllers to a population of robots performing the desired behavior. On the other hand, natural evolution has been capable of evolving organisms of much higher complexity than this threshold which suggests that the natural mechanisms might not be sufficiently well exploited in ER.

In Chap. 5, an evolutionary setting is proposed that evolves the genotype-phenotype mapping (GPM) along with the behavior, replicating nature’s mechanism of evolving the translation process from DNA to proteins along with the evolution of the organisms’ phenotypes. Changing the GPM implies a change of the effects of genotypic mutations to the resulting robot behaviors on the phenotype level. Furthermore, as the GPM is encoded among the behavioral properties in a robot’s genotype, it is translated together with them by “an earlier version of itself” to become part of a robot’s phenotype (which consists of the behavior defined by a MARB and the GPM defined by a MAPT). Therefore, adapting the effects of evolutionary operations on the phenotypic level as described above recursively includes adapting the effects of these operations on the GPM. In this way, GPMs and, in consequence, mutation strategies for both the evolution of behaviors and of the GPM can be coevolved to match the search space features given by the target behavior to evolve and the according environmental properties.

While there exist approaches to adapt the effects of evolutionary operations during evolution (the most prominent being the Evolution Strategies, cf. discussions in Chapters 2 and 5), they usually require fixed top-level operations, i.e., “the meta-mutation operation which changes the effects of the mutation operation remains unchanged”. Using the recursively self-adapting GPM structure proposed here, there is only one level of evolutionary operations rather than a hierarchy of meta-operations, thus allowing for an adaptation of the effects of these operations in a highly flexible way. Experiments in simulated EE show that the approach allows for the GPM to successfully adapt to given search spaces as intended, thus increasing evolvability. Furthermore, for the behaviors evolved in Chap. 4 using classic static evolution, a significantly higher success rate has been achieved with the evolvable GPM. Therefore, the approach using an evolvable GPM provides a robust foundation for evolving these behaviors in an EE setting.

Nevertheless, for several tested behaviors of higher complexities, for example, orientation in a dynamically changing environment, so far no successful results have been achieved. This suggests that the observed improvements might originate not only from the desired increase in evolvability due to the evolvable GPM, but primarily from effects such as an increased population diversity. One reason for a potentially insufficient exploitation of the GPM flexibility might be the syntactical and computational constraints induced by the usage of FSMs. A good starting point for further research is, therefore, to transfer the approach to ANN controllers. As these have fewer syntactical restrictions and a greater computational flexibility than FSMs they might allow for a smoother evolution of the GPM (Chap. 5 discusses some important issues concerning the implementation of the approach using ANNs). For this purpose the above-mentioned structural advantages of FSMs would have to be given up, but hopefully insights from such studies might eventually be transferred back to FSM-based evolution.

Furthermore, the approach has shown to improve evolvability in a specifically designed test scenario. Therefore, another way of improving the adaptation of GPMs can be to more accurately investigate the test scenario and carefully transfer it into a more realistic scenario.

Finally, the EE approach followed in this thesis might be unfavorable for a proper functioning of evolvable GPMs as it implies constraints to selection and fitness calculation. A centralized and offline evolutionary approach might provide means to more accurately select for desired behavioral and translator properties. In principle, the proposed evolvable GPM is not even limited to ER, but suitable for many evolutionary settings. Overall, the approach is promising to enhance evolutionary systems in their ability to generate complexity, however, solving the problem of adjusting it properly might still require a lot of effort.

Closing statement

The field of ER and its subfield ESR offer great potentials for the automatic creation of robotic behaviors. However, the road which has to be followed until evolution of reliable complex autonomous robotic systems may get into reach still involves obstacles and unresolved problems. While it is likely that significant progress will be made in near future, it is unforeseeable from today’s perspective if systems comparable to nature’s simplest animal “robots” such as flies or spiders will ever be achievable by artificial processes. As long as the natural example seems unattainable, a noticeable thought is that not killing a fly or a spider may always be a greater contribution to complexity in the world than putting the highest possible effort in building a sophisticated robot. Considering this and setting it into relation to the actual amount of animals, including humans, coming to harm from consequences of human progress, elucidates the high moral responsibility which technological research overall and ER in particular have. Apart from mere progress, scientists should be aware of the implications of their findings and responsibly put them into perspective before letting them enter a self-organized and market-driven application phase. If used wisely, major advancements in every-day life as well as in many important fields of research and application can be expected through ER in the years and decades to come.