The Evolution of Simon's Ant

 Gerhard Werner

 Biomedical Engineering Program
 Department of Electrical and Computer Engineering
 University of Texas at Austin, TX, USA

e-mail address:

When locating a URL with great expectation of finding valuable information we experience great disappointment with the message  "under construction".  This discussion will introduce ideas "under construction", but hopefully persuade you that it makes good sense to continue the construction job

I take as point of departure Simon's Ant which was introduced in the important lecture series on "The sciences of the artificial", subsequently  published in 1969 in a booklet of the same title. At one point in these lectures, Herbert Simon, known for his seminal role in the formulation of the original concept of Artificial Intelligence, reflected on the seemingly opportunistic ways in which an ant traces a path through its environment. He captured his observations in this hypothesis:

"An ant, viewed as a behaving system, is quite simple. The apparent complexity of its behavior over time is largely a reflection of the complexity of the environment in which it finds itself".
    Simon then generalizes by substituting "man" for "ant", thus suggesting that the apparent complexity of man's behavior is also largely a reflection of the complexity of the environment in which he lives.

[Show sketch of ant on beach]

 I am placing the emphasis on the word largely since I will attempt in the following to show that developments in  the symbiosis of AI and  theories of Cognition during the past 30 or so years can be viewed as a progressive change in the allocation of complexity in the actor-environment dialectic. I will finally try to convince you that doing complete justice to the ant's performance requires taking a new perspective which can capitalize on methods and approaches in nonlinear systems and complexity theory.

 Simon himself did not elaborate at this occasion as to how he thought the ant would accomplish its behavior, but we can assume that he had the  Physical Symbol Theory in mind, which he has consistently adhered to: algorithmic transformations over symbolic representations. Yet, some 20 years later, in addressing  various revisionist challenges to this theory, he said this : "..the ant deals with each obstacle as it comes" . This sounds to me strikingly similar to what is now known as "subsumption architecture" of R. Brooks and others. However, he hastened to add that this is quite different for, say the monkey, which can perform delayed response tasks, implying that at this stage of evolution, symbolic internal representations have assumed importance for behavior.

Stepping back from the claims of this and conflicting theories, I suggest a more general way of conceptualizing the ant's (and for that matter, the monkey's) problem:  for the ant to behave successfully in the complex environment, its internal functional organization must be of a degree of complexity  that is commensurate  to that of the task requirements. Complexity is here defined in terms number of degrees of freedom or,  more precisely, as algorithmic complexity. The reasoning is then analogous to the implication of algorithmic complexity theory:  to prove a theorem, the axiomatic system must be of equal or larger complexity than the theorem. Accordingly, the issue  for any kind of problem solving, including Cognition and Behavior,  turns on matching the complexity of demands (or goals) with the complexity of the available resources.

The complexity of internal organization that the ant brings to the task can be considered as of two kinds: 1) the Complexity  of the apparatus for execution of the required behavior, i.e.: the functional organization of its motor apparatus; and 2) the Complexity  of its decision making apparatus that selects one trajectory of movement or direction over another, in accord with environmental exigencies, goals etc.  Somehow, both (1) and (2) must match the the latter: the former presumably in some part  in virtue of developmental adaptation in ontogeny and phylogeny, according to average expectable environmental demands; source and nature of the latter is the subject of theories of Cognition and AI.

According to the symbolicist outlook in the Physical Symbol theory, the agent possesses some symbolic internal representation over which it can perform algorithmic transformations for solving specific problems, i.e.: for making plans for their execution.  This approach is of course straightforward in conventional AI problem solving, where the programmer provides the machine with both the symbolic representation and the algorithms. The situation is more complex in an autonomous agent behaving in an environment: we must invoke some form of symbol grounding, represented by the schema that highlights the steps involved:

                                                                SLIDE of ROSEN

On closer look, this view has its problems: in conventional AI programming, the semantics of the encoded symbols is -pictorially speaking- in the programmer's head.  The machine deals merely with mappings of the programmer's semantics on to physical instantiations. Physical states per se do not  have a semantics, on first principles: confounding the domains of Causality and Logical entailment is a category error.  Of course, mental processes can be matched by ('represented by') physical processes: the brain does just this (at least in the philosophic stance of Materialism), and so does the machine, except that the latter has the programmer do the matching.

We are left with the question: How can functionally effective internal representations come about autonomously, i.e.:  if there is no 'programmer' that provides the semantics ?   Short of abandoning the notion of internal representation (as some schools of thought propose), is there a way of constructing some form of internal representations (not necessarily symbolic) that would  in fact produce a kind of  'representation'  that is intrinsic to the machine, to be FOR THE MACHINE, rather than FOR A THIRD PARTY (i.e.: the observer or programmer) ? This is of course the long standing philosophic problem of first vs. third person perspective.

Before turning to Connectionism as one proposed route, I will mention briefly the revisionist trajectory of the AI genealogy in the form of Situation-Action Theory and Embodiment. The former replaces the postulated  behavior-mediating internal symbolic representation  with the direct (i.e. unmediated) interaction between the agent's controller and the environment: the agent (program) is a participant in its environment in that the world is immediately accessed through perception. Behavioral routines are causally related to objective events in the world which are, in the terminology of Agre and Chapman,  indexical and functionally individuated: "the-coffee-pot-in-front-of-me".  This form of deictic representation implies direct participatory interaction with the environment and designates the momentary relation between agent and its world.

One might argue that Situation Theory goes only half way,  the rest of the way being  taken by Embodiment: it adds  the emphasis on the agent's causal efficacy in the world, due to its  physical embeddedness in its environment . The agent's  realistic relation to the world  is constrained by the finiteness of its resources, the limited perspective available to it as its "life world", the indexicality of its perception, its physical locality, motility: that is, the entirety of its physical grounding is in its "Umwelt". It is  the active participation in the physical world that  establishes an intrinsic semantics FOR the agent.  The essential claim  is this: in strong AI, semantics is in the 'eye of the beholder' and FOR THE BEHOLDER, while  the semantics in Embodiment is BY and  FOR THE AGENT.

The shift of emphasis is notable: 'strong AI'  focused on the individual problem solver, its leading motif was the classical 'logical theorist' program. The revisionists  view problem solving increasingly from he point of view of the physicality of the agent embedded in an environment, functioning under the constraints of its own physicality and the world it interacts with. Yet, the goal of understanding cognition is not abandoned, except its laboratory is now cognition and behavior in practice, as a new form of 'experimental epistemology'.

I will now turn to the second branch in computational and theoretical Psychology: Connectionism, limiting this sketch to the contrast to the symbolicist program. From the point of view of computation theory, connectionist nets are inherently nonlinear parallel dynamical systems, with capacity for self-organization. It had been known from the very earliest studies in Neurodynamics that connectionist nets can exhibit the full range of nonlinear behavior, given the appropriate parameters. In fact, the original motive for this work was to determine the kind of properties which networks of McCulloch-Pitts type neurons would have to have so that they will NOT go into uncontrollable oscillations and chaos. The nonlinear properties of neural networks have attracted considerable attention in Physics for the formal characterization of spin glasses, turbulence and other complex physical phenomena.

However, historically, most investigators with connectionist orientation avoided  exploiting the full range of activity such systems can produce, limiting themselves to operate in the zone of "well behavedness" where the system converges to stable, stationary states which can be considered attractors of a dynamical system:

                          SLIDE of attractor phase space: stable attractors with difft. trajectories in separate Attractor Basins.

This seemed quite appropriate since Connectionism aspired to being a Theory of Cognition, in opposition to strong AI, but with a different concept of 'representation': it is now distributed over the connection weight matrices among the network elements.  Whether this change removes the programmer (network designer) out of the loop, so to say, is not in all instances clear, but it is noteworthy that connectionist networks can autonomously perform categorization tasks and, in that sense, can construct concepts and  build their own structural constraints.  The thrust of connectionist's current orientation seems to be shifting to  control system design. In theoretical Neurosciences, research in Connectionism aimed at elucidating principles of information encoding in the Nervous System, but lack of biological realism and basic uncertainties as to the meaning of 'neural coding'  have  frustrated the achievement of this objective.

The fact that Neural Networks can display the full range of nonlinear behavior is underscored in the next few  Slides:

                      SLIDE introducing Bifurcation Diagram: time evolution of quadratic map for difft. parameter values
                                                SLIDE comparing bifurcation diagrams of quadratic map and a NN

A new contender for a theory of  Cognition is the Dynamicist Theory which consolidated its image  with the publication of v. Gelder's and Ports' "Mind as Motion" about 5 years ago.  It asserts its identity by  (1) repudiating any form of representationalism (symbolic or subsymbolic), but the distinction from Connectionism is blurred: perhaps, more of emphasis than of substance; and (2)  by a new root metaphor: it claims that higher level cognition has its developmental roots, and reveals its functional structure,  in the organization of motor behavior. The following example illustrates the principle: consider the phase relation of moving two fingers; it is constant over a wide range of frequencies up to a critical point at which a sudden phase shift occurs. The frequency of motion is viewed as a control parameter of the complex neural mechanisms that support  the finger motion; the sudden phase shift is thought to be analogous to phase transitions in physical systems.

                                                           [SLIDE of Finger motion]

This type of observation and the associated phase transitions in the Electroencephalogram and data from brain imaging lead to the postulate that the brain is predisposed to  forming selforganizing patterns according to its intrinsic dynamics, and to abruptly shifting among them, if prompted by system specific control parameters.  It resonates with the significant work of Randall Beer's computational models of the dynamics of agent-environment coupling in continuous time recurrent Neural Networks: complexity of the behavior resides neither in the environment alone, nor in the organism alone, but rather in the dynamics of the coupled system. This point of view resolves the complexity matching  which I raised initially as a crucial issue in the story of Simon's ant.

That Cognition and Computation are dynamic processes is, of course, trivially true. Irrespective of whether we embrace the theory as a whole, or not, the dynamicist theory of cognition is alerting us to the possibility that the methods and concepts of nonlinear system theory can illuminate aspects of cognitive processes, that may have heuristic value. There are a priori good reasons to expect some payoff from this approach: for it is plausible that cognition and behavior as functions of of living organisms are subject to their basic nature as nonlinear open systems, operating far from equilibrium, and displaying the dynamics of broken symmetry; thus capable of  the entire range of manifestations, characteristic of nonlinear systems.

Here are some of the questions the dynamicist theory challenges us to ask:  what methodological tools of relevance to Cognition can nonlinear dynamics offer ?  Does it offer concepts for organizing empirical data coherently and consistently across different empirical  domains ?  Can nonlinear dynamics in  Neural Networks studies enrich our perspective on Cognition, as it has in various areas in statistical mechanics  ?   And what about the more recent extension of neural network style models to Cellular Neural Networks and Coupled Map Lattices ?

It seems to me that there is a wide range of explorations at out doorsteps: here we enter the zone of "under construction" I referred to initially. In the following, I will  illustrate with simple examples several potential assets of dynamical system analysis, as I see them at this time:

1): As a first step, thinking of cognition in terms of attractor dynamics in phase space can be a helpful tool for sharpening one's intuition about the selforganizing capacity of nonlinear systems: here are two examples. The trajectories can be viewed as pathways to finding solutions to a problem:

                      [Slide on itinerant behavior in coupled quadratic map, under influence of changing coupling parameter]
                                                  [Same, in 3D: a two-dimensional attractor,  two solutions]

These simulations are intended to show the dynamics of attractor itineration in the phase space of the coupled quadratic maps, in interaction with external parameter changes, or changes in coupling strength between agent and environment. Note that in the two slides shown, it is the phase spaces of the coupled agent-environment system that is traversed, reflecting the interaction dynamics of agent and surround. Hence the attractor 'belongs'  to say to both the agent and the world. We need no longer speak of complexity matching between agent and task environment. Instead, we are dealing with ONE system in which both parties  participate at varying degrees of coupling.

Applying this line of thought to several interacting agents and their environment brings to mind the image of  dancers in a ballet, or musicians in an orchestra, and leads  to the theory of coevolving systems in computational Ecology and Distributed AI.  For the latter case, the next slide from the work of Hogg  & Huberman shows the nonlinear dynamics in a group of agents:

                      [Slide from Hogg & Huberman: periodic and chaotic oscillations, as function of payoffs and resources]

2):  Returning to the Slides of (1): intriguing as the display of trajectories may be, what can it offer for cognition ?  The answer lies in the application of  Symbolic Dynamics.  Here is the principle: dividing the phase space into a finite number of regions, each of which may be labeled with a symbol, or stand for a behavioral routine, or a plan for execution. Then, the evolution of a trajectory in phase space is  de facto  an encoding of the attractor's orbits.

3) This leads to a further important consideration: GENERATION OF NEW INFORMATION by chaotic attractors:

   [show Henon map at difft. resolutions]

Assume again the phase space divided into cells of arbitrary degree of resolution, each cell containing an item of a data structure. Then, each orbit of the attractor traverses a different sequence of  data items: each orbit will link them to a different sequential pattern.  View this in the light of the defining characteristics of chaotic attractors: confinement to a circumscript region in phase space, and sensitivity to initial conditions. Hence, each orbit will generate a sequence of data items which is specific to the initial condition, yet deterministically related to it. In this sense, the each orbit targets information which is not implicit in its initial conditions. This behavior can formally characterized as topological entropy, roughly measuring the growth rate of the number of resolvable orbits (given a certain measurement partition) whose initial conditions are all close.

The important point is that harnessing the properties of chaotic attractors for computational and informational purposes has intriguing potential which is under active investigation in a number of centers. Parenthetically, note the converse issue: assuring by computational approaches that nonlinear systems do NOT enter chaotic regimes: see the work of Weeks & Burgess, using the NN  of  Moriarty & Miikulainen).

4): Reduction of dimensionality of phase space:

                                                                      [SLIDE including Ruelle graph]

This slide also shows one of the powerful analytical tools, which is justified by  the  'embedding theorem" : it stipulates that  multidimensional phase portraits can be constructed from measuring  one of the system's  observables at regular intervals, thus obtaining a time series. Under quite general constraints on the dynamics, the 'delay coordinate vector' thus obtained corresponds to the true dynamic of the system, but  representing it in a space of lower dimension.

The previously shown slide on phase transitions in finger movement showed the same principle of reduction of dimensionality. This is more impressively illustrated in the next slide, taken form  experiments with the Belousov-Zabotinskii reaction :

                                                                 [Slide from experiment of Swinney]

5): Here is an example from Neurobiology- applying a coherent explanatory system across different domains of inquiry, based of the principle of reduction of dimensionality::

                         [Freeman Slide: comparing model and biological recording, still showing dimensionality reduction]]

The importance of all this is in the possibility of deriving from the time sequence of behavior the internal dynamics of the system. Note here also the possibility offered by dynamical system approach to frame both neurological and cognitive-behavioral processes in the same conceptual framework.

6): A final point: the role of chaotic attractors for control and targeting : [here the remarkable success of NASA with steering a spacecraft that was 'parked' in a stabilized orbit, to encounter the comet Giaccobini-Zinner, by piecing together segments of different chaotic orbits, generated from a series of different initial values]. An extrapolation from this would be a more general application of chaotic attractors for control system design.

We started this discussion with Simon's Ant and followed the trend of viewing agent and its environment as two interacting, coupled and adaptive complex systems: for each act of the agent affects the environment in some way; and conversely, each change in the environment (including those brought about by the agents action) calls for the agent's  internal reconfiguration. Moreover, this  reciprocity of interaction must be understood in terms of the fact that each partner in this duo is itself a complex system, i.e.: consisting of many multiply interacting elements, each capable of adaptive change in the dynamics of their intrasystemic transactions.

 In retrospect, it appears that the failure to recognize the ubiquity of complexity and  nonlinearity in actor-environment systems prevented classical AI and a large segment of traditional Connectionism  from achieving their goals as theories of Cognition, and imposed certain limitations on their practical usefulness. I conclude with the suggestion that the lessons from Situation Theory, Embodiment, and Connectionism can  be accommodated, and brought to full fruition, in the framework of nonlinear dynamics of coupled systems.