Lukas König - Complex Behavior in Evolutionary Robotics

Preamble:

First Law: A robot may not injure a human being or, through inaction, allow a human being to come to harm.

Second Law: A robot must obey the orders given to it by human beings, except where such orders would conflict with the First Law.

Third Law: A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.

The Three Laws of Robotics by Isaac Asimov

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 Asimovs famous Three Laws of Robotics are such complex properties that are undeniably desirable, but by todays 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 (). 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 (). 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 (). 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 systems 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 (). 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.