[back]

Evolutionary Design Synthesis – From Sensors to Controllers
Yizhen Zhang, Alcherio Martinoli, Erik Antonsson

Abstract. In this project, an automated engineering design synthesis methodology based on evolutionary methodology is being explored, with special interest on design and optimization of distributed embodied systems. Two case studies have been considered so far; the first one concerns the design of a collective sensory system for traffic monitoring purposes, while the second one deals with the development of neural-based robot controllers for turbine blades inspection. It has been shown that the evolutionary methodology is able to address the engineering design challenges present in the case studies as well as other complex design problems, and synthesize novel design solutions of good quality. Moreover, the fitness function can be formulated as an aggregation of fuzzy design preferences with different weights and trade-off strategies leading to an automatic generation of the complete Pareto-optimal frontier.

Motivation. Design has traditionally been a creative process that requires human ingenuity and experience. In modern engineering design process, highly complex design tasks such as the development of intelligent vehicles [Martinoli 2002] or swarms of miniature robots for internal turbine inspections are characterized by severe reliability and robustness requirements. The main challenges in designing such complex, distributed, embedded systems include, but are not limited to, the following difficulties [Zhang 2003]:

• high, or sometimes even a priori unknown, complexity of good design solutions
• multiple objectives, competing factors, trade-offs and/or simultaneous hardware and software optimization requirements
• the evaluation process and result for a given design solution can be intrinsically dynamic and stochastic instead of static and deterministic

All these problems make it difficult for an engineer, using traditional engineering methods, to synthesize an appropriate design solution under complex system design requirements.

Research. Up until now, no traditional engineering methods have been available for meeting all of the challenges mentioned above. As a result, we look at biological systems as a source of inspiration. The principal advantage of a biologically inspired approach is that such techniques have stood the test of eons of competition and evolution. Not only are these techniques robust, they also having the advantage of being fairly scalable and applicable to distributed systems which might consist of heterogeneous agents.

In this project, an evolutionary computation methodology based on Genetic Algorithms (GA) [Goldberg 1989, Mitchell 1996] and Evolutionary Strategy (ES) [Bäck 1996] is applied. The methodology works off-line (i.e. based on a realistic simulator) and generates new design solutions in an autonomous way. It is platform-independent, system-oriented, and faithful enough to be transported onto real hardware. It allows variable chromosome lengths to evolve solutions of suitable complexity. Multiple competing factors can be expressed as design preferences using fuzzy sets and then aggregated into the fitness function with different weights and trade-off strategies, which can be tuned to evolve the whole family of achievable engineering design trade-offs, i.e., the Pareto-optimal frontier. In case the evaluation process is of stochastic properties, multiple re-evaluations are employed to select robust solutions which can survive over generations, and a final fair test of an equal number of evaluations is used to assess the most efficient and robust solution.

Sample collective robotic scenarios are simulated in Webots [Michel 1998], a 3D, embodied, and sensor-based robot simulator. In the first case study, a simplified model of a human driver, aware of its own speed, position, orientation, and what lies within its field of view, tries to keep a safe distance from other vehicles and decides to either follow or change lanes on a straight three-lane highway (see Figure 1a). A collective sensory system is evolved on the smart vehicle to monitor and judge the safety or danger of the current state.

Figure 1. Screenshots of Webots 2.0 simulation program

In the second case study, the robot is equipped with necessary sensorial abilities, and a controller is being evolved for the robot to closely inspect as much blade surfaces as possible without any collisions. Up to date, two simplified blade shapes have been considered: cylinders and bars (see Figure 1b & c, where the small green dot is the robot). More realistic blade shapes will be introduced later. The Artificial Neural Network (ANN) architectures considered are shown in Figure 2. They may consist of 2 or 3 neural layers, with or without recurrent connections (indicated by blue dashed lines). So far, the input layer includes just on-board local sensors, and only the synaptic strengths of connections are evolved by the algorithm for a fixed ANN architecture. In the future, the ANN architecture itself could also be evolved by the evolutionary algorithm, i.e. a connection could be added or deleted between any two neurons or even a neuron could be added into or deleted from the architecture.

Figure 2. ANN architectures used in the second case study

Achievements. In the first case study, the evolutionary algorithm is used to determine the optimal number and configuration of the proximity sensors mounted on the vehicle. The proposed solutions of sensory configurations are evaluated in the traffic scenarios simulated in Webots and get improved through the evolutionary loop.
To understand how noise influences the evolved solution and to minimize the computational cost for evolution, a series of different types of tests, including static, quasi-static and full coverage tests, are also implemented as evaluation tests in the evolutionary loop in addition to the embodied test. A probability density function (PDF) generated from the data collected in the embodied simulation is used in quasi-static and full coverage tests to reflect the traffic pattern, distinct from a uniform pattern which has a flat PDF. Four different cases (20 sensors or variable number of sensors, and forcing symmetry or not) are investigated for each type of tests. The best evolved solutions in a given test are cross-evaluated with those of the other tests.

As a result, different sensor configuration solutions have been evolved according to the evaluation criteria selected by the designer. A whole family of different achievable trade-offs evolved by the algorithm under different settings constitutes an approximate feasible Pareto optimal frontier for this design problem. For more results and figures, please refer to [Antonsson 2003, Zhang 2003]. For the second case study, the same evolutionary methodology has been able to evolve robot controllers that could closely inspect the 2D simplified blades without collisions. We are currently extending the controller architectures to enhance (probabilistic) completeness and reduce redundancy in coverage.

Publications/References
Antonsson E. K., Zhang Y., and Martinoli A., “Evolving Engineering Design Trade-Offs”. Proc. of the ASME 15th Int. Conf. on Design Theory and Methodology, September 2003, Chicago, IL. To appear.

Zhang Y., Martinoli A., Antonsson E. K., and Olney R., “Evolution of Sensory Configurations for Intelligent Vehicles”. Proc. of the IEEE Intelligent Vehicles Symp., June 2003, Columbus, OH, pp. 351-356.

Zhang Y., Martinoli A., and Antonsson E. K., “Evolutionary Design of a Collective Sensory System”. In H. Lipson, E. K. Antonsson, and J. R. Koza, editors, Proc. of the 2003 AAAI Spring Symposium on Computational Synthesis, March 2003, Stanford , CA , pp. 283-290.

Martinoli A., Zhang Y., Prakash P., Antonsson E. K., and Olney R. D., “Towards Evolutionary Design of Intelligent Transportation Systems”. Proc. of the Eleventh International Symposium of the Associazione Tecnica dell'Automobile on Advanced Technologies for ADAS Systems, October 2002, Siena, Italy.

Michel O., “Webots: Symbiosis between Virtual and Real Mobile Robots”. In Heuding J.-C., editor, Proc. of the First Int. Conf. on Virtual Worlds, July 1998, Paris, France, pp. 254-263, Springer Verlag. See also http://www.cyberbotics.com

Bäck T., “Evolutionary Algorithms in Theory and Practice”. Oxford University Press, New York, NY, 1996.

Mitchell M., “An Introduction to Genetic Algorithms”. The MIT Press, Cambridge, MA, 1996.

Goldberg D. E., “Genetic Algorithms in Search, Optimization, and Machine Learning”. Addison-Wesley, Reading, MA, 1989.