Dumb agents? Can intelligence emerge from a bunch of dumb machines? Can we study intelligence using dumb agents? Researchers at Indiana University (IU) are part of a growing community that believe that the dumb-agent approach will both enable Artificial Intelligence (AI) researchers to build more intelligent systems and enable cognitive scientists to study intelligence more broadly. These researchers are moving away from the traditional artificial intelligence approach which models intelligent behavior by designing and implementing a complex agent. The single-agent approach has shown success in specialized, rational domains such as game playing, reasoning, and path planning [14]. However, it seems important to acknowledge all of nature's successes, especially since nature happens to be replete with intelligent agents.
In some dumb-agent projects, the agents are isolated, trying to optimize their own performance. In other domains, the agents are not isolated and can interact with each other. Agent behaviors can then involve coordination with other agents. The problem domains currently under investigation at IU include sensory and motor control, the study of social behaviors, modeling interactive modes of cognition (such as language), and even solving complex problems by integrating these agents.
Several IU research projects have tried to use knowledge acquired from observing these natural domains to solve real-world problems, study social behaviors, and study action. The dumb-agent approach involves generating a population of initially dumb (naive) agents. The population is usually large (perhaps 50, 100 or even 1000 agents). Agents may all be identical to each other, or they may be different. Agents are often randomly constructed with the expectation that some of the natural variation in the population will contain seeds for solving the desired task. The entire population of agents is then evaluated for suitability to accomplish the task of interest. The better agents are usually selected for further modification. Through a continuous cycle of selection and modification, agents that are better suited for the task emerge. In some cases, the agents work alone, each trying to outperform the others in solving the task at hand. In other cases, the agents work together to solve the task.
We'd like to introduce you to the dumb-agent approach to intelligent behavior at Indiana University.
Gary Parker is working with six legged robots and the motor control routines necessary for each leg. With perfect conditions, programming the robot to walk would be straightforward. However, the real world does not offer many situations with perfect conditions. The various complications that Parker encounters include: individual legs with different lengths, traction and degrees of motion, individual motors with different speeds and torques, and walking surfaces that are rarely completely flat. It would be extremely difficult to design a specific program that could account for these varying conditions and constraints from both the robot and the environment. Instead, Parker evolves the motor control programs.
Parker has constructed a computer model of the robot which includes variables for each aspect of the robot's physical characteristics. Control programs can be fed into the model, making the simulated robot move. For each real robot, he calibrates the model to match the characteristics of the robot. In fact, during a single robot's lifetime, recalibration is sometimes necessary. Once the robot model is defined, he runs a genetic algorithm (GA) over motor control solutions.
A GA is a search method inspired by natural selection [6]. A population of solutions is randomly generated and each solution is evaluated for its fitness, which is a measure directly related to the solution's performance in the problem task. In Parker's case, the problem is moving the robot forward and the solutions are the motor control routines. The most fit solutions are used to spawn new solutions. Repeating this process many times (evolving generations of solutions) can lead to a set of solutions that solve the problem task well.
For Parker's work, the simulated robots start out with random movement in their legs. This usually does not move them very far. However, some do move forward a bit. These solutions lead to other solutions, some performing worse and some performing better. Over time, Parker has been able to get smooth motor control routines that mimic several different insect gaits [17, 18, 19]. Using these control routines in real robots leads to walking robots. Dumb robots, unable to move in any meaningful manner, have evolved into very capable robots through generations of simulated evolution.
However, Parker wants robots that can do more than just move forward. Now his GAs search for motor control routines to enable robots to thoroughly examine a target space. Though the tasks are similar to those tackled by Rodney Brooks [4], Brooks' architecture is very different. Instead of the low level agents in the Brooks' subsumption architecture, Parker's models evolve only motor commands, without any a priori knowledge of gaits. These commands are similar to those one might imagine are instinctive to simple animals.
One problem the robots face is that the environment changes around the robots, while their motor control does not. For this reason, Parker is looking into placing the GA that searches for the motor control routines on the robot itself. This would allow the robot to constantly evolve its walking routines for the current environment. It would also enable the robot to adjust its gait if any of the leg motors were damaged or inhibited. With the ``anytime'' learning technique in place, new robot controllers would be continuously tested, with the best potential solutions for the current environment always available for the robot.
While Parker's simulation tackles the problem of coordinating the legs on a single robotic agent, Cristobal Baray works on coordinating the actions between multiple agents. While distributed artificial intelligence models typically pursue coordination protocols for complex agents, there are other applications for it. Nature offers several coordinated animal societies to use for inspiration. Ants use pheromones to communicate about food sources, nest maintenance, and threats. Some squirrels and monkeys have communication systems that include several different types of alarm calls for different types of predators. Drawing on these systems, Baray developed a small artificial world, with food, poison, and some dumb agents.
The dumb agents in this case are simply reactive agents. They are stimulus response machines, controlled by a set of ``if-then'' statements. They are partially inspired by the ever intriguing Braitenburg vehicles [3]. The condition for the ``if'' is based on the agent's current environment, and the ``then'' clause defines a specific action to take. The agents do not have memory, nor are they able to learn (alter their if-then statements) during their lifetime. To allow the agents to cooperate, they are able to emit and receive signals. To decide what set of if-then statements the agents should utilize, genetic algorithms are deployed. Populations of identical agents are put into the world and their average lifespan represents the fitness of the if-then rules.
Simulations of the world were run, trying to parameterize the conditions where communication systems would evolve. Early experiments showed that the world was not hostile enough to motivate signals. If the living is easy, simple (even random) behaviors would do. In an attempt to alleviate this problem, mobile predators were introduced into the world. These predators were able to drive the evolution of the agents' behavior further. Alarm calls were discovered, with two different responses. In some cases, the agents would move away from an alarm call. However, other populations evolved the behavior of moving towards alarm calls [1]. Although the agents could not help each other directly when faced with a predator, they were able to help indirectly. The predators themselves are quite simple and they can easily be confused by many agents in their field of view. When other agents move towards the endangered agent, the predator has difficulty tracking any specific agent. In some cases, all of the agents can escape unharmed. This behavior is also seen in natural systems and is entitled the ``confusion effect''.
Currently, co-evolution of groups of agents is being introduced into the model. By relaxing the homogeneous restriction on the populations, specific roles might develop. Signaler/listener or leader/follower societies might show some advantages over homogeneous populations. Again, the goal is parameterizing the conditions leading to various strategies evolved. This knowledge could lead to better design methods for cooperative multi-agent systems. In addition, the work might be ported into high level controllers on Parker's robots in order to coordinate the actions of a robot colony.
Much like Cris Baray's work on coordinating the actions of multiple agents with signals, Kyle Wagner's work revolves around the actual signals that the organisms use. He looks at the effects of various environmental variables on the evolution of communication systems, such as human language. Why have communication systems evolved in so many species [11, 23]? Do these systems always eventually emerge in a species, or are there aspects of a species' environment that can predict whether or not a system of communication will arise? Questions such as these cannot be answered by traditional AI approaches as they require many interacting (signaling) agents.
Wagner's simulations deal with the effects of resource abundance, signal costs and population density on the evolution of signaling. Each agent is a simple stimulus-response mechanism: it can detect the presence of resources, signals and other agents, and it can move and send signals. Each agent's particular behavior is determined by its genes. Initially the agents have randomized genes, so they are dumb agents, incapable of responding to their environment properly. As their success in the world determines their mating success, each following generation of agents becomes better at negotiating its environment. Eventually, some populations evolve signaling behaviors that help them gather resources more effectively. In other experiments, populations evolve simple resource-gathering behaviors that do not use signaling at all (this occurs when the signal cost is too high or population density and lack of resources make signaling less useful).
Wagner also explores the interactions between learning and evolution in a society of agents [22, 21]. Particularly, he asks, why is cultural transmission so important for the specific form of language that a human speaks [5, 16]? For instance, a baby born to German parents that subsequently grows up in Japan -- and goes to Japanese schools -- will learn Japanese. However, the baby is not of Japanese ancestry. How can this be if DNA controls behavior such as communication? The answer may be that learning combines with evolution to develop complex behavior such as language. (See [7] for more on the relationship between evolution and learning.)
Wagner's simulations of the tension between evolution and learning are moving toward capturing the dynamics of a population of signalers that cannot rely on their innate (genetically-specified) signaling system. Why might organisms not be able to rely on the signals that evolution has built in? One explanation is that the environment is changing too rapidly for genetics to keep pace. Learning is introduced as a solution to this problem. It is possible that humans transmit their signal system culturally because the environment was very unstable sometime in our species' past, and evolution was too slow to modify the current signals to fit the new environment. Only time (and many experiments) will tell if this evolutionary hypothesis holds.
Jim Newkirk's interests can be seen as a complement to Wagner's. Instead of focusing on the solution of a complex problem in the environment, Newkirk focuses on the tools that the agents develop to solve it. The challenge in his artificial world is relatively simple: to learn to communicate about the objects in the world by creating names for them, and to consistently use these names so that a common vocabulary emerges among all agents[11]. Agents begin prelinguistically, with only the ability to make and recognize a set of sounds, and to observe the use of sounds by others. When two agents meet and use the same sound to describe the objects that they know, they are rewarded. This sharing of words for things is a linguistic accomplishment that improves survival by advancing cooperation. Their choice of words will spread if other agents observe this behavior and go on to imitate it in their own meetings.
In real life, things always change; similarly, agents in Newkirk's model continually discover new objects in their world. When new objects are encountered, the agents are faced with a choice. They must choose between invention or improvisation: they can try to invent a new word for this object by using a single new sound for it, or they can improvise a new name by combining words that already exist, much as we do with compound words. The more complex name will be favored if the new object resembles a known one, which will make the new name easier to learn. But it is also harder to interpret a complex name because the meanings of its component words may be combined in many ways. Not every agent will make the same choice, of course, so that these two forms of new names will compete in the population. The form that fits the new object best and is easiest to learn will spread most quickly, and eventually become part of the common vocabulary. Complex names are powerful choices because they have the potential to describe many new objects in terms of others. However, if agents choose to use them, they must develop a consistent method for interpreting a whole name from the meanings of its parts. This is the fundamental process behind the syntax of language: not only the use of words, but an effective structure for combining them.
Even more intriguing is that agents appear at two levels. On one level there are the communicating agents that, in their virtual world, use simple interactions to evolve a sophisticated vocabulary. At a higher level, there is the linguistic world whose agents are the individual words, competing against each other to dominate the vocabulary, and cooperating with each other to describe more objects than they could describe alone[2, 15]. Each kind of agent has its own problem to solve: virtual agents must survive in the world of objects, and words must survive in the vocabulary. However, since each species of agent depends upon the other, they collectively solve the larger problem of developing a useful language to describe the world.
The advances in computational power over the years have impressed Professor Gregory Rawlins, yet the software available for these powerhouses disappoints him. He often reminds us that computers should be tools which aid us in our daily tasks [20]. Instead it seems that many of the applications available increase the amount of work necessary for us to accomplish our tasks. His latest project, temporarily titled KnownSpace, is an attempt to improve the interface between users and data.
The project's goals include analyzing of data files (web pages, news documents, e-mail, and local files), clustering data among many dimensions and ranges, searching the web periodically for information that is relevant and/or potentially interesting, and displaying all this information in in a spatial environment through which the user can easily navigate. In addition, the specifics of each task need to adapt over time to each user's needs, interests, and preferences. For this project, Rawlins designed a multi-agent framework.
A strict design rule runs throughout this project: no agent in the program is capable of more than a simple job. Simple jobs include parsing data for attributes, searching for data with specific attribute values, clustering data on various attributes, collecting more data from the variety of sources, and monitoring user actions. Other agents monitor these lower level agents, enforcing selection.
Important attributes are hard to predict. They will change from user to user, and possibly from day to day. Thus, hundreds of attributes will be used, measuring aspects of pages that one might not think are important. However, within the data there probably exist patterns that depend on attributes we, as designers, might not predict. Novel attributes will be generated continuously. New clusters will form, relying on a variety of relationships between attributes. Over time, user actions will select some attributes and clusters. This allows the system to adapt its organization to reflect user interests and behavior patterns.
The projects just described are applying new methods to study and solve old problems. The methods are still in their infancy: the tools are constantly under development, results are hard to predict and interpret, and the approach is still more of an art than a science.
Yet, we still carry the belief that the interactions of many simple agents can lead to complex behavior.
The projects we have described are only a part of a growing group of work by researchers who believe that distributed, dumb agents can ``do the job'' better than a single, sophisticated agent[23, 11, 9, 13]. These works are all inspired in one way or another by the genetic algorithms introduced by John Holland, Marvin Minsky's wonderful essays on the various dumb agents that make up The Society of Mind, Douglas Hofstadter's ``Aunt Hillary'' in Godel, Escher, Bach, who so eloquently paints the analogy of ants and anthills with neurons and minds; and many other works that can be found in the proceedings from the Artificial Life and the Simulation of Adaptive Behavior conferences.
One area of human endeavor demonstrates clearly the power of many naive agents working on a much larger and more complex goal: science. No scientist is trying to understand everything at once. Instead, each scientist attempts to work in their highly-specific field, making contributions to the sum knowledge in that area. As each area grows through the contributions of individuals, those individuals can use the previous work to build new and better theories.
Though it may seem paradoxical to say that complex behaviors can arise from initially naive agents, the work at Indiana University and elsewhere shows that a great diversity of problems can be tackled with the dumb-agent approach. Intelligent agents are hard to program from scratch as AI researchers, and some tasks cannot be performed at all by a single agent. The alternate approach, starting with a population of dumb agents and selecting for increased performance, seems to work well for a great number of task domains.
Finally, our own society is composed of many agents, each able to achieve more than it could individually with the help of cooperation, communication, and evolution.
Kyle Wagner is also a graduate student pursuing a joint PhD in Computer Science and Cognitive Science at Indiana University. He studies the evolution of communication and the nature of meaning. He programs in Java. His favorite food group is chocolate. His email address is elyk@cs.indiana.edu
Copyright 1999 Cristobal Baray and Kyle Wagner
Want more Crossroads articles about Artificial Intelligence? Get a listing or go to the previous one.
This article has been selected to appear in the Dr. Dobb's DevSearcher Programmers Search Engine! This privledge allows you to rate this article:
Last Modified:
Location: www.acm.org/crossroads/xrds5-4/dumbagents.html