Refereed Journal Articles

Hornby, G. S., Takamura, S., Yamamoto, T., and Fujita, M. Autonomous Evolution of Dynamic Gaits with Two Quadruped Robots. IEEE Transactions on Robotics, 21:3, 402 - 410, June 2005.

Abstract
A challenging task that must be accomplished for every legged robot is creating the walking and running behaviors needed for it to move. In this paper we describe our system for autonomously evolving dynamic gaits on two of Sony's quadruped robots. Our evolutionary algorithm runs on board the robot and uses the robot's sensors to compute the quality of a gait without assistance from the experimenter. First we show the evolution of a pace and trot gait on the OPEN-R prototype robot. With the fastest gait, the robot moves at over 10m/min., which is more than forty body-lengths/min. While these first gaits are somewhat sensitive to the robot and environment in which they are evolved, we then show the evolution of robust dynamic gaits, one of which is used on the ERS-110, the first consumer version of AIBO.

Hornby, G. S. Functional Scalability through Generative Representations: the Evolution of Table Designs. Environment and Planning B: Planning and Design, 31(4), 569 - 587, July 2004.

Abstract
One of the main limitations for the functional scalability of computer automated design systems is the representation used for encoding designs. Here we describe a generative representation, a representation which allows reuse of elements in the encoding, as a way of augmenting evolutionary design systems to achieve greater functional scalability. We compare the generative representation against a non-generative representation and find that table designs evolved with the generative representation have higher fitness than table designs created with the non-generative representation. Further, we show that the evolved table-design representations are structured into meaningful ways that correspond to the height, dimensions and surface of the table.

Edited Works

Refereed Book Chapters

Hornby, G. S. Using Generative Representations to Evolve Robots. In, Evolutionary Machine Design: Methodology and Applications, N. Nedjah and L. Mourelle (eds). (in press).

Abstract
Recent research has demonstrated the ability of evolutionary algorithms to automatically design both the physical structure and software controller of real physical robots. One of the challenges for these automated design systems is to improve their ability to scale to the high complexities found in real-world problems. Here we claim that for automated design systems to scale in complexity they must use a representation which allows for the hierarchical creation and reuse of modules, which we call a generative representation. Not only is the ability to reuse modules necessary for functional scalability, but it is also valuable for improving efficiency in testing and construction. We then describe an evolutionary design system with a generative representation capable of hierarchical modularity and demonstrate it for the design of locomoting robots in simulation. Finally, results from our experiments show that evolution with our generative representation produces better robots than those evolved with a non-generative representation.

Lohn J., Hornby, G. S., and Linden D. An Evolved Antenna for Deployment on NASA's Space Technology 5 Mission. In, Genetic Programming Theory and Practice II, U.-M. O'Reilly and R. L. Riolo and T. Yu and B. Worzel (eds). Chapter 18, Kluwer, 2004.

Abstract
We present an evolved X-band antenna design and flight prototype currently on schedule to be deployed on NASA's Space Technology 5 (ST5) spacecraft. Current methods of designing and optimizing antennas by hand are time and labor intensive, limit complexity, and require significant expertise and experience. Evolutionary design techniques can overcome these limitations by searching the design space and automatically finding effective solutions that would ordinarily not be found. The ST5 antenna was evolved to meet a challenging set of mission requirements, most notably the combination of wide beamwidth for a circularly-polarized wave and wide bandwidth. Two evolutionary algorithms were used: one used a genetic algorithm style representation that did not allow branching in the antenna arms; the second used a genetic programming style tree-structured representation that allowed branching in the antenna arms. The highest performance antennas from both algorithms were fabricated and tested, and both yielded very similar performance. Both antennas were comparable in performance to a hand-designed antenna produced by the antenna contractor for the mission, and so we consider them examples of human-competitive performance by evolutionary algorithms. As of this writing, one of our evolved antenna prototypes is undergoing flight qualification testing. If successful, the resulting antenna would represent the first evolved hardware in space, and the first deployed evolved antenna.

Pollack, J. B., Lipson, H., Ficici, S. G., Funes, P., Hornby, G. and Watson, R. A. Evolutionary Techniques in Physical Robots. In Creative Evolutionary Systems, P. J. Bentley and D. W. Corne (eds). Morgan-Kaufmann, 2001.

Fujita, M., Hornby, G.S., Takamura, S., and Yamamoto, T. Identeki Algorithm wo motiita yonkyaku Robot no kokuo pattern no kurituteki sinka. Kitano, H. (ed), Chapter 6, Identeki Algorithm 4. Sangyou-Tosho Coorporation. 2000. (japanese)

Refereed Conference Proceedings

Lohn J., Hornby, G. S., and Linden D. Evolution, Re-evolution, and Prototype of an X-Band Antenna for NASA's Space Technology 5 Mission. Sixth International Conference on Evolvable Systems: From Biology to Hardware, 2005.

Abstract
One of the challenges in engineering design is responding to a change of design requirements. Previously we presented a four-arm symmetric evolved antenna for NASA's Space Technology 5 mission. However, the mission's orbital vehicle was changed, putting it into a much lower earth orbit, changing the specifications for the mission. With minimal changes to our evolutionary system, mostly in the fitness function, we were able to evolve antennas for the new mission requirements and, within one month of this change, two new antennas were designed and prototyped. Both antennas were tested and both had acceptable performance compared with the new specifications. This rapid response shows that evolutionary design processes are able to accommodate new requirements quickly and with minimal human effort.

Hornby, G. S. Measuring, Enabling and Comparing Modularity, Regularity and Hierarchy in Evolutionary Design. Genetic and Evolutionary Computation Conference. Springer-Verlag, 2005.

Abstract
For computer-automated design systems to scale to complex designs they must be able to produce designs that exhibit the characteristics of modularity, regularity and hierarchy -- characteristics that are found both in man-made and natural designs. Here we claim that these characteristics are enabled by implementing the attributes of combination, control-flow and abstraction in the representation. To support this claim we use an evolutionary algorithm to evolve solutions to different sizes of a table design problem using five different representations, each with different combinations of modularity, regularity and hierarchy enabled and show that the best performance happens when all three of these attributes are enabled. We also define metrics for modularity, regularity and hierarchy in design encodings and demonstrate that high fitness values are achieved with high values of modularity, regularity and hierarchy and that there is a positive correlation between increases in fitness and increases in the measured values of modularity, regularity and hierarchy.

Lohn, J. D., Linden, D. S., Hornby, G. S., Kraus, W. F., Rodriguez-Arroyo, A., Seufert, S. S. Evolutionary Design of a Single-Wire Circularly-polarized X-Band Antenna for NASA's Space Technology 5 Mission. Proc. IEEE Antennas and Propagation Society Symposium, 2005.

Globus A., Hornby G., Larchev G., Hancher M., Cannon H., Lohn J. Teleoperated Modular Robots for Lunar Operations. Proc. AIAA 1st Intelligent Systems Technical Conference, 2004.

Lohn J., Hornby G., Larchev G., Kraus W. Evolvable Hardware for Space Applications. Proc. AIAA 1st Intelligent Systems Technical Conference, 2004.

Hornby, G. S. Shortcomings with Tree-structured Edge Encodings for Neural Networks. Genetic and Evolutionary Computation Conference. Springer-Verlag, 2004.
Nominated for: Best Paper, GP Track.

Abstract
In evolutionary algorithms a common method for encoding neural networks is to use a tree-structured assembly procedure for constructing them. Since node operators have difficulties in specifying edge weights and these operators are execution-order dependent, an alternative is to use edge operators. Here we identify three problems with edge operators: in the initialization phase most randomly created genotypes produce an incorrect number of inputs and outputs; variation operators can easily change the number of input/output (I/O) units; and units have a connectivity bias based on their order of creation. Instead of creating I/O nodes as part of the construction process we propose using parameterized operators to connect to pre-existing I/O units. Results from experiments show that these parameterized operators greatly improve the probability of creating and maintaining networks with the correct number of I/O units, remove the connectivity bias with I/O units and produce better controllers for a goal-scoring task.

Lohn, J. D., Linden, D. S., Hornby, G. S., Kraus, W. F., Rodriguez-Arroyo, A., Seufert, S. S. Evolutionary Design of an X-band antenna for NASA's Space Technology 5 Mission. Proc. IEEE Antennas and Propagation Society Symposium, Vol. 3, 2313-2316, 2004.

Hornby, G.. S. Generative Representations for Evolving Families of Designs. Genetic and Evolutionary Computation Conference. Springer-Verlag, 2003.
Nominated for: Best Paper, GP Track.

Abstract
Since typical evolutionary design systems encode only a single artifact with each individual, each time the objective changes a new set of individuals must be evolved. When this objective varies in a way that can be parameterized, a more general method is to use a representation in which a single individual encodes an entire class of artifacts. In addition to saving time by preventing the need for multiple evolutionary runs, the evolution of parameter-controlled designs can create families of artifacts with the same style and a reuse of parts between members of the family. In this paper an evolutionary design system is described which uses a generative representation to encode families of designs. Because a generative representation is an algorithmic encoding of a design, its input parameters are a way to control aspects of the design it generates. By evaluating individuals multiple times with different input parameters the evolutionary design system creates individuals in which the input parameter controls specific aspects of a design. This system is demonstrated on two design substrates: neural-networks which solve the 3/5/7-parity problem and three-dimensional tables of varying heights.

Hornby, G. S. and Pollack, J. B. Body-Brain Co-evolution Using L-systems as a Generative Encoding. Genetic and Evolutionary Computation Conference. 2001.

Hornby, G.S., Fujita, M., Takamura, S., Yamamoto, T. and Hanagata, O. Autonomous Evolution of Gaits with the Sony Quadruped Robot. Proceedings of 1999 Genetic and Evolutionary Computation Conference (GECCO). Banzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, Smith, eds., Morgan Kauffmann, pp. 1297-1304. 1999.

Hornby, G. S. and Mirtich, B. Diffuse versus True Coevolution in a Physics-based World. Proceedings of 1999 Genetic and Evolutionary Computation Conference (GECCO). Banzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, Smith, eds., Morgan Kauffmann, pp. 1305-1312. 1999.

Watson, R. A., Hornby, G. S. and Pollack, J. B. Modeling Building-Block Interdependency . Parallel Problem Solving from Nature, proceedings of Fifth International Conference /PPSN V, Springer, pp.97-106. 1998.

Refereed Workshop Papers, and Posters

Hornby, G. S. Properties of Artifact Representations for Evolutionary Design. Workshop on Self-Organization and Development in Artificial and Natural Systems, Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9), 2004. Springer-Verlag.

Hornby, G. S. Improving Evolvability through Generative Representations. Workshop on Modularity, regularity and hierarchy in open-ended evolutionary computation, Proc. Genetic and Evolutionary Computation Conference, 2004. Springer-Verlag.

Hornby, G.. S. Creating Complex Building Blocks through Generative Representations AAAI Spring Symposium: Computation Synthesis: From Basic Building Blocks to High Level Functionality; TR SS-03-02, pp 98-105. AAAI Press, 2003.

Theses

Hornby, G. S. Generative Representations for Evolutionary Design Automation. Brandeis University, Dept. of Computer Science, Ph.D. Dissertation. 2003.