Engineering topics

Hornby, Gregory S.

Publications and source records attributed to Hornby, Gregory S..

17 records

NASA NTRS2009

Steady-State ALPS for Real-Valued Problems

The two objectives of this paper are to describe a steady-state version of the Age-Layered Population Structure (ALPS) Evolutionary Algorithm (EA) and to compare it against other GAs on real-valued problems. Motivation for this work comes from our previous success in demonstrating that a generational version of ALPS greatly improves search performance on a Genetic Programming problem. In making steady-state ALPS some modifications were made to the method for calculating age and the method for moving individuals up layers. To demonstrate that ALPS works well on real-valued problems we compare it against CMA-ES and Differential Evolution (DE) on five challenging, real-valued functions and on one real-world problem. While CMA-ES and DE outperform ALPS on the two unimodal test functions, ALPS is much better on the three multimodal test problems and on the real-world problem. Further examination shows that, unlike the other GAs, ALPS maintains a genotypically diverse population throughout the entire search process. These findings strongly suggest that the ALPS paradigm is better able to avoid premature convergence then the other GAs.

Hornby, Gregory S.↗

NASA NTRS2008

Evolving MEMS Resonator Designs for Fabrication

Because of their small size and high reliability, microelectromechanical (MEMS) devices have the potential to revolution many areas of engineering. As with conventionally-sized engineering design, there is likely to be a demand for the automated design of MEMS devices. This paper describes our current status as we progress toward our ultimate goal of using an evolutionary algorithm and a generative representation to produce designs of a MEMS device and successfully demonstrate its transfer to an actual chip. To produce designs that are likely to transfer to reality, we present two ways to modify evaluation of designs. The first is to add location noise, differences between the actual dimensions of the design and the design blueprint, which is a technique we have used for our work in evolving antennas and robots. The second method is to add prestress to model the warping that occurs during the extreme heat of fabrication. In future we expect to fabricate and test some MEMS resonators that are evolved in this way.

Hornby, Gregory S.↗

NASA NTRS2006

Automated Antenna Design with Evolutionary Algorithms

Current methods of designing and optimizing antennas by hand are time and labor intensive, and limit complexity. Evolutionary design techniques can overcome these limitations by searching the design space and automatically finding effective solutions. In recent years, evolutionary algorithms have shown great promise in finding practical solutions in large, poorly understood design spaces. In particular, spacecraft antenna design has proven tractable to evolutionary design techniques. Researchers have been investigating evolutionary antenna design and optimization since the early 1990s, and the field has grown in recent years as computer speed has increased and electromagnetic simulators have improved. Two requirements-compliant antennas, one for ST5 and another for TDRS-C, have been automatically designed by evolutionary algorithms. The ST5 antenna is slated to fly this year, and a TDRS-C phased array element has been fabricated and tested. Such automated evolutionary design is enabled by medium-to-high quality simulators and fast modern computers to evaluate computer-generated designs. Evolutionary algorithms automate cut-and-try engineering, substituting automated search though millions of potential designs for intelligent search by engineers through a much smaller number of designs. For evolutionary design, the engineer chooses the evolutionary technique, parameters and the basic form of the antenna, e.g., single wire for ST5 and crossed-element Yagi for TDRS-C. Evolutionary algorithms then search for optimal configurations in the space defined by the engineer. NASA's Space Technology 5 (ST5) mission will launch three small spacecraft to test innovative concepts and technologies. Advanced evolutionary algorithms were used to automatically design antennas for ST5. The combination of wide beamwidth for a circularly-polarized wave and wide impedance bandwidth made for a challenging antenna design problem. From past experience in designing wire antennas, we chose to constrain the evolutionary design to a monopole wire antenna. The results of the runs produced requirements-compliant antennas that were subsequently fabricated and tested. The evolved antenna has a number of advantages with regard to power consumption, fabrication time and complexity, and performance. Lower power requirements result from achieving high gain across a wider range of elevation angles, thus allowing a broader range of angles over which maximum data throughput can be achieved. Since the evolved antenna does not require a phasing circuit, less design and fabrication work is required. In terms of overall work, the evolved antenna required approximately three person-months to design and fabricate whereas the conventional antenna required about five. Furthermore, when the mission was modified and new orbital parameters selected, a redesign of the antenna to new requirements was required. The evolutionary system was rapidly modified and a new antenna evolved in a few weeks. The evolved antenna was shown to be compliant to the ST5 mission requirements. It has an unusual organic looking structure, one that expert antenna designers would not likely produce. This antenna has been tested, baselined and is scheduled to fly this year. In addition to the ST5 antenna, our laboratory has evolved an S-band phased array antenna element design that meets the requirements for NASA's TDRS-C communications satellite scheduled for launch early next decade. A combination of fairly broad bandwidth, high efficiency and circular polarization at high gain made for another challenging design problem. We chose to constrain the evolutionary design to a crossed-element Yagi antenna. The specification called for two types of elements, one for receive only and one for transmit/receive. We were able to evolve a single element design that meets both specifications thereby simplifying the antenna and reducing testing and integration costs. The highest performance antenna found using a getic algorithm and stochastic hill-climbing has been fabricated and tested. Laboratory results correspond well with simulation. Aerospace component design is an expensive and important step in space development. Evolutionary design can make a significant contribution wherever sufficiently fast, accurate and capable software simulators are available. We have demonstrated successful real-world design in the spacecraft antenna domain; and there is good reason to believe that these results could be replicated in other design spaces.

Hornby, Gregory S.↗

NASA NTRS2006

ALPS: The Age-Layered Population Structure for Reducing the Problem of Premature Convergence

To reduce the problem of premature convergence we define a new attribute of an individual, its age, and propose the Age-Layered Population Structure (ALPS), in which age is used to restrict competition and breeding between members of the population. ALPS differs from a typical EA by segregating individuals into different age-layers by their age - a measure of how long the genetic material has been in the population - and by regularly replacing all individuals in the bottom layer with randomly generated ones. The introduction of new, randomly generated individuals at regular intervals results in an EA that is never completely converged and is always looking at new parts of the fitness landscape. By using age to restrict competition and breeding search is able to develop promising young individuals without them being dominated by older ones. We demonstrate the effectiveness of the ALPS algorithm on an antenna design problem in which evolution with ALPS produces antennas more than twice as good as does evolution with two other types of EAs. Further analysis shows that the ALPS model does allow the offspring of newly generated individuals to move the population out of mediocre local-optima to better parts of the fitness landscape.

Hornby, Gregory S.↗

NASA NTRS2006

Generative Representations for Computer-Automated Evolutionary Design

With the increasing computational power of computers, software design systems are progressing from being tools for architects and designers to express their ideas to tools capable of creating designs under human guidance. One of the main limitations for these computer-automated design systems is the representation with which they encode designs. If the representation cannot encode a certain design, then the design system cannot produce it. To be able to produce new types of designs, and not just optimize pre-defined parameterizations, evolutionary design systems must use generative representations. Generative representations are assembly procedures, or algorithms, for constructing a design thereby allowing for truly novel design solutions to be encoded. In addition, by enabling modularity, regularity and hierarchy, the level of sophistication that can be evolved is increased. We demonstrate the advantages of generative representations on two different design domains: the evolution of spacecraft antennas and the evolution of 3D objects.

Hornby, Gregory S.↗

NASA NTRS2006

A Modular Robotic System with Applications to Space Exploration

Modular robotic systems offer potential advantages as versatile, fault-tolerant, cost-effective platforms for space exploration, but a sufficiently mature system is not yet available. We describe the possible applications of such a system, and present prototype hardware intended as a step in the right direction. We also present elements of an automated design and optimization framework aimed at making modular robots easier to design and use, and discuss the results of applying the system to a gait optimization problem. Finally, we discuss the potential near-term applications of modular robotics to terrestrial robotics research.

Hancher, Matthew D.↗

NASA NTRS2005

Measuring, Enabling and Comparing Modularity, Regularity and Hierarchy in Evolutionary Design

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 modularity. regularity and hierarchy.

Hornby, Gregory S.↗

NASA NTRS2004

Generative Representations for Computer-Automated Design Systems

With the increasing computational power of Computers, software design systems are progressing from being tools for architects and designers to express their ideas to tools capable of creating designs under human guidance. One of the main limitations for these computer-automated design programs is the representation with which they encode designs. If the representation cannot encode a certain design, then the design program cannot produce it. Similarly, a poor representation makes some types of designs extremely unlikely to be created. Here we define generative representations as those representations which can create and reuse organizational units within a design and argue that reuse is necessary for design systems to scale to more complex and interesting designs. To support our argument we describe GENRE, an evolutionary design program that uses both a generative and a non-generative representation, and compare the results of evolving designs with both types of representations.

Hornby, Gregory S.↗

NASA NTRS2004

Shortcomings with Tree-Structured Edge Encodings for Neural Networks

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 preexisting 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.

Hornby, Gregory S.↗

NASA NTRS2004

Improving Evolvability through Generative Representations

One of the main limitations of computer automated design systems is the representation used for encoding designs. Using computer programs as an analogy, representations can be thought of as having the properties of combination, control-flow and abstraction. Generative representations are those which have the ability to reuse elements in an encoding through either iteration, a form of control-flow, or abstraction. Here we argue that generative representations improve the evolvability of designs by capturing design dependencies in a way that makes them easier to change, and we support this with examples from two design substrates.

Hornby, Gregory S.↗

NASA NTRS2004

Using Generative Representations to Evolve Robots

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.

Hornby, Gregory S.↗

NASA NTRS2004

An Evolved Antenna for Deployment on NASA's Space Technology 5 Mission

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 similar performance. Both were comparable in performance to a hand-designed antenna produced by a contractor for the mission, and so we consider them examples of human-competitive performance by evolutionary algorithms. One of the evolved antenna prototypes is undergoing flight qualification testing.

Lohn, Jason D.↗

NASA NTRS2004

Properties of Artifact Representations for Evolutionary Design

To achieve evolutionary design systems that scale to the levels achieved by man-made artifacts we can look to their characteristics of modularity, hierarchy and regularity to guide us. For this we focus on design representations, since they strongly determine the ability of evolutionary design systems to evolve artifacts with these characteristics. We identify three properties of design representations - combination, control-flow and abstraction - and discuss how they relate to hierarchy, modularity and regularity.

Hornby, Gregory S.↗

NASA NTRS2004

Autonomous Evolution of Dynamic Gaits with Two Quadruped Robots

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 10/min/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, Gregory S.↗

NASA NTRS2003

Generative Representations for Evolving Families of Designs

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, Gregory S.↗

NASA NTRS2003

Evolutionary Design of an X-Band Antenna for NASA's Space Technology 5 Mission

We present an evolved X-band antenna design and flight prototype currently on schedule to be deployed on NASA s Space Technology 5 spacecraft in 2004. The mission consists of three small satellites that wall take science measurements in Earth s magnetosphere. The 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 genetic algorithms were used: one allowed branching an the antenna arms and the other did not. The highest performance antennas from both algorithms were fabricated and tested. A handdesigned antenna was produced by the contractor responsible for the design and build of the mission antennas. The hand-designed antenna is a quadrifilar helix, and we present performance data for comparison to the evolved antennas. 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.

Lohn, Jason D.↗

NASA NTRS2003

Generative Representations for the Automated Design of Modular Physical Robots

We will begin with a brief background of evolutionary robotics and related work, and demonstrate the scaling problem with our own prior results. Next we propose the use of an evolved generative representation as opposed to a non-generative representation. We describe this representation in detail as well as the evolutionary process that uses it. We then compare progress of evolved robots with and without the use of the grammar, and quantify the obtained advantage. Working two- dimensional and three-dimensional physical robots produced by the system are shown.

Hornby, Gregory S.↗