Brückner, Sven: Return From The Ant Synthetic Ecosystems for Manufacturing Control

6

Chapter 2. Background

The following chapter provides the context for this thesis. The thesis has two major themes: (a) the general support of the design of synthetic ecosystems (Chapter 3), and (b) the exemplary development of a complex synthetic ecosystem for manufacturing control (Chapter 4). Accordingly, the first section in this chapter focuses on concepts and techniques related to synthetic ecosystems in general, while the second section provides a short review of the state-of-practice and the state-of-the art in manufacturing control.

2.1 Concepts and Techniques

This thesis investigates systems made up of a number of separate entities, which interact among each other. As a result of these local interactions a global system-level behavior is observed. There are several branches in science where such systems are studied and each branch sets its own focus and uses its own techniques. Only very recently, interdisciplinary research has begun to emerge.

In the following, some of the basic concepts and technologies in the research into distributed systems are presented. The review presents approaches developed in biology, physics, chemistry, and in different branches of computer science. The purpose of the short review is not to cover all research activities and all the specific results gained. Rather, by looking at the same class of systems from different perspectives, a basic understanding of the characteristics of such systems should be conveyed.

2.1.1 Equilibrium Statistical Physics

In physics complex system-level behavior emerging from local interactions of spatially distributed individuals is studied in equilibrium statistical physics [Ashcroft and Mermin, 1976][Reif, 1965]. The entities in the system are simple physical objects - often called particles. There is no centralized control of any sorts. Local deterministic laws that are superimposed with probabilistic noise processes specify the interactions among the particles. The application of techniques from equilibrium statistical physics usually requires a huge number of particles (e.g., 1023).

The analysis of such particle systems focuses on the stable state character of the system. It is assumed that with ongoing interactions on the particle level, the overall system behavior settles in a stable state. The location of the stable state is dictated by the specific characteristics of the local interactions. Equilibrium statistical physics has developed a number of mathematical techniques. These are, for instance, the mean field theory, self-averaging approximations, analysis of phase transitions, Monte Carlo techniques, the replica trick, or tools to analyze the thermodynamic limit when the number of particles approaches infinity [Wolpert and Tumer, 1999].

An open issue in research is the adaptation of the model to a system of more complex individuals so that such techniques may also be applied to analyze their emerging system-level behavior. There are already examples in literature pointing the way to solutions. The iterated prisoner's dilemma played on a lattice is investigated numerically [Szabo and


7

Toke, 1998], stochastic games are analyzed by expressing the deviation from rationality in the form of a „heat bath“ [Marsili and Zhang, 1998], the complexity of a voting system is quantified on the basis of its topological entropy [Meyer and Brown, 1998], and the required simplicity of individuals that produce sufficiently complex system-level behavior is investigated [Delgado and Sole, 1997].

2.1.2 Cellular Automata

Another widely used technique to analyze particle systems is to represent the system and the underlying physical laws in a cellular automata model. Ulam and Von Neuman have already conceived cellular automata in the 1940s. The model provides a formal framework for an investigation of the behavior of complex, extended systems [von Neumann, 1966]. In the 1980s, Wolfram added substantially to the body of knowledge.

A cellular automata model is a regular n-dimensional grid of cells where each cell is a finite state machine. Usually, cellular automata models are considered in one, two, or three dimensions, permitting finite or infinite numbers of cells. The state of the system changes in time by changing the state of each automaton according to its local interaction rules. In most models time is discrete, the update occurs synchronously, and all automata share the same rule.

The interaction rule, also known as the transition function, determines the state of an automaton on the basis of its own previous state and the state of the cells in a surrounding neighborhood. A radius specifies the neighborhood of a cell. The rule maps every possible configuration of states in the neighborhood to a new state for the respective cell. Often, a rule table is used to specify the transition function.

Cellular automata models are applicable to a wide range of research topics. They are used in the study of general phenomenological aspects of the world, including communication, computation, construction, growth, reproduction, competition, and evolution [Margolus and Toffoli, 1987] [Burks, 1970] [Smith, 1969] [Perrier et al., 1996]. Since the late 1960s, Conway's „game of life“ [Gardener, 1970] [Gardener, 1971] fascinates researchers in Artificial Life (Section 2.1.4). The „game“ specifies one of the most well known rule sets for cellular automata. Later, the set of „game of life“ rules was shown to be computation-universal [Berlekamp et al., 1982]. In physics cellular automata provide discrete models for a branch of dynamical systems theory that studies the emergence of well-characterized collective phenomena such as ordering, turbulence, chaos, symmetry-breaking, fractality, etc. [Vichniac, 1984] [Bennett and Grinstein, 1985] [Wolfram, 1984] [Wolfram, 1983]. There, research departs from the equilibrium statistical physics (Section 2.1.1) and investigates dynamics outside static stability points. Finally, cellular automata models find their way into biological modeling as a review in [Ermentrout and Edelstein-Keshet, 1993] shows.

2.1.3 Population Biology and Ecological Modeling

Similar to equilibrium statistical physics (Section 2.1.1), population biology and ecological modeling is concerned with the large-scale „emergent“ processes when a large number of (relatively) simple entities interact with one another [Begon et al., 1996] [Hastings, 1997]. But, while in physics these entities are particles, in the related biological field members of one or more species are the individuals in the model. Hence, in


8

practically relevant systems the number of entities is much smaller than in physics.

The interactions among the separate entities in the system are an abstraction of the process of natural selection as it occurs in biological systems. Usually, processes like genetic reproduction, genotype-phenotype mapping, or inter and intra-species competition for resources are modeled. As in its counterpart in physics, population biology and ecological modeling focuses on the dynamics of the resulting ecosystem and its long-term behavior depending on the local interactions.

The results gained in population biology and ecological modeling are applicable to non-biological systems too. For instance, social issues like the emergence of language or culture, warfare, and economic competition are investigated [Epstein and Axtell, 1996] [Gabora, 1998]. Population models lend themselves to the research into the behavior of large complex systems with many interacting components [Hanski et al., 1996] [McFarland, 1994] [Nishimura and Ikegami, 1997] [Polls, 1998].

2.1.4 Artificial Life

Research into artificial life links biology with the field of computer science. But it also draws from physics, chemistry, economics, and philosophy. Langton defines artificial life research as follows:

„A field of study devoted to understanding life by attempting to abstract the fundamental dynamical principles underlying biological phenomena, and recreating these dynamics in other physical media, such as computers, making them accessible to new kinds of experimental manipulation and testing.“
-[Langton, 1992]-

Artificial life research has two major objectives. First, it seeks to understand the abstract functioning and especially the origin of terrestrial life. And second, it attempts to create artificial organisms that can meaningfully be called “alive“.

Formalizing and abstracting the mechanical processes underpinning terrestrial life serves the first objective. One fundamental process investigated here is the assembling of lipids into more complex structures such as vesicles and membranes [Deamer and Oro, 1980] [Edwards and Peng, 1998] [New and Pohorille, 1999]. On a more abstract level, the processes of self-replication [Breyer et al., 1998] [Smith, 1992] [von Neumann, 1966] and of functional self-organization [McMullin and Varela, 1999] are examined.

The second objective of artificial life research is less analytical and more creative. It takes terrestrial life as an inspiration and designs living systems. The design of an immune system for computers remains very close to the biological model. Such a system develops “antibodies“ that fight computer viruses, which many consider a life-form in its own right, more rapidly and more efficiently than other algorithms [Forrest et al., 1994] [Kephart, 1994] [Hofmeyr and Forrest, 1999]. The development of software through evolution [Koza, 1992] is a more abstract application of biological principles in systems design. Finally, the creation of artificial worlds inside a computer to study general forms of life (“Life-As-It-Could-Be“) serves both objectives since, up to now, life on Earth is the only real-world sampling point available to understand life.

Decentralized systems with many interacting individuals abound throughout the terrestrial biosphere and artificial life research investigates such systems too. One famous


9

example of a distributed artificial life system is the model of flocking behavior [Reynolds, 1987] as it is encountered in birds. The individual entity in the distributed system is called “Boid“. It represents a virtual bird with basic flight capabilities. The flock, the global system, is a collection of Boids in a simulated world.

Each Boid has a restricted perception of its local environment. It can only perceive nearby flock-mates or obstacles. Global perception, as provided by maps for instance, is not permitted. The behavior of each Boid as it moves through the virtual space is expressed by three simple rules:

Collision Avoidance (1).-Avoid collisions with nearby flock-mates or obstacles.

Velocity Matching (2).-Attempt to match velocity with nearby flock-mates.

Flock Centering (3).-Attempt to stay close to nearby flock-mates.

As an effect of the local activities of each Boid, the flock moves in a cohesive group that spontaneously splits into subgroups when encountering obstacles. After the obstacle is cleared, the subgroups join again. The observation of Boids has an analytical and a practical implication. Analytically, the fact that tuning the parameters of the behavior results in flight patterns analogue to different bird species indicates that similar rules dictate collective animal behavior too. As a practical consequence, photo-realistic imagery of swarms has been produced in computer animation. These animations have been used to model bat swarms for several movies already.

The flocking behavior demonstrated in the Boids gives rise to a new search heuristic in optimization. Particle swarm optimization [Kennedy and Eberhart, 1995] [Ozcan and Mohan, 1999] replaces the 3-dimensional computerized world the Boids “live“ in with the n-dimensional (continuous) space of solutions to an optimization problem. Thus, the current location of a Boid represents one solution. Similar to genetic search methods, a flock of Boids in a search space is a set of solutions currently examined.

The behavior of each Boid is extended by a fourth rule that probabilistically biases the individual towards better solutions (local gradient in search space). The cohesion of the flock, provided by the other three rules, ensures that local search (hill climbing) is tempered by more global information coming from nearby individuals. The probabilistic component in the local search guarantees that the whole search space is covered eventually by random walk. While the heuristic in traditional genetic search (outcome of genetic recombination) may select two good solutions from different ends of the search space, particle swarm optimization produces new solutions (next Boid position) dynamically guided by a number of neighbors [Eberhart and Shi, 1998].

Particle swarm optimization generally requires a continuous search space. The effectiveness of the heuristic depends on the settings of the parameters that specify the four individual behaviors. These parameters effectively select the “bird species“ modeled in Reynold's original flock of Boids. As each bird species has adapted its flocking behavior to its specific ecological niche, the particle swarm must be adapted to the respective search space. In [Shi and Eberhart, 1998] first steps towards parameter adaptation are taken.

2.1.5 Multi-Agent Systems

Historically, the behavior of the individual entity is often rather simple in systems explored in physics, biology, and even in artificial life. Only recently, more complex


10

individual behavior is considered. The “trajectory“ of research runs from simple to complex individual behavior.

On the other hand, artificial intelligence (AI) initially was primarily concerned with singular entities like expert systems. Research into distributed artificial intelligence (DAI) only set in when traditional AI tasks were implemented in parallel. Such implementations either parallelized the AI production system or the underlying programming language [Forgy, 1982] [Rich and Knight, 1991], or different modules with different tasks (e.g., reasoning, planning, scheduling) concurrently attempted to achieve a common goal [Huhns, 1987] [Iyer and Ghosh, 1995] [Lee et al., 1999].

The concern of DAI, especially of its sub-field “Distributed Problem Solving“ (DPS), is how to modularize a given task efficiently. DPS is defined as follows:

“Distributed Problem Solving considers how the work of solving a particular problem can be divided among the number of modules that cooperate at the level of dividing and sharing knowledge about the problem and developing a solution.“
-[Bond and Gasser, 1988]-

DPS solutions often involve a centralized controller that allocates tasks to the different modules and then processes the associated results. Since such architectures are often brittle, more recently there has been a move towards more autonomous modules and fewer restrictions in the interactions among the modules. But DAI still maintains the traditional AI concern, focusing on particular aspects of intelligence, such as reasoning, understanding, learning, etc.

The field of Multi-Agent Systems (MAS) research has its roots mainly in DAI. It is based on the idea that intelligence should emerge from the interactions among components without constructing it explicitly into them [Minsky, 1986] [Brooks, 1991b] [Brooks, 1991a] [Jennings et al., 1998]. Hence, multi-agent systems are similar to the distributed systems observed in physics or biology in the sense that multiple individuals (here: agents) interact and complex system-level behavior is observed. But, agents are traditionally much more complex than, for instance, particles or Boids. There has been a long discussion how to define an agent that never really came to a conclusion. A thorough review of the different definitions is presented in [Franklin and Graesser, 1997].

As the single agent may be a complex system in itself, MAS research has two major foci: the inner workings of each agent, and the interactions among agents [Bradshaw, 1997], [Sycara, 1998] [Jennings et al., 1998]. But, the final objective is to organize the agents to achieve some global task. Thus, several techniques are developed (e.g., coordination [Sen et al., 1994], negotiation [Kraus, 1997], coalition forming [Sandholm et al., 1998] [Sandholm and Lesser, 1995] [Zlotkin and Rosenschein, 1994], contracting [Andersson and Sandholm, 1998].

2.1.5.1 Design Methodology

MAS research is a field in computer science and hence it has a strong engineering aspect. Whereas equilibrium state physics, for instance, takes a system of interacting individuals and asks what are the emerging features of the system, MAS researchers are concerned with the inverse problem: given a specified global behavior, what individual behavior is required to achieve it. To solve the inverse problem, design methodologies for multi-agent systems are developed.


11

One example of a multi-agent design approach is presented in [Burmeister, 1996]. The approach is derived from the successful object-oriented system design, which dominates current software engineering. The agent-oriented design process results in three sub-models specifying the system: the agent model, the organizational model, and the cooperation model.

The agent model contains agents and their internal structure. To derive the agent model, first the agents and their environment are specified. Then for each agent its motivations, its behavior, and its knowledge are laid out.

The organizational model specifies the relationships among agents and agent types. These may be inheritance relations (among agents and agent types, and agent types and sub- or super-types), or relationships among agents based on their roles in organizations. These organizations may be means for structuring a complex system into subsystems (as done in some object-oriented techniques) or they may be used to model real organizations. The organizational model is constructed by identifying the roles in the respective scenarios, by building inheritance hierarchies, and, finally, by structuring roles into organizations.

The cooperation model describes the interaction or more specifically the cooperation among agents. It contains the “dynamics in the large“ only. The “dynamics in the small“ (i.e., the description of agent behavior) are part of the agent model. To design the cooperation model the cooperations and the cooperation partners are identified first. In a second step, the message types and the cooperation protocols are specified.

2.1.6 The Artificial Life Road to Artificial Intelligence

At the intersection of traditional multi-agent systems research, biology, and artificial life the so-called “Artificial Life Road to Artificial Intelligence“ [Steels, 1995] opens up. Here, researchers seek to apply concepts inspired by biological systems to the design of (intelligent) multi-agent systems. A similar approach is found in a related area of AI that researches artificial neural networks.

Very close to the biological model are computational ecologies [Huberman and Hogg, 1988]. Computational ecologies are related to the field of ecological modeling (Section 2.1.3). They are large distributed systems with independently acting individuals. But, the mathematics of the interaction model need not be derived directly from biological processes. Implementations of computational ecologies are often based on cellular automata instead of independently acting software entities.

Another approach that is more related to Reynold's model of flocking behavior (Section 2.1.4) explores active walker models. Physicists have initially pioneered these models [Batty, 1997] [Helbing et al., 1997a] [Helbing et al., 1997b]. Active walkers, which may be humans or simple physical objects, cross a field along trajectories. While they cross the field the walkers leave trails behind. The trajectory chosen by a walker optimizes its private utility function, which is influenced by several factors including in particular existing trails. The specific concern in active walker models is how to design the field (e.g., introducing obstacles or paths), so that some required trail patterns emerge, assuming that the internal utility function cannot be changed. A practical application of active walker models is the design of cement pathways that are actually followed by human walkers.

The “Physics-Agent-System Model“ [Shehory et al., 1999] is another adaptation of a


12

physical system to model the interaction and coordination in large fine-grained multi-agent systems. Here agents and goals that require agent coordination are modeled as particles in a (simulated) world. Each particle has its own mass and location and the particles that represent an agent also move with a direction and speed that changes over time. The mass of a goal particle relates to the importance of the goal whereas the mass of an agent particle matches the portion this agent may bring into the goal fulfillment. The movement of the agents results from gravitational forces among the particles and the coordinated goal fulfillment is triggered by the collision of agent and goal particles.

2.1.6.1 Swarm Intelligence

In recent years swarm intelligence has gained increasing popularity. Swarm intelligence is broadly defined as follows:

“Any attempt to design algorithms or distributed problem-solving devices inspired by the collective behavior of social insect colonies and other animal societies.“

-[Bonabeau et al., 1999]-

The approach is motivated by the realization that the rich behavior of social insect colonies arises not from the sophistication of any individual entity, but from the interaction among these entities. It has even been proposed that the more complex a society, the more simple the individual may be [Delgado and Sole, 1997].

Historically, early attempts to incorporate social animal mechanisms into systems design can be found in the work of Tselin and Rabin. Rabin [Cook and Racko, 1980] [Rabin, 1982] constructed moving automata that solve problems on graphs and lattices by interacting with the consequences of their previous actions. Tsetlin [Tsetlin, 1973] suggested that especially randomness, decentralization, indirect interactions, and self-organization are characteristics that make the swarm-based approach potentially powerful.

In general, the objective of swarm intelligence is to uncover the kinds of interactions among the entities that lead to some pre-specified system-level behavior. Furthermore, learning in large distributed systems is investigated.

2.1.6.1.1 Collective Intelligence

Collective Intelligence (COIN) [Wolpert and Tumer, 1999] can be seen as one instance of swarm intelligence that specifically focuses on the learning issue. Wolpert and Tumer define the following characteristics for a COIN: Many processors (agents) run concurrently, performing actions, which affect the behavior of other processors. Centralized and personalized communication or control is not permitted. Finally, there has to be a well-specified task set for the entire distributed system that typically requires extremizing some utility function.

To achieve system features like scalability, wide applicability, little hand tailoring, robustness, or adaptivity the single processors in COIN models run a local reinforcement learning mechanism. The local reinforcement learning mechanisms are fed by external “reward“ and “penalty“ signals. The learning approach does not require a “teacher“. It may be model-free and it operates on-line. On the basis of the COIN model a formal specification of the optimal agent design and initialization for a given problem is attempted.


13

2.1.6.1.2 Stigmergy

A fundamental principle in the emergence of coordinated system-level behavior from the local interactions of individuals is stigmergy. The French biologist Grassè already introduced the concept in the 1950s [Grassè, 1959] [Grassè, 1984] but only now it becomes a major issue in agent system design. Grassè discovered the principle when studying the behavior of social insects. The name stigmergy is a combination of the Greek words “stigma“ (outstanding sign) and “ergon“ (work), indicating that some activities of agents are triggered by external signs, which themselves may be generated by agent activity. Thus, simple activities may be coordinated by indirect communication and robust phenomena may emerge that remain virtually unchanged even under heavily changing circumstances.

Two general forms of stigmergy are identified. Sematectonic stigmergy involves a change in the physical characteristics of the environment. Termite nest building is an example of sematectonic stigmergy in multi-agent coordination. An individual observes a developing structure and adds to it. The second form is sign-based stigmergy. Here, some marker is deposited in the environment that makes no direct contribution to the task being fulfilled but influences subsequent task related behavior.

Stigmergy does not explain the detailed coordination mechanisms. But, for the inverse problem of designing a system to fulfill a global task, stigmergy provides a general concept that links individual and colony-level behavior. The advantages gained by applying stigmergy are simple agents, reduced communications, the incremental construction and improvement of solutions, and the flexibility of the system-level behavior in the face of disturbances.

Social ants exhibit both forms of stigmergy. Sematectonic stigmergy is observed, for instance, in the piling of dead ants. Ants fulfilling the piling task show the following probabilistic behavior:

Rule (1).-Move randomly over the field.

Rule (2).-If you find a dead ant at point x in the field and if you do not carry one already then pick it up with a probability Pup(f(x)).

Rule (3).-If you carry a dead ant then drop it with a probability Pdown(f(x)).

The probabilities Pup and Pdown depend on the density f(x) of dead ants in the vicinity of location x. An ant perceives the density by keeping a short-term memory of the number of dead ants encountered in its random walk. The higher the density of dead ants, the lower is Pup and the higher is Pdown.

An example of sign-based stigmergy is the behavior of ants when they collectively construct the shortest path from a food source to the nest [Beckers et al., 1992] [Goss et al., 1989]. It has been shown that in general the ants do not use any visual input in their activities [Hölldobler and Wilson, 1990] and, there is also no centralized reasoning. But still, the ants find their way even if introducing obstacles changes the landscape. The underlying mechanism of the adaptive optimization is shown in the following scenario. The figures used to illustrate the example are taken from [Dorigo, URL].

Figure 2.1. Straight Pheromone Trail


14

Figure 2.1 displays the initial scenario. The ants move on a straight path that is marked with pheromones. The path connects the food source with the nest. A pheromone is a specific chemical substance that is generated and perceived by the ants. It is the medium of indirect communication in the scenario. The ants on their way from the food source to the nest deposit a certain amount of pheromone while they walk and they probabilistically prefer to move into a direction where the pheromone trail is strongest.

Figure 2.2. Obstacle Introduced

When the existing trail is obstructed (Figure 2.2) the ants arriving at the obstacle face a random choice of going left or right. Without any pheromone information available the flow of ants splits roughly in half, going around the obstacle. The random choice explores both options (Figure 2.3).

Figure 2.3. Two Options are Explored

On the shorter path the ants arrive faster back at the original trail permitting a faster flow between the nest and the food source. Statistically, a higher rate of pheromone deposits on the shorter path than on the longer one results. Thus, taking evaporation of pheromones into account, the shorter path reaches higher pheromone strength, attracting more ants until all ants are recruited to the short path (Figure 2.4).

Figure 2.4. Shortest Path Dominates

The food foraging behavior of the ants is discussed in more detail in Section 3.1.4 where it serves as an example for naturally occurring self-organization.

2.1.6.1.3 Ant Colony Optimization

Ant colony optimization is a specific application of the swarm intelligence approach that seeks to adapt coordination mechanisms employed in social ant colonies to solve discrete optimization problems. The ant colony optimization meta-heuristic [Dorigo and Di Caro, 1999] [Dorigo et al., 1999] has its roots in the ant system presented originally in the Ph.D. thesis of Dorigo in 1992.


15

Ant systems are applied to the traveling salesman problem [Dorigo et al., 1996] [Colorni et al., 1993] [Dorigo and Gambardella, 1997] [Bullnheimer et al., 1999] and to the quadratic assignment problem [Maniezzo et al., 1994] [Taillard and Gambardella, 1997] [Maniezzo, 1998] [Gambardella et al., 1999] [Maniezzo and Colorni, 1999] [Stützle and Dorigo, 1999]. Recent extensions hybridize ant systems with Q-learning (Ant-Q) and incorporate local search.

Ant colony optimization is also successfully applied to dynamic real-world problems like routing and load balancing in circuit switched telecommunications networks [Schoonderwoerd et al., 1996] [Schoonderwoerd et al., 1997] and routing in packet switched telecommunications networks [Di Caro and Dorigo, 1998a] [Di Caro and Dorigo, 1998b] [Varela and Sinclair, 1999]. An application to connection management and diagnostics in communications networks is presented in [White and Pagurek, 1998] that explicitly operates on a generic „chemistry“ of pheromones.

The processing of local information in a shared physical environment and its incorporation into probabilistic decision making as demonstrated by the ants' pheromone-based coordination mechanisms also inspired a reactive chess-playing algorithm [Drogoul, 1993]. In the MARCH system individual game figure strength and material value is propagated to the threatened fields before a move. There these values combine locally to create a weighting of the different possible moves. The actual move is then selected probabilistically based on these weights. Even though this architecture does not make any use of the ants' swarming behavior it nevertheless achieves an acceptable playing performance.

2.1.6.1.4 Synthetic Ecosystems

According to the definition of swarm intelligence, the synthetic ecosystems approach [Parunak, 1997] [Parunak et al., 1998] applies swarm intelligence to the design of multi-agent systems. The main concern of research into synthetic ecosystems is to provide practical engineering guidelines to design systems of industrial strength.

In its practical application the synthetic ecosystems approach is not bound to apply the actual social animal coordination mechanisms to the problem at hand. Rather, the proposed design guidelines seek to capture the underlying logic of the biological and other complex systems. Examples for design guidelines are: Identify agents according to things, not functions, keep agents small, decentralize system control, support risky redundancy, enable agents to share information, and plan and execute concurrently.

These are all general design guidelines that are orthogonal to design methodologies as they are proposed in multi-agent systems research (Section 2.1.5). As a consequence, the three models proposed in [Burmeister, 1996], for instance, may still be constructed in the design phase. The design principles from synthetic ecosystems research apply to the intermediate steps that lead to the models.

2.1.7 General Concepts

Two concepts are often invoked in discussions of global features of distributed systems when appealing to the intuition of the reader. Many interesting features are said to be “emergent“ or “self-organized“.


16

2.1.7.1 Emergence

There is still an ongoing discussion in the scientific community, if emergence really exists or if it is only a trick of perception. The discussion is not restricted to computer science. Rather, it has been a philosophical question for at least one and a half centuries [Mill, 1843]. One of the more successful attempts to define the concept is to be found in “The Dictionary of Philosophy of Mind“:

“Properties of a complex physical system are emergent just in case they are neither (i) properties had by any parts of the system taken in isolation nor (ii) resultant of a mere summation of properties of parts of the system.“
-[Eliasmith, URL]-

This definition is a rather general, since it does not explain where the emergent properties of the systems may come from. In the exploration of distributed systems of locally interacting components the interactions are seen as the source of emergent properties. But it is also important that the local individuals do not perceive the global property. There are different levels of perception in the system. One set of properties is perceived and handled at the level of the individuals (e.g., velocity of a particle), while another set of properties dominates the system level (e.g., temperature of a particle system).

For the purpose of this thesis, the separation into levels of perception should be sufficient to capture the essence of emergence. In the design of a distributed system that fulfills some specified requirements, the designer has to know how a specific system-level property is influenced by local knowledge and interaction patterns. In the specification of the system it must be clear what the current context is. There are the definitions of the local behavior of the individuals and there are system-level specifications. The local part may not incorporate global properties and vice versa. Only when arguing the translation from local to global features (emergence) both property sets are discussed.

2.1.7.2 Self-Organization

The concept of self-organization originally emerged in the context of physics and chemistry [Haken, 1983] [Nicolis and Prigogine, 1977] to describe the emergence of macroscopic patterns out of processes and interactions defined at the microscopic level. More recently, self-organization is also invoked in reference to colonies of social insects where wide ranges of collective phenomena are self-organized [Deneubourg et al., 1989]. The advantage of interpreting complex colony-level behavior on the basis of self-organization is that it does not require the invocation of complex behavior at the individual level.

Self-organization is seen as a set of dynamical mechanisms in a system where structures appear at system levels that are not externally imposed. As it is already discussed in the context of emergence, self-organization requires that the local interactions of the individuals do not reference to these global structures.

For a system to show self-organized properties, the following ingredients are proposed [Nicolis and Prigogine, 1987]. It is still subject of research to formally validate the items in the list.

Besides these (assumed) requirements for self-organized properties in a system, the following indicators of self-organization should be followed [Bonabeau et al., 1999]:

2.1.8 Summary

Synthetic ecosystems research is the application of swarm intelligence to the design of multi-agent systems. The primary focus lies on the problem of designing individual agent behavior to achieve a pre-specified system level behavior. This thesis provides designers of such systems with a set of guidelines supporting a systematic engineering of stable self-organized behavior. These guidelines seek to capture the underlying (bio-)logic of interaction mechanisms in large-scale natural agent systems like social insect colonies and integrate it into the software engineering process.

Besides supporting the design of swarm-intelligent systems for industrial applications, the formal evaluation of the global behavior of these systems is a major issue in research. This thesis sets up a foundation for the formal description of stigmergetic agent interactions and their analysis. On the basis of such a formal model emerging patterns of system-level behavior may be predicted and the fulfillment of the global requirements may be evaluated. Starting out with formal models of multi-agent behavior, future research may be able to integrate methodologies adapted from statistical physics or population biology to further improve the evaluation process.


18

Figure 2.5. “Trajectories“ of Research into Distributed Systems

The integrative approach followed in this thesis is illustrated in Figure 2.5. Traditional research into multi-agent systems has focused mainly on the systems design aspect, while branches in natural sciences like population biology seek to analyze emerging global behavior. Industrial strength system engineering eventually requires both, design and analysis of distributed systems of interacting individuals.

2.2 Manufacturing Control

The design and formal evaluation of synthetic ecosystems is exemplified in this thesis on the basis of a manufacturing control application. The following review presents manufacturing control as part of the production processes and characterizes manufacturing systems as they are encountered today. In a second step, requirements on tomorrow's control systems are derived from the current change in the environment businesses operate in. As a consequence of these changes, distributed manufacturing control systems that self-organize dynamically in a bottom-up fashion have to be developed. The last step of the review classifies systems following such an approach as they are proposed in research.

2.2.1 Manufacturing Control in Context

2.2.1.1 Production Processes

Activities in production are differentiated into the physical production and manipulation of products on the one hand, and the management and control of these physical activities on the other hand [Bongaerts, 1998]. According to its perspective, management and control is further divided into strategic (long-term), tactical (mid-term), and operational (short-term) activities.

Strategic production management determines the set of products of the company. It considers the markets and the expectations of potential customers. Long-term management also designs the manufacturing system for the respective products, including a master schedule.


19

Tactical production management takes the master schedule and generates detailed production plans, which comprise release and due dates for assemblies, subassemblies and components. In make-to-order production, mid-term management operates on real customer orders, while make-to-stock production uses predicted orders. Today's planning processes are usually supported by MRP systems (Material Requirements Planning) or MRP-II systems (Manufacturing Resource Planning).

Operational production management handles the manufacturing processes on the shop floor. The schedule generated by the mid-term planning process is translated into detailed plans that specify the appropriate resource for every task and the optimal sequence of all tasks on every resource. Short-term management explicitly coordinates the machines, workers, tools, and other resources, usually considering a period spanning a day up to a few weeks.

Short-term production management does not take the current situation into account when it allocates the resources. In most of today's production systems it is the task of the manufacturing control system to implement the detailed short-term schedule generated by the operational production management. During the implementation immediate reactions to disturbances are required, which often invalidate the schedule.

Figure 2.6. Production Management and Control

Figure 2.6 illustrates the position of the manufacturing control process in the traditional hierarchy of production management and control. In literature, manufacturing control systems are also found under the name “manufacturing execution systems“ (MES).

Most of today's automated systems that support the production management process mirror the hierarchical structure of the processes. The hierarchical system architecture reduces the complexity of the development and makes them easier to change compared to monolithical systems.

Decisions in the planning phase are taken in a top down fashion. In mid-term planning real or assumed customer orders are given release dates and due dates, which in turn determine the resource allocation specified in short-term scheduling. Finally, the optimized schedule is handed over to the manufacturing control system for implementation. In case of disturbances during schedule execution the planning process may have to restart at some point because the schedule became infeasible. The hierarchical approach is rigid, modifications are costly, and intelligent reaction to disturbances during execution is not


20

considered.

2.2.1.2 Characterizing Manufacturing Systems

There are several dimensions by which manufacturing systems may be characterized. The type of the material flow distinguishes continuous and discrete manufacturing systems. Mass production, large batch manufacturing, and one-of-a-kind manufacturing are identified when the volume of production is considered.

The layout is a third dimension that differentiates manufacturing systems. In discrete manufacturing single machine models, identical processors models, flow shops, job shops, and recently, flexible flow shops are encountered. In single machine models there is only one machine fulfilling all operations. Identical processors models assume multiple but identical machines, whereas in flow shops different machines are permitted. But then, flow shop production requires each operation to be executed on a specific machine and the sequence of all operations of an order is fixed. Additionally, the sequence of orders visiting machines is fixed too. The latter requirement does not hold for job shops. In job shops orders might overtake each other during execution.

Flexible flow shops are presumed to retain the efficiency and transparency of a flow line, combining it with the reactivity and flexibility of a job shop. Flexible flow shops increase flexibility in machines selection, operation sequencing, and routing in high-volume production. An important characteristic of the control of flexible flow shops is that of all feasible routes through the system only a small subset is preferable in terms of the production goals. The composition of the subset changes dynamically when disturbances occur and it is not always obvious what routing to choose in a given situation.

2.2.2 Requirements of Tomorrow‘s Manufacturing Control

The subsequent argument follows a discussion in [Bussmann and McFarlane, 1999]. It is illustrated in Figure 2.7, which links (marked squares) the changing business environment with the requirements of modern manufacturing control systems.

Driven by globalization and the growing surplus of industrial capacity, more and more businesses are faced with a change from a supplier's market to a customer's market. The trend empowers the customers to demand, for instance, constant product innovation, low-cost customization, and better service. As a consequence, companies have to shorten product life cycles, reduce time-to-market, and increase product variety. At the same time the quality of the products has to be maintained and the investment costs must be reduced to remain competitive.

Future manufacturing systems are faced with an increasing complexity in processes and products, they have to cope with continual change, and the costs in manufacturing have to go down. In detail, products will have more features and more variants combined with a shorter time-to-market, a decreased life cycle, and lower investment per product. Additionally, the volume of a product manufactured and the mix of variants requested from the manufacturing system varies strongly over time.

Such a drastic change in the external conditions of production must be answered by changes in the manufacturing system. To handle the process complexity, manufacturing systems must be restructured in an intuitive and self-explaining way and they must


21

guarantee a well-defined behavior in a wide range of situations. Furthermore, flexibility and reconfigurability of manufacturing units and processes must increase to support re-use and scalability of the system. Finally, the manufacturing process must be robust.

Figure 2.7. Linking Business Trends with Control Requirements

A new type of manufacturing system also requires a new approach to manufacturing control. The architecture of the control system must be decentralized on the basis of a product, order, and resource partition. The resulting interactions in the decentralized system should be abstract, generalized, and flexible. The control system as a whole has to take reactive and proactive actions concurrently in a self-organized manner.

2.2.3 Distributed Architectures for Manufacturing Control

2.2.3.1 Holonic Systems

Distributed systems of interacting individuals for production management and control are considered by the academic community and also by industry. Initially, research into distributed architectures for the manufacturing domain developed separately in production research and in the multi-agent systems community (Section 2.1.5). Only recently, these two strands recently grew together.

Following the specific requirements of modern manufacturing systems (Section 2.2.2), Suda [Suda, 1989] proposed a “holonic“ model for designing and operating elements comprising manufacturing processes. The philosopher Arthur Koestler [Koestler, 1967] coined the term “holon“ based on the observation that most entities encountered in nature are also part of other (higher-level) entities. Hence, a “holon“ is a whole individual (Greek: “holos“) and a part (Greek suffix “on“) at the same time.

A holon in the manufacturing domain is defined as “an autonomous and cooperative building block of a manufacturing system for transforming, transporting, storing and/or validating information and physical objects“ [Christensen, 1994]. A manufacturing holon comprises a control part and an optional physical processing part. Multiple holons may dynamically aggregate into a single (higher-level) holon.


22

A distributed system of interacting holons is called a “holarchy“. The holons in the system may cooperate to achieve a goal or objective. Holarchies are created and dissolved dynamically. The application of the holonic concept to the manufacturing domain is expected to yield systems of autonomous, cooperating entities that self-organize to achieve the current production goals. Such systems meet the requirements of tomorrow's manufacturing control systems.

Bussman argues in [Bussmann, 1998] that MAS research may provide the technology to realize the information processing part of a holon. In that sense, holarchies are multi-agent systems with specific structures and interactions; while holons are agents in the manufacturing context that may have physical abilities and that may aggregate. This thesis focuses on information processing and hence the term “agent“ is used predominantly even in a manufacturing context.

2.2.3.2 Dimensions of Control Architectures

Agent-based application architectures may be characterized in the following three dimensions:

Individuals and Types.-What becomes an agent?

Interaction Structure.-Who talks to whom?

Interaction Contents.-What is said and how is it said?

These dimensions are not independent. A design decision in the identification of individuals, for instance, influences the available interaction structures and the type of contents exchanged in the interactions, and vice versa. In accordance to these three dimensions, a classification of agent architectures for manufacturing control is presented.

2.2.3.2.1 Individuals and Types

When identifying the individuals in an application, the partition into agents can be entity-oriented or function-oriented. Most manufacturing control architectures proposed recently primarily follow the entity-oriented approach. Often, the resulting architectures in discrete manufacturing applications may be interpreted in terms of the PROSA reference architecture. This is the case, for instance, in the WEST architecture [Bussmann and Schild, 2000].

PROSA is a holonic reference architecture for manufacturing systems developed at K.U.Leuven [Van Brussel et al., 1998] [Wyns, 1999]. As reference architecture it specifies what kinds of holons should comprise the system, what the general responsibilities of these holons are, and what the structure of the interactions in the holarchy is. PROSA may serve as a starting point for designing specific manufacturing applications.

PROSA identifies three kinds of basic holons: Product-holons, Resource-holons, and Order-holons. A Product-holon encapsulates the process and product knowledge required for a correct manufacturing of the product with sufficient quality. It provides information to the other holons (e.g., product life-cycle, user requirements, design, process plan) without being able to take any physical actions itself.

The physical part of a Resource-holon is a production resource, and the control of the resource comprises the information processing part. Resource-holons provide production


23

capacity and functionality to other holons. They have the complete knowledge and abilities to organize, use, and control their production resource.

An Order-holon represents a manufacturing order. It has to make sure that all required tasks are performed correctly and in time.

The operation of the basic holons may be assisted by Staff-holons. These holons are intended to offer functionality that is typically found in higher levels of hierarchical control systems. But in difference to the hierarchical approach, Staff-holons only have an advisory role. The actual decisions are taken by the basic holons. The rationale behind the introduction of Staff-holons is to decouple the robustness and agility provided by the basic holons from optimization functions fulfilled by Staff-holons.

The PROSA architecture is used for instance to identify agents in the manufacturing control system developed in the ESPRIT LTR project MASCADA [Peeters et al., 1999]. The entities comprising the lowest level of the architecture in the example application of this thesis (Chapter 4) are also specified according to PROSA.

In domains other than manufacturing control, a functional identification of agents in an application is an alternative to entity-oriented partitioning. The RETSINA agent architecture [Sycara et al., 1996], for instance, comprises three abstract types of agents: interface agents, task agents, and information agents. In contrast with the entity-based agent types in PROSA, these agent types represent functions to be performed by the system.

An example for the function-oriented partition of an application on the basis of the RETSINA architecture is the portfolio management system WARREN [Sycara et al., 1995]. Task agents in WARREN are the “Fundamental Analysis Agent“, the “Technical Analysis Agent“, or the “Breaking News Agent“. Each agent represents a particular function of the system. New functions are added or removed by changing the agent structure.

Applying the function-based partitioning to manufacturing control applications, functions like mid-term planning, short-term scheduling, transportation, processing, or quality checking may be identified with agents. Such an approach tends to result in hierarchical systems that are similar to the traditional ones (Section 2.2.1) except that there may be more autonomy in the modules.

2.2.3.2.2 Interaction Structure

The identification of the agents in a distributed manufacturing control architecture influences the resulting structure of the interactions. Following [Parunak et al., 1997], there exist four different ways of structuring agent interaction in manufacturing architectures.

The simplest form of interaction configuration is given in broadcast communication. Examples for broadcast communication in manufacturing control systems are force fields as applied in [Vaario and Ueda, 1998], or the undirected communications in LMS [Fordyce and Sullivan, 1994] or A-Teams [Lee et al., 1996] [Akkiraju et al., 1998]. The MASCADA application architecture [Peeters et al., 1999] combines broadcast structures (pheromone fields) with direct interactions along the process flow.

Interactions structured along the information and material flow are predominant where the agents map to entities in the manufacturing system. The AARIA system [Parunak et al., 1997] and the WEST system [Bussmann and Schild, 2000] are examples for process flow


24

communication paths in manufacturing control systems, while ISCM [Fox et al., 1993], for instance, follows the same approach in a business process model.

Process flow structured interactions often employ the contract net protocol [Shaw and Whinston, 1988]. It specifies a sequence of auction announcement, bidding, bid evaluation, and winner announcement. In control systems that are partitioned into manufacturing entities, either the job or the resource may announce (host) an auction. There are resource driven auctions where a resource starts the protocol when it is idle and available (e.g., [Ferguson et al., 1988] [Shaw and Whinston, 1988] [Ramaswamy, 1995] [Dewan and Joshi, 1998]). The announcement is answered by interested jobs, which submit bids for time slots on the resource. Other systems follow a job-driven approach (e.g., [Malone et al., 1983] [Upton, 1992] [Brueckner, 1997] [Bussmann and Schild, 2000]), and there are mixed approaches where jobs and resources host auctions depending on the current load of the system.

Manufacturing control systems that follow a hierarchical approach in the identification of their components (e.g., YAMS [Parunak, 1987], BOSS [Hynynen, 1989] display interaction structures that are hierarchical too. In such a system constraints are communicated top down from higher-level agents to lower-level ones. At the same time status information is sent up from lower levels in the hierarchy.

Mediator-based approaches promote a hybrid of hierarchical and process flow configuration (e.g., [Burke and Prosser, 1994] [Butler and Ohtsubo, 1992] [Interrante and Goldsmith, 1998] [Shen and Norrie, 1998]). These systems identify their primary set of agents according to the entities in the domain. Then, the agents are split into groups and a “mediator“ agent joins each group. It is the task of the mediator to oversee its group of agents and to resolve conflicts arising in the interactions of the agents in the group. These mediators often employ centralized conflict resolution mechanisms.

The direct interactions specified in the manufacturing control system presented in this thesis (Chapter 4) are predominantly structured along the process flow, while the hierarchical information exchange is based on stigmergy and may be identified as broadcast communication.

2.2.3.2.3 Interaction Contents

Agent interactions in manufacturing control systems are also differentiated according to the contents of the messages. In general, there are symbolic and numerical contents.

Symbolic messages have their roots in classical artificial intelligence research. They often convey complex status and constraint information, which in turn requires considerable intelligence on the side of the receiver to parse and process such a message sufficiently. As a consequence, the more complex the contents of the messages, the more complex the agents tend to be (e.g., the agents in FAKOS [Baumgärtel, 1999]. But there are also exceptions to such a tendency. The WEST system [Bussmann and Schild, 2000], for instance, requires only limited reasoning capabilities in the individual agents.

Numerical messages, on the other hand, do not require complex agent reasoning except for very specific tasks. Natural or economic models often inspire agent systems interacting on the basis of numerical messages. In numerical message exchange balanced and unbalanced exchanges are considered.

Balanced numerical interactions are exemplified in market systems. These systems conserve a currency in its internal trades. The “money“ an agent earns is the same amount


25

another agent has to spend. Examples of market-based systems in manufacturing control are found in [Baker, 1996] [Lin and Solberg, 1992] [Upton et al., 1991] [Walsh et al., 1998], [Odell and Greenstein, 1999] or [Parunak et al., 1997].

In unbalanced numerical interactions, the messages are independent of the agents. As a consequence more than one agent may read the communicated information since the message itself is not erased when it is received. Force fields [Vaario and Ueda, 1998], posted numerical priorities on a blackboard [Sikora and Shaw, 1997], or pheromone fields [Parunak and Brueckner, 2000] are examples for such interaction contents.

The manufacturing control system presented in this thesis combines unbalanced numerical interactions (via pheromone fields) and simple symbolic interactions along the process flow.

2.2.4 Summary

Bussmann and McFarlane present the following vision of holonic manufacturing control:
“In the beginning, a holonic manufacturing system only consists of a set of unorganized resource holons which form a manufacturing holon. Upon arrival of an order, however, the manufacturing holon creates an order holon which starts to negotiate with resource holons on the provision of certain manufacturing operations. During the negotiation process, the order holon demands specific properties of the operation, such as high quality or high throughput, while the resource holons try to maximize their utilization. At the end of the negotiation, the resource holons move to form the agreed manufacturing line and the order holon initiates the creation of work piece holons.
The work piece holons enter the manufacturing holarchy (e.g., from the stock) and immediately bargain for resources in order to get processed. Each work piece holon does so individually and focuses on the next operation(s). Once these operations have been performed at a resource, the work piece re-initiates the bargaining with the remaining (next) operations. The overall organization of the resource holarchy - initially or subsequently negotiated between order and resource holons - assures that the work piece load is efficiently distributed over the available resources in order to achieve the global goals of this holarchy.
In case of a disturbance, the affected resource holon removes itself from the resource holarchy and goes to a repair booth. The remaining resource holons re-organize themselves in order to account for the capacity loss. From the point of view of the work piece holons, the processing continues as usually, only with less resource holons with which it may bargain. After repair, the resource holon tries to join the resource holarchy again.
At the end of the order processing, the order holon is removed and the resource holarchy dissolves into the resource holons which then try to participate in new order holarchies.“
-[Bussmann and McFarlane, 1999]-

Following the holonic vision, this thesis demonstrates the design and evaluation of a complex stigmergetic synthetic ecosystem in the example of a manufacturing control system. The spontaneous self-organization of agents in the processing of an order to the


26

system is coordinated in sign-based stigmergy where the signs are pheromones managed by an extension to the software run-time environment of the agents - the pheromone infrastructure.

The presented manufacturing control system goes beyond the holonic vision. The emerging patterns in the material flow are observed by a higher-level advisory system, which considers the manufacturing process under global performance goals. On the basis of the observation the self-organized processes on the entity-level are influenced. The presented application architecture explicitly incorporates emerging system features.


© Die inhaltliche Zusammenstellung und Aufmachung dieser Publikation sowie die elektronische Verarbeitung sind urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung. Das gilt insbesondere für die Vervielfältigung, die Bearbeitung und Einspeicherung und Verarbeitung in elektronische Systeme.

DiML DTD Version 2.0
Zertifizierter Dokumentenserver
der Humboldt-Universität zu Berlin
HTML - Version erstellt am:
Fri Jun 15 12:30:34 2001