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

27

Chapter 3. Adopting Nature‘s Principles

Chapter 3 first states a number of guidelines for the design of synthetic ecosystems. On the basis of these guidelines and the observation of coordination mechanisms in insect colonies, an extension to traditional agent runtime environments, the pheromone infrastructure, is introduced. In the remainder of the chapter the pheromone infrastructure is formally modeled and an agent-oriented implementation is specified.

3.1 Synthetic Ecosystems in Manufacturing Control

The synthetic ecosystems (SE) approach proposes design principles applying to the design of agents and of the architecture of the agent system as a whole, and it suggests principles for the interaction design. The distinction is not a “clear“ one, but for each principle the primary focus may be identified.

In the following each principle is stated, motivated, and explained in its effects. Where applicable, consequences for the design of agent-based manufacturing control systems are discussed. Then, returning to the emergent food foraging behavior of an ant colony, the application of the principles in the “design“ of a natural agent system is shown. Finally, Section 3.1.5 describes a generic software infrastructure for artificial agents that supports the application of the design principles in the development of self-organizing multi-agent coordination.

The design principles have several sources. Some principles are already suggested in [Kelly, 1994] or [Parunak, 1997]. Others occur in a wide variety of complex systems that are examined in [Flake, 1999], [Kauffman, 1993], or [Bonabeau et al., 1999]. Finally, there are design principles that are added to the list simply because they represent sensible approaches to the design of complex software systems for real-world applications.

3.1.1 Single-Agent Principles

Things, not Functions (SE-Principle 1).-Identify agents on the basis of existing physical entities, rather than based on functions performed.

The agent system is assumed to directly control parts of the physical world. If the agents are identified according to distinct physical entities, the responsibilities remain well defined and knowledge and skills are encapsulated. Furthermore, when agents are mapped to real-world entities, the agent interactions may be adopted from their real-world counterparts. The physical world provides the relevant trigger-events, advancing agent interactions. A similar approach is promoted in object-oriented design.

Modeling agents on the basis of physical objects is intuitive. Changes in the composition of the controlled system are easily handled by changing the composition of the agent system. But automatic re-configuration mechanisms are still required.

In a manufacturing control environment, physical entities that could be mapped to agents are, for instance, workpieces, machines, tools, workforce, or transport elements. What granularity is finally chosen for the agent model primarily depends on the applied


28

control mechanisms.

Functions are only mapped to agents wherever legacy systems or watchdogs are part of the resulting control system. Legacy systems in manufacturing are often encountered in MRP(-II) or quality management systems.

Small Agents (SE-Principle 2).-Keep agents of a synthetic ecosystem “small“. The effort in communication and computation to execute an agent in a runtime environment must be small compared to the execution of the multi-agent application. Furthermore, there must be only a small impact from the activities of an agent on the state of the whole system.

Modeling a system on the basis of small agents has several advantages. Small agents are easy to implement, to debug, to understand, and to change. A software system made up of many small agents of several types is easier to implement and stabilize than a system made up of just some complex agents. With clear-cut responsibilities of an agent requiring the repeated application of only some agent skills, the challenge of engineering the agent itself is small.

A system of many small agents may easily express a wide range of very complex behavioral patterns. Programming all these patterns into one central entity requires a larger effort in implementation, debugging, and maintenance. Thus, the state-space covered by a system with an equal effort in implementation, stabilization, and maintenance is much larger for systems made up of small agents.

In general, if an agent is small in its impact on the whole system then its failure should also have a small impact only. But, while a single agent may fail without major consequences for the system, an error in the software implementation of an agent type still is critical because there are potentially many agents carrying the error.

Keeping agents small is also achieved through a restricted life cycle for each agent. Thus, aggregation of minor faults into a major one in the state of an agent over time may be avoided. The systematic death of agents is also a way to provide forgetting in the system (SE-Principle 16).

Modeling agent systems for manufacturing control based on small agents obviously influences the granularity of the model. For instance, instead of modeling whole manufacturing cells as one agent, a cell may be controlled by an ecology of agents, one for each part of the cell. The level of abstraction gives another important influence on the granularity, in which the control system operates. The focus may be on separate workpieces or on aggregated material flows, for instance.

Diversity, Heterogeneity (SE-Principle 3).-Have many agents of different types (diversity) and introduce slight variations within the agents of one type (heterogeneity) either sequentially (generations) or in parallel (families).

Diversity in multi-agent systems supports the notion of small agents. With each agent being small, there have to be different agent types with different responsibilities, skills, and knowledge. Together, agents of different types perform complex tasks in a coordinated manner.

Heterogeneity, on the other hand, enables the system to try out different approaches in solving the same problem. Heterogeneous agent types are more adaptive than homogeneous ones. Providing that effective use of heterogeneity is made, the resulting system behavior may maintain behavioral patterns to fulfill its tasks in a changing


29

environment.

Heterogeneity always poses a certain risk to the system. When trying out another approach to a problem, it is not guaranteed that the solution found is an optimal one. Not even feasibility is guaranteed in all cases. A sub-optimal resource usage results. Hence, the system has to trade off exploitation of known solutions against exploration for new solutions. The level of risk taken is another factor differentiating the agents.

Redundancy (SE-Principle 4).-Introduce redundant elements in the synthetic ecosystem either by tackling the same problem in parallel by multiple agents or by enabling the agents to take up tasks, other agents have not been able to finish for some reason.

Having redundant elements in the system is advantageous for the stability of the system. If an agent fails, then the system does not have to break down as a whole. Instead other solutions are instantly available or other agents pick up the tasks of the lost agent automatically.

Redundancy also requires additional resources. Either, there are more agents operating than minimally required. Or, the effort in the design of the agents is increased. Again the need for backup in case of local breakdowns has to be balanced against the costs for the additional resources.

3.1.2 System-Architecture Principles

Decentralization (SE-Principle 5).-Decentralize the synthetic ecosystem consequently and design its structure inherently dynamic. The agents have to explore the system by themselves, encountering other agents as source of information or services. Centralized services provided by the environment or by specialized agents are not permitted.

Decentralization is a major principle in the agent-oriented approach in general. But many applications still retain central elements in their structure. The need for a global White Pages (WP) service is often an indicator for structural centralization. There is someone who needs to know all agents.

Consequent decentralization prevents the occurrence of bottlenecks in computation or communication when the system is scaled up. The multi-agent system remains truly open since each agent has to operate as if it just had joined in. Teams are dynamically formed to fulfill arising tasks, and when a task is fulfilled the team falls apart.

To enforce decentralization, a global WP service should be avoided. Agents should learn about potential partners for interaction from other agents only. References to agents are kept only as long as they are actually used in an interaction. Keeping stale references is a risk to the stability of the system, since agents may join in or leave the system at any time.

Even strictly local WP service is permissable along the scaled dimension only. In manufacturing control applications such a dimension may be the physical space. All agents that are located in a spatial structure may be listed in local White Pages. A local WP service comprises references to agents that are all located in the same local area.

When the system is scaled up, the space covered by the system is extended. With only local WP services available, the number of agents in existing local WP is not increased.


30

Rather, new WP clusters for the new space are created.

Modularity (SE-Principle 6).-Grow a synthetic ecosystem by adding parts, with each part encapsulating some functionality provided by an ecology of agents. The system is designed, set up, tested, and started in a given sequence of added parts, starting with a minimal configuration.

Ideally the parts of the system are strictly layered. Each layer extends the functionality of the layer beneath it. Every step in the design adds another layer to the system from bottom up.

There is a number of parts forming the core of the system - the minimal configuration. The core has to guarantee the basic operation. All hard constraints set to the operation of the system have to be fulfilled by the core already.

Additional parts of the SE may be added or removed dynamically, minding the interdependencies among the parts. In a layered structure, for instance, higher layers generally require the presence of some or all layers beneath for correct operation. Each additional part refines and optimizes the operation of the whole system. While the hard constraints have to be fulfilled in any valid configuration, specific additional parts fulfill optional requirements or goals.

In manufacturing control applications the core parts have to realize the manufacturing of products. They guarantee that every workpiece is processed correctly. No workpieces are ever taken to machines, to which they must not go. Only the required processing steps are performed and the processing sequence, which is constrained by the process graph of a product, is minded.

Parts extending the core behavior could realize fairness in processing or avoidance of deadlocks in transport. The performance of the manufacturing process is improved according to the production goals or additional services are provided to the operators of the system.

Parallelism (SE-Principle 7).-Solve multiple problems in parallel as they arise in different groups or teams of agents that are created dynamically. Enable the agents to participate in several teams concurrently, internally intertwining their interactions within the different teams.

The agents are very specialized in their skills. There is almost never an agent able to perform a task alone. In a consequently decentralized and asynchronous system, tasks arise in parallel. Hence, there must be more than one team operating at the same time. Agents with specific skills or knowledge may join multiple teams. These agents have to be able to manage multiple interactions in parallel.

Parallelism occurs in manufacturing control systems. Different workpieces have to be processed at different processing resources at the same time. Agents controlling these resources solve these tasks in parallel. Depending on the design of the agent system, there could be agents providing process information about the manufacturing of a product. These information providers then possibly join multiple teams in parallel.

Bottom Up Control (SE-Principle 8).-Control the physical environment from bottom up through the interactions and decisions of a multitude of agents. There must be no single entity, to which control can be pinpointed. With many (and small) agents wielding control of the environment, emergent features should dominate the design of the system.


31

Control emerging from bottom up is another consequence resulting from strict decentralization. In a synthetic ecosystem there are some agents that are most closely linked to the physical environment. These agents have the primary control of the physical entities. Since the agents are identified according to things, not functions, there is no centralized control of the environment. Instead, the global control emerges from the local activities of the agents.

Other agents, conceptionally farther away from the physical world, influence the primary controllers. The emerging control pattern changes. With each component added to the system, the complexity of the resulting behavior controlling the physical world grows.

A single agent does not have much impact on the operation of the system. The design of the behavior of the agents of a specific type defines the global behavior. As a consequence of the multiplicity of the agents and their repeated actions and interactions small changes in the specification of an agent type might result in the emergence of completely different system-level behavior.

3.1.3 Interaction Principles

Locality (SE-Principle 9).-Restrict the sensor input and the direct effect of actions of an agent to its local environment. No agent must have access to all information currently available. No agent may affect major segments of the controlled physical world or interact directly with agents outside its local environment.

Along with the principle of keeping agents small, remaining local is the most important principle in the design of a SE. It is introduced on the basis of results gained in research of complex dynamical systems. Examining random Boolean networks [Kauffman, 1993] for instance, it was concluded that the connectedness of the local entities strongly influences the emerging global behavior. If too many agents influence other agents, then ordered system-level behavior is hard to achieve. On the other hand, the available system behavior is strongly reduced if there are too less influences.

To reduce the connected-ness of the agents in the SE, each agent only perceives and influences a small subset of the overall system. If there is a spatial structure imposed on the agent system, the access of an agent is reduced to its local neighborhood. The restriction goes hand-in-hand with the restriction of White Pages services to only local ones. The availability of only local WP services effectively disables any system-wide communication in dynamically structured agent systems.

In manufacturing control applications, locality enforces local team formation linked to the arising tasks. Transport is affected even more by the design principle. If the locality restriction is observed, then the routing of workpieces cannot be handled by a global transport system. Rather, subsequent local routing steps on the basis of locally available information only should be taken.

Additionally, process information for the manufacturing of products should not be globally available. It must be localized specific to the respective section of the manufacturing system.

Indirect Communication (SE-Principle 10).-Wherever feasible, decouple agents in their communications, transferring information through a shared environment instead of directly passing messages.


32

Message-based exchange of data among agents is one way to provide information required in the decision processes. Another one is to transfer data indirectly through the environment of the agents.

Direct agent-to-agent communication requires the partners in the exchange to synchronize. One partner requests information and the other partner now is forced to handle the request, regardless the current priorities of the agent. The requesting agent is forced to wait until the provider finally has come up with the data. If the agents operate on different time scales, then the whole exchange is extremely difficult to handle, especially when the provider of information is the slower one.

Another disadvantage of direct agent-to-agent communication is the effort required to stabilize such interactions in the face of possible agent-breakdowns. Complex transaction mechanisms have been developed to make sure the data is really transferred, and backtracking mechanisms allow resetting an interaction in case one of the partners has broken down.

Finally, aggregation of data from many sources for the use of multiple agents (many-to-many communication) takes more effort using direct interactions. Either, there would have to be a specific service provider aggregating the data, and each recipient would have to request the result of the aggregation from the provider. Or, the recipients do the aggregation on their own.

Indirect communication requires an environment jointly accessible by all potential senders and receivers. It must be possible to store and retrieve data in such an environment. The provider of information stores the data it has generated in the environment. The data is picked up by anyone requiring it. Stigmergy (Section 2.1.6) is based on indirect communication.

Indirect transfer of data requires no explicit synchronization. The agent that needs information only has to wait if there is no data generated yet. Otherwise it just reads it from the environment. The information provider generates the data when it fits into its own priorities.

Since there is no direct coupling of agents in the data transfer, the agent activities are more stable. Neither the information provider, nor the consumer has to care if the other breaks down. They do not have to perceive each other at all. But nevertheless, the internal agent operation has to prepare for missing information.

Most aggregation processes still require an agent to execute them. The agent may pick up stored data from the respective providers and after processing it stores the result. Each agent that requires the aggregated data just takes it. But, depending on the chosen active environment, some processes may even be executed automatically.

In manufacturing planning and control there are many processes executed at different time scales, with data being exchanged among these processes. For example, there are the different planning processes ranging from long-term to short-term planning. Each planning process takes the results of the previous one and refines it. Continuous planning and replanning mechanisms should be based on indirect interactions to avoid the coupling of processes on different time scales.

Recursion, Self-Similarity (SE-Principle 11).-Repeat structurally similar interaction mechanisms on different levels of the agent system (recursion). Wherever appropriate, apply a successful approach in solving a problem to similar problems at all scales (self-similarity).


33

Recursion and self-similarity are applied all over nature. Many large systems owe their complexity the recursive repetition of simple mechanisms or structures. Self-similar structures are found in the growth of all kinds of plants, in cells, organisms, or ecosystems.

Structural recursion provides simple building blocks that fit together to form larger blocks. It was already suggested that a SE might be modularized. When applying recursion to the structure and the mechanisms of the parts, modularity becomes simpler to realize and the resulting system is much easier to understand.

A very obvious example for recursion in structure and mechanisms in manufacturing execution is found in the AMIS system [Odell and Greenstein, 1999]. The agent responsible for the fulfillment of the task breaks down an incoming task into sub-tasks. The agent either performs the sub-tasks, or they are sold out to other agents. These sub-contractors repeat the process recursively. The general principle is very simple, but the emerging global behavior is sufficiently complex and dynamic to fulfill very complex orders.

Feedback, Reinforcement (SE-Principle 12).-When coordinating large crowds of small agents turn to feedback and reinforcement effects. Always take into account the feedback of effects of actions in the environment back into the agents‘ operation.

An important principle in the design of emergent coordination mechanisms in a SE is the focus on increasing returns. Knowledge, skills, or behavioral patterns that produce positive results in agent activities are reinforced in their importance with every usage. The consequence of the reinforcement is a higher impact on future agent behavior. Thus, cause and effect in agent activities are linked in a positive feedback loop. The design principle holds for the single agent as well as for groups of agents.

Another form of feedback inevitably occurring is caused by the activities of agents in their environment. Agents change their surroundings by their actions. Hence, future actions must take these changes into account. Complex cause-and-effect chains couple the agents. Most of these chains feed back into the originator of the effects. Such feedback through the environment must be taken into account when designing the agent behavior. When effectively used, feedback-aware behavior may drastically improve the performance of an agent.

Manufacturing control applications may make use of increasing returns effects. For example, the selection of a processing resource from a set of available ones should increase the probability for the following agents to chose the same resource as well, if the processing was successful. Such a mechanism may be used throughout the production system and similarly for the selection of transport routes.

Randomization (SE-Principle 13).-Introduce a random factor into the moment and the outcome of agent decisions in massively parallel interactions of many agents to prevent the emergence of negative synchronism and to explore alternative solutions.

There are devastating effects in multi-agent coordination known as thrashing, stemming from synchronism in parallel interactions. They occur when many agents take a deterministic decision regarding the same choice at the same moment based on the same information. The classic example for thrashing is the synchronized selection of the shortest queue, when many agents rush from one queue to another because they all select the same queue, making it a much longer one. Adding randomization to the decision moment and to the outcome of the selection of the agents effectively prevents thrashing in the example.

Additionally, randomization may dampen avalanching effects caused by feedback. The


34

number of agents joining an avalanche is reduced, if their decision is not deterministic. Randomization provides alternatives that may prove advantageous to the system as a whole.

Inherent randomization of decision processes prevents the system from settling in at a local optimum. It is kept alive and adaptive, always trying out slight variations of the main theme. Simulated annealing technique is a successful application of randomization in search mechanisms.

Randomization breaks symmetries and thus supports self-organization in complex dynamical systems. With non-linear processes in such a system, very small random fluctuations may be amplified and one of the many stable states of the system is selected.

In manufacturing control applications following the SE-approach, many decisions are taken in parallel and independently by many agents. Without randomization, such massive parallelism is hard to handle and stabilize. The system is prone to catastrophic thrashing and avalanching. Feedback may not be used in coordination; instead it would have to be prevented by all means.

Evolutionary Change (SE-Principle 14).-Always prefer gradual or evolutionary change in the state of the system to abrupt or revolutionary change. Global evolutionary change may be achieved if each agent changes gradually only.

A situated agent system acts in an external environment, which has its own dynamics. All actions in the environment take a while to become perceptible in their consequences to the agent system. Repeated abrupt changes in the state and in the behavior of the system may superimpose potentially contradicting actions in its environment.

Abrupt major changes in the state of a system are in their consequence comparable to longer jumps in the search within weakly auto-correlated fitness landscapes. There is no prediction of what the resulting fitness - the resulting performance of the system - will be after the change [Kauffman, 1993]. How timid the system should be in its change is dictated by the dynamics of the surrounding environment, as the optimal length of jumps in dynamic fitness landscapes depends on the ruggedness and the strength of the auto-correlation of the landscape and on the dynamics of its change.

Evolutionary change is further supported by the demand for locality. Each agent perceives and acts in its local environment only. To initiate and control major changes takes a huge effort. It is much easier to propagate changes in a distributed manner. Depending on the granularity of the system, propagation of change takes a while to affect the whole system. Hence gradual change is achieved.

Information Sharing (SE-Principle 15).-Include information sharing mechanisms into the standard operation of the agent system. Share information between generations of agents; learn as individuals, or as a society.

Whenever a new approach to solve a problem is tried out, the agents put resources at risk. If the experiment fails, the invested resources are lost. A successful trial yields a new solution. To make maximal use of the invested resources, the new information should be shared among the agents.

Information sharing may be incorporated into the activities of the agents wherever appropriate. An effective way to make sure information is shared is to underpin the information storage infrastructure with automatic information sharing mechanisms. Information stored by an agent is potentially made available to others, always preserving


35

locality.

As already mentioned in the discussion of randomization (SE-Principle 13), there are many opportunities for a manufacturing control system to learn and to adapt. Automated learning and adaptation processes may help to simplify system design.

Forgetting (SE-Principle 16).-Include forgetting if an agent or the agent system is enabled to learn. The multi-agent system should include mechanisms for automatic dissipation of acquired information over time.

Without forgetting, information remains within the system even when it is outdated. The agents would have to make sure that data that is no longer valid is removed. The removal becomes a major effort if information is stored in the environment for indirect communication.

When reinforcement mechanisms are applied, automated forgetting may prevent overload. Without a process that levels out the bias values for a probabilistic selection from a set of options, repeated reinforcement could take these values beyond any sensible limit.

The loss of information helps the system to adapt in a similar way randomization does. Reinforcement processes tend to bias the agents, and hence the whole system, towards specific solutions or behavioral patterns. The bias is intentional since these solutions have proven themselves in the past. But, in a changing environment, good solutions are never sure to remain good for all time. To prevent the system from being trapped in one solution and to remain adaptive, acquired information must be given up.

Multiple Goals (SE-Principle 17).-Before designing the agent system, identify the different goals and their respective type. Design the system to be able to handle multiple goals.

The operation of synthetic ecosystems in real-world applications almost always requires the fulfillment of multiple goals. Furthermore, these goals are mostly maintenance-goals without a final goal of the operation of a system. Instead, the agent activities maintain an ongoing operation and adjust to cope with disruptions. Often, a number of given requirements are sufficed.

The continued sufficing of maintenance-goals instead of the optimized fulfillment of achievement-goals is one of the major differences between the operation of a SE in (manufacturing) control applications and systems in problem solving domains like process planning or failure diagnosis. Before the design process is started it has to be clarified what problem class the system will have to cope with. In the case of achievement-goals, a predominantly SE-oriented approach may even be inappropriate.

If the application is dominated by maintenance-goals, then traditional problem-solving techniques are still applicable in the performance of specific sub-tasks. The fulfillment of all requirements over the full run of the system is verified in the evaluation of the global performance. To compare the performance of systems, parameters like resource usage, efficiency, or the fulfillment of other soft requirements are evaluated.

In many mass-production systems in industry the predominant maintenance-goal is high global throughput, followed by high resource usage, low work-in-progress, or low production costs. These goals are contradictory and quantitative; hence they can only be sufficed.


36

3.1.4 Go to the Ant

The design principles are identified and illustrated in the context of a single task of a natural agent system. Returning to the ant colony visited already in Section 2.1.6, the joint food foraging is considered. This coordination mechanism is probably the most cited example of naturally occurring self-organization in literature related to swarm intelligence. A “(#)“ references the number of a design principle when identified in the description.

Social ants construct networks of paths that connect their nests with available food sources. Mathematically, these networks form minimum spanning trees. Thus, they minimize the energy they spend to bring food to the nest. The colony accomplishes this feat without any centralized control. The paths emerge from the activities of the individual ants (8).

A single ant is very small compared to the whole colony in terms of resource usage and impact (2). As a physical entity in the environment (1) it has a spatial location. Its sensing and acting is restricted to a very small environment (9, 5). In a colony there are different types of ants fulfilling specialized tasks (3). Following natural evolution, recombination and mutation effects ensure heterogeneity in the types.

Many ants attempt to solve the food-foraging problem in parallel (4). Depending on the current situation in the environment of the colony, some ants may succeed while others fail. If the rate of failures is kept below a certain threshold, the system remains stable.

Ants communicate indirectly through their environment (10). Direct ant-to-ant communication occurs only occasionally. Highly volatile chemical substances, called pheromones, provide the means for indirect communication. Each ant is able to produce pheromones. It drops them to the ground or it sprays the pheromones into the air. At their current location, ants perceive the different pheromones separately. They discern the local strength and the local gradient of the strength of pheromones.

Pheromones are carriers of data, since each existing pheromone type is deposited in a specific context. Once dropped to the ground, pheromones of the same type aggregate in strength. The aggregated strength is available to all ants present. The perceived strength and gradient is incorporated into the probabilistic decision processes of the single ant.

Pheromones evaporate over time. The continuous decreasing of the local pheromone strength is governed by a dispersion function of the form s(t+1)=s(t)*E, where E is a constant evaporation parameter between one and zero specific for each pheromone type. Each ant foraging for food expresses a behavioral pattern, which is emulated with sufficient correlation by the following set of simple rules that incorporate one specific pheromone type.

Rule (1).-Avoid obstacles.

Rule (2).-If you find yourself at food and you are not holding any, pick the food up.

Rule (3).-If you find yourself at the nest and you are carrying food, drop the food.

Rule (4).-Select every step from the current distribution over possible directions. If no pheromones are sensed, use a uniform distribution, executing Brownian motion. If pheromones are sensed, bias the probabilistic selection in favor of the scent's direction.

Rule (5).-If you are holding food, drop fixed amounts of pheromone at a constant rate as you walk.


37

The presented behavior of the food-foraging ants falls into different parts (6). At the core there is obstacle avoidance (Rule 1), making sure an ant can navigate even in complex landscapes.

The second building block of the food-foraging behavior makes sure the food is picked up and delivered (Rules 2, 3). Actually, the food-dropping rule (Rule 3) is more complex in reality, where food is stored at specific places of the nest.

To ensure the whole surroundings of the nest are covered by the search of the colony for food, random search is executed. Rule four provides that even in the absence of any additional knowledge the ants eventually find a food source, if there is any. Random search is the ultimate “weak method“ in navigating through a search space. By itself, it breaks down due to the combinatorial explosion. But combined with the information sharing realized by the pheromones, it keeps the system robust, adaptive, and alive.

In the presence of pheromones, the walk of an ant is still randomized. But the selection of the direction is weighted in favor of the direction of the scent. The principles stated in the SE approach require randomization (13) of the moment and of the outcome of the internal decisions of the agents wherever possible.

The probabilistic component in the movements of an ant realizes an ongoing search for improved solutions to the food-foraging problem. As a consequence of rule five, new paths found in the search are shared with other ants (15). The evaporation of pheromones realizes forgetting (16), which is required to “forget paths“ to depleted food sources. Furthermore, the gradual change of the information incorporated into the decision processes depend on may lead to an evolutionary change of the state of the system (14).

An ant regularly drops pheromones while it carries food. Thus, trails are only created by successful ants, which have found food. Additionally, each successful ant that finds a pheromone trail in its random walk follows the trail to the nest. Thus, positive feedback occurs (12). Negative feedback comes into play with the restricted number of ants and the finite amount of food.

Finally, the system as a whole - the ant colony - suffices a number of maintenance-goals (17). Besides foraging for food, it has to sort the brood, and build and maintain the nest. The colony has to protect itself and eventually it spawns new colonies. Each task is fulfilled as good as possible without achieving a final solution. The colony maintains and adapts its global behavior to constantly suffice the set goals in a changing environment.

3.1.5 Return from the Ant

Consider a synthetic ecosystem where software agents act in a physical environment. On the one hand, the agents control physical entities in the real world. But on the other hand, there are interactions among the agents in a software environment.

To enable indirect coordination among software agents in the same way social ants coordinate, the software environment should emulate the “services“ provided by the real world to the ants. The part of the software environment realizing the services is called the pheromone infrastructure (PI). In the following, major features of the PI are specified, using terminology taken from descriptions of insect colonies.

The PI models a discrete spatial dimension. It comprises a finite set of places and a topological structure linking the places. A (topological) link connecting two places has a


38

downstream and an upstream direction. Thus, for each place there is a set of downstream and a set of upstream neighbors - places that are directly linked to it.

Each agent in a SE is mapped to a place. The mapping represents the current location of the agent, which may change over time. A change in the location of an agent must always follow a link in a downstream or upstream movement.

The PI models a finite set of pheromone types. A pheromone type is a specification of a software object, comprising a “strength“ slot and other data-slots. The domain of the “strength“ slot is the set of real numbers. The domain of every other data-slot must be finite. For each pheromone type, a propagation direction (downstream or upstream) is specified.

The PI handles a finite set of (software) pheromones for each pheromone type. A pheromone is an incomplete specialization of its respective pheromone type. Every data-slot, except “strength“, is assigned a value from its respective domain to form one pheromone. A pheromone provided with a “strength“ value is interpreted as a specific amount of the pheromone. All possible pheromones of a SE may be stored together with their respective local amount in the pheromone management of each place. In the following, the term “strength of a pheromone“ is used as shorthand for the value in the “strength“ slot of a pheromone.

An agent may perform the following activities at its current place in the PI:

The PI manipulates the values in the “strength“ slots of the pheromones at each place in the following way:

External Input.-Based on a request by an agent, the strength of the specified pheromone is changed by the specified value.

Internal Propagation.-Assuming an external input of strength s into a pheromone g at a place p. The input event is immediately propagated to the neighbors of p in the propagation direction of g. There, the local strength of g is changed by an input weaker than s. An even weaker input propagates to the following neighbors. The stepwise weakening of the input is influenced by g's propagation parameter.

Evaporation.-Without taking changes caused by external input or propagation into account, the strength of each pheromone is constantly reduced in its absolute value. The reduction is influenced by the evaporation parameter of the pheromone.

There is a major difference between the algorithms realized in the PI and those observed in nature. After an ant places pheromones on the ground, evaporation disperses it. Particle by particle the pheromone moves through continuous space driven by Brownian motion. At the initial location the amount of pheromones is reduced while it builds up somewhere else or vanishes completely.

In the discrete space of a PI, propagated pheromones have only specific locations on which to “settle down“. Furthermore, the structure of the space is not homogeneous - at some places pheromones may be propagated to many neighbors, while at other places no further propagation is possible. Finally, in an implementation of the PI, continuous erosion


39

of the pheromone levels would require interaction among all places at all time.

As a consequence, the mechanisms of evaporation and propagation of pheromones are modeled separately in the software environment of the agents. Instead of continuously exchanging particles among the places, there is one “wave“ of input events running along the links, which is triggered by the original input of an agent.

A pheromone infrastructure realizes an application-independent support for a SE designed according to the proposed principles. Specifically, a PI supports:

Decentralization (SE-Principle 5).-The mapping of each agent to a place in the PI introduces a spatial structuring of the agent system. With the ability of each agent to request the references to other agents located at its place, a local White Pages (WP) service is realized. The topology data permits the agents to explore the spatial structure of the system.

Locality (SE-Principle 9).-Each agent is only permitted to request information local to its current place. It can perceive the agents located at its place, the neighboring places, and the values of the “strength“ slot of the pheromones present at its place. It can act only on local pheromones and it can interact directly only with local agents whose references it receives through the local WP service.

Indirect Communication (SE-Principle 10).-A pheromone represents specific data in the same way the pheromones of the ants do. If one agent changes the value in the “strength“ slot of a local pheromone, other agents can perceive the change. Thus, information is transmitted through the environment. The environment aggregates data automatically when multiple inputs to the same pheromone occur. The pheromone infrastructure directly supports sign-based stigmergy.

Feedback and Reinforcement (SE-Principle 12).-The pheromones provide the means to externally store and reinforce bias values for the decision processes of the agents. The automatic evaporation of the pheromones requires a continuous reinforcement of stored information.

Randomization (SE-Principle 13) and Evolutionary Change (SE-Principle 14).-Wherever the value in the “strength“ slot of a pheromone at a place is incorporated into the decision processes of the agents, randomization occurs because the agents operate asynchronously and the decision parameter changes over time independent of the activities of the agents. An even better way to realize randomization is to have the strength directly determine a probabilistic weighting of decisions.

Information Sharing (SE-Principle 15).-Putting data into a PI provides the ideal means for information sharing among the agents. As the pheromone trails in the food-foraging example represent the acquired knowledge of the colony of paths to food sources, the data in a PI represents the accumulated knowledge of a synthetic ecosystem. It is stored for the agents to retrieve locally, and it is even propagated to other places to make information available in a wider area.

Forgetting (SE-Principle 16).-A PI provides an automated way of forgetting information stored there. Data put into a PI evaporates over time. If the “strength“ slot is taken as an indicator for the relevance of a specific information then the relevance is lost after a while if it is not reinforced. Any bias acquired by the agents has to be repeatedly reinforced to realize a probability distribution other than a uniform one.

If the PI is incorporated into the runtime environment and if coordination mechanisms


40

are implemented that are analogous to the pheromone-based food-foraging behavior of ants, then other principles in the design of synthetic ecosystems are indirectly realized too. Consider parallelism (SE-Principle 7) and the control from bottom up (SE-Principle 8). Following a pheromone-based approach requires the agents to be able to handle parallel interactions, and control decisions emerge influenced by the successive inputs of agents to pheromones. Self-similarity, for instance, is encountered in the regular input to a pheromone as in rule five of the food foraging example. Such a regular input behavior is applicable to a multitude of information transmission scenarios as the following chapters demonstrate.

3.1.6 Summary

Section 3.1 proposes a set of design principles for synthetic ecosystems in manufacturing control applications. The principles have been adopted from a general set of SE principles, from research into complex systems, and from previous experience with agent system design. It is shown in the food foraging example that these principles are also found in pheromone-based coordination in nature.

A set of features assigned to a specific part of the software environment of agents is suggested under the assumption that synthetic ecosystems for manufacturing should be designed according to the proposed principles. A “pheromone infrastructure“ provides the agents in a synthetic ecosystem with a similar environment as natural agents, like ants, have available to “execute“ their stigmergetic coordination mechanisms.

As an application-independent part of the software environment, the PI provides all major elements that are required in the design of pheromone-based coordination mechanisms for software agents. But, for a widespread use of such an approach to system design, a deeper understanding of the PI is still required.

The principles presented in the synthetic ecosystems approach to manufacturing control and the general use of a pheromone infrastructure in software agent development are revisited in the “Synthesis“ section (Section 6.1). There the advantages and disadvantages of the approach are discussed on the basis of the guided manufacturing control system presented in Chapter 4.

3.2 Analyzing the Pheromone Infrastructure

In the following, a formal model of the PI is specified. The features of the model are analyzed in different scenarios. A real-world example analysis of a pheromone-based control mechanism concludes the section.

3.2.1 A Formal Model

The PI extends the runtime environment of the agent system of an application. For an analysis of emerging pheromone patterns, agent behavior towards the PI has to be formally specified.

The formal model considers one pheromone only. The descriptive model of the PI (Section 3.1.5) proposes that different pheromones are managed separately. Input events


41

for one pheromone do no affect the strength of other pheromones at any place, and also the propagation and evaporation mechanisms do not introduce any inter-dependencies among the different pheromones. Multiple pheromones are considered using multiple models. In difference to the descriptive model, the formal model is based on discrete time.

Notation 1 (Numbers)

Throughout the following discussion À denotes the set of natural numbers and  stands for the set of real numbers.

The definition of an environment captures the spatial structure of the PI. Each pheromone type has a specific propagation direction for the propagation of input events. That means the event of a pheromone deposit at one place is propagated to all neighboring places in the propagation direction of the pheromone type.

The formal model links the places in propagation relations. A propagation relation is analogous to a topological link in the descriptive model that is reduced to the propagation direction of the pheromone. In contrast with the descriptive model, where places are linked bi-directionally and one of the directions is labeled “upstream“ and the other one “downstream“, the places in an environment are linked uni-directionally. Nevertheless, the term “neighbors of a place“ is used to refer to places linked through the propagation relation to a place, even though it is not the traditional bi-directional neighborliness.

Definition 1 (Environment)

An environment is a tuple <P,N>, where

P is a finite set of places and

is an irreflexive propagation relation among places.

The set of neighbors of a place is defined as .

The current state of the PI model comprises two patterns. For each place the propagation pattern specifies the strength of the propagated input at the place and the pheromone strength pattern specifies the current local pheromone strength at the place.

Definition 2 (State)

Let <P,N> be an environment. The current state of the PI in <P,N> is given in the two mappings q and s, where

is a total mapping that maps a place to . q(p) is to be thought of as the strength of the propagated input at place p.

is a total mapping that maps a place to . s(p) is to be thought of as the strength of the pheromone at place p.

If a scenario does not specify the initial state of the PI, q(0)=0 and s(0)=0 is assumed by default.

The PI emulates the evaporation and the propagation of pheromones in the real world. Evaporation decreases the local pheromone strength, whereas propagation spreads the effect of an input to the PI to the surrounding neighborhood of the place at which an external input occurred. The rate with which a pheromone evaporates is specified in the evaporation parameter of the pheromone. The reduction in strength of the input in a propagation step is influenced by the propagation parameter of the pheromone. All


42

pheromones of the same type must share the same evaporation and the same propagation parameter.

Definition 3 (Parameters)

The real values E and F are two parameters of the pheromone. E ( ) is the evaporation parameter and F ( ) is the propagation parameter of the pheromone.

In a given scenario, the agents located at places of an environment jointly generate an external spatial-temporal input pattern to the pheromone. For every moment and for each place the input pattern specifies the strength of the external input. From the perspective of the PI, such a pattern completely specifies the scenario. To guarantee the global stability of the PI (Section 3.2.2), the external input pattern is globally limited in strength.

Definition 4 (External Input Pattern)

Let <P,N> be an environment. The external input pattern in <P,N> is given by the real number R and the mapping r, where

is the global limit of the external input pattern, and

is a total mapping that maps every point in time and each place to . r(t,p) is to be thought of as the strength of the external input at place p and at time t.

In the analysis of scenarios, external spatio-temporal input patterns are often considered separately for each place. In this case the following notation of an input sequence at a place is used.

Notation 2 (External Input Sequence)

An external input pattern considered for only one place is called the external input sequence at p. Let R and r' represent an external input pattern. The mapping that maps a point in time to is the input sequence at p if r(t)=r'(t,p) holds for all t.

The state of the PI changes over time through external input, internal propagation, and continuous evaporation. The following transition functions formally specify the evolution of the state. The first transition function specifies the propagation of input events through the PI and the second function combines the input from the agents and the propagated input with a general dispersion function to determine the current strength of the pheromone.


43

Definition 5 (Transition Functions)

Let <P,N> be an environment, let E and F be the parameters of the pheromone, and let R and r be an external input pattern. The change of the state of a PI is determined by the two transition functions q and s, where

is a total mapping that maps a point in time and a place to and

is a total mapping that maps a point in time and a place to .

Specifically, the transition of the propagated input pattern (q) is defined as

(3.1)

And the transition of the pheromone strength pattern (s) is defined as

(3.2)

 

Besides the external input generated by local agents, input events propagated from neighboring places change the strength of the pheromone. The mechanism of a “wave“-like propagation of an input event through the PI is captured in the definition of the transition function q (3.1). Every transition takes all input events at each place and propagates them to the direct neighbors according to the propagation relation.

Multiplied with the propagation parameter F, there is a reduction in the absolute strength in every propagation step. |N(p')| influences the strength of an input event when it is propagated from place to place . The term represents the number of neighbors of p' according to the propagation relation N. The N(p') selected in a transition are never empty, because p is one of these neighbors.

The strength of inputs propagated from different places to p add up in every step. The strength of an input propagated on from p‘ to the neighbors of p‘ (N(p')) is split among these neighbors. Thereby, auto-reinforcement effects in cyclic propagation are prevented (Section 3.2.2).

The local strength (s(p)) models a quantity of the pheromone. Negative values for the pheromone strength are permitted too, intuitively representing an amount of “anti-pheromone“. But, only the context of an application specifies the exact semantics of the pheromone.

The model chosen for the PI has three basic features. It is finite and discrete in space (set of places P), infinite and discrete in time ( ), and the model is infinite and continuous in its states ( , ).

In most cases a scenario-based analysis may consider one pheromone at a time. Only when considering local strength patterns at one place, multiple pheromones enter the analysis. The topological structure, the pheromones with their propagation direction and their evaporation and propagation parameters, and the input behavior of the agents have to be formally modeled to analyze how the state of the PI evolves in a specific scenario.


44

Notation 3 (Scenario)

A (one-pheromone) scenario S=<L,E,F,R,r> specifies an environment L=<P,N>, pheromone parameters E and F, and an external input pattern (R, r). Optionally, the initial state of the PI (q(0), s(0)) may be specified by the scenario.

3.2.2 Proof of Stability

The Global Stability theorem is stated for an arbitrary scenario. The first stage of the proof introduces a global majorant for the external input, knowing that the desired stability is achieved when the PI is stable in face of the majorant input pattern already. In a second step, the local dampening of the aggregated input at a set of places is shown.

Finally, all ingredients are assembled to take the main step, showing that there is an upper limit to the aggregated effect of one external input at one place on the pheromone strength at any place. The additivity of the transition function (3.2) is used to extend the argument to infinite input sequences at all places.

Theorem 1 (Global Stability)

Let S=<<P,N>,E,F,R,r> be an arbitrary scenario. There exists a fixed upper limit B ( ) for the absolute value of the pheromone strength at any place in (|s(p)|) in any state of the PI.

Without loss of generality it is assumed in the following that all external input values are either equal to or larger than zero.

An external input r(t,p) at a place and at time adds to the local pheromone strength. A constant input pattern , adding R at each place and at every moment, is the majorant for the input pattern r. If the PI remains stable faced with an input r', global stability is also guaranteed for the input r.

3.2.2.1 Local Stability

Consider an arbitrary set of places and an aggregated input (the sum of external and propagated input) to it at one point in time. Local stability of the PI guarantees an output of weaker strength propagated to the neighbors of the chosen set in the next step. The truth of the statement becomes clear with the following additional definition that is only required for the proof of stability.


45

Definition 6 (Input/Output)

Let S=<<P,N>,E,F,R,r> be an arbitrary scenario.

An aggregated input at a set of places is a mapping that maps a point in time and any subset of P ( ) to . Following the definition 5, an aggregated input at a set of places is given by:

(3.3)

A single output out of one place into another one is a mapping that maps a point in time and two arbitrary places to . Following the definition 5, a single output is given by:

(3.4)

An aggregated output out of a set of places is a mapping that maps a point in time and any set of places to . Following the definition 5, an aggregated output out of a set of places is given by:

(3.5)

 

O(t,P')=F*I(t-1,P') holds at any point in time and for any subset of places. Therefore, the local weakening of an input required for local stability is given, because F<1 holds.

3.2.2.2 Propagation Stability

Local stability does not provide an approximation of the limit of all strength values. In the following the aggregated effect of one external input is approximated for an arbitrary place. But, to formally state the propagation stability theorem, a one-time and one-place external input pattern r“ must be declared first.

Assume that at the arbitrary place one and only one external input of strength 1 at time t=0 is generated. No other external input is ever observed at any place. The external input is formally specified as:

(3.6)

Theorem 2 (Propagation Stability)

There exists a fixed upper limit to the aggregated sum of all propagated inputs at an arbitrary place if a one-time and one-place external input is assumed.

In the following, sets of places are considered and hence, additional notations have to be declared first.


46

Notation 4 (Notations for Sets of Places)

Let <P,N> be an environment.

The neighbors of a set of places according to the propagation relation N are denoted by .

The number of neighbors of a set of places according to the propagation relation N is denoted by .

The number of occurrences of a place in the neighborhood of a set of places according to the propagation relation N is denoted by .

The following statement always holds true: . The statement is central to the following approximation of the upper limit of the local pheromone strength.

Proof (Theorem 2). Consider an arbitrary place . The proof of theorem 2 aggregates the propagated input at px while it follows the propagation of the effects of the single external input.

Let the set P0={ pin } comprise only the place where the one external input occurred. Furthermore let Pi denote the set of neighbors of P0 that are reached in the i-th propagation step given by Pi = N(Pi-1) (i>0). According to the previous discussion of local stability and assuming the specific one-time and one-place external input pattern, the aggregated input at the places of Pi at the i-th propagation step is given by I(i+1,Pi)=Fi and it occurs at time t=i+1.

Assume that an arbitrary step in the propagation takes the input events from set Pi-1 to set Pi. The overall input into Pi is I(i+1,Pi)=Fi. A portion of the input, specifically , is propagated to px. Therefore, the propagated input to px aggregated for all time is given by:

(3.7)

With holding, the infinite sum in (3.7) is always limited by:

(3.8)

The sum of the effects of propagated inputs resulting from one external input of strength R at an arbitrary place is always finite and limited by .

3.2.2.3 Conclusion

After the effect of one external input at one place on all other places is proven to be


47

limited, the majorant input pattern is considered.

One external input of strength R to one place increases the strength at each place by maximally . With each place receiving an external input of R at every unit time, an aggregated input of at any time and at each place results. In the case of such a fixed aggregated input, at any moment t the pheromone strength at each place is smaller than:

(3.9)

The given limit may be approximated for large t by:

(3.10)

The pheromone strength at all places in the PI remains finite under the majorant external input . Hence, the infrastructure remains stable under the original input r. Thereby the Global Stability theorem (Theorem 1) is proven.

3.2.3 Single-Pheromone Analysis

Most features of the PI are discussed for one pheromone alone. In the following, E and F represent the evaporation and propagation parameter of an arbitrary pheromone in the respective scenario. Furthermore, for every external input pattern an arbitrary global limit is assumed without always stating it explicitly.

3.2.3.1 Single-Place Scenarios

Let <Ps,Ns> be an environment. The tuple represents a single-place environment, if Ps={ ps } holds. results from the irreflexivity of Ns. In the following, ps denotes the single place in the environment of the scenarios. For one place the transition function (3.2) may be reduced to:

(3.11)

The no-input scenario with is the simplest one to consider. There, the transition function is further reduced to s(t+1)=s(t)*E=s(0)*Et+1. The initial strength s(0) simply evaporates over time.

An external input is taken into account in all other scenarios. The following analysis considers the transition function (3.11) in its non-recursive form:

(3.12)

A basic scenario to consider is a repeated constant input by one agent located at place ps. The aim of the agent is to reinforce the relevance of information expressed by the pheromone. The behavior is called refreshing the pheromone. Hence, the input scenario is


48

a one-agent regular-refresh scenario.

3.2.3.1.1 One-Agent Regular-Refresh Scenario

For the analysis of the pheromone strength at ps, it is sufficient to specify the input strength and the input rate . The actual motivation of the input behavior is irrelevant. Without loss of generality it is assumed throughout the following discussion that the refresh strength A is larger than zero.

Knowing A and T, r is formally expressed by

Based on the regular input sequence, the transition function is reduced to

(3.13)

with j, the number of previous inputs, specified as: .

Are there one or more fixed points - equilibria - in the evolution of the strength at ps? The location of fixed points in a scenario is very important because they determine the most probable results when sampling the pheromone strength. If there exists a close approximation of a fixed point, then agent scenarios may be designed and tuned analytically.

In the one-agent regular-refresh scenario equilibrium is reached. The following analysis formally describes its location, the current distance to the equilibrium, and the time it takes to reach it.

3.2.3.1.2 Equilibrium

The transition function s(t) is considered for large t to derive the equilibrium the pheromone strength reaches. The function does not evolve continually. It has a local maximum at followed by a steady decline until it reaches its local minimum at tm+T-1=T(n+1). Then, it jumps up to the next maximum at tm+T=T(n+1)+1 (Figure 3.1).

For later discussion it must be noted that the local minimum at tm+T-1 is only the “visible“ minimum in the discrete-time model. When considering the scenario in continuous time, the evaporation continues right to the moment, the input strength is added. There, at a moment of discontinuity, the local minimum and maximum meet. The local maximum “hides“ the actual minimum in the discrete model.

The local maximum at time tm=Tn+1 is given by:

(3.14)


49

Figure 3.1. Pheromone Strength under Regular Refresh - A=2, T=5, E=0.99

The sequence of local maxima has a fixed point, denoted by Bm. It is the limit value of equation (3.14), given by:

(3.15)

With Bm approximating the local maxima for large t, Bm-A or Bm*ET gives the “hidden“ local minima. Both terms are valid. The first one follows the reasoning that the pheromone is refreshed regularly by an input of A, whereas the second term represents the evaporation of the pheromone strength throughout the time between two refresh moments. Bm*ET-1 gives the visible local minima.

Figure 3.2. Pheromone Strength under Regular Refresh - Equilibrium

Hence, the range that limits the pheromone strength at equilibrium is

(3.16)

Figure 3.2 illustrates the equilibrium state reached under the regular refresh behavior of A=2, T=5. The evaporation parameter is set to E=0.99.


50

3.2.3.1.3 Distance to Equilibrium

With an analytic description of the equilibrium range at hand, the next step in the analysis focuses on the current distance to the equilibrium. Since the equilibrium is specified by the local minimum and maximum of the strength, the distance between a local maximum and the upper boundary of the equilibrium range is considered.

Let dm(tm) denote the distance to the equilibrium at a maximum moment tm. dm(tm) is given by

(3.17)

Under what conditions does dm(tm)=0 hold? Whereas as a solution for dm(tm)=0 does not tell much, is also fulfilled with since Tj=tm-1. Thus, the equilibrium is approached by the pheromone strength, but it is reached after infinite time only.

Another solution to dm(tm)=0 is s(0)=Bm*ET-1, the “visible“ local minimum. The first transition step in the formal model reduces the initial value to Bm*ET - the “hidden“ minimum - and simultaneously adds the input A. Thus, s(1)=Bm*ET+A=Bm is the local maximum of the equilibrium state.

In real (continuous) time, the initial strength would have been set to Bm to start right in the equilibrium state. This difference between the model and reality vanishes only for T=1. In this specific case, there is a refresh at every moment and no local minima result in the discrete model. In such a scenario the analytically predicted equilibrium collapses into one point

(3.18)

and the expression of the distance to the equilibrium is reduced to

(3.19)

Figure 3.3. The Deterministic and the Statistical View on a Refresh Scenario

If the model is most accurate for T=1, how may other scenarios be translated into such a configuration? In the previous discussion, the one-agent regular-refresh scenario was considered in a deterministic way only. It is completely determined when the pheromone is refreshed by an input of strength A. The event happens every T time steps. A less discrete stance would consider a refresh by A over a period of T, statistically resulting in an average refresh by A/T at every unit time (Figure 3.3). In this case, only one fixed point exists for all sub-sequences of the strength at ps. It is denoted B and given by:


51

(3.20)

A less deterministic view on a given scenario may reduce the complexity of the analytic expressions gained and even remedy differences that are introduced in the model‘s abstraction from reality. But, with only one agent in the scenario and with its refresh rate restricted to natural numbers, the strict deterministic view is more correct when considering the long-term evolution of the pheromone strength. The strength value oscillates widely between the local minima and maxima for larger refresh strength values A or longer refresh rates T.

In the deterministic view, the equilibrium is given by the local extrema, whereas in the statistical stance an average pheromone strength is predicted. Figure 3.4 illustrates the difference.

Figure 3.4. Location of the Predicted Equilibrium

The remaining analysis of the one-agent regular-refresh scenario considers both perspectives, whereas the statistical view is more appropriate to handle multi-agent scenarios.

3.2.3.1.4 Time to Equilibrium

Generally, the equilibrium state is only approximated in finite time. But, in the process of tuning pheromone-based coordination mechanisms, it is sufficient to know when the approximation of the equilibrium state has reached a certain quality. Assume the following quality measure: The approximation is sufficiently close if the distance between the current and the equilibrium value is smaller than x percent ( ) of the input strength. The criterion is formally stated as dm(tm)< | x * A |. The time to reach the equilibrium state when applying the quality measure is given by

(3.21)

In the statistical stance, the criterion is stated as d(t)<|x*A/T| and the time t fulfilling it is given by:

(3.22)

3.2.3.1.5 Sampling under Regular Refresh

Assume that the equilibrium for a pheromone under a specific refresh scenario is predictable. The predictability may be used to explicitly communicate data from one agent


52

to another based on the observed strength.

Consider again the previous scenario where one agent refreshes a pheromone regularly. In the following the agent is called “Sender“. Another agent (“Receiver“) is added to the scenario that samples the current strength of the pheromone. The following discussion presents approximations that enable Receiver to derive the parameters specifying the refresh behavior of Sender. These parameters may carry numerical data from Sender to Receiver.

Let S denote the pheromone strength sampled at an arbitrary moment. The primary assumption on the side of the Receiver is that the pheromone strength has reached equilibrium already. Taking the deterministic stance, S must be within the equilibrium range of [Bm-A,Bm]. In the statistical view, S is equal to the fixed point B.

Figure 3.5. Sampling the Equilibrium Range

The deterministic view is considered first, discussing the two extrema S=Bm-A and S=Bm (Figure 3.5). In the first case, the local minimum was sampled. Formally, the parameters of Sender, as perceived by Receiver, are given by Amin=S(1-ET)E-T and Tmin=ln(E)-1ln(S/(S+A)) respectively. At the other extreme, the parameters are computed by Amax=S(1-ET) and Tmax=ln(E)-1ln((S-A)/S) respectively. Consequentially, Receiver has to know one refresh parameter to deduce the other.

Based on the discussion of these extreme cases, Receiver has an interval to choose from when deducing the missing parameter of Sender. If it knows the refresh strength A, then it may pick one value from [Tmin,Tmax] for the perceived refresh rate. Or, it knows the refresh rate T. Then, it is the interval [Amin,Amax] from which to select a refresh strength value.

Assume that Receiver picks the perceived parameter from the center of the available range. In this case, it may directly use the following equations:

and

(3.23)

Having sampled the pheromone strength only once, Receiver does not know the actual position of S in the interval [Bm-A,Bm]. Thus, there may be an error in its deduction using equations (3.23). The maximum error is given by:

and

(3.24)

The statistical view states that the sampled value S is equal to the equilibrium value B. Thus, the parameters are simply computed as:


53

and

(3.25)

With every sampled value assumed to be the equilibrium value, there is no error in the deduction of the parameters.

3.2.3.1.6 Multi-Agent Scenarios

The previous scenario of one agent regularly refreshing the pheromone at ps is now extended to n agents showing the same behavior.

Figure 3.6. Approaches to Scenario Translation

With more than one agent at ps regularly refreshing the pheromone, the input pattern (r) changes. There are three different approaches available to describe the new pattern in terms of the already analyzed one-agent scenario. The refresh behavior in the one-agent scenario is denoted by A1 and T1. It approximates the multi-agent refresh behavior where each agent refreshes the pheromone by A in a rate of T (Figure 3.6).

Table 3.1. Translation Approaches in
the Multi-Agent Scenario

translation approach

refresh strength (A1)

refresh rate (T1)

deterministic resonance

n*A

T

deterministic synchronized

A

T/n

probabilistic

n*A/T

1

The deterministic resonance approach assumes the input from all agents to arrive at the same moment. Thus, the refresh strength of all inputs adds up. The refresh rate remains the same indifferent of the number of agents (A1=n*A, T1=T).

The deterministic synchronized approach assumes the refresh actions of all agents to occur evenly spaced over time. Thus the refresh strength of every aggregated input is equal to the input from one agent. The refresh rate, on the other hand, depends on the number of agents. In the discrete-time model such an approach does not seem appropriate, since it restricts n to those numbers where holds (A1=A, T1=T/n).


54

A third approach is the probabilistic approach, which is strongly related to the statistical view. It considers the probability for a refresh action of one agent to happen at a specific moment in an interval of T. The probability is 1/T. Hence, the probable refresh strength for every moment in an interval of T is A/T with one agent, as argued in the statistical stance. With n agents, the refresh strength increases to A1=n*A/T with a refresh rate of T1=1.

As in the analysis of the one-agent regular-refresh scenario, the probabilistic approach lacks the inconveniences dictated by the choice of the formal model. Hence, the probabilistic translation of multi-agent scenarios is selected for the following analysis.

In the multi-agent regular-refresh scenario the equilibrium is the most important feature to discuss too. It is determined translating equation (3.15) on the basis of the probabilistic approach. The equilibrium value for n agents is denoted by B(n):

(3.26)

As the equation indicates, there is a convenient linear relation between the number of agents present and the equilibrium value of the pheromone strength.

3.2.3.1.6.1 Distance between two Equilibria

Let D(n,m) denote the distance between the equilibrium reached with n agents and the one with m agents (Figure 3.7). It is given by:

(3.27)

Figure 3.7. Changing the Number of Agents

The prediction of the distance between two equilibria may be used to tune the quality of perception of an agent according to the respective requirements of the designed interaction mechanism.

3.2.3.1.6.1 Time between two Equilibria

Assume that the number of agents refreshing the pheromone changes over time. In this case, it is important to know how long it takes to come sufficiently close (by a x-percent threshold) to the new equilibrium. The responsiveness of agent interactions built upon the


55

PI depends on the time it takes for the pheromones to stabilize at the new equilibrium. Similarly to the one-agent case (statistical view) the “sufficiently close“ criterion for a change from n to m is expressed in the statement:

(3.28)

The new equilibrium B(m) is approximated. The values of t fulfilling the statement (3.28) are given by

(3.29)

It should be noted that the required time neither depends on the refresh strength of an agent, nor does it depend on its refresh rate.

3.2.3.1.7 Providing Regularity in a Different Way

The scenario of multiple stationary agents is easily translated to a multi-agent scenario with mobile agents, if the input pattern is analyzed instead of the agent behavior creating it. Consider a flow of mobile agents passing sequentially through ps. Each agent in the flow generates one input and then it leaves (Figure 3.8).

Figure 3.8. Multi-Agent Mobility Scenario

The number of agents passing through ps in a unit time characterizes the flow. n is also called the “load“ of ps. The input behavior of an agent is specified by the strength of the single input. As a consequence, there is an average input of n*A strength every unit time, taking the pheromone strength at ps to a fixed point of:

(3.30)

A change in the strength of the flow from n agents to m agents ( ) results in a change in the location of the fixed point. The distance of two equilibria and the time to change to the new equilibrium is computed as in the stationary agent scenario (Equations (3.27), (3.29)).

3.2.3.1.7.1 Visibility of Load Changes

Assume that the number of agents passing through place ps changes from n to agents per unit time. The change is considered visible in the pheromone strength if the distance between the respective equilibria is sufficiently large. As in the


56

discussion of the time to equilibrium in the context of a single agent scenario, a specific percentage ( ) of the input strength is used to define the criterion:

(3.31)

Thus, to become visible, the strength of the change of the load at ps must fulfill:

(3.32)

3.2.3.1.7.1 Visibility of Perturbations

In the last step of the analysis of the mobile-agent scenario, the duration of the change of the load at ps is restricted in time. Whereas equation (3.32) considers the visibility of a permanent change, during a temporary change - a perturbation - the pheromone strength may not reach equilibrium.

A perturbation in the load of ps is formally characterized by the following parameters. Assume that a flow of n ( ) agents per unit time passes through ps. The duration of the perturbation is specified by , while specifies the strength of the perturbation. Finally, tx (tx>>0) is the moment the perturbation starts. The load changes back to n at . Figure 3.9 illustrates the effect of a perturbation as seen in the strength of the refreshed pheromone.

Figure 3.9. Effect of a Perturbation

The fixed point under the new load may not be reached during . Instead, the strength right at the end of the perturbation has to be considered for the restriction of the visibility. Thus the visibility criterion is stated as

(3.33)

Assume a fixed duration of a perturbation . According to the criterion, the perturbation is visible in the pheromone strength if the strength of the change fulfills the following condition:


57

(3.34)

The minimum duration for visible perturbations of a fixed strength may be predicted similarly.

3.2.3.2 Multi-Place Environments

After considering the pheromone strength at the single place ps, the following discussion extends the scope of the analysis to the effects of spatial propagation of input events.

The following two scenarios specify different environments. First a simple sequence of places is assumed. In a second environment, the ends of the sequence are joined to form a circle to explore the effects of cyclic propagation.

3.2.3.2.1 Sequential Topologies

Let <Pseq,Nseq> be an environment. It represents a sequential topology of n places ( , n>1) if the following two statements hold:

In every propagation step, the number of neighboring places is never larger than one. Therefore, in equation (3.1) the term “|N(p')|“ may be replaced by a constant value of one. In the following discussion, the term si(t) denotes the pheromone strength at place pi at time t.

One stationary agent provides the first input scenario. Without loss of generality, the agent is located at place p1 and it expresses a regular-refresh behavior specified by the parameters A (refresh strength) and T (refresh rate). The agent provides the only external input.

Because of the sequential nature of the topology, the strength at p1 is only changed by the external input from the agent. No additional strength comes through spatial propagation. As far as s1 is concerned, the situation is the same as in the previous single-place one-agent regular-refresh scenario. Bi denotes the fixed point in the sequence of the strength values at the place pi. For p1 the fixed point is given by B1 = A/T/(1-E).

Consider s2(t), the pheromone strength at the next place in the sequence. There, the refresh by the agent at p1 arrives through one step of spatial propagation weakened by the multiplication with F, the propagation parameter (Figure 3.10).


58

Figure 3.10. Diminished Effects of Distant Refreshes

Extending the argument to the other places in the sequence, the equilibrium at an arbitrary place in the sequence is predicted as:

(3.35)

Exemplary for multi-agent scenarios in a sequential topology, a two-agent scenario is considered. The first agent resides at place p1, whereas a second one is located a different place px, . Both agents exhibit the regular-refresh behavior specified by the parameter A and T.

The strength at the places { p1, ..., px-1 } evolves towards the equilibrium given by equation (3.35). The remaining places { px, ..., pn } also receive input from the actions of the second agent.

At place px, the external input from the second agent directly affects the pheromone. Additionally, it receives the propagated input from the first agent reduced to Fx-1*A/T. Hence, the equilibrium at px is given by . The prediction of the equilibrium at an arbitrary place is:

(3.36)

In the same way any other multi-agent scenarios in a sequential topology may be analyzed. There remains no restriction on the position of the agents or on their respective regular-refresh behavior.

3.2.3.2.2 Cyclic Topology

With the analysis of sequential topologies completed, the next step is to analyze topologies with loops. Within such loops, spatial propagation of one input event is repeated infinitely.

Let <Pcyc,Ncyc> be an environment. The environment represents a single loop of n places ( , n>1) if the following two statements hold:

The pheromone strength at a place is denoted by si, and as in sequential environments pheromone strength is not split during propagation to neighbors in a single-loop layout.

Consider one agent located at place px. With all places being part of the loop it does not


59

make a difference where the agent resides. As in most of the previous scenarios, the agent exhibits a regular-refresh behavior of an average strength A/T. Following the definition of the spatial propagation of an input event in the formal model, it takes n units time for an input event to be propagated around the n-places loop. During a one-loop propagation the refresh strength is reduced to Fn*A/T.

In Figure 3.11 an example for the cyclic propagation of one refresh event in a three-place (n=3) topology is given.

Figure 3.11. Infinite Cycles of one Refresh Event

When considering the equilibrium, large values are assumed for t. Thus r(t,px)+q(t,px), the aggregated input to the place of the agent, is approximated by (A/T)/(1-Fn). All other places receive the input weakened by the propagation from px. Hence the following equation gives the equilibrium for each place in the loop:

(3.37)

3.2.4 Multi-Pheromone Analysis

The formal model does not provide any extra support to analyze agent scenarios with multiple pheromones. For each pheromone one model must be instantiated. In a multi-pheromone scenario all models share the same set of places, and each two models either have the same propagation relation, or the relations are inverse to represent upstream and downstream links.

To discuss the strength of different pheromones at the same place, input patterns to all pheromones and all places are defined first. In the discussion, the whole set of pheromones or just a subset is considered. The collection of all pheromone strength values at one place in a multi-pheromones scenario is called the mix at the place. Subsets of the pheromones are considered in sub-mixes.

Mixes or sub-mixes of pheromones are analyzed when the ratio of their strength values transmits application specific information. Then, there is information in the absolute and in the relative pheromone strength. In most applications it is only a sub-mix of pheromones jointly transmitting some data.

As an example for the transmission of data in a mix of pheromones the communication of the current mix of agent-states is considered. Assume that there are n different pheromones { g1, ... ,gn } managed in the PI. The mix of these pheromones is evaluated at a singular place ps in the environment (no propagated input).

Let there be a set of n arbitrary agent-states Z = { zi: 1=1..n }. Each agent located at ps is


60

in one of these states. Assume that there are agents in state zi. An agent in state zi refreshes the pheromone gi regularly. The refresh behavior is governed by the global parameters A (refresh strength) and T (refresh rate), which apply to all agents.

For each pheromone, a separate formal model is constructed. On the basis of the model, the fixed point of the pheromone strength at ps is predicted. Let Ei represent the evaporation parameter of pheromone gi and furthermore, let Bi denote the equilibrium of pheromone i at ps given by:

(3.38)

With the additional requirement fulfilled, the relative number of agents in state zi at any time is represented in if the pheromones have reached equilibrium.

3.2.5 Load Balance - A Real-World Example

The problem at hand is the control of an inflow of agents into a place. A similar problem arises for the guided manufacturing control system presented in Chapter 4.

The environment of the PI comprises two places, p1 and p2 (Figure 3.12). The places are linked and p2 is the downstream neighbor of p1. The example considers one pheromone type called “Resistance“ that carries no additional data-slots. Hence, there is only one “Resistance“-pheromone. PR denotes the pheromone in the following. The propagation direction of PR is upstream. The formal model for PR specifies an evaporation parameter ER and a propagation parameter FR.

Figure 3.12. Problem Description

There is a flow of mobile agents passing downstream through the PI. Each mobile agent first enters the capacity restricted place p1. The restriction states that there must never be more than c ( ) agents located at p1 in a unit time. After leaving p1 each mobile agent enters p2 and then moves out of the scope of the example. Without a capacity restriction, the strongest possible inflow into p1 would be n ( ) agents per unit time. It is the goal to reduce the load of p2 to g ( ) agents per unit time.

The following assumption on the decision process of the mobile agents enables a pheromone-based control of the flow. The mobile agents are known to sample the strength of PR at p1 (sR(t,p1)). On the basis of the current strength, each agent decides either to pause


61

or to move on as described in the following agent procedure:

  1. Sample the strength of PR at p1 (sR(t,p1)).
  2. Probabilistically decide to pause or to continue, biased by sR(t,p1). The probability to pause (P) is computed as:
  1. If the decision is in favor of moving on, continue to p2, else go to step (1) in one unit time.

The “Resistance“ pheromone provides the means to control the strength of the outflow at p1, which is at the same time the inflow into p2.

3.2.5.1 Capacity Restricted Flow

Assuming an infinite capacity at p1, there may be an infinite number of agents present at the same time. Further assume a fixed probability P for each mobile agent to remain at p1 for one unit time.

In the beginning, p1 is assumed to be empty. Then, there arrive n agents in the first cycle. Applying the probability P, n(1-P) agents leave and nP agents stay. The next n agents join these nP agents. Then there are n+nP agents at p1. Out of this group (n+nP)(1-P) agents leave and (n+nP)P agents remain. Taking the argument to infinity ( ) sees agents leaving and agents remaining in one cycle. Reducing these expressions reveals that the flow of agents out of p1 approximates the inflow of n agents. The number of agents remaining at the place in one cycle stabilizes at . When the next n agents arrive, n/(1-P) agents have gathered at p1.

The discussion concludes in the following statement: With a capacity-restriction higher than n/(1-P), the flow of agents through the place is only delayed in time but not restricted in strength.

In a second step a capacity restriction of is assumed. The assumption results in the following requirement on the inflow strength: . The requirement is also motivated by the following discussion. Assume a maximally filled place p. Of the c agents available, c(1-P) agents leave and cP agents remain. To sustain the further outflow of c(1-P) agents, another c(1-P) agents have to arrive in the next cycle. Then, p1 is filled up again.

The final conclusion is: With an unrestrained inflow n greater than c(1-P), the outflow depends on c and P alone. Thus, influencing P if c is known controls the flow.

3.2.5.2 Predicted Flow Control

One stationary agent located at p2 realizes the flow control. The agent knows the flow-restriction goal g and the capacity of p1. With the ability to influence the strength of the “Resistance“ pheromone at p1 the agent is able to compute its own optimal refresh behavior on PR at p2 to fulfill the goal (Figure 3.13).


62

Figure 3.13. Solution to the Load-Balance Problem

The outflow c(1-P) out of p1 has to equal g to restrict the inflow at p2 to g. Therefore, the individual probability to pause must be set to P=1-g/c. Since P depends only on the strength of PR at p1, the pheromone strength has to be set to .

It is not possible to set the strength of a pheromone to a specific value. But, it is possible to regularly refresh it so that it stabilizes near the required value. From the previous analysis of the PI it is known that a regular refresh by a strength of A every unit time results in a fixed point of A/(1-ER) in the sequence of the strength values of PR at the place of an agent.

The one-step propagation from the place of the stationary agents (p2) to the place where the mobile agents read the pheromone is taken into account. The regular input strength required to get sR(t,p1) to stabilize at the optimal value is computed by:

(3.39)

Thus, the stationary agent is able to reach its goal of a required inflow restriction without being able to actually perceive the inflow at p2. It does not even have to know the unrestricted inflow into p1. It only needs to know the static capacity value of p1 and the probabilistic description of the behavior of the mobile agents.

3.3 Implementing the Pheromone Infrastructure

The following section presents a distributed implementation of the PI. The implementation is application-independent since the PI is part of the runtime environment of the multi-agent system of an application. Many of today's runtime environments already provide a communication infrastructure to their agents. But, there is no specific support for pheromone-based coordination mechanisms. To realize a pheromone-based multi-agent application in one of today's runtime environments, it is necessary to implement the PI as an agent system too.

Two practical extensions to the PI that are not covered by the formal model are introduced first. Then, the agents realizing the infrastructure are presented. Finally, requirements to the agent runtime environment are discussed.


63

For the remainder of the thesis, the propagation of an input to a pheromone is simply called propagation of the pheromone. In the implementation, where a pheromone is an instance of a software object, propagation is actually the transfer of such a pheromone instance.

3.3.1 Two Practical Extensions

The formal model presented in Section 3.2 is designed to facilitate the analysis of general features of the PI. Practical considerations lead to extensions of the infrastructure only introduced in the implementation, but not in the model. The extensions increase the ability of the PI to actually process information. Agents in the application could also realize automatic manipulation and the generation of specific views on the information. But, facilitating these operations right in the infrastructure reduces the costs of information processing and increases the applicability of the approach to a wide range of problems.

3.3.1.1 Direction Specific Aggregation

The first extension concerns the propagation of pheromones. Often it is necessary to know at a place from what neighbors a pheromone had been propagated. At a place with multiple upstream or downstream neighbors, from each neighbor an input could have been propagated to the place.

In the implementation of the PI, all pheromones carry a data slot “direction“. The value in the slot is changed during propagation from one place to the next. At each place px, the value in the “direction“ slot of a propagated pheromone is set to a reference to px. Thus, upon arrival at the neighbors, only the pheromones propagated from the same place aggregate. The different values in the “direction“ slot may be interpreted as additional local specifications of a pheromone type.

Agents may selectively sample the strength of a pheromone for the whole place, or specific for each neighbor of the place. Thus the set of all (upstream and downstream) neighbors of a place may be considered in terms of places where the pheromone had been propagated from, and in terms of those from which no propagation occurred.

3.3.1.2 Application Specific Filtering

The second extension of the PI in the implementation introduces an automatic application-dependent change of pheromones during propagation. The filtering mechanism is very powerful as it departs from the notion that different pheromones do not interact in the PI.

The simplest case of application-specific filtering is given when the propagation of a pheromone is blocked depending on the presence of specific agents at a place. In this case, arriving propagation still changes the local strength values. But the pheromone is not propagated any further regardless of the availability of neighboring places.

The propagation of a pheromone may be inhibited by other pheromones. There could be threshold values to the strength of inhibiting pheromones specified: If the strength of these pheromones is stronger than a threshold value, the propagation is blocked. A continuous version of the filtering mechanism specifies an inhibition function that reduces the


64

propagated strength (in addition to F) depending on the local strength of the inhibiting pheromones. Inverse to the inhibition of propagation, the propagated pheromone strength could be reinforced through the local presence of other pheromones.

Finally, the arrival of a propagated pheromone may trigger the generation of other pheromones. Thus, an actual input to a pheromone x could trigger a virtual input to a pheromone y further down.

The application-specific filtering may be realized by local propagation rules that are executed at arrival or departure of the propagated pheromones. A direction specific aggregation as introduced in the previous section may be realized by such a departure-rule too.

With the introduction of local changes to the propagated pheromone strength, the results gained in the analysis of the formal model do not apply to the implementation as such. Especially the reinforcement of the propagation puts the general stability of the infrastructure at risk. Application programmers have to be careful when applying propagation filters.

The implementation of the PI allows the application programmer to define two sets of filters specific for each pheromone type. The first set is applied to incoming propagation events. The second set applies to outgoing propagation. The order, in which the filters of each set are applied, may be specified as well.

3.3.2 Agent-Based Implementation

The agent-oriented implementation of the PI is message-based and event-driven. Each place of the infrastructure is represented by a Place-agent. The computations required to operate the infrastructure may be distributed over a network of processing nodes in the same way the agent system of an application is distributed. The agents of an application interact with this part of their environment as they may interact among themselves.

In the following, a Place-agent and its place are used as synonyms. Furthermore, the general use of “agent“ stands for the agents of the actual application in distinction to the Place-agents, which are “just“ part of the runtime environment of the application.

3.3.2.1 Knowledge and Responsibilities

Each Place-agent has the references to all its upstream and downstream neighbors. The knowledge is stored in the topology management of the agent.

To get access to a place in the PI, the agents of an application register with the respective Place-agent. All agents registered with a place are stored in the local agent management. Only agents registered with the place may request its services.

A Place-agent manages pheromones. For each pheromone type of an application, the pheromones are stored and evaporation and propagation is realized. The registered agents are permitted access to the pheromones. A software object represents a pheromone type in the infrastructure. The object has value slots for the data of the pheromone type, and for the strength and the direction. The methods provided by the object realize the evaporation mechanism and the access to the data of a pheromone.


65

A Place-agent implements the pheromone evaporation asynchronously in an as-needed fashion. The continuous change of the pheromone strength is triggered by events. Reducing the computational load on the infrastructure, the current strength value is computed only when a new input to the pheromone arrives or when an agent samples the pheromone.

The access to a pheromone is pattern-based. For each pheromone type patterns may be defined that constrain the matching values in a data slot. Also, an open match to any value (“don‘t care“) may be specified in a pattern. The match is realized in methods of the software object of the respective pheromone type.

Figure 3.14. The Structure of the Knowledge of a Place-agent

Not every possible pheromone for each pheromone type is present in the pheromone management of the Place-agent. Reducing the precision of the implementation in comparison to the formal model, each pheromone type specifies a positive threshold value “precision level“. A Place-agent erases a pheromone from its pheromone management when the absolute value of the strength has fallen below the threshold. The same threshold halts further propagation of a pheromone.

A Place-agent applies all filters in the propagation of pheromones. The filters come in filter-objects, programmed by the designer of the application.

Figure 3.14 illustrates the structure of the knowledge of a Place-agent.

3.3.2.2 Service: Access and Topology

Before an agent may request any of the services of a place, it first has to register with the Place-agent in a “RegisterAgentForPlace“ message. The message takes the reference to the agent and its type. The Place-agent stores the data and checks if any notifications (see „Service: Notification“ in this section) result from the registration.

An agent should be registered with only one place at a time. To gain access to services of another place, the agent deregisters from its current one. A message “DeregisterAgentFromPlace“, containing the reference to the agent, is sufficient. Upon receiving the message, a Place-agent again checks for resulting notifications.

If an agent is registered with a Place-agent, it may request the local topology information. The message sent in reply to “RequestTopology“ contains the references to all the neighbors of the place and an indication if the neighbor is upstream or downstream. Thus, the agents may maneuver through the PI dynamically.


66

3.3.2.3 Service: White Pages

The PI sets up a spatial structure to the multi-agent system. The system is dynamically split into groups of agents according to their current mapping to places. To support a spatial structuring of potential direct agent-to-agent communication, agents should only communicate directly inside their place.

A simple way of realizing the restriction of direct communication is to refuse the agents any system-wide White Pages service. In dynamic multi-agent systems any communication is thereby disabled since an agent needs a reference to its potential partner to send a message. Without a global White Pages service, a local service provided by the respective Place-agent still enables local communication. It is up to the designer of the application to ensure that departing agents do not take the locally received references with them.

The White Pages service is accessed with a “RequestAgents“ message. In reply a place sends the set of references to the currently registered agents and their application-types.

3.3.2.4 Service: Pheromones

An agent registered with a place may generate an input to a pheromone by sending a “PutPheromone“ message to the place. The message contains an instance of the software object that represents the pheromone type. All data slots are set to specify the pheromone. The “strength“ slot is set to the strength of the input. The “direction“ slot is initialized with a reference to the agent that generated the input.

Upon arrival of a “PutPheromone“ message, a Place-agent extracts the pheromone from the message. If the pheromone is already present in the pheromone management, the strength of the newly arrived pheromone is added to the (correctly evaporated) strength of the managed pheromone. The aggregation only applies to pheromones with all but the “strength“ slot set to the same value. A difference in the “direction“ slot already prevents an aggregation.

If there is no managed pheromone matching the new pheromone, it is put directly into the pheromone management.

If the propagation parameter of the respective pheromone type is not zero, propagation to the neighbors of the place commences. On the basis of the propagation direction of the pheromone type, the Place-agent first determines the set of neighboring places, to which the pheromone is to be propagated. In a second step, for each neighbor a new pheromone is created. The strength values are set according to the weakening by the propagation parameter and the division by the number of neighbors (Equation 3.1). After all relevant filters have been applied, the pheromones are sent to the neighboring places, again using the “PutPheromone“ message.

“PutPheromone“ messages arriving from agents and not from other places may trigger the notification of local agents.

The registered agents may also access the locally managed pheromones. A “GetPheromones“ message contains patterns. The Place-agent determines all currently available pheromones that match the patterns. For each matching pheromone a copy is created, which carries the current strength and the additional data. The resulting set is sent to the agent, from which the request came.


67

Compared to the other data slots, the “direction“ slot in a pattern is handled differently in the matching process. If a specific direction (reference to a place) is set in a pattern, only completely matching pheromones are selected. But, if any direction is accepted, all pheromones matching the other slots are selected first. Then, the strength of the pheromones is added up. The “direction“ slot of the resulting aggregated pheromone is set to a reference of the local place.

3.3.2.5 Service: Notification

Most pheromone-based agent algorithms specify agent activities in response to specific events in the PI. Such events are the arrival or departure of agents, or an input to a pheromone.

Agents registered with a place may request a notification in case of the occurrence of specific events. The messages “RegisterForAgentEvent“ and “RegisterForPheromoneEvent“ enter an agent in the notification management of the place. The agent type and whether an agent arrival or departure is expected specifies a notification request in case of agent movement. The type of the pheromone specifies a notification request in case of an input.

The notification is given using the “AgentEventOccured“ and “PheromoneEventOccured“ messages. The messages specify the event occurred, giving reference to the actual agent, or containing the generated pheromone respectively.

A place handles the respective deregistration messages too.

Figure 3.15. The Services of the Place-agent

The messages sent to a Place-agent to request its services are shown in Figure 3.15.

3.3.3 The Agent Runtime Environment

The agent-based implementation of the PI assumes features of the agent runtime environment that concern the internal architecture of the agents, the communication infrastructure, and the execution capabilities. Furthermore, there are features required for an effective execution of real-world sized applications.

It is assumed that the internal agent architecture supports reactive agent behavior. A Place-agent is never proactive. It only reacts to the incoming requests. Since a Place-agent does not have any physical abilities in the real world (sensors, actors), its reactiveness is


68

directed towards inter-agent communication only.

The second assumption taken is the ability of an agent to handle internal data. It is not just required that the agent may operate on large sets, it has to cope with sets of variable size too. It is assumed that the internal data management is object oriented, operating on object hierarchies defined by the programmer of the application.

The chosen message-based implementation of the interface between the agents and the PI requires a fast and efficient agent-to-agent communication. Sending a message has to be “cheap“ in terms of transmission time and resource usage.

It has to be assumed, in a general-purpose agent runtime environment, that there is a homogeneous address-space where each agent is uniquely referenced. In principle it has to be possible to communicate with any agent, regardless of the location of its processing node. The distribution of the agent execution to several processing nodes should be transparent on the reference-level.

Messages sent among agents have to carry software objects and sets of objects. The designer of an application defines these objects. During communication not a reference to an object, but the object itself is transmitted. Thus, the receiver really owns the received object by having the sole reference to it.

In terms of execution capabilities the ability of the runtime environment to handle many lightweight agents is assumed. The assumption states a general requirement in pheromone-enhanced synthetic ecosystems. It does not just hold for the specified implementation of the PI. Real-world sized applications may comprise hundreds or even thousands of agents.

Following a pheromone-based approach in real-world sized agent systems also requires a specific structure of the distribution of the agents to processing nodes. The same processing node should execute agents located at the same place in the PI. With the restriction of direct agent-to-agent communication to interactions where both agents are registered with the same place, the global bandwidth needed in the execution of the system is drastically reduced, assuming that communication on one processing node does not take up any actual bandwidth on the network (re-using bandwidth).

With the aim to have agents of the same place executed at the same processing node, the execution of agents has to be mobile if the agents themselves are mobile too. An agent may deregister from its current place at any time and register with another place. If the agents at the new place are computed at a different processing node, then the virtual movement in the PI should be mirrored in an actual change in the distribution of the agent system. The requirement holds especially for fielded applications, operating in real-time.

The PI implemented by Place-agents has been realized prototypically in the JAVA-based system DARE (“Distributed Agent Runtime Environment“) of the Multi-Agent Systems department at DaimlerChrysler AG - Research and Technology 3. DARE provides all the presented requirements except the dynamic relocation of the execution of agents. Using a general implementation of the PI, it was possible to evaluate the results of the formal analysis in different scenarios. The guided manufacturing control system, presented in Chapter 4, is implemented on the basis of DARE and the Place-agents too.


© 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