next up previous contents index
Next: Multicellular Programming and Swarm-Programming Up: The Goal: Evolution of Previous: The Goal: Evolution of   Contents   Index

Subsections

Distributed Intelligence - Related Work

Distributed intelligence is a subject that has until now mainly been studied by other parts of the computer science community which use quite different methods for developing distributed intelligent systems. Probably the most prominent area of research trying to create distributed intelligence is the field known as Distributed Artificial Intelligence (DAI) and its subfield called Multiagent Systems (MAS). This field will be shortly characterized in section 4.1.2. But in section 4.1.1, I will first describe another approach to creating distributed intelligence that has primarily been developed by an equally called research group at the Massachusetts Institute of Technology: Amorphous Computing. The reason for this order of presentation is, that the idea of amorphous computing is much closer related to the multicellular approach of OOOP than multiagent systems, so that OOOPS can very easily be used for evolving amorphous computers. Evolving multiagent systems with OOOPS requires to leave the notion of cell clusters and extend the Multicellular Programming approach of OOOP to Swarm-Programming as described in section 4.2.

Section 4.3 finally tries to fit the new field denoted as Evolution of Distributed Intelligence (EDI) into a taxonomy covering all the major current approaches to creating intelligent problem solutions on the basis or with the help of computers.


Amorphous Computing

The idea of amorphous computing is to randomly distribute a great number of similar computing elements on a surface or throughout a volume. These computational particles are sensitive to the environment, may affect actions and are all programmed identically2. They should be as self-sufficient as possible and work asynchronously, but they can interact with each other using local communication based on diffusible carriers like short-distance radio or chemical substances. Each particle has only modest computing power and a modest amount of memory, but a large group of such particles can self-organize to build a single amorphous computer which can solve new types of problems.

The computational particles constituting an amorphous computer can be such different entities as tailor-made biological cells or very small chips integrating many microelectronic mechanical components. The development in both microfabrication and fundamental biology will probably enable the production of huge numbers of almost-identical information-processing units at almost no cost in the future, provided that all the units need not work correctly and that their geometric arrangement and interconnections need not be precisely manufactured. There are already some research groups that build such cubic millimeter-scale microelectromechanical computing units with the desired physical abilities ["Smart Dust" Project, ,Ultralow Power Wireless Sensor Project, ,Wireless Integrated Network Sensors (WINS) Project, ]. Eventually, it may be possible to construct even smaller and cheaper microfabricated particles using molecular devices [Rotman, 2000].

Harold Abelson et al. of the Amorphous Computing Project at MIT write in [Abelson et al., 1999]:

Yet fabrication is only part of the story. Digital computers have always been constructed to behave as precise arrangements of reliable parts, and almost all techniques for organizing computations depend upon this precision and reliability. So while we can envision producing vast quantities of individual computing elements--whether microfabricated particles or engineered cells--we have few ideas for programming them effectively. The opportunity to exploit these new technologies poses a broad conceptual challenge, which we call the challenge of amorphous computing:

How does one engineer prespecified, coherent behavior from the cooperation of immense numbers of unreliable parts that are interconnected in unknown, irregular, and time-varying ways?
This question could be answered with: "By using multicellular programming." Indeed, we have seen that OOOPS as a realization of multicellular programming exactly does what is being requested here. This is not surprising, because the OOOP paradigm is inspired by the same natural examples as is amorphous computing. Still, the researchers working on the field of amorphous computing do until now not use the natural way of producing such systems. To my knowledge, there is no approach until now that uses evolutionary algorithms for breeding good particle programs for amorphous computers (except OOOPS). The main reason for this is probably that the necessary interactions in an amorphous system seemed to be too complex for the evolutionary power of current evolutionary algorithms. There was not yet a programming paradigm like OOOP that fits exactly the amorphous computing notion of distributed intelligence on the basis of the interaction between many small identically programmed units and which can easily be combined with evolutionary algorithms.

But why did the amorphous computing researchers not even try evolutionary computation? Might another reason be a misunderstanding about EC? Harold Abelson et al. note in [Abelson et al., 1999]:

As engineers, we must learn to construct systems so that they end up organized to behave as we a priori intend, not merely as they happen to evolve.
This comment is not targeted on evolutionary computation but on artificial life research about self-organizing systems. Nevertheless, it should have been followed by a remark like: "One possible approach is to direct the evolutionary development with breeding methods. This is called evolutionary computation."

If you compare descriptions of the amorphous computing challenges with what you have read in previous chapters about OOOP and OOOPS, you will notice that the object-oriented ontogenetic programming system is ideally suited for developing programs for the particles in amorphous computers. All the following quotes are taken from [Abelson et al., 1999].

Traditionally, one seeks to obtain correct results despite unreliable parts by introducing redundancy to detect errors and substitute for bad parts. But in the amorphous regime, getting the right answer may be the wrong idea: it seems awkward to describe mechanisms such as embryonic development as producing a "right" organism by correcting bad parts and broken communications. The real question is how to abstractly structure systems so we get acceptable answers, with high probability, even in the face of unreliability.

...

Wave propagation with hop counts, as Nagpal [Nagpal, 1999] remarks, is evocative of the gradients formed by chemical diffusion that are believed to play a role in biological pattern formation. Consequently, we can attempt to organize amorphous processes by mimicking gradient phenomena observed in biology.

...

All of the particles have the same program. As a result of the program, the particles "differentiate" into components of the pattern.

...

In general, it is plausible to expect that the most powerful techniques for amorphous computing will be ones that will tie computation intimately to particle activation and mobility, and to physical constraints of the environment.
All these quotes could as well be taken from a description of the OOOP paradigm3. Even though OOOP was developed without having any idea about amorphous computing, it is a nearly exact realization of the amorphous computing ideas, just because the ideas in both cases are taken from the natural example of cooperation between cells in a multicellular creature.

Amorphous computing as realized by the MIT project does not include mobile particles even though this possibility is included in the amorphous approach described in [Abelson et al., 1999]:

In general, the individual particles might be mobile, but the initial programming explorations described here do not address this possibility.
A project called "Programming the Swarm" initiated by David Evans works on programming methodologies for amorphous computers including mobility of the particles ["Programming the Swarm" Project, ]. OOOPS is also perfectly suited for developing particle programs for these types of systems. For doing this, only the multicellular approach of OOOP has to be extended to a swarm approach as described in section 4.2. This extension also enables OOOPS to breed control programs for the interacting units of multiagent systems and with that opens up a huge field of possible applications for the object-oriented ontogenetic programming paradigm and for the OOOP communication paradigm.


Multiagent Systems

Compared to amorphous computers, multiagent systems do not concentrate on large numbers of very small interacting entities. Instead, they can consist of arbitrarily complex and powerful units called agents. Such an agent could for example be a robot in an automated production process which would be much more flexible than the current industrial robotic systems. Or it could be one of several robots autonomously exploring a distant planet. The cooperation of several robots would have the advantage over one single explorer that they could help each other in difficult situations and that the exploration could be done much faster. The agents do not have to be physical entities; they can also be separate programs that interact either on a single computer or in a network. But the example of real mobile robots each solving complex tasks shows best the mentioned difference to amorphous computing and the extensions to OOOP that are necessary for developing such systems. These extensions will be discussed in section 4.2.

As the field of multiagent systems is already very well known and spans a wide area of possible applications, there are several introductory publications that can be recommended for getting more information about this subject. [Schmutter, 2000b] is a short introduction to the main ideas and approaches. [Stone and Veloso, 2000] is more detailed concentrating on machine learning methods. [Weiss, 1999] finally is a book extensively covering most current MAS approaches and problems.

The research field of multiagent systems has come into being as a subfield of distributed artificial intelligence which itself is a subfield of Artificial Intelligence (AI). As we will see in section 4.3, artificial intelligence uses a quite different approach to creating intelligence than evolutionary computation. This explains, why also in multiagent systems research there are very few works trying to use evolutionary methods for developing distributed intelligence, even though this research field is older and much larger than amorphous computing.

One of the few approaches to using genetic programming with multiagent systems is described by Thomas Haynes et al. in [Haynes et al., 1995]. They write:

The identification, design, and implementation of strategies for coordination is a central research issue in the field of Distributed Artificial Intelligence (DAI) [Bond and Gasser, 1988]. Current research techniques in developing coordination strategies are mostly off-line mechanisms that use extensive domain knowledge to design from scratch the most appropriate cooperation strategy. It is nearly impossible to identify or even prove the existence of the best coordination strategy. In most cases a coordination strategy is chosen if it is reasonably good ...We believe that evolution can provide a workable alternative in generating coordination strategies in domains where the handcrafting of such strategies is either prohibitively time consuming or difficult.
Sean Luke and Lee Spector describe another approach to using genetic programming for the evolution of distributed intelligence in [Luke and Spector, 1996]. These first steps into EDI have already been discussed in section 1.5.2 where I also described some disadvantages of the presented models. In spite of these pitfalls, especially of the simplicity of the models, the real reasons for their little impact on other multiagent systems researchers have to be sought for somewhere else. The main reason might be the large separation of the EC and the AI research communities. The relation between the different approaches to creating intelligence will be discussed in section 4.3.


next up previous contents index
Next: Multicellular Programming and Swarm-Programming Up: The Goal: Evolution of Previous: The Goal: Evolution of   Contents   Index
 
© 2002 Peter Schmutter (http://www.schmutter.de)