Search

Cells are complex biochemical systems whose behaviors emerge from interactions among myriad molecular components. Computation is often invoked as a general framework for navigating this cellular complexity. However, it is unclear how cells might embody computational processes such that the theories of computation, including finite-state machine models, could be productively applied. Here, we demonstrate finite-state-machine-like processing embodied in cells using the walking behavior of Euplotes eurystomus, a ciliate that walks across surfaces using fourteen motile appendages (cirri). We found that cellular walking entails regulated transitions among a discrete set of gait states. The set of observed transitions decomposes into a small group of high-probability, temporally irreversible transitions and a large group of low-probability, time-symmetric transitions, thus revealing stereotypy in the sequential patterns of state transitions. Simulations and experiments suggest that the sequential logic of the gait is functionally important. Taken together, these findings implicate a finite-state-machine-like process. Cirri are connected by microtubule bundles (fibers), and we found that the dynamics of cirri involved in different state transitions are associated with the structure of the fiber system. Perturbative experiments revealed that the fibers mediate gait coordination, suggesting a mechanical basis of gait control.

For decades, the evolution of cooperation has piqued interest in numerous academic disciplines, such as game theory, economics, biology, and computer science. In this work, we demonstrate the emergence of a novel and effective resource exchange protocol formed by dropping and picking up resources in a foraging environment. This form of cooperation is made possible by the introduction of a campfire, which adds an extended period of congregation and downtime for agents to explore otherwise unlikely interactions. We find that the agents learn to avoid getting cheated by their exchange partners, but not always from a third party. We also observe the emergence of behavior analogous to tolerated theft, despite the lack of any punishment, combat, or larceny mechanism in the environment. [ABSTRACT FROM AUTHOR]

Many researchers in AI and Cognitive Science believethat the information processing complexity of a mecha-nism is reflected in the complexity of a description of itsbehavior. In this paper, w e distinguish two types of com-plexity and demonstrate that neither one can be anobjective property of the underlying physical system. Ashift in the method or granularity of observation cancause a system's behavioral description to change inboth the number of apparent states and the complexityclass. These examples demonstrate h o w the act of obser-vation itself can suggest frivolous explanations of physi-cal phenomena, up to and including computation.

This paper' proposes a new approach to mental imagery that has the potential for resolving an old debate. W e show that the methods by which fractals emerge from dynamical systems provide a natural computational framework for the relationship between the "deep" representations of long-term visual memory and the "surface" representations of the visual array, a distinction which was proposed by (Kosslyn, 1980). The concept of an iterated function system (IFS) as a highly compressed representation for a complex topological set of points in a metric space (Bamsley, 1988) is embedded in a connectionist model for mental imagery tasks. T w o advantages of this approach over previous models are the capability for topological transformations of the images, and the continuity of the deep representations with respect to the surface representations.

In this paper' we describe a genetic algorithm capable of evolving large programs by exploiting two new genetic operators which construct and deconstruct parameterized subroutines. These subroutines protect useful partial solutions and help to solve the scaling problem for a class of genetic problem solving methods. W e demonstrate our algorithm acquires useful subroutines by evolving a modular program from "scratch" to play and win at Tic-Tac-Toe against a flawed "expert". This work also amplifies our previous note (Pollack, 1991) that a phase transition is the principle behind induction in dynamical cognitive models.

Cognitive scientists, AI researchers in particular, have long-recognized the enormous benefits of modularity (e.g., Simon, 1969), as well as the need for self-organization (Samuel, 1967) in creating artifacts whose complexity approaches that of human intelligence. And yet these two goals seem almost incompatible, since truly modular systems are usually designed, and systems that truly learn are inherently nonmodular and produce only simple behaviors. Our paper seeks to remedy this shortcoming by developing a new architecture of Additive A d i ^ v e Modules which we instantiate as Addam, a modular agent whose behavioral repertoire evolves as the complexity of the environment is increased.'

This paper discusses the problem of how to implement many-to-many, or multi-associative, mappings within connectionist models. Traditional symbolic approaches wield explicit representation of all alternatives via stored links, or implicitly through enumerative algorithms. Classical pattern association models ignore the issue of generating multiple outputs for a single input pattern, and while recent research on recurrent networks is promising, the field has not clearly focused upon multi-associativity as a goal. In this paper, we define multiassociative memory M M , and several possible variants, and discuss its utility in general cognitive modeling. W e extend sequential cascaded networks (Pollack 1987, 1990a) to fit the task, and perform several initial experiments which demonstrate the feasibility of the concept.

The communication of musical thoughts and emotions requires that some musical knowledge is shared by composers, performers, and listeners. Computational models of musical knowledge attempt to specify the intermediate representations required to generate adequate predictions of musical behavior. W e describe a connectionist model that encodes the rhythmic organization and pitch contents of simple melodies. As the network learns to encode melodies, structurally more important events tend to dominate less important events, as described by reductionist theories of music (Lerdahl & JackendofF, 1983; Schenker, 1979). W e describe an empirical study in which improvisations on a tune by a skilled music performer are compared with the encodings produced by the network. The two are examined in terms of the relative importance of the musical structure they posit at intermediate levels of representation.

This paper explores the effect of initial weight selection on feed-forward networks learning simple functions with the badt-propagation technique. W e first demonstrate, through the use of Monte Carlo techniques, that the magnitude of the initial condition vector (in weight space) is a very significant parameter in convergence time variability. In order to further understand this result, additional deterministic experiments were performed. The results of these experiments demonstrate the extreme sensitivity of bade propagation to initial weight configuration.

Sequential Cascaded Networks are recturent higher order connectionist networks which are used, like fiuoite state automata, to recognize lansuages. Such networks may be viewed as discrete dynamical systems (Dynamical Recognizers) wnose states are points inside a multi-dimensional hypercube, whose transitions are defined not by a list of rules, out by a parameterized non-linear function, and whose acceptance decision is defined by a threshold applied to one dimension. Learning proceeds by the ad^tation of weight parameters under error-driven feedback from performance on a teacher-suppbed set of exemplars. The weights give rise to a landscape where input tokens cause transitions between attractive points or regions, and induction in this framework corresponds to the clustering, splitting and joining of these regions. Usually, the resulting landscape settles into a finite set of attractive regions, and is isomorphic to a classical finite-state automaton. Occasionally, however, the landscape contains a "Strange Attractor" (e.g fig 3g), to which there is no direct analogy ia finite automata theory.

The field of evolutionary robotics has demonstrated the ability to automatically design the morphology and controller of simple physical robots through synthetic evolutionary processes. However, it is not clear if variation-based search processes can attain the complexity of design necessary for practical engineering of robots. Here, we demonstrate an automatic design system that produces complex robots by exploiting the principles of regularity, modularity, hierarchy, and reuse. These techniques are already established principles of scaling in engineering design and have been observed in nature, but have not been broadly used in artificial evolution. We gain these advantages through the use of a generative representation, which combines a programmatic representation with an algorithmic process that compiles the representation into a detailed construction plan. This approach is shown to have two benefits: it can reuse components in regular and hierarchical ways, providing a systematic way to create more complex modules from simpler ones; and the evolved representations can capture intrinsic properties of the design space, so that variations in the representations move through the design space more effectively than equivalent-sized changes in a nongenerative representation. Using this system, we demonstrate for the first time the evolution and construction of modular, three-dimensional, physically locomoting robots, comprising many more components than previous work on body-brain evolution. Index Terms--Design automation, evolutionary robotics, generative representations.

Author(s): Hod Lipson; Jordan B. Pollack (corresponding author) Biological life is in control of its own means of reproduction, which generally involves complex, autocatalysing chemical reactions. But this autonomy of [...]