Guiding Evolution of Complex Robot Behaviours:
Virtual Sensors and Task DecompositionDavid Wilcock
24th September 1998
abstract
This project tackles issues of scalability and reality transfer in evolutionary (in simulation) robotics through the hard task of scoring goals in robot football.
The use of vision addresses sensory complexity and a novel technique of object level representation, using software or virtual sensors to provide such a description, is implemented and seen to work. The use of task decomposition addresses task complexity, allowing division of a complete task into simpler sub-behaviours and potentially making an intractable problem tractable. Both of these are hybrid engineering/evolution approaches and the results show that designer input can improve tractability but there is a danger that sub-optimal solutions may be imposed. Genetic programming, in conjunction with the logic tree architecture of [Lee 97] is used.
Evolutionary robotics is the application of evolutionary algorithms to the synthesis of robot controllers. Evolution is typically done in simulation because of the impractical time required to do this in the real environment. As a field it has emerged as a response to the growing realisation that ''interesting robots may be too difficult to design'' [Harvey et al. 93]. As such it's raison d'etre is to allow behavioural complexity beyond that imposed by the limitations of design and scalability of techniques to more complex task is therefore a critical issue. The aims of the project were to work at the current limit of behavioural complexity in evolutionary robotics, developing techniques that would allow progression beyond this. Successful reality transfer under pinned all aspects of design, and all techniques were validated by testing on a real robot 1
1A LAMI Khepera
The work is characterised by it's object level virtual sensor
approach to vision, task decomposition, use of genetic programming and
look-up table approach to modelling for simulation. The former two
tackle the issue of scalability: The use of vision addresses sensor
complexity; required for more complex tasks. The use of task
decomposition addresses task complexity, allowing division of a
complete task into simpler sub-behaviours and potentially making an
intractable problem tractable to the evolutionary algorithm.
The task of scoring goals in robot football is decomposed into simpler sub-behaviours. At each divide is an arbitrator that selects which sub-behaviour is active. Arbitrator and behaviour modules have essentially the same architecture: a logic tree with sensor thresholds/comparisons at the leaves and a boolean output that is interpreted as robot motor commands [Lee 97]. The controller is entirely reactive.
The Genetic programming works on a population of controllers. Controllers are evaluated by running the controller on the simulated robot and calculating it's fitness via a fitness function that rewards desired behaviour.
A simulator written by
[Lee 97] in C was developed and adapted
for use in the project. A graphical display was added, using an
interface to MATLAB. Khepera control software was written that allowed
transfer of the evolved controllers (and virtual sensors) to the real
robot.
Virtual sensors that returned the object-level descriptions 'ball/goal visible (or not)' were synthesised using genetic programming, through training on a database of images taken using the Khepera's vision system.
Using large population sizes, goal and ball presence detectors with 82% and 87% correct classification, respectively were evolved. Reasons are given for the difficulty (large computational resources required for relatively unreliable sensors) GP has in solving this problem.
The virtual sensor approach is attractive because: Vision at the pixel level need not be simulated; easing implementation and computational requirements of the simulator. Controller tractability is improved by hiding the complexity of vision from the controller, by putting it in a `black box'. A potential criticism is that the perceptual constructs chosen by the designer may prevent a more efficient, simpler `solution'; one that could evolve if the perceptual constructs, with access to the raw pixel data, were free to evolve.
The sgpc GP engine [Tackett and Carmi] was modified to evolve the
virtual sensors. Collection of the image database was automated
through Khepera control software. As was the IR and Khepera-movement
look-up tables...
This is a data intensive method that involves sub-sampling of sensor response or movement in the real world. For example an IR sensor response to a wall is measured over varying distance and orientation to the wall. Given a particular situation in simulation the actual responses of the sensors can then be recalled -- recreating a faithful representation of the robot's world. Movement as a function of motor command can be similarly captured.
Simulation of the virtual sensors is in the same ethos; the evolved
sensor is run on the database of images and analysis of variance is
used to identify parameters (recorded during data collection, e.g.
distance-to-ball) that effect performance. Sensor performance can then
be predicted in simulation through indexing a performance look-up
table with the current positional parameters.
Successful, consistent, evolution of all controllers in simulation is shown, including a controller that could push the ball to the goal from any starting position in proximity to the ball. Populational requirements are low; typically an order of magnitude less than most similar work, indicating that the GP and controller architecture are particularly efficient. The inclusion of the high bandwidth vision sense has not increased populational requirements over those required by simpler senses -- this is a result of the object level modelling of vision 2.
Some comments and guidelines on GP as a behavioural level programming/design methodology are given.
The evolved controllers could cope with the unreliability of the sensors, sometimes evolving novel behaviours that would have required radically lateral thinking on behalf of a designer. The ease of evolution indicated that the perceptual constructs imposed by the designer did not hinder evolution in this case.
Reality transfer was successful for the most part, with qualitatively and occasionally quantitatively identical behaviour in simulation and reality. A quirk of the sensors, [understandably] overlooked in the modelling prevented one transfer.
A monolithic push-to-goal controller was also evolved. This considerably outperformed the hierarchical one, indicating that [unintended] bad design can prune `solutions' from the search space. Some heuristics for task decomposition are given from the lessons learnt.
The results contribute to issues of combining engineering design and evolution. The work is relevant in that behaviours were evolved at the current limit of behavioural complexity in evolutionary robotics. The techniques show promise in terms of scalability, partially validated in this respect by working on a complex task. Comparative work is needed to fully evaluate the efficacy of the virtual sensor approach.
2However it should be noted that, prior to
controller evolution, virtual sensor evolution required much
computation.