Evolutionary Computation Technologies for Space Systems Richard J. Terrile, Christoph Adami, Hrand Aghazarian, Savio N. Chau, Van T. Dang, Michael I. Ferguson, Wolfgang Fink, Terrance L. Huntsberger, Gerhard Klimeck, Mark A. Kordon, Seungwon Lee, Paul von Allmen and Joseph Xu Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA 91109 818-354-6158 [email protected] Abstract—The Evolvable Computation Group,1,2 at explore larger volumes of design space than could be NASA’s Jet Propulsion Laboratory, is tasked with examined by a human designer or by computational brute demonstrating the utility of computational engineering and force (i.e., complete enumeration, exhaustive search, or computer optimized design for complex space systems. The other deterministic search algorithms). group is comprised of researchers over a broad range of disciplines including biology, genetics, robotics, physics, The advantage of this approach is that it allows complex computer science and system design, and employs systems to be designed for and adapted to their environment biologically inspired evolutionary computational techniques (simulation or model) in the same way in which living and to design and optimize complex systems. Over the past evolving systems adapt to natural environments. Knowledge two years we have developed tools using genetic of how the design should be optimized is not required. The algorithms, simulated annealing and other optimizers to necessary components are a good simulation of the design improve on human design of space systems. We have environment, a framework that allows evolution and further demonstrated that the same tools used for computer- knowledge of what requirements are desired (fitness). aided design and design evaluation can be used for Competition and selection drive the systems to higher automated innovation and design. These powerful fitness and increased robustness. Computationally derived techniques also serve to reduce redesign costs and schedules. evolutionary designs have shown competitive advantages over human created designs in complexity, creativity and robustness. Our group has demonstrated this in the areas of TABLE OF CONTENTS power system design, low thrust trajectory optimization, robotic arm deployment path finding, MEMS micro-gyro 1. INTRODUCTION............................................1 calibration, mission planning and scheduling, neural 2. OVERVIEW..................................................1 network design, and avionics architecture design. We have 3. COMPUTER OPTIMIZED DESIGN......................3 also developed a framework for the rapid introduction and 4. RESULTS......................................................3 parallelization of optimization problems in an evolutionary 5. CONCLUSIONS..............................................8 environment using computer clusters. 6. ACKNOWLEDGEMENTS...................................9 REFERENCES....................................................9 These techniques offer an alternative approach to system BIOGRAPHY...................................................10 engineering of complex systems by the imposition of design rules (Figure 1). Whereas this has been a successful approach for hardware systems that can rely on physics, mathematics, material science etc. as their foundation, 1. INTRODUCTION software systems have largely failed to improve in robustness by the imposition of new design rules. The Complex engineering design problems are multi-parameter approach of evolutionary computation uses the same optimizations where physics models predict the outcome principles of variation and selection that have been so derived from a series of input parameters. Design, however, successful in the development of natural biological systems. depends on desiring an outcome and deriving the necessary input parameters. Generally it is not feasible to invert the physics models to derive an optimal solution. Instead, by 2. OVERVIEW parallelizing the problem into a large population with varying input parameters and competing the results, we can extract favorable combinations of inputs. In the same way Evolutionary Computation Framework biological evolution functions, this process is repeated over The strength of evolutionary computation comes from the many generations and uses the sophisticated biological ability to utilize existing computer models and simulations operators of selection, mutation, and recombination to that predict the results of multiple input parameters. These types of models are now common elements of computer- 1 0-7803-8870-4/05/$20.00© 2005 IEEE aided design (CAD) as well as scientific modeling and 2 IEEEAC paper #1257, Version 26, Updated December 1, 2004 1 forecasting. In evolutionary computational techniques, a may be performed by the genetic principles that govern the population of these models is created and input parameters evolvable system algorithms. The software framework are varied. The results are evaluated using fitness functions development for this evolvable system effort must be and a percentage of the highest fitness individuals from one performed by an experienced team of software engineers, generation is promoted to the next generation, while new computer scientists, electrical engineers, biologists, and models are created through variation (e.g., by mutation or physicists in order to provide any hope for a reasonable cross-over). outcome compared to the high mark targets. Best PGAPACK Software Package with Structure Graphical User Interface Input: • Simulation Targets Genes Fitness • GA parameters GGeneneses FFitintneessss • Platform parameters • Interaction between workstation MODEL and supercomputer NEMO NEMODesired Simul. DDaetasired Output: DaStSiamimuul.l. DDeDastaaitraed • Evolution development DDataata • Evolution results • Evolution statistics Gene FitnGesesne Gene Fitness Fitness Figure 2. PERSON graphical evolutionary computational framework. Models can be introduced Figure 1. Complexity and Design Rules. As complexity with existing tools and simulators and are adapted into increases from hardware systems to software to nature, a parallel evolutionary environment. the formalism and number of design rules decreases. Genetic Algorithms Current efforts in software engineering are trying to move software systems to higher formalism. Our effort Genetic algorithms (GA), first introduced by John Holland tries to explore the creation of complexity by removing and his colleagues [2], are search algorithms based on the formalism and using a biological evolutionary mechanics of natural selection and sexual reproduction. GAs approach. are theoretically and empirically proven to provide robust search in complex parameter spaces. Furthermore, they are In order to rapidly adopt new problems into an evolutionary not fundamentally limited by restrictive assumptions about framework we have developed a graphical user interface that the search space such as continuity and existence of enables the parallel operation of genetic algorithms and derivatives. other optimizers on a cluster computer. This framework enables the tie-in of a variety of different applications and The standard GA proceeds as follows: A possible solution the management of application inputs and outputs. The of a given problem is encoded as a finite string of symbols, operation of a parallel genetic algorithm to optimize a known as a genome. An initial population of the possible variety of tasks has been demonstrated. This evolvable solutions called individuals is generated at random or software system also includes a variety of algorithms useful heuristically. At every evolutionary step, known as a for optimization such as local searches and simulated generation, the individuals in the current population are annealing. We have baptized the framework “Parallel, decoded and evaluated according to some predetermined Evolvable, and Revolutionary Synthesis and Optimization quality criterion, referred to as the fitness. To form the next Environment (PERSON)”. The computational architecture generation, parents are selected with a probability of PERSON is based on a package created by D. Levin at proportional to their relative fitness. This ensures that the Argonne National Lab [1]. The major contribution of expected number of times an individual is chosen is PERSON is the scriptable front-end that turned the software approximately proportional to its relative performance in the into a tool. We have a scripted approach to the integration population. Thus, low-fitness individuals are more likely of applications into PERSON, which enables rapid to disappear. integration of a variety of different physical models and a variety of different fitness functions without recompilation The parent selection process is followed by genetically of the design environment. This architecture resembles a inspired operators to form offspring. The most well known generalized optimization toolkit that can be applied to a operators are mutation and crossover. The mutation large array of physical system simulation problems that operator is introduced to prevent premature convergence to require optimization in a huge search space. Note, however, local optima by randomly sampling new points in the that this system goes beyond the traditional optimization search space with some probability. Crossover is performed approach in that truly novel synthesis and design/selection with a different probability between two selected parents, by 2 exchanging parts of their genomes to form two offspring. In too easily (greedy downhill optimization). The annealing its simplest form, substrings are exchanged after a randomly temperature directly influences the Boltzmann probability selected crossover point. This operator tends to enable the by making it less likely to accept an energetically evolutionary process to move toward promising regions of unfavorable step, the longer the optimization lasts (cooling the search space quickly, by recombining partial solutions. schedule). Then the overall procedure is repeated until the Genetic algorithms are stochastic, iterative processes that are annealing temperature has reached its end value, or a preset not guaranteed to converge. The termination condition may number of iterations has been exceeded, or the energy be specified as some fixed, maximum number of function E has reached an acceptable level. generations or as the attainment of an acceptable fitness level. Further discussions of GAs have been published by this research group with respect to algorithm details and 3. COMPUTER OPTIMIZED DESIGN their application to nanoelectronic device designs [3], microelectronic device designs [4], automated circuit designs [5], quantum mechanical basis set selection [6], We have demonstrated that evolutionary computational space craft power system design [7], low thrust orbit techniques can now be used for automatic innovation and transfers [8], and neural network evolution [9]. design, using the same computer models that are employed to evaluate engineering designs. Five areas, described in This publication is focused on the application of efficient this paper, demonstrate human competitive performance as optimization techniques to a variety of space science described by Koza et al. [13]. Optimizations and designs systems. The method of operation is the repeated using evolutionary techniques result in designs matching or application of already sophisticated physics based models exceeding the performance of those derived from traditional which predict reality. We would like to mention here that means by human designers. Metrics used for this the availability of efficient optimization tools and the performance evaluation include design time, robustness and ability to explore large parameter spaces also enables the fault-tolerance, cost, and comparison to accepted and flown development of more sophisticated physics based models designs. The areas described in this paper are the automatic that predict “reality” better. One such concrete example is design of power systems, robotic arm deployment path the development of an advanced model to treat the planning, the design of low-thrust trajectories, the automatic consequences of arbitrary mechanical strain distortions in tuning of MEMS micro-gyroscopes, and the evolution of semiconductor crystals [10]. This advanced model expands neural networks. We expect that future work will lead to the physical parameter space dramatically, which could not further advances in computational engineering and in the have been usefully explored without the PERSON development of Computer Optimized Design (COD) (Figure framework. GAs can therefore not only seek better 3.). engineering solutions, they can also help to refine our physical understanding of problems. Computational Evolutionary Design + + Simulated Annealing Algorithms Model Framework Simulated annealing (SA) is a widely used and well- Single design based Predicts and evaluates the Competes a population of established optimization technique especially for high- on expertise of outcome (design) of variable variable input parameters human designer sets of input parameters over many generations dimensional configuration spaces [11,12]. The goal is to minimize an energy function E (in the following three cases: 1) the squared distance from a start joint angle set to a target Computer Computer Traditional joint angle set for the rover arm; 2) the required flight time Aided Design Optimized Design and propellant mass for low thrust trajectories; and 3) the (CAD) Design (COD) frequency split of the MEMS micro-gyro), which is a Allows only one point Allows rapid exploration Allows automatic exploration function of N variables (in the three following cases: 1) the of design space to of alternative designs by and optimization of designs be examined human designer over huge volumes of 4 joint angles for FIDO (Field Integrated Design and design space Operations) or the 5 joint angles for the MER (Mars Exploration Rover) rover platforms; 2) the Q-law parameters; and 3) the 4 bias voltages for the MEMS micro- Figure 3. Elements of Computer Optimized Design gyros), with N being usually a large number. The (COD). The use of an evolutionary framework coupled minimization is performed by randomly changing the value to a computational simulation allows the extension of of one or more of the N variables and reevaluating the computer aided design to rapidly and automatically energy function E. Two cases can occur: 1) the change in the evaluate huge volumes of design space. variable values results in a new, lower energy function value; or 2) the energy function value is higher or unchanged. In the first scenario the new set of variable 4. RESULTS values is stored and the change accepted. In the second scenario, the new set of variable values is only stored with a Automatic Design of Power Sub-systems certain likelihood (Boltzmann probability, including an annealing temperature). This ensures that the overall Early in the formulation phase of a flight project the goals optimization algorithm does not get stuck in local minima and objectives of the mission are defined and several 3 plausible mission concepts are created. These preliminary mission concepts will trade-off various elements in the design so that project managers can choose between different alternatives for mass, cost, performance and risk. This cycle of goal definition, mission concept creation and design trade study is repeated many times with each pass refining and improving the resolution of the design. The product of this process is a mission architecture characterized such that its effectiveness in achieving mission objectives can be properly evaluated. More formally, a trade study is a process for seeking one or more optimal solutions when there are multiple, often conflicting, objectives. An optimal solution in this case means that if one objective improves, other objectives are compromised or traded off. The classic example of this is in Figure 5. Weighted Sum Approach [14] car buying. Buyers must make a decision between cost and comfort since the less expensive cars are inevitably less spacious. This hypothetical trade-off is shown in Figure 4. Figure 4 Hypothetical Car Buying Trade-Off [14]. Figure 6. Ideal Approach [14]. To make the best decision, the buyer would want to This approach uses the same reproductive cycle as described consider solutions that are evenly distributed along the in the Introduction. The main difference is that niches are Pareto-optimal front. While the classical weighted sum used to help evaluate and replace the population members. approach is intuitive and easy to implement, creating these solutions using this method poses some problems. The In evolutionary computing, niching refers to forming most obvious is that since only one solution is generated at artificial subpopulations in the population to emphasize and a time, users will need to perform multiple runs in order to maintain multiple solutions. This can be done in either the obtain a set of possible solutions. More importantly, these objective or parameter space. Since we wanted to maintain solutions may not be evenly distributed, as illustrated in diversity in the solutions to trade-off regardless of how Figure 5. Furthermore, since evolutionary algorithms are similar or different they are, we elected to niche by the stochastic the method may find an optimal solution only to objective space. lose it in later generations. Ideally, we would want to generate all of the solutions in one run, evenly distributing To evaluate the fitness of a particular design and implement them first and then mapping them to the weightings the evolutionary cycle, we used a JPL power analysis tool afterward, as shown in Figure 6. Moreover, we would want called MMPAT within the PERSON evolutionary to preserve the best solutions from both the parent and child computing framework. MMPAT (Multi-Mission Power populations. One way to achieve this is with a Niched- Analysis Tool) is a tool that models the behavior of a Elitist approach. spacecraft’s power sources and energy storage devices as they interact with the spacecraft loads and the environment over a mission timeline. It is currently used in Mars Exploration Rover (MER) operations to predict the power subsystem resources before a sequence of activities is uploaded. By using this tool in an evolutionary computing framework we were able to provide a set of optimized designs based on the anticipated performance of the subsystem rather than using worst-case estimates. 4 To verify the utility of this approach we used the mission lies beyond exhaustive search in a timely manner. To plans from some current JPL missions and generated several increase the degree of complexity even more, the rover arm alternative designs for each. One of these tests was an deployment requires the generation/calculation of a series of optimization of one of the Mars Exploration Rovers (MER), valid configurations, i.e., the safe arm deployment path. a NASA mission of two rovers that landed in January 2004. We have created three separate software programs using a To setup the analysis we gave the PERSON optimization modified simulated annealing algorithm: 1) calculation of a framework some initial design parameters and a valid range safe, collision-free rover arm end configuration given a of values. We also needed to define the cost and mass predetermined x-y-z end position of the instrument-carrying constants and create an activity plan. For the MER joint together with a surface normal at that point; 2) optimization, we varied the number of cells per string and calculation of a safe, collision-free deployment path from a the number of strings per segment for the six solar array start rover arm configuration into the pre-calculated end segments, as well as the battery capacity. The PERSON configuration (1); and 3) optimization of safe, collision-free framework chose the initial population based upon a random rover arm deployment path with respect to minimizing the draw over a uniform distribution for each of the variable overall absolute joint angle movement. The software is power subsystem design parameters before invoking written in standard C and thus requires no special MMPAT. As a starting point, the framework was instructed computing platform. It runs under Linux, Unix, Windows, to use the actual MER rover solar array size and battery DOS, and Mac OS X and requires less than 1.25MB of capacity. RAM. The time necessary to calculate a safe deployment path is now reduced from hours to hundreds of milliseconds The rover was placed at 14.95 degrees south latitude and (on a Macintosh PowerBook 800MHz G4). given an activity plan that lasted 90 sols. This corresponds to the planned length of surface operations of MER-A at the We also applied a genetic algorithm [15] to the rover arm Gusev Crater landing site. The activity plan consisted of path planning problem, trying to mimic evolutionary applying a 50-watt load for six hours during local daytime principles used by nature in applying genetic operations and 8 watts the rest of the day. This simulated the load on such as point mutation, cross-over, and inversion to the rover while it performed its duties during the day, and parameter strings, called “genes” or “chromosomes”, in let it conserve battery power for the heaters at night. order to evolve a set of parameters that achieve a high fitness as determined by a fitness function (similar to the Using a population of 200 we ran the analysis for 177 energy function in simulated annealing). Our improved generations. This resulted in 35400 unique designs being algorithm for the safe rover arm deployment problem uses evaluated. The optimization took 18 hours using 8 Intel(R) the following seven-step process: Xeon(TM) CPU 2.80GHz processors. As expected, this resulted in several credible alternative solutions being 1. Start with a random initial population generated where each niche optimized their primary 2. Determine arm extent bounding volume to prune the objective while compromising the others. search space 3. Define fitness function based on obstacle avoidance and Rover Arm Path Planning goal orientation 4. Perform collision detection and prune population Current and future planetary exploration missions involving followed by goal orientation landers and/or rover-type vehicles such as Mars Exploration 5. Perform mutation with a probabilistic choice of small Rover (MER), Mars Science Laboratory (MSL), and variation in state or segmented path mutation followed subsurface access missions are and will be equipped with by another fitness evaluation robotic arms with four or more joints, each joint having a 6. Promote top 10% of the survivors to the next arm high degree of freedom (e.g., an angle range of 100 degrees extent bounding volume in 1 degree steps). Fast and efficient safe rover movement 7. Repeat steps 2 to 6 until placement point reached. (e.g., legged rovers and cliff-climbing rovers) and rover arm This approach will give an incremental path to the goal deployment algorithms, taking rover position and position, without having to search through the entire path surrounding ground obstacles (e.g., rocks) into account that from start position to end. can be executed with onboard CPU power, will tremendously enhance mission autonomy by cutting down The simulated annealing-based rover arm path planning on up-/downlink events, and thus increase the useful algorithm as well as the GA-based algorithm have been lifespan of a mission. This work is capable of increasing successfully tested both onboard the FIDO rover platform science return of future missions and enabling support of and on the FIDO software simulator at JPL (see Figure 7). intelligent in-situ science experiments to be performed The optimizer part came up with a novel, shortest (2-step) autonomously. deployment path from the stowed to the safe rover arm position. The calculation of a collision-free rover arm deployment path is a search in a high-dimensional configuration space. A rover arm consisting of N joints with, e.g., on average 100 angle positions per joint, spans a configuration space of 10(2*N). With N>6, the number of possible configurations 5 The general goal of the design problem is to maneuver a spacecraft with a series of thrust arcs from orbit A to orbit B in the most fuel-efficient and simultaneously time-efficient manner. Since the fuel efficiency and the time efficiency often conflict, the goal of this design problem becomes to determine the Pareto front, which is the envelope in the objective space resulting from the trade-off between the optimal propellant mass and the flight time; each point along the Pareto front corresponds to one particular mission scenario. In order to access the Pareto front with reasonable accuracy and to provide the time history of the state variables and the thrust vector for any chosen point of the Pareto front, we have developed an efficient and efficacious method. A search for the Pareto-optimal trajectories is performed in two stages: 1) optimal thrust angles and thrust-arc locations are determined by the Q-law, and 2) the Q-law is optimized with two evolutionary algorithms: a modified simulated annealing algorithm (SA) and a genetic algorithm (GA) with non-dominated sorting [8]. Figure 7. Reachability Map for FIDO Rover: Comparison of digital terrain maps showing reachability of targets with the FIDO robotic arm. Green (light) areas are reachable with arm path solutions. Grey areas are not reachable and red (dark) areas indicate no data available for a solution. Top image is default elbow up reachability derived from the FIDO arm path algorithm. This algorithm derives an un-optimized safe path to each target. The bottom image is the same terrain map analyzed with a genetic algorithm to find the safest paths to targets. The larger reachable area of the genetic algorithm is an indication of the power of the technique in not only providing a greater number of targets, but also in providing the fittest arm path solutions with respect to safety from arm (self and terrain) collisions. We are in the process of deploying both algorithms on the MER rover software simulator and hardware platform, with possible real-world arm deployments during the extended NASA/JPL MER Mars Mission. Details of this work will Figure 8. Pareto front for an orbit transfer from a be published in a future publication. slightly-inclined geostationary-transfer orbit to a geostationary orbit. Optimization of Low-Thrust Trajectories Future space missions DAWN and JIMO will use electric propulsion for inter-planetary cruise and orbital operations. We applied our method to several types of orbit transfers The strength of electric propulsion is that in spite of its low around the Earth and the asteroid Vesta. Substantial thrust levels, the momentum transfer to the spacecraft per improvements in both final mass and flight time over state- kilogram of expelled propellant is ten or twenty times of-the-art are found in the calculation of the Pareto front. greater than for chemical propulsion. However, the control For example, for a low-thrust orbit transfer from a slightly- of low-thrust spacecraft poses a challenging design problem inclined geostationary-transfer orbit to a geostationary orbit because perturbative forces often dominate the thrust and a we have obtained as much as a 15% propellant savings over significant change of the orbit requires many revolutions. the nominal Q-law. Furthermore, the resulting Pareto front Here we address the problem of designing low-thrust orbit contains the optimal trajectories found by other transfers between arbitrary orbits in an inverse-square gravity optimization algorithms such as a static/dynamic control field by using evolutionary algorithms to drive parameter algorithm [16] and an orbit averaging technique [17]. Figure selection in a Lyapunov feedback control law (the Q-law). 8 shows the substantial improvement in the estimation of the true Pareto front by the optimized Q-law with SA and GA over the nominal Q-law, and the comparable 6 performance of the optimized Q-law to other optimization techniques. Even more promising is that our method builds the Pareto front within a few hours of computation time, while other optimization algorithms require a comparable computational effort to acquire a single optimal trajectory. A more detailed description of our method and results is reported elsewhere [8]. Future plans comprise the direct optimization of low-thrust trajectories, i.e., determination of sequence of thrust arcs, both in space and time, and individual duration thereof, independent of human-prescribed control laws such as Q- law. Automatic Tuning of MEMS Micro-Gyroscopes The MEMS Micro-Gyro, developed by the MEMS Technology Group at JPL, is subject to an electro-static fine-tuning procedure, which is necessary due to unavoidable manufacturing inaccuracies. In order to fine- tune the gyro, 4 bias voltages, applied to 8 capacitor plates, have to be determined independently within a range of –60V to 15V. The fine-tuning directly correlates with the accuracy of the gyros in later use. In order to fully automate the time-consuming (on the order of several hours) manual fine-tuning process, we have established a hardware/software test bed to the existing manual gyro-tuning hardware-setup using commercial-off- the-shelf (COTS) components, which includes four programmable power supplies, one offset power supply, and an (electronic) signal analyzer as well as driver and analyzing software. FiguFrieg u9r. eF 9r.e qFureenqcuye nspclyi t sapsli ta afsu nac tfiuonnc toiof nS iomf uSliamteudlated We developed and implemented two algorithms for AnnAeanlinnega lIitnegr aIttieornast:i o(ntosp: )( tfoopr) tfhoer MthEe MMSE MpoSst -pgoysrto-g;yro; (bottom) for the MEMS disk-resonating gyro. efficiently determining the bias voltages: 1) a modified (bottom) for the MEMS disc-resonating gyro. simulated annealing algorithm and 2) a dynamic hill- climbing algorithm. Both have been incorporated into the hardware/software test bed. We were subsequently able to successfully fine tune both MEMS post-gyros and MEMS disk-resonating gyros within one hour for the first time fully automatically to a level of accuracy that is equal to or better than what can be accomplished manually (see Figure 9). One of the key problems solved during the course of this research was that of determining the resonant frequencies along both axes of oscillation. In this closed-loop system, the resonant frequencies were determined by scanning through the range of likely frequencies to determine two peaks in the amplitude of vibration. The objective is to reduce the difference in resonant frequencies, also called the “frequency-split”, to zero. The frequency split before tuning can be seen in Figure 10. The resonant frequencies are determined by fitting the data to two Lorentzian curves. The best-fit curves are seen in the inset. The fit parameters tell us the position of the peak, and hence the resonant frequency. Using this method we can accurately report the Figure 10. The frequency split before tuning. The two frequency split to a resolution below 0.06Hz, which is Lorentzian curves are shown, as dashed and dotted considerably better than the resolution determined by a lines below the solid line indicating the sum of the human operator. The final tuned result can be seen in curves. The inset shows the details of the peak data Figure 11. points. 7 4. Application of technique to mission rovers and spacecraft. We have finished step one, and were able to demonstrate the evolution de novo of sequences that encode extremely robust networks that perform complex logical functions. The structure of these networks (Figure 12) is unlike any designed by humans, and resembles instead the decentralized structure of animal nervous systems, such as that of the flatworm Caenorhabditis elegans. The network in Figure 12, because it is derived from a growth process, is reconstituted automatically even if more than half of the cells that make up its tissue are removed [9]. We are now proceeding with step 2, by evolving Khepera controllers within the Webots! 4 simulation platform linked to the Norgev software. Figure 11. The frequency split after tuning is shown, reduced to approximately 0.05Hz. The novel capability of fully automated gyro tuning enables ultra-low mass and ultra-low-power high-precision Inertial Measurement Unit (IMU) systems to calibrate themselves autonomously during ongoing missions, e.g., Mars Ascent Vehicle. Evolution of Neural Networks Spacecraft and rovers are conventionally controlled by software systems that determine attitude, position, direction, and speed as a function of environmental variables. To some extent, such controllers perform the Figure 12: Evolved complex computational tissue same function as the nervous system of animals, a standard solving a logical 3-input/2-output task [9]. Neurons are example being the fruit fly Drosophila melanogaster. colored according to their level of expression of specific Because of the analogy to nervous systems, robotic simulated chemicals. Connections are colored according controllers can also be cast in the language of neural to their activity. networks, which perform the computation of output variables as a function of input variables. Historically, . neural networks have been designed according to standard rules from abstract neurons connected to each other. However, artificial brains based on standard neural network architectures failed to deliver on the initial promise, and have faded from use. We have started a research program in which not only the structure of neural networks is being evolved, but also the rules for growth and learning, within a n a software environment called “Norgev” (Neural Organism p s Evolution) [18]. This program is proceeding in four steps: e k a M 1. Proof of principle by evolving networks that perform complex logical input/output functions in a robust manner exceeding human-design standards 2 . Evolution of neural networks that control Generations simulated test robots (Khepera) better than human- Figure 13: Plot of viable schedule at each generation designed controllers and their makespan 3. Transfer and optimization of evolved controllers to real test robots 8 Mission Operations Planning and Scheduling changing fitness requirements and redesign, which inevitably occurs in real systems and generally causes great The Mission Operations Planning and Scheduling problem fiscal and schedule disruption, can be accommodated at is comprised of a large number of events that may be relatively low cost. scheduled if the resources and constraints permit in an allotted time period, also referred to as the planning Our future work will consider the optimization of multiple horizon. The goal of this study is to use the genetic sub-systems into full spacecraft optimizations. We are also algorithm (GA) technique to find the schedule that would evolving mission plans and schedules and hope to integrate globally minimize the amount of time it takes for all events this work into the co-design of a spacecraft optimized to the to complete within the planning horizon and also to enable mission plan. more high priority events to be scheduled. It was found that the GA technique alone does not enable one to achieve global optima. However, it is capable of quickly finding a 6. ACKNOWLEDGEMENTS population whose spans are sufficiently close to the global optima (Figure 13). In contrast, it is also observed that sequential quadratic programs (SQP) such as those found in The work described in this publication was carried out at the Matlab using FMINCON are able to find the global optima Jet Propulsion Laboratory, California Institute of more rapidly but require the search to start with a set of Technology under a contract with the National Aeronautics viable initial schedules. Therefore, the GA technique can be and Space Administration. The research was supported by used in conjunction with SQP to find the whole set of the JPL Research and Technology Development Program. globally optimal solutions such that the solutions from the Leveraged funding was provided by NASA ESTO-CT, GA can serve as viable initial guesses for the SQP. This ARDA, and ONR. coupling of GA with SQP can produce the global optima more quickly and accurately than just using one of the techniques alone. Details of this work will be published in REFERENCES another publication in the future. [1] D. Levin, Argonne National Lab, h t tp://www- Architecture Synthesis Tool fp.mcs.anl.gov/ccst/research/reports_pre1998/comp_bio/st alk/pgapack.html The purpose of the Architecture Synthesis Tool (AST) is to automatically generate functionally viable architectures for [2]J.H. Holland, Adaptation in Natural and Artificial spacecraft Command and Data Handling (C&DH) Systems, The University of Michigan Press, Ann Arbor, subsystems that will adapt to frequently changing system Michigan, 1975. requirements during the early phase of a flight project. These changes in requirements frequently lead to weeks of [3] Gerhard Klimeck, Carlos H. Salazar-Lazaro, Adrian labor spent on redesign, and it would be highly beneficial to Stoica, and Tom Cwik, "Genetically Engineered" have a tool that is sensitive to such requirement changes and Nanostructure Devices, in "Materials in Space Science, able to respond to these changes with viable architectures in Technology, and Exploration", MRS Symposium a matter of hours. Proceedings, Vol. 551, pg. 149 (1999). The AST consists of an Architecture Generator and a [4] Tom Cwik and Gerhard Klimeck, "Integrated Design and Functionality Evaluator. The Architecture Generator Optimization of Microelectronic Devices", Proceedings of employs genetic algorithms to generate populations of 1999 Aerospace Conference, IEEE Volume: 5 , 1999 , C&DH architectures and the Functionality Evaluator uses Page(s): 131 -138. the availability of the components required by system functions to evaluate the fitness of these architectures. In [5] Didier Keymeulen, Gerhard Klimeck, Ricardo Zebulum, preliminary tests, the AST has produced viable architectures Adrian Stoica, and Carlos Salazar-Lazaro, "EHWPack: A that were optimal within the design space defined by the Parallel Software/Hardware Environment for Evolvable database inputs. Details of this work will be published in Hardware", in Whitley Darrell (eds.), Proceedings of the another publication in the future. Genetic and Evolutionary Computation Conference (GECCO-2000), July 8-12, 2000, Las Vegas, Nevada USA. San Francisco, CA: Morgan Kaufmann. 5. CONCLUSIONS [6] Gerhard Klimeck, R. Chris Bowen, Timothy B. Boykin, Carlos Salazar-Lazaro, Thomas A. Cwik, and Adrian We have demonstrated that evolutionary computational Stoica, "Si tight-binding parameters from genetic techniques can be applied to the design and optimization of algorithm fitting", Superlattices and Microstructures, Vol. space systems. Generally, these applications offer better 27, No. 2/3, Mar 2000, pp. 77-88. performance (in the range of at least 10%) than traditional techniques and show faster design times. Additionally, 9 [7] M. Kordon, G. Klimeck, D. Hanks and H. Hua, BIOGRAPHY "Evoluionary Computing for Spacecraft Power Subsystem Design Search and Optimization," IEEE Aerospace Conference Proceedings, Big Sky, MT., March Richard J. Terrile created and leads the Evolutionary 2004. Computation Group at NASA’s Jet Propulsion Laboratory. His group has developed genetic algorithm [8] S. Lee, P. von Allmen, W. Fink, A. Petropoulos, R. based tools to improve on human Terrile, “Design and Optimization of Low-thrust Orbit design of space systems and has Transfers Using the Q-law and Evolutionary Algorithms” demonstrated that computer aided 2005 IEEE Aerospace Conference Proceedings, March design tools can also be used for 2005. automated innovation and design of complex systems. He is an [9] A.N. Hampton and C. Adami, “Evolution of Robust astronomer, the Mars Sample Return Developmental Neural Networks”, Proc. of Artificial Life Study Scientist, the JIMO Deputy Project Scientist and the IX, Boston, MA, Sep 12-15, 2004. J. Pollack, M.A. co-discoverer of the Beta Pictoris circumstellar disk. Dr. Bedau, P. Husbands, T. Ikegami, and R. Watson, eds., Terrile has B.S. degrees in Physics and Astronomy from the (Boston: MIT Press, 2004) pp 438-443. State University of New York at Stony Brook and an M.S. and a Ph.D. in Planetary Science from the California [10] Timothy B. Boykin, Gerhard Klimeck, R. Chris Institute of Technology in 1978. Bowen, and Fabiano Oyafuso, "Diagonal parameter shifts due to nearest-neighbor displacements in empirical tight- Christoph Adami is a Visiting Scientist and former binding theory", Phys. Rev. B 66, 125207 (2002). Principal Scientist in the Exploration Systems Autonomy [11] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, Section of NASA’s Jet Propulsion A.H. Teller, E. Teller, “Equation of State Calculation by Laboratory, and a Professor of Fast Computing Machines,” J. of Chem. Phys., 21, Applied Life Sciences at the Keck 1087--1091, 1953. Graduate Institute in Claremont, CA. His interests concern the [12] S. Kirkpatrick, C.D. Gelat, M.P. Vecchi,, “Optimization fundamental mechanisms involved in by Simulated Annealing,” Science, 220, 671--680, 1983. the evolution of complexity from simplicity, both in natural and [13] J.R. Koza, F.H. Bennett III, D. Andre, M.A. Keane artificial systems. He has pioneered the use of digital life “Genetic Programming III: Darwinian Invention and in computational evolutionary biology, and is the author of Problem Solving,” 1999, Morgan Kaufmann Publishers. over 70 peer-reviewed articles in theoretical physics and biology, as well as the textbook “Introduction to Artificial [14] D. Kalyanmoy Multi-Objective Optimization using Life” (Springer). He has a B.A. and a Diplom in Evolutionary Algorithms, John Wiley & Sons, Ltd., theoretical physics from Bonn University (Germany), as 2001, p. 2, 172, 239, 173 well as an M.A in physics and a Ph.D. in theoretical physics from SUNY Stony Brook. [15] D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Hrand Aghazarian is a Senior Member of the Engineering 1989. Staff in the Mobility and Robotics Section at the Jet Propulsion [16] A.E. Petropoulos, “Simple Control Laws for Low- Laboratory in Pasadena, CA. He Thrust Orbit Transfers,” AAS/AIAA Astrodynamics has extensive work experience in the Specialist Conference, AAS Paper 03-630, 2003. design and development of real-time embedded software for a variety of [17] G.J. Wiffen and J.A. Sims, “Application of a Novel avionics systems. Currently he is Optimal Control Algorithm to Low-Thrust Trajectory involved in providing software Optimization,” AAS/AISS Space Flight Mechanics solutions in the area of software Meeting, AAS Paper 01-209, 2001. [17] S. Geffroy and architecture, low-level drivers, R. Epenoy, “Optimal Low-Thrust Transfers with motor control, user interfaces for commanding planetary Constraints – Generalization of Averaging Techniques,” rovers, and navigation algorithm for SRR and FIDO Astronautica Acta, 41, 1333-149, 1997. rovers. His research interests are Rover Navigation/Control and Real-Time Embedded software [18] J. Astor and C. Adami, “A Developmental Model for Design and Development. He received a dual B.S. degree in the Evolution of Neural Networks”. Artif. Life 6, 189- Applied Math and Computer Science and a M.S. degree in 218, 2000. Computer Science from California State University in Northridge. He is a member of ACM and INNS. 10