Gregory Rawlins

Robotics control problems, such as gait coordination, require sequential solutions where a series of actions is continually repeated. Genetic Algorithms that do parameter optimization have not been widely applied to these cyclic sequential decision problems; although some form of evolutionary computation would be well suited for the adaptability required. In this paper we introduce Cyclic Genetic Algorithms, which were developed precisely for this purpose. The specific problem addressed, adaptive gait development for hexapod robots, was the impetus for this new kind of evolutionary computation, but it can be applied to other robotics domains.

To determine influences on the production of a scientific article, the content of the article must be studied. We examined articles in biogeography and found that most of the influence is not cited, specific types of articles that are influential are...

Given a set O of orientations (or angles) a line, ray, or line segment, in the plane, is said to be O-oriented if the smallest angle it makes with a horizontal line is in O. We are interested in planar objects that are formed by O-oriented lines, rays, and line segments; we say that they are O-oriented objects. Our interest in this area stems from the observation that orthogonal objects can, in general, be handled more efficiently than arbitrarily-oriented ones. As we demonstrate, as far as convexity is concerned O-oriented geometry bridges the gap between orthogonal geometry and arbitrarily-oriented geometry.

We show for any n-matrix instance of the Matrix Chain Ordering Problem (MCOP) to have certain parenthesizations of depth (n) as solutions requires the matrix dimensions that are input to be exponential in n. That is, to ensure the MCOP can have any parenthesization as a solution, we must allow very expensive inputs. This exponential input lower bound implies a worst case bit complexity lower bound of (n 2). This lower bound is parameterized and, depending on the optimal product tree depth, it goes from (n 2) down to (n lg n). Also, this paper gives a very simple (n lg n) time lower bound for the MCOP for a class of algorithms on a comparison model with unit cost comparisons. This lower bound, to the authors' knowledge, captures all known algorithms for solving the matrix chain ordering problem, but does not consider bit operations. Finally, a trade-off is given between the input complexity lower bound and the atomic comparison based lower bound.

Trying to find information on the Web is like trying to find something at a jumble sale: it is fun, and you can make serendipitous discoveries, but for directed search it is better to go to a department store; there, someone has already done most of the arranging for you. Unfortunately, the Web's continuing explosion in size, its enormous diversity of topics, and its great volatility, make unaided human indexing impossible. This problem is just a special case of the general problem of organizing information to create knowledge. A similar problem arises on the desktop when dealing with file systems, where users must search by name. When searching for a particular file, however, users often do not remember the file's name or location. File names are artifacts of current operating systems, but human understanding neither requires objects to be named, nor does it have problems with multiple objects sharing properties, names, for instance. That more general approach is not developed in current file systems or user interfaces. We argue for an approach to information representation based on the use of attributes and search. This representation is organization-neutral, thereby giving a flexible substrate for anyone to build multiple simultaneous organizations. We argue the approach from three perspectives: Attribute Value System (AVS), a networked storage system where objects are composed solely of attribute-value pairs; DomainView (DV), a desktop metaphor where objects do not have explicit names and retrieval is done by content; and KnownSpace (KS), a personalized desktop data manager.

Trying to find information on the Web is like trying to find something at a jumble sale: it's fun, and you can make serendipitous discoveries, but for directed search it's better to go to a department store; there, someone has already done most of the arranging for you. Unfortunately, the Web's continuing explosion in size, its enormous diversity of topics, and its great volatility, make unaided human indexing impossible. This problem is just a special case of the general problem of organizing information to create knowledge. A similar problem arises on the desktop when dealing with file systems, where users must search by name, and often they do not remember the file's name or location. File names are artifacts of current operating systems, but human understanding neither requires objects to be named, nor does it have problems with multiple objects sharing properties---names, for instance. The limitations mentioned above result because today's computer systems do not analyz...

This paper considers the problem of using genetic algorithms to design structures. We relax one constraint on classical genetic algorithms and describe a genetic algorithm that uses differential information about search direction to design structures. This differential information is captured by a masked crossover operator which also removes the bias toward short schemas. We analyze performance and present some preliminary results. Further, consideration of this problem suggests a partial solution to the identification of the deception problem. 1 INTRODUCTION The problem of designing structures is pervasive in science and engineering. The problem is: Given a function and some materials to work with, design a structure that performs this function subject to certain constraints. As an example of the design problem, consider the combinational circuit design problem: Given a set of logic gates, design a circuit that performs a desired function. Two instantiations of this...

We use the average hamming distance of a population as a syntactic metric to obtain probabilistic bounds on the time convergence of genetic algorithms. Analysis of a flat function provides worst case time complexity for static functions and gives a theoretical basis to the problem of premature convergence. We suggest simple changes that mitigate this problem and help fight deception. Further, employing linearly computable syntactic information, we can provide upper limits on the time beyond which progress is unlikely on an arbitrary function. Preliminary results support our analysis.

This paper defines a class of spaces which are easy for genetic algorithms and hard for stochastic hill--climbers. These spaces require genetic recombination for successful search and are partially deceptive. Problems where tradeoffs need to be made subsume spaces with these properties. Preliminary results comparing a genetic algorithm without crossover against one with two--point crossover support these claims. Further we show how a genetic algorithm using pareto optimality for selection, outperforms both. These results provide insight into the kind of spaces where recombination is necessary suggesting further study of properties of such spaces, and what it means to be GA--easy and hill--climbing hard. 1 INTRODUCTION Recombination plays a central role in genetic algorithms (GAs) and constitutes one of the major differences between GAs and other blind search algorithms. 1 The answer to the question of whether a search space is particularly suited to a genetic algorithm therefore hin...

Many large image databases are springing up as cheap optical technology finally lets users store large numbers of images. The database community has few solutions to the problem of finding one image, picture, or face out of a million. We present a solution which is simple, intuitive, and permits image-based searching on a large database by selection. Keywords: interfaces, image databases, pictures, images, statistics, clustering, vector spaces, face recognition, image analysis, file identification, file indexing. 1 Introduction When designing interfaces for image databases, current database ideology suggests querybased interfaces expressed in SQL or similar languages (e.g. [4].) We believe this approach is not well suited to typical use. Query-based interfaces are hard for most non-experts to use, and wearying even for experts. Users must possess knowledge about the domain of the database, the functionality of the retrieval system, and the classification scheme employed by the databa...