1994 Machine Learning
Published Papers and Technical Reports

Abstract: A central problem in the theory of genetic algorithms is to build predictive models of how well genetic algorithms are expected to perform, given a representation, a fitness landscape, and a set of genetic operators. This paper attempts to provide pieces of such a theory. We develop some tools that predict the behavior of genetic algorithms based on assumptions concerning the "fitness distribution" of genetic operators. The fitness distribution of an operator describes the expected fitness value of an individual resulting from an operator application, as a function of the fitness of the original individual. It shown that in some cases, the fitness distribution for genetic operators may be described by simple functions of the fitness of the parents. For these cases, predictive models of population fitness can be derived.

John J. Grefenstette
"Evolutionary Algorithms in Robotics," Robotics and Manufacturing: Recent Trends in Research, Education, and Applications, v5, Proceedings of the Fifth International Symposium on Robotics and Manufacturing (ISRAM '94), Mohammad Jamshidi and Charles Nguyen,(editors), 65-72, ASME Press: New York, August 14-18, 1994, (NCARAI Report: AIC-94-002).
Download PostScript

Abstract: The field of robotics offers an endless supply of difficult problems, requiring an equally impressive array of methods for their solution. One class of methods that has shown its utility on a number of relevant problems is called Evolutionary Computation. This term applies to computational methods that incorporate principles from biological population genetics to perform search, optimization, and machine learning, and includes a variety of specific formulations with names such as genetic algorithms, evolutionary programming, evolution strategies, and genetic programming. This article presents an overview of evolutionary algorithms, and discusses selected issues concerning their application to robotics.

Alan C. Schultz
"Learning Robot Behaviors Using Genetic Algorithms," Intelligent Automation and Soft Computing: Trends in Research, Development, and Applications, v1, Mohammad Jamshidi and Charles Nguyen (editors), Proceedings of the First World Automation Congress (WAC '94) and Fifth International Symposium on Robotics and Manufacturing (ISRAM '94) Manufacturing, 607-612, TSI Press: Albuquerque, NM, August 14-17, 1994, (NCARAI Report: AIC-94-003).
DownloadPostScript or PostScript, Compressed

Abstract: Genetic Algorithms are used to learn navigation and collision avoidance behaviors for robots. The learning is performed under simulation, and the resulting behaviors are then used to control the actual robot.

The approach to learning behaviors for robots described here reflects a particular methodology for learning via a simulation model. The motivation is that making mistakes on real systems may be costly, dangerous, or time consuming. Since learning may require experimenting with behaviors that might occasionally produce unacceptable results if applied to the real world, or might require too much time in the real environment, we assume that hypothetical behaviors will be evaluated in a simulation model (the off-line system). The current best behavior can be placed in the real, on-line system, while learning continues in the off-line system.

The learning algorithm was designed to learn useful behaviors from simulations of limited fidelity. The expectation is that behaviors learned in these simulations will be useful in real-world environments. Previous studies have illustrated that knowledge learned under simulation is robust and might be applicable to the real world if the simulation is more general (i.e. has more noise, more varied conditions, etc.) than the real world environment. Where this is not possible, it is important to identify the differences between the simulation and the world and note the effect upon the learning process. The research reported here continues to examine this hypothesis.

Brian Yamauchi and Randall Beer
"Integrating Reactive, Sequential, and Learning Behavior Using Dynamical Neural Networks," Third International Conference on Simulation of Adaptive Behavior, 1994, (NCARAI Report: AIC-94-004).
Not available on-line at this time. Please see order form.

Abstract: This paper explores the use of dynamical neural networks to control autonomous agents in tasks requiring reactive, sequential, and learning behavior. We use a genetic algorithm to evolve networks that can solve these tasks. These networks provide a mechanism for integrating these different types of behavior in a smooth, continuous manner. We applied this approach to three different task domains: landmark recognition using sonar on a real mobile robot, one-dimensional navigation using a simulated agent, and reinforcement-based sequence learning. For the landmark recognition task, we evolved networks capable of differentiating between different landmarks based on the spatiotemporal information in a sequence of sonar readings obtained as the robot circled the landmark. For the navigation task, we evolved networks capable of associating the location of a landmark with a corresponding goal location and directing the agent to the goal. For the sequence learning task, we evolved networks that can learn to generate one of a set of possible sequences based upon reinforcement from the environment. A novel feature of the learning aspects of our approach is that we assume neither an a priori discretization of states or time nor an a priori learning algorithm that explicitly modifies network parameters during learning. Instead, we expose dynamical neural networks to tasks that require learning and allow the genetic algorithm to evolve network dynamics capable of accomplishing these tasks.

Helen G. Cobb and Peter Bock
"Using a Genetic Algorithm to Search for the Representational Bias of a Collective Reinforcement Learner," Third Parallel Problem Solving from Nature (PPSN-III), 1994, (NCARAI Report: AIC-94-005). PostScript or PostScript, Compressed

Abstract: In reinforcement learning, the state generalization problem can be considered to be the problem of finding a strong and correct representational bias for the learner. The study presented in this paper uses a genetic algorithm based system to evolve a reinforcement learner's representational bias. The State Partitioning Collective Learning System (Sparcle) is a hybrid system that combines a generational GA with an stochastic reinforcement learner called a Collective Learning Automaton (CLA). The primary focus of this study is to investigate the usefulness of the very strong representational biases that the Sparcle system finds for the CLA in terms of two qualities: stability and transferability. The stability of a representational bias is a measure of the quality of an experienced learner's solution, whereas the transferability of a bias measures how well an evolved bias can be transferred to a novice learner. The results presented in the paper show that the usefulness of the CLA's representational bias differs greatly with respect to its stability and its transferability. A representation that can be successfully interpreted by an experienced learner is sometimes inadequate as a representation for a novice learner, due to the fact that a strong representation may integrate knowledge into the representation to such a large extent that only an experienced learner can successfully interpret the representation.

William M. Spears
"Simple Subpopulation Schemes," Evolutionary Programming Conference, 1994,
(NCARAI Report: AIC-94-006).
Not available on-line at this time. Please see order form.

Abstract: This paper considers a new method for maintaining diversity by creating subpopulations in a standard generational evolutionary algorithm. Unlike other methods, it replaces the concept of distance between individuals with tag bits that identify the subpopulation to which an individual belongs. Two variations of this method are presented, illustrating the feasibility of this approach.

Devika Subramanian and Diana Gordon
"Assimilating High-Level Advice in Embedded Agents," Internal Report, April 1994, (NCARAI Report: AIC-94-008).
Not available on-line at this time. Please see order form.

Abstract: In this paper, we address the problem of designing and refining strategies for agents embedded in dynamic, multi-agent worlds. We use high-level advice given by an expert, as well as knowledge of the domain dynamics, to design a parametric action map from an agent's sensors and its internal state to its effectors. A genetic algorithm (GA) refines the action map as the agent dynamically interacts with the environment. We compare the performance of our multistrategy learner against a GA that uses a random initial seed. Our learner converges substantially faster and, in many cases, to a more accurate solution, than a randomly initialized GA in two complex simulated domains and performs well on navigation with a Nomad 200 robot. We experimentally identify and analyze the conditions under which high-level advice can be expected to significantly improve the design of task-level strategies.

John J. Grefenstette
"Predicting the Performance of Genetic Algorithms," Invited presentation at the American Geophysical Union 1994 Spring Meeting, May 23-27, 1994, (NCARAI Report: AIC-94-009). Download PostScript

Abstract: Genetic algorithms are probabilistic optimization techniques based on principles derived from natural population genetics. These algorithms have been used successfully in a variety of problems that are not amenable to traditional optimization methods. As with many heuristic methods, the development of the theoretical foundations of genetic algorithms has proceeded at a slower pace than the progress in the applications of the method. However, there have been some recent developments that may be of interest to users.

A central goal of the theory of genetic algorithms is to understand the relationships among the performance of a genetic algorithm, the problem representation, and the genetic search operators. We are working to develop tools that predict the behavior of genetic algorithms based on properties of the "fitness distribution" of genetic operators. The fitness distribution of an operator describes the expected fitness value of an individual resulting from an operator application, as a function of the fitness of the original individual. It can be shown that in many cases, the fitness distribution for genetic operators may be described by simple functions of the fitness of the parents. For these cases, predictive models of population fitness can be derived.

David W. Aha and Richard L. Bankert
"Feature Selection for Case-Based Classification of Cloud Types: An Empirical Comparison," Proceedings of the AAAI-94 Workshop on Case-Based Reasoning, July 1994, (NCARAI Report: AIC-94-011). Download PostScript, Compressed

Abstract: Accurate weather prediction is crucial for many activities, including Naval operations. Researchers within the meteorological division of the Naval Research Laboratory have developed and fielded several expert systems for problems such as fog turbulence forecasting, and tropical storm movement. They are currently developing an automated system for satellite image interpretation, part of which involves cloud classification. Their cloud classification database contains 204 high-level features, but contains only a few thousand instances. The predictive accuracy of classifiers can be improved on this task by employing a feature selection algorithm. We explain why non-parametric case-based classifiers are excellent choices for use in feature selection algorithms. We then describe a set of such algorithms that use case-based classifiers, empirically compare them, and introduce novel extensions of backward sequential selection that allows it to scale to this task. Several of the approaches we tested feature subsets that attain significantly higher accuracies than those found in previously published research, and some did so with fewer features.

John Rachlin, Simon Kasif, Steven Salzberg and David W. Aha
"Towards a Better Understanding of Memory-Based Reasoning Systems," 1994 International Machine Learning Conference, July 1994, (NCARAI Report: AIC-94-012). Download PostScript, Compressed

Abstract: We quantify both experimentally and analytically the performance of memory-based reasoning (MBR) algorithms. To start gaining insight into the capabilities of MBR algorithms, we compare an MBR algorithm using a value difference metric to a popular Bayesian classifier. These two approaches are similar in that they both make certain independence assumptions about the data. However, whereas MBR uses specific cases to perform classification, Bayesian methods summarize the data probabilistically. We demonstrate that a particular MBR system called PEBLS works comparatively well on a wide range of domains using both real and artificial data. With respect to the artificial data, we consider distributions where the concept classes are separated by functional discriminants, as well as time-series data generated by Markov models of varying complexity. Finally, we show formally that PEBLS can learn (in the limit) natural concept classes that the Bayesian classifier cannot learn, and that it will attain perfect accuracy whenever Bayes does.

John Grefenstette and Alan Schultz
"An Evolutionary Approach to Learning in Robots," Machine Learning Workshop on Robot Learning, New Brunswick, NJ, July 13, 1994, (NCARAI Report: AIC-94-014). PostScript or PostScript, Compressed

Abstract: Evolutionary learning methods have been found to be useful in several areas in the development of intelligent robots. In the approach described here, evolutionary algorithms are used to explore alternative robot behaviors within a simulation model as a way of reducing the overall knowledge engineering effort. The learned behaviors are then placed into actual robots. This paper presents some initial results of applying the SAMUEL genetic learning system to a collision avoidance and navigation task for mobile robots.

Connie Loggia Ramsey and John Grefenstette
"Case-Based Anytime Learning," Case Based Reasoning: Papers from the 1994 Workshop, D.W. Aha, editor, Technical Report WS-94-07, AAAI Press: Menlo Park, CA, August 1994, (NCARAI Report: AIC-94-016). Download PostScript or PostScript, Compressed

Abstract: We discuss a case-based method of initializing genetic algorithms that are used to guide search in changing environments. This is incorporated in an anytime learning system. Anytime learning is a general approach to continuous learning in a changing environment. A genetic algorithm with a case-based component provides an appropriate search mechanism for anytime learning. When the genetic algorithm is restarted, strategies which were previously learned under similar environmental conditions are included in the initial population of the genetic algorithm. We have evaluated the system by comparing performance with and without the case-based component, and case-based initialization of the population results in a significantly improved performance.