©1990-2007 Nick Porcino
This paper was originally written in 1990 for presentation at Neural Information Processing Systems '91, but I left for Japan and so didn't submit it.
Created with wordle.net A lot has happened since 1990. The fields of computational neuroethology, neuromimetic control systems, and distributed control have advanced markedly. Since then, I've become involved with the entertainment industry and have been shipping games, not publishing papers. Peter Molyneux has this to say about the application of AI to games: The real trick now is to give the [gaming] world a realistic personality. To achieve that, the gaming industry has to start concentrating on artificial intelligence. Since the 1970s when the concept first was brought to the public eye, artificial intelligence has been completely out of fashion. Now, the amazing thing that's happened is that the entertainment industry is pulling artificial intelligence back into the limelight. The artificial intelligence problems of the 70s are now being cracked by scientists in the universities - and by game developers. Now, this is an absolutely incredible turn around in the computing industry. But the game designers have to drive this forward because if we're ever going to approach interactive movies, we're going to need artificial personalities. And to have artificial personalities, you need artificial intelligence. Up until that point in the process, every single thing has to be drawn and choreographed by an artist, but once you have artificial personalities then there are no limits - all of a sudden the world will start to generate itself. And this will mean a really true revolution in games.
Keywords: distributed control, neural networks, subsumption, Braitenburg, games, artificial intelligence, robotics, mechatronics, neuroethology
An Overview of the Methodology Presented here is a design methodology for distributed control of intelligent systems. Traditional task decomposition of control problems can lead to a combinatorial explosion in the complexity of a problem (the Complexity Trap), necessitating an alternative approach. The approach presented here offers a way out of the Complexity Trap by:
- Distinguishing between high level behavioural control (meta-reflexes) and low level reflex behaviours
- Recognizing that complex behaviours may be the result of a complex environment
- Emphasizing the important distinctions between external environment sensing, intention, self-awareness, and peripheral sensing
- Mimicking the functional success of biological nervous systems
- Specifying that behaviours must be self-calibrating
- Promoting consensus decision making rather than absolute control by individual sub-systems
- The idea that behaviours and systems are reciprically related, rather than hierarchically.
The use of a desires automaton in the instinct module allows the sequencing of behaviours through the manipulation of self-awareness signals. Peripheral signals are used by the instinct module to modulate such basic reflexes as manipulator control, body orientation, locomotion, and so on. The use of the proposed architecture is demonstrated by Network 1 which accomplishes the task of multi-robot coordination, and by Network 2, the artificial insect controller of (Beer, et al, 1990) whose architecture is isomorphic with the work presented here. 1. Introduction: Escaping the Complexity Trap AI has advanced as far as it has through the successful application and exploitation of Reductionism. Unfortunately, reductionism leads to the "Complexity Trap". Von Neumann (1958) said that "if you can describe something precisely enough in A implies B language, you can program it. " Accordingly, it should be possible to fully describe a task through a decomposition of "fine enough" detail. Unfortunately, as the early practitioners of AI soon discovered, task decomposition quickly becomes monstrous for a task of any significance. The difficulty, or even the impossibility, of making precise enough system descriptions is the Complexity Trap. The architecture proposed here is not so much a new architecture for distibuted control as it is a conceptual framework to facilitate the development of intelligent systems with a high degree of flexibility in their operation and in their interactions with underspecified environments. The Blockworld Problem
Consider the plight of a Blockworld robot equipped with a video camera and an arm told to put the small red block on top of the green block (Minsky, 1988). At first, the task decomposition is fairly straight forward: find the small red block, find the green block, put the red block on top of the green one. The lurking complexity is revealed at the next level of decomposition: "find the small red block" becomes a question of selecting one object among many in the environment. The task breaks down into smaller and smaller steps until it finally reaches the level of basic manipulation of bit-mapped figures. How can a block be recognized in its environment? How can the arm be moved to a particular point in space? How can the concept of on top of be specified? The description of the problem soon becomes monstrous, the decomposition enormous. As it turns out, the functions of human intelligence which we consider the highest (such as logical reasoning) are the easiest for a computer to do. Integral calculus and logical proofs can be easier to program than "simple" tasks like distinguishing a circle from a square because at the lowest levels the calculus problems are logical operations on strings of symbols, whereas distinguishing circles from squares involves more difficult problems such as the fundamental representations of concepts and geometries (Minsky, 1988). Complex Behavior arises from the Environment The architecture presented here follows an alternative approach.Instead of aiming for a system description (which must almost necessarily be incomplete), simplex reflex arcs subserving low level behaviours are designed, and feedback is introduced to modulate the interactions of the behaviours. The resulting system exhibits so called "emergent behaviours" - behaviours which have not been explicitly specified at the level of the system's implementation. As von Neumann (1958) warned, the full description of a system's behaviour may be more complex than the system itself. Complex behaviour may be the result of a complex environment (Brooks, 1986). The architecture presented here was designed to exploit this idea. Internal and Peripheral Senses The difference in character between autonomous, strictly reactive reflexes and the more complex behaviours which are a result of the interactions of lower level reflexes suggests a functional split for the proposed architecture. Following (Nagata, et al, 1990) the architecture splits a system into an "instinct" module where all the simple reflexes exist autonomously, and a "reason" module comprised of what are essentially meta-reflexes operating in reaction to both signals from the instinct module and to environmental stimuli. The reason module sends an intention vector to the instinct module to modulate the low level reflexes. Study of architectures incorporating the reason-instinct split revealed that the two modules can be characterized in terms of the sensory modalities appropriate to each module. Some senses such as hearing and vision are specific to the external environment. Other senses are internal, for example, feedback about the state of low level reflexes, and proprioceptive sensing such as force feedback from a manipulator. Whereas external senses are of primary importance only to the reason module, the internal senses must be divided into a self-awareness vector for the reason module, and peripheral senses for the instinct module. The self-awareness signals are the means by which the reason module's meta-reflex can monitor (be aware of) the activity of the reflexes in the instinct module. The peripheral senses and intention vector drive the instinct module, which in turn controls the effectors, completing the loop by providing a means whereby a robotic or other intelligent system can modify, and be modified by, the total environment. Figure 1 summarizes the Level I architecture.Figure 1
- The Architecture is modelled after the invertebrate nervous system. The reason module is analogous to the invertebrate's cerebral ganglia, the instinct module corresponds to the thoracic or sub-cerebral ganglia. The intention vector is the means by which meta-reflexes control reflexes, and the self-awareness vector allows the reflexes to influence the meta-reflexes.
Neuronal Networks
Neural and neuronal networks are important to the Architecture as a quick glance at the references reveals. In fact, the Architecture grew out of a study of invertebrate nervous systems and the application of neuromimetic computational architectures to intelligent systems control (Porcino 1990, Porcino and Collins, 1990). Invertebrates exhibit a high level of sophistication despite the relative simplicity of their nervous systems, and thus pose a significant challenge to researchers (Cliff, 1990). Furthermore, invertebrate neuronal networks are self-calibrating, like the behaviours intended for the Subsumption Architecture. Invertebrate neuronal networks are very much like adaptive control systems, and are ideally adapted by Nature for realtime control. Artificial neural networks attempt to mimic the functional success of biological nervous systems. Most neural network methods attempt to model large numbers of regularly connected identical neurons with no feedback. Typically gradient descent is performed on an associated Lyapunov energy function, and through this process a neural network converges on a solution. Traditional neural computational structures are only now beginning to demonstrate some competence in the termporal domain, but they are still unwieldy as they are still only functional black boxes with well defined input-output relations - signals are pipelined straight through with no internal feedback. In contrast, the approach taken in the development of the Architecture presented here differs in that inspiration was taken from the study of simple invertebrate neuronal networks which in general have small numbers of dedicated purpose neurons whose interconnections are fairly easy to ascertain or deduce.2. Distributed Control By Invertebrate Neuronal Networks
Returning again to von Neumann's warning about complexity, we can deduce that if the full description of a system's behaviour is more complex than the system itself, it follows that many abilities will not be directly specified in a full system description. In other words, complex behaviours emerge from the interactions of environment and the simpler elements making up the system. Theoretical system models often capture the flavour of some small aspect of a system's behaviour, but these models usually consider only very restricted contexts (cf. Guthrie, 1980). In actual fact the sheer multiplicity of behaviours and interactions between behaviours is natrual organisms are too complex for full description. Similarly, the behaviour of useful intelligent systems is equally hard to describe. Most current robotic systems operate in highly constrained environments such as the factory floor where only small numbers of predefined task need be performed on certain types of objects. The environment can be explicitly controlled; precisely defined objects are found only in specified places, thereby facilitating reliability, determinisim, speed, and operational efficiency. It is far easier to describe a very restricted environment and the behaviours possible in that environment than it is to specify open-ended real world systems. Nonetheless, modern intelligent systems have to deal with humans and more natural, less well-behaved environments. Inspired by the evolutionary progress of natrual systems, the neuro-mimetic computational structure is highly parallel, locally simple, and robust in the face of unexpected situations or even systemic failures. In natural nervous systems, no single processing unit controls behaviour - there is a progression of behavioural complexity beginning with the basic reflex arcs governed by a relatively small group of neurons (behaviours such as simple rhythmic motions or withdrawing from aversive stimuli), and ranging to the more complex behaviours governed by the higher nuclei and cortex (such as feeding and social interaction). Natural nervous systems are reciprocally connected and build consensus (Figure 3). They exhibit simple stereotyped behaviours generated by simple reflexes, and the interactions of simple reflexes lead ultimately to sophisticated behavioural repetoires. These concepts for distributed architectures imply:- Redundancy and Robustness because responsibility for any particular behaviour resides in no single unit
- Self Calibration of Behaviours through tight sensory feedback
- Behaviours which outlast the triggering stimulus through the action of feedback signals
- Command locus near the site of incoming information for maximum processing speed and minimum connection lengths and communication times (Davis, 1976)
- Specialization of units near sensory input due to self organization of neural circuits in reaction to patterns in sensory input (Davis, 1976); and
- Optimization and self adaptation of behaviours resulting from cooperation and competition between units (cf. Klopf, 1988, Grossberg, 1987).
3. Reflexes and Meta-Reflexes
If the head of an insect is severed, reflexes governed by ganglia lower than the cerebral ganglia are often released. Leeches swim continuously. Cockroaches walk spontaneously. Nereis will spontaneously creep, and it no longer withdraws if tapped. Female mantises bite off the head of the male to disinhibit copulatory behaviour. It seems that meta-reflexes in the cerebral ganglia control the reflexes of the lower ganglia. The reason-instinct split is suggested by this commonly observed nervous organization. The utility of meta-reflexes is simply illustrated by an example. One of the most apparently complicated behavioural displays is the group action of a large number of organisms, whether it is the flocking of birds, the schooling of fish, the milling of crowds, or the herding of mammals. When a flock of birds wheels overhead, it seems there must be some sort of central coordinating intelligence or some wonderfully complex communication system to allow all the birds to swoop and swirl around each other without ever crashing, or for all the birds to begin a turn in the same direction at almost the same time. As it turns out, no "super" control or communication is necessary. The flocking behaviour can be imitated by a very simple controller local to every member of the flock. Consider Network 1 (Figure 4). This behavioural controller, cast in the Architecture developed here's mould, is reminiscent of Braitenberg's Vehicles (1984) and Reynolds' Boids (1987). Figure 5 shows the behaviour of simulated vehicles using the controller. Notice that in general the vehicles attempt to reach the goal, but swerve to avoid collisions. A number of similar examples in three dimensions can be found in (Reynolds, 1987) and (Wilhelm and Skinner, 1990). The Wilhelm and Skinner paper elaborates on an interactive design system for Boid architectures, called Notions. The robots are given simple bodies equipped with some means of locomotion - wheels or legs, and some rudimentary senses. In Figure 3, sensors are drawn in left-right pairs pointed a few degrees off center. Each half of a sensor pair is sensitive to stimuli that are strongest in the direction the sensor is pointing. As the stimuli is moved off the sensor's axis, sensor response falls off logarithmically. This sensitivity pattern assures that the sensor whose axis passes nearest the stimuli will respoind the strongest. If a stimuli is "dead ahead, " both sensors respond equally. Logarithmic sensor response is used throughout the Architecture. Sensors are designed so that behaviourally significant states evoke a high resopnse, but response falls off quickly as the significant state is left. Logarithmic sensor response ensures that significant states evoke an impreative signal to reflexes and meta-reflexes (Porcino, 1990). The highest activations of a sensor indeicate the most imperative conditions in a fashion analogous to pain. This analogy points the way to learning in these circuits, perhaps using drive-reinforcement learning as described in (Klopf, 1988). Consider the instinct module of Network 1. Locomotion receives peripheral sensing signals specific to the mode of locomotion - for example, slip sensors for wheels, load sensors for legs. In addition, locomotion receives an intention vector consisting of a turn left magnitude, and a turn right magnitude. Based on the difference between the two inputs, the robot turns and moves forward. The reason module introduces the concept of "consensus decision building." The intention vector is the sum of the sum turn left and sum turn right processes. These processes simply pass on a weighted sum of their inputs, the simplest possible form of consensus. The inputs on the sum turn processes come from three meta-reflexes: avoid collisions, move to center, and move to goal. Move to goal is defined according to Reynolds (1987): it attempts to move a flock member to the center of its nearest flockmates and also to match the average velocity of the nearest flock mates. Move to goal causes a taxis towards some "homing" point that can be used to steer and direct the flock. Avoid collisions steers a flock member away from imminent disaster. Avoiding collisions has the highest behavioural priority, so avoid collisions ensures that its outputs dominate sum turn in times of crisis by shutting off the other two meta-reflexes. On the other hand, neither move to center nor move to goal is more important than the other, so sum turn forms a consensus between the two.4. Self Awareness
Network 1 illustrates the use of reflexes and meta-reflexes. It is ia controller which could be easily implemented by Levels 0, 1, and 2 of the Subsumption Architecture (Figure 6). Like the Architecture presented here, the Subsumption Architecture makes use of networks of simple interacting reflexes (Brooks, 1986). Higher level Subsumption Architecture behaviours supproess lower level behaviours and take over their functionality in a process called "subsumption." Lower level behaviours can never suppress higher level behaviours. In contrast, the Architecture presented here avoids a hierarchical arranagement by introducing the Self-Awareness feedback vector, which allows the emergence of interesting behaviour.Limitations of the Subsumption Architecture
The principal advantage of Subsumption is that low level behaviours can be readily designed and implemented, and subsequencty layers can be added on top of the correctly functioning lower levels. Unfortunately, there are some implicit problems with the Subsumption Architecture which have been addressed with varying degrees of success:- Since the Subsumption Architecture's hierarchical structure is strictly reductionist, the higher level behaviours fall victim to the task decomposition problems inherent in the Complexity Trap (Brooks, 1986, section IIC);
- It is completely reactive to the environment: its behaviour is nondeterministic and entirely state-driven. (Bellingham et al, 1990);
- It does not incorporate memory of actions and so cannot carry out predetermined sequences of events (Bellingham et al, 1990).
- The controller groups and sequences behaviours (to obtain food when hungry);
- It is goal directed (it generates movements which serve to find food);
- It exhibits changes in behaviour based upon an internal state (it attempts to find food when hungry, and ignores food otherwise);
- Behaviours can persist if stimuli are removed (if food is removed or runs out while the insect is eating, appetitive behaviour persists.