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

69

Chapter 4. Guided Manufacturing Control

Chapter 4 presents a stigmergetic synthetic ecosystem for manufacturing control. In the design of the system the design principles (Section 3.1) have been followed. The pheromone infrastructure is deployed to support the implementation, the tuning, and the evaluation of the software system (Sections 3.2 and 3.3).
First, Section 4.1 introduces the chosen manufacturing control domain and derives the spatial structure of the agent system. Then, the components of the software architecture are listed. These components, the sub-systems and their internal layers, are presented in the remainder of the chapter.
The reactive layer of the control sub-system is presented in Section 4.2, the tasks and agents of the singular interface layer are specified in Section 4.3, and Section 4.4 introduces the strategy implementation layer of the advisory sub-system. The resulting system-level behavior is discussed in a small but realistic demonstration in Section 4.5 where all the previously presented components are evaluated.

4.1 Domain, Structure, and Architecture

On the basis of the rationales for holonic manufacturing as they are presented in the background Section 2.2.2, the agent system presented in the following combines distributed and reactive control with optimization according to global production goals. The combination is achieved bottom up, leaving the decisions that directly change the physical environment to the localized control, but guiding it with advice given under explicit global consideration. Hence, the agents make up a guided manufacturing control (GMC) system.

The GMC system is designed for flexible flow shops (Section 2.2.1) in industrial mass-production. The most important characteristic of a flexible flow shop is that of all possible material flow patterns only a very small sub-set results in a globally optimal performance of the production process. The current optimal sub-set of flow patterns strongly depends on the situation in the manufacturing system and it usually cannot be determined beforehand.

There is a specific flexible flow shop, onto which the GMC system is primarily designed: the final steps of painting passenger cars at the Mercedes-Benz car plant of the DaimlerChrysler AG in Sindelfingen (Germany) provide the application background. Manufacturing specific design decisions have been taken to fit this flow shop and the demonstration and evaluation in Section 4.5 is based on a segment that is characteristic for the paint shop. Therefore, to give an understanding of these characteristics, the paint shop is briefly introduced first.

4.1.1 The Paint Shop

Figure 4.1 plots a process graph that applies to car bodies, passing the last two processing steps in the paint shop in the plant. Structurally, the process graph is similar to those of other paint shops in the automotive industry.


70

Figure 4.1. Process Graph of the Paint Shop Segment

The last two steps in the painting of car bodies require the highest flexibility. First, the cars have to successfully pass “Basic Layer Painting“ (BLP) and then they have to get through “Final Layer Painting“ (FLP). Whereas BLP paints only three different types of basic color (light, medium, dark), the FLP process provides a choice of more than twenty colors in an automated painting process.

A car entering this section of the manufacturing system represents a specific order already and hence the required final color is fixed. There is a relatively small set of frequently occurring colors, but most colors are seldomly requested. The volume and the mix of orders always change with the changing demand on the market.

The complexity of the considered manufacturing control problem stems from the cyclic character of the process graph of a car. Not every painting process is successful. Most cars emerging from the exit of a BLP unit are permitted to go on to one of the FLP units. But some have to get a “Basic Layer Grinding“ job performed and then they must reenter a BLP unit. The relative strength of these different output streams over a fixed period defines the yield of a BLP unit.

A FLP unit has a yield too. Successfully painted cars may leave the system. But the other cars require repair tasks like “Spot Repair“, “Repair Preparation“, “Final Layer Grinding“, or even “Heavy Repair“. Except cars emerging from a “Spot Repair“ unit, all these cars reenter the FLP units after the repair task.

To provide capacity, flexibility, and redundancy, there is always more than one processing unit able to perform the required processing step. It is the task of the control system to make efficient use of the available flexibility. A highly connected layout of the transport system linking the processing units supports the effort.

The transport system in the BLP and FLP segment of the paint shop comprises standardized stationary transport elements. Currently, there are more than 500 elements of different types, mainly conveyors and lifts. With the exception of the sorting buffers, which provide random access to create batches of cars of the same color, all buffers are just specific zones in the transport system made up of standard transport elements.


71

4.1.2 The Spatial Structure

First, the layout of the virtual space where the agents of the GMC system operate in is defined. The layout is represented in the PI and it is derived from the spatial structure of the underlying manufacturing system, which comprises transport elements, processing elements, and workpieces. In the paint shop transport elements are lifts, conveyors, and rotation tables, whereas processing elements are paint-booths, dryers, and other processing stations. With the focus on the material flow, the model does not represent single robots, tools, or human workforce. Every car is considered one workpiece.

The space of the manufacturing system is divided into elementary zones. A zone either covers transport elements making up buffers or crossings in the material flow, or it mostly contains processing elements and thus aggregates elementary processing steps into one abstract step. In addition, there are small-sized zones, containing loading or unloading machinery. These are the physical interfaces to the world outside of the manufacturing system.

Each elementary zone is connected to other zones in the material flow. These connections are either entries (material coming in) or exits (material sent out). The following restriction to the allocation of elementary zones holds: A zone containing processing elements is only reached through one entry and it has only one exit. The restriction supports the identification of zones where transport decisions are taken, and of zones where processing tasks are fulfilled.

Additionally, elementary zones without entries are only permitted to have one exit, and those without exits must have one entry only. Hence, there are no routing decisions taken in the loading and unloading zones.

The layout of the PI is specified in a one-to-one mapping of the elementary zones to places. The links among these places are set according to the connections of the zones. The downstream direction of a link is the direction of the material flow from the exit of one zone into the entry of the next one. In Section 4.5 the identification of elementary zones in a manufacturing system is discussed on the basis of the paint shop.

4.1.3 The Architecture

Illustrating the following presentation of the system architecture, in Figure 4.2 the structure of the system is shown, marking where agent types are introduced in the bottom-up specification and also, where their behavior is extended. The illustration starts with the bottommost part of the system, the PI and its Place-agents. It only includes the components presented in Chapter 4.

The PI constitutes a part of the environment of the agents of the GMC application. It provides the means for indirect communication and automated aggregation of data in an active environment to realize stigmergetic multi-agent coordination. As it is discussed in Section 3.3.2, the PI is implemented as a multi-agent system sharing the runtime environment with the agents of the GMC application.


72

Figure 4.2. Components and their Agents

The GMC systems architecture is specified from bottom up. Structuring the major functionalities, the architecture comprises two sub-systems, one of which provides reactiveness and flexibility while the other one adds optimization based on the production goals. Accordingly, the first sub-system is called the control system and the second one is the advisory system.

Both sub-systems may in turn comprise several layers. Restricting the following specification to basic functionality only, the reactive layer of the control system and the strategy implementation layer of the advisory system are presented and evaluated in detail. Concepts for additional layers of the advisory system and for a third sub-system are discussed in Chapter 5.

An interface layer links the two sub-systems. It does not provide any additional functionality to the (human) operator of the GMC system, but it facilitates the operation of the advisory system by aggregating information and it incorporates advice into the control system.

The components of the GMC system contain a large number of agent types. In the bottom-up specification for each agent type there is one layer where its basic functionality is defined. At higher levels of the architecture (layers or sub-systems) the basic functionality of an agent may be extended to provide additional services.

There is a minimal configuration of the GMC system. The reactive layer of the control system alone is already sufficient to operate the manufacturing system. It guarantees that every workpiece sent into the system is eventually processed according to its requirements. The other layers and sub-systems only provide optimization of the basic operation without compromising the fulfillment of hard constraints.

4.1.4 Performance Evaluation

Before the structure and the mechanisms of the GMC system are presented in more detail a short remark on the evaluation of the performance of a new manufacturing control system should be made. Later sections propose an approach to model and analyze the agent system that eventually may provide qualitative or even quantitative predictions of the emerging system behavior. But in general today's manufacturing processes are much to complex to be formally modeled in the required granularity.


73

The only alternative to formal modeling short of physically installing the control system on the factory floor is to create a realistic simulation model of the desired production processes to which a manufacturing control system may interface. In a first step of the evaluation process, an implementation of the current control approach should provide the baseline against which every new approach has to measure up. This step is only feasible if the production process can still be handled by conventional manufacturing control systems. Completely new processes might mandate new control approaches.

In the following steps, instantiations of the new control system are linked to the simulation. In all simulation runs the same performance indicators are observed and protocols of their value over time are created. Performance indicators of the production process are for instance local and global throughput values, the load of processing stations and buffers, or the work in progress (WIP) and its composition in the system. The evaluation should not be restricted to production performance parameters alone. Performance parameters of the control system, like computation and communication load or required human interference, and the required effort for the design, implementation, tuning, and maintenance of the system should be included into the evaluation.

4.2 Control System: The Reactive Layer

The reactive layer of the control system is the core of the GMC system. Therefore, it is responsible for the fulfillment of all hard constraints for the production operation. The agents of the layer enable the manufacturing of products. There is no optimization implemented into their basic functionality.

The agents making up the reactive layer are identified on the basis of the layout of the PI following the PROSA reference architecture (Section 2.2.3). They are introduced in terms of their responsibilities, their knowledge, and their behavior. The specification of the reactive layer concludes with a high-level integration of the behavior of the agents.

4.2.1 Entities and their Behavior

The PROSA reference architecture suggests three basic agent types for manufacturing control: the Resource-agent type, the Order-agent type, and the Product-agent type. Resource-agents represent the resources of the manufacturing system, controlling the physical handling of the workpieces. Order-agents are identified with requests to the manufacturing system. Product-agents provide process knowledge for the different product variants produced.

The specific Resource-agent types are derived from the structure of the PI and the characteristics of the underlying elementary zones. There is exactly one Resource-agent for each place.

Loader-agents map to places whose zones contain the loading machinery, and there are Unloader-agents at places of the unloading machinery. These places either have only one exit (Loader-agent) or one entry (Unloader-agent). Transport decisions are taken at places with multiple entries or multiple exits. These places are occupied by Switch-agents, routing the material flow from the entries to the exits. Finally, Processing-agents are located at places where processing elements dominate the elementary zone. A Processing-agent represents an aggregated processing step taken while a workpiece passes its zone.


74

Each Resource-agent has complete control of all its local elements of the manufacturing system. Local elements are located in the elementary zone that is mapped to the place of the agent.

In the paint shop an order to the manufacturing system maps to exactly one workpiece (car). Hence a Workpiece-agent is an Order-agent. Other applications with complex orders (e.g. in assembly) might require the introduction of an aggregation of Workpiece-agents into higher-level Order-agents.

Each Workpiece-agent has a place in the PI determined by the physical location of the workpiece of the agent. The elementary zones represent a clear-cut subdivision of the manufacturing system and thus the position of a workpiece always coincides with exactly one zone. The place mapped to the zone is where the Workpiece-agent resides. As a consequence, each Workpiece-agent always occupies the same place as the Resource-agent handling its workpiece. Hence, direct interaction may commence without compromising locality.

The reactive layer does not include any specific Product-agents, restricting the GMC system to applications with only a relatively small number of product variants and slowly changing processes. The paint shop fits these restrictions. Process knowledge is directly incorporated into the Processing-agent and into the Workpiece-agent. They share the responsibilities of a Product-agent.

Figure 4.3. Reactive Layer Agents as Derived from PROSA

Figure 4.3 illustrates the agent types of the reactive layer with their responsibilities derived from PROSA. In the following, each agent type is presented, specifying its responsibility, its knowledge, and its behavior.

4.2.1.1 The Loader-Agent Type

A Loader-agent represents a physical entry into the manufacturing system. Through the entry workpieces are loaded into the transport system. It is assumed that the GMC system is able to decide when a workpiece is loaded and that the Loader-agent may select the next workpiece according to a specific product or variant.

The inflow at the entry is specified by two parameters: the product mix and the volume of inflow. A Loader-agent may influence both in its loading operation by varying the products and the moment they enter the system. The behavior of a Loader-agent is specified by the following cycle:

  1. Select next product.
  2. Attempt to load the respective workpiece.

    75

  3. If the attempt was successful, create a Workpiece-agent and hand over the responsibility for the loaded workpiece.
  4. Wait in accordance to the current loading rate and then restart at step one.

The loading of a workpiece may fail for two reasons: Either the exit of the loading machinery is blocked, or there are no workpieces of the required product available.

There is no interaction between the Loader-agent and other agents besides handing over of the responsibility for the workpiece. All decisions are taken by the Loader-agent alone, based on static information available to the agent.

4.2.1.2 The Switch-Agent Type

A Switch-agent is responsible for one elementary zone in the transport system. Its zone has a set of entries and exits and a routing structure in-between. Because of possible internal routing restrictions inside the zone, a workpiece entering the zone through a specific entry has access to only a subset of all exits.

The Workpiece-agent tells the Switch-agent, where to take its workpiece. If such information is not given, the Switch-agent awards a default exit that is specific to each entry.

The activity of a Switch-agent is triggered by two external events. First, there are incoming requests by the Workpiece-agents, registering their workpieces for a transport to a specified exit. The Switch-agent stores the information together with a reference to the agent for a fixed period.

The second trigger-event is the arrival of a workpiece at an entry of the Switch-agent. In this case, the Switch-agent determines the required exit for it. Either the exit is specified in a request previously received by the agent of the workpiece, or the default exit for the respective entry is selected. Eventually, the Switch-agent realizes the physical transport of the workpiece through its zone.

Whenever alternatives in the sequencing of workpieces arise during transport, the selection is taken randomly. Priorities or other additional workpiece parameters are not considered. Alternative internal routes are also selected regardless of the workpieces.

With the arrival of a workpiece at an exit, the task of a Switch-agent is completed. If the Switch-agent knows the agent responsible for the workpiece, it tells the agent the place in the PI the exit is linked to, so that the agent may follow its workpiece in virtual space.

4.2.1.3 The Processing-Agent Type

A Processing-agent is responsible for an elementary zone in the manufacturing system where the processing state of passing workpieces is changed. It aggregates the processing activities in the zone into one abstract processing step, representing the processing ability of the local resources that may be parameterized. The Processing-agent manipulates a workpiece as requested by its agent.

Activities of a Processing-agent are triggered by incoming requests of Workpiece-agents and by the arrival of their workpieces. In a request the Workpiece-agent asks the Processing-agent to apply its processing capability with a given set of parameters to the


76

workpiece. The request is stored together with the reference to the Workpiece-agent. When the workpiece arrives, the Processing-agent knows what processing is to be performed with it.

If a workpiece arrives at the zone of a Processing-agent without having been registered beforehand it is either passed through the zone without being processed. If passing is not possible, the entry remains blocked and the Processing-agent has to handle the internal disturbance of the control system. It could, for instance, try to find out the responsible Workpiece-agent, or it could inform the administrator. Behavior safeguarding stability is required for the fielded implementation and it takes an important place in the design effort. But, it is not essential for the demonstration of the basic functionality and therefore it is not considered here any further.

It is assumed that the Processing-agent is able to sense the new processing state of the workpiece at the end of the processing. When the workpiece has reached the exit, its agent is told the new state and the next place in the PI. The task of the Processing-agent is fulfilled.

Before processing workpieces, the Processing-agent has to attract them first. The attraction is realized by pheromones. The reactive layer defines a pheromone type “Ability“ (PA). Besides “strength“ and “direction“, PA specifies one additional data-slot “ability“ where the processing ability of a Processing-agent is stored. Extensions to the GMC system may introduce additional data-slots, specifying, for instance, parameters to the respective ability. Inputs to PA propagate upstream against the flow of the workpieces. The propagation is stopped one place before the next upstream Processing-agent. The restriction, realized by a propagation filter in the PI (Section 3.3.1), is required to handle cycles in the layout.

Each Processing-agent regularly generates an input to PA pheromones at its place. It refreshes the pheromone matching its current processing ability. These inputs propagate upstream, thereby creating a flow field for Workpiece-agents to follow in case they require the respective processing.

4.2.1.4 The Unloader-Agent Type

The behavior of an Unloader-agent is very similar to that of a Processing-agent. Responsible for one exit out of the manufacturing system, it attracts workpieces. Therefore, it regularly refreshes the PA pheromone that carries “unloading“ in its “ability“ slot.

When a workpiece arrives at the entry of the elementary zone and it is registered for unloading, the agent takes it out of the system. After completion of the unloading process, the responsible Workpiece-agent is informed.

4.2.1.5 The Workpiece-Agent Type

A Workpiece-agent is responsible for one workpiece while it is transported and processed in the manufacturing system. It is created when the workpiece is loaded by the Loader-agent. Its task is completed when an Unloader-agent takes the workpiece out of the system. The decision loop of a Workpiece-agent is depicted in Figure 4.4. It is one continuous cycle with several alternative branches, advanced by the ongoing transport and


77

processing of the workpiece.

Workpiece-agent knows the current processing state of its workpiece. A change in the state is communicated from the Processing-agent that has caused it. The agent knows the process plan of its workpiece because of its Product-agent functionality. But a Workpiece-agent does not plan ahead. Instead, it follows the late commitment philosophy; taking decisions only when they are due while keeping options open as long as possible.

Figure 4.4. The Behavior of the Workpiece-agent in the Reactive Layer

A Workpiece-agent mirrors the movement of its workpiece through the manufacturing system in its moves through the PI. While it moves, it executes the following decision loop, starting with the arrival at a new place:

If it has arrived at a place of a Loader-agent:

  1. Find the only downstream place

If it has arrived at a place of a Switch-agent:

  1. Determine all possible next processing steps from the process plan
  2. Sample PA pheromones specific to the exit-directions
  3. Determine the set of downstream directions, abilities to fulfill one of the next processing steps have been propagated from
  4. Randomly select one of these directions
  5. Request transport of the workpiece into the selected direction from the Switch-agent
  6. Receive reference to next place from Switch-agent after transport was completed

If it has arrived at a place of a Processing-agent:

  1. Determine all possible next processing steps from the process plan
  2. Request all these steps from the Processing-agent
  3. Receive new processing state and reference to the only downstream place from Processing-agent after processing was completed

    78

  4. Update internal processing state

If it has arrived at a place of an Unloader-agent:

  1. Request “unloading“ from Unloader-agent
  2. Receive information about completed unloading
  3. Fulfill any cleanup or archiving task and finish

Move to the next place as determined and restart loop

Following this algorithm, the Workpiece-agent takes local routing and processing decisions based on only locally available information and its internal state. The operation does not require any communication with agents outside of the current place of the Workpiece-agent in the PI. It respects the autonomy and expertise of the Resource-agents.

4.2.2 The Emerging Behavior

The manufacturing system is divided into elementary zones, each controlled by a Resource-agent. There are Switch-agents realizing the transport of workpieces through their zones in the transport system. There are Processing-agents able to transport workpieces too, but their focus is on the processing of workpieces. Finally, there are Loader-agents and Unloader-agents physically interfacing the manufacturing system with the outside world.

The structure of the physical system is mirrored in the PI. For each Resource-agent one place exists where the agent resides. Located at the same place there are the Workpiece-agents representing workpieces in the zone of the Resource-agent. Direct interactions only take place among agents located at the same place.

Whereas the Resource-agents are stationary in the PI, the Workpiece-agents move from place to place. They follow the physical transport of their respective workpiece through the manufacturing system. A movement of a Workpiece-agent is triggered by a notification that the workpiece has been passed on into the next zone. The notification comes from the local Resource-agent.


79

Figure 4.5. The Activities of a Workpiece-agent Trigger Resource-agents

Only zones of Switch-agents have more than one exit. Hence, routing decisions are taken only at the place of a Switch-agent. A routing decision is taken by a Workpiece-agent and then executed by a Switch-agent taking the workpiece to the selected exit. The exit is chosen on the basis of the current processing state of the workpiece, the process plan of the product, and the local flow fields of PA pheromones.

The global routing behavior emerging from these local decision processes takes the late commitment approach to the extreme. Workpiece-agents never actually commit to a processing resource. With every routing step they just reduce their options to those offered by one of the available local directions. The routing mechanism is always open to resources coming on-line or going off-line.

Figure 4.5 illustrates how the behavior of the Workpiece-agent and the transport of its workpiece trigger the activities of the Switch-agent and the Processing-agent. The processes on shaded background are the ones run by Resource-agents. A Workpiece-agent and Resource-agents synchronize in the handling of the workpiece, dynamically creating two-agent teams to fulfill the arising transport and processing tasks.

PA provides local information on the processing abilities of processing resources, separate for each downstream direction of a place. Each downstream direction corresponds to an exit of the respective zone in the manufacturing system. Selecting a downstream direction is equivalent to choosing an exit. When a workpiece has eventually passed an exit, the Workpiece-agent moves to the corresponding downstream neighbor. In Section 4.5.2 the emergence of spatial patterns in PA is discussed in the paint shop demonstration.

Evaporation of PA pheromones guarantees that a change in the availability of downstream processing resources eventually becomes known at the relevant places in a change of the local flow field. The dynamics of these changes and the constraints of the manufacturing system have to be taken into account when the evaporation parameter of PA and the refresh behavior of the Processing-agents and the Unloader-agents are tuned.


80

Information is lost too fast if evaporation is too strong. The Processing-agents and the Unloader-agents have to spend a lot of resources to keep the required attraction of workpieces sufficiently strong. On the other hand, if PA does not evaporate fast enough, too many workpieces might be attracted into the wrong direction. The delay in communication is extremely critical if a processing ability is permanently lost and the zone of the respective Processing-agent does not permit a workpiece to pass unchanged.

The formal model of the PI (Section 3.2.1) provides the means to tune the parameters according to the specific requirements of the underlying manufacturing system. There are results available providing predictions of fixed points in the local strength of a pheromone and the time required to reach them in specific layouts and under specific input patterns.

A Workpiece-agent takes probabilistic routing decisions. First, the set of permitted downstream directions is determined. These are all directions where a flow field of a PA pheromone exists that matches one of the required next processing steps. The selection of a permitted exit is random - an interfacing point for additional layers of optimization. Instead of an equal chance for all permitted directions, the choice might be weighted according to probabilities provided by additional reasoning. Statistically, the material flow splits and merges evenly as long as there is no congestion. Other flow-patterns are achievable with additional influence on the routing decisions. The advisory system attempts to set such an influence.

4.3 The Interface Layer

In-between the control system and the advisory system there is the interface layer. It is the task of the interface layer to collect information about the control system and to extend the basic behavior of the reactive layer agents to integrate the advice given by the advisory system into the operation of the control system.

The advisory system operates on material flow data, specifically on patterns in the flow of workpieces through the manufacturing system. A pattern combines sets of load values that are specific for a processing state at each elementary zone in the manufacturing system at a given time. The load is the number of workpieces in a given state present at a zone at that time.

The emergence of a material flow pattern depends on the inflow into the system, the currently available processing capabilities of the resources, and the yield of their processing actions. Furthermore, the routing decisions taken by the Workpiece-agents strongly influence a pattern. The interface layer has to create two patterns for the advisory system: the current material flow pattern, and a prediction of the pattern in the near future. The first part of the following section focuses on the generation of these two patterns.

Advice generated by the advisory system must be transmitted to the control system and integrated into the decision processes. The second stage of the presentation of the interface layer discusses how the agents of the reactive layer are extended so that the control system is able to heed the given advice.

4.3.1 Information for the Advisory System

For two reasons it is very important that the interface layer links the two sub-systems only through indirect communication through the PI. First, the advisory system operates on


81

a different time-scale than the control system. Its decision processes run slower because it reasons on aggregated flow data. If the advisory system were coupled with the agents of the control system in direct communication, the generation of advice would have to run on the time-scale of the control system too.

A second reason to decouple the two systems is the preservation of the autonomy and stability of the control system, which is the sole controller of the manufacturing system. The advisory system only provides guidance. It is up to the agents of the control system to heed or to ignore the given advice. Ignoring signs in the environment is much easier to achieve than ignoring direct communication by one interaction partner, which requires complex interaction mechanisms.

4.3.1.1 Emergence of the Current Flow-Pattern

The current load of a zone in the manufacturing system equals the number of Workpiece-agents present at the related place in the PI. It is the task of the Workpiece-agents to update the load information in the environment.

As demonstrateted in the analyses of the formal model, a joint regular refresh behavior of agents located at the same place takes the strength of the refreshed pheromone to a fixed point. The value of the fixed point is proportional to the number of agents (Section 3.2.3). To generate the required pattern, each Workpiece-agent regularly refreshes a specific pheromone.

The interface layer defines a pheromone type “State“ (PS). In the global spatial pattern of this pheromone type, the current flow is captured. PS has one addition data-slot “state“, accepting values from the set of possible processing states of the workpieces. The propagation parameter of PS is zero, preventing any propagation.

All Workpiece-agents follow the same regular refresh behavior. They always refresh the PS pheromone whose “state“ slot is equivalent to the current processing state of the represented workpiece. Each Workpiece-agent generates input events of a strength specified by the global parameter “StateRefreshStrength“. The rate of the input is given by the joint parameter “StateRefreshRate“.

As a consequence of the refresh activity of the Workpiece-agents, at each place the current load specific for each processing state is perceivable in the PS pheromones.

4.3.1.2 Emergent Prediction of the Future

The prediction of the near future is based on a Monte Carlo simulation approach. In Monte Carlo simulations there is a model comprising several probability distributions in a model structure. During the course of the simulation, these probabilities are sampled, following the model structure. The distribution of the simulation results is examined and the more often the simulation is run, the more correctly reflects the observed distribution the modeled system.

In the case of the pattern prediction, the system is its own model. The PI gives the structure of the simulation model, the agents of the GMC system realize the simulation, and the results are again made available in the PI. With the integration of the prediction model into the general operation of the GMC system, the model changes in step with the rest of the system. Furthermore, the prediction is always up-to-date because it is


82

continuously recreated based on the current situation.

The pattern of the material flow is influenced by the processing of workpieces and by the transport decisions of their agents. Predicting a future pattern requires the prediction of processing results and an emulation of routing decisions. These two processes contain the probability distributions for the Monte Carlo simulation, since neither the execution of a processing step nor a routing decision is deterministic. Therefore, these processes have to be sampled repeatedly in the simulation.

A Processing-agent handles the processing of workpieces. For the prediction of the future pattern, each Processing-agent has to predict results of processing attempts. The probable outcome of a processing step is determined by the yield of the resource. Depending on the result, a processed workpiece has to take different routes, resulting in different flow patterns. On the other hand, processing time is not relevant for the short-term prediction of the material flow.

The prediction of processing results is more up-to-date when using a short-term average yield of the processing step instead of a long term one. Therefore, a Processing-agent internally keeps a short floating average of the yield of its processing step.

In its extended behavior specified by the interface layer, a Processing-agent acts on an additional trigger. When the agent receives a request for the simulated processing of a workpiece in a specified processing state, it immediately replies with the predicted outcome. The prediction is probabilistic, determined by the floating average yield of recent processing operations.

The requests for simulation come from Ghost-agents. Ghost-agents are the only genuine agents of the interface layer. They are regularly created by Workpiece-agents. A Ghost-agent emulates a Workpiece-agent in its run through the PI. Right after its creation, the Ghost-agent is a perfect copy of the Workpiece-agent by which it was created. Its internal state equals the current processing state of the workpiece and it is located at the same place as its Workpiece-agent.

A Ghost-agent represents one possible future of its Workpiece-agent and it realizes one simulation run through the Monte Carlo model. Encountering a Switch-agent, a Ghost-agent samples the same pheromones and then it takes a routing decision on the basis of the same decision process followed by its Workpiece-agent. Only, the Ghost-agent does not interact with the Switch-agent, because it does not have a real workpiece to route. After taking the decision it just moves to the next place in the selected direction.

When a Ghost-agent meets a Processing-agent it requests a simulated processing according to its internal state. It immediately receives the simulated new processing state, which it assumes as its new state. Then, the Ghost-agent moves on to the next place.

The run of the Ghost-agent is terminated at a place of an Unloader-agent. To reduce the computational load of the system, each Ghost-agent should be permitted only a small number of moves in the PI before it dies without having encountered an Unloader-agent.


83

Figure 4.6. The Process Graph of the Ghost-agent

Figure 4.6 shows the process graph of a Ghost-agent. As a simulacrum of a Workpiece-agent, the graph of a Ghost-agent is very similar to that of a Workpiece-agent. The transport decision process of a Ghost-agent in the encounter with a Switch-agent is the same one its Workpiece-agent would follow. For more details on the actual decision see Figure 4.8.

Workpiece-agents jointly generate a representation of the current flow pattern by regularly refreshing PS pheromones according to their current processing state. Similarly, the interface layer defines a pheromone type “Prediction“ (PP), to which only Ghost-agents provide input. As PS, PP has one additional data-slot “state“, carrying an element from the finite set of processing states. The propagation parameter of PP is zero as well.

In contrast with a Workpiece-agent, a Ghost-agent never stays long enough at one place to generate an input with significant regularity. As a consequence, Ghost-agents only refresh a PP pheromone once at each place visited. The affected pheromone matches the internal state of the respective Ghost-agent. The strength of the input is specified in the global parameter “GhostRefreshStrength“. Regularity of the refresh at one place is provided by the regular creation of Ghost-agents by the Workpiece-agents in the Monte Carlo simulation. The rate Ghost-agents are created with by a Workpiece-agent is set by the global parameter “GhostCreationRate“. Workpiece-agents run an additional process in a closed loop, creating a Ghost-agent every “GhostCreationRate“ units time.

The strength of a PP pheromone at a place is linked to the probable local load of workpieces in the state specified by the pheromone. The actual arrival of a workpiece at a zone depends on the outcome of processing steps and transport decisions yet to come.

As in Monte Carlo simulations in general, the quality of the prediction of the future pattern depends on the number of samples of the probabilistic model. In the case of the GMC system, the Ghost-agents running through the PI, emulating their respective Workpiece-agent, sample the model. The more often a Workpiece-agent generates a Ghost-agent, the better the quality of the prediction. The rate of the Ghost-agent generation must be tuned for the dynamics of the model change (changing yield, changing advice, etc.) and for the rate in which the advisory system accesses the prediction.


84

4.3.2 Integrating Advice

To integrate the advice given by the advisory system into the operation of the reactive layer of the control system the Switch-agents are enabled to delay the transport of a workpiece, and the decision processes of the Workpiece-agents and the Loader-agents are extended. These functional extensions are part of the specification of the interface layer.

4.3.2.1 Delaying the Transport

In contrast with the reactive layer, the interface layer permits Workpiece-agents to delay the further transport of their workpieces. Whereas the basic behavior of a Switch-agent demands a transport of workpieces even without a given direction, in its extended behavior a Switch-agent may be asked to delay a workpieces.

Depending on the layout of the elementary zone controlled by a Switch-agent, a transport of a workpiece is delayed by storing it in a local buffer, by routing it in an internal parking loop, or by simply stopping the workpiece where it is, blocking the flow.

No additional processes are added to the Switch-agent in the interface layer. The existing interaction and routing mechanisms are only extended by the delay option.

4.3.2.2 Guidance Pheromones

Advice is given through the pheromone type “Force“ (PF). The local strength of PF pheromones provides an additional bias to the probabilistic transport decisions of the Workpiece-agents and their Ghost-agents.

There is one additional data-slot to PF. The slot “state“ specifies a pheromone according to a processing state. In addition to all possible states, the slot may also take an “any state“ value, indicating relevance independent of the processing state. An input to a PF pheromone propagates upstream with a non-zero propagation parameter.

The spatial strength pattern of PF pheromones represents the advice. Locally, the advice is meant to attract or to repel workpieces in their flow. Attraction is signaled in positive values of the strength of the PF pheromones. Repulsion uses negative strength values. The agents are designed to cope with a flow field of mixed negative and positive strength.

4.3.2.3 Extending the Workpiece-agent

The local strength of PF pheromones is incorporated into the routing decision process of a Workpiece-agent. As in its basic behavior, a Workpiece-agent first determines all possible next processing steps and samples PA to restrict the set of potentially available directions accordingly. But, in its extended behavior a Workpiece-agent then samples the current strength of all PF pheromones that match the processing state of its workpiece, including the pheromone “any state“. It perceives the strength of the pheromones separately for each downstream direction (Section 3.3.1).

The final routing decision is taken in two steps that are illustrated in an example in Figure 4.7. First, a Workpiece-agent decides if it should request a fixed delay for its workpiece. If this is not the case, it selects a downstream direction according to the flow


85

field spanned by the PF pheromones sampled.

Figure 4.7. PF Biased Probabilistic Selection of the Exit Direction

The agent delays the transport based on a probabilistic decision. Let s denote the sum of all previously sampled strength values of relevant PF pheromones. s represents the general local downstream repulsion or attraction of the specific workpiece. The probability Pd that the routing decision is delayed is computed using the following equation:

(4.1)

In the equation x1 ( ) is a constant parameter permitting the tuning of the decision process. Considering the definition of Pd, a workpiece is only delayed if its agent perceives a general downstream repulsion.

Finally, the Workpiece-agent picks a random number rnd ( ). It requests a delay of the workpiece from the local Switch-agent, if holds. In this case, the Switch-agent delays the workpiece until further notice and the Workpiece-agent pauses for a fixed time before it restarts the whole decision process.

In the second stage of the extended routing decision, the Workpiece-agent finally selects the direction of the transport. If there is only one direction available, it simply requests the transport and eventually moves on. Otherwise, the Workpiece-agent sums up the previously sampled strength of the PF pheromones, but now specific for each permitted direction. Thereby, it perceives directed forces of repulsion or attraction.

The direction specific forces bias the otherwise random selection of a direction. The following requirements determine a force-biased selection out of a set of n permitted directions:

  1. A significantly stronger repulsion from one direction results in a low selection probability for this direction.
  2. A significantly stronger attraction to one direction results in a high selection probability for this direction.
  3. With no force from any direction, each exit is selected with a probability of 1/n.

The following two-step algorithm determining the selection probabilities for each permitted direction meets these requirements. First, the force of all directions is used to compute a “potential“ value for each direction, assuming that repulsion from one direction


86

is equivalent to attraction from all other directions and vice versa. Hence the potential value poti of n directions is computed as:

(4.2)

The value si is the sum of all PF pheromones relevant for direction i and s is computed as before as the sum of all relevant PF pheromones. With all forces localized, in a second step the selection probability Pi for each direction is computed by:

(4.3)

These probability values fulfill the specified requirements. Most importantly, they provide a random selection of a direction in the absence of any advice from the advisory system. As long as the advisory system is not active, the control system operates in the extended behavior of the Workpiece-agents as it does in the basic behavior specified in the reactive layer.

Figure 4.8. Extended Behavior of the Workpiece-agent

The selected direction enables the Workpiece-agent to request from the Switch-agent a transport of its workpiece. In Figure 4.8, the extended behavior of the Workpiece-agent is shown, focusing on the new transport decision process.

4.3.2.4 Guiding the Inflow

The extension of the behavior of a Loader-agent is similar to the extended Workpiece-agent behavior where a product specific delay of the material flow is the control instrument.

In its basic behavior a Loader-agent implements a given product mix and a preset rate when loading workpieces into the manufacturing system. In every cycle it first selects the next product according to the required mix. Then, the agent tries to load a workpiece


87

matching the selected product.

In its extended behavior the Loader-agent also selects a product first. But, then it samples the current strength of PF pheromones. Since workpieces of different products may have different initial states, the Loader-agent samples only pheromones that are relevant to the potential workpiece.

Figure 4.9. PF Biased Probabilistic Loading

The potential workpiece has no agent yet. The Loader-agent carries the responsibility for the workpiece, deciding if it should be delayed or if it is loaded into the system. The decision process is based on the same algorithm a Workpiece-agent would use (Equation (4.1)). The Loader-agent sums up all relevant PF pheromones and computes a probability Pd. On the basis of Pd, the loading of the workpiece is canceled or it commences as in the basic behavior.

Figure 4.9 depicts the process graph of the extended loading cycle.

4.4 Advisory System: Strategy Implementation Layer

The advisory system is the second major component of the GMC system. The following presentation focuses on the bottommost layer of the advisory system, the strategy implementation layer. The task of the strategy implementation layer is to generate advice for the underlying control system. It operates on the material flow patterns provided by the interface layer, accessing an aggregated current state of the manufacturing system and a prediction of the near future.

The concept of a (material flow) “strategy“ is the central element of the advisory system. It represents a flow pattern that is to be achieved. The strategy implementation layer is given such a strategy for implementation. The advice generated by the layer attempts to guide the control system towards the goal pattern. The agents of the layer try to achieve and maintain the current strategy - a flow pattern in the manufacturing system that mirrors the current goal pattern.

Structurally, a goal pattern matches the current or the predicted pattern generated by the interface layer. Local load values are given for specific to processing states. A strategy may define a local load for all or for only some places, permitting the strategy implementation layer to act in the PI. The advice is generated distributedly, expressed in the PF pheromones (Section 4.3).


88

In the strategy implementation layer a new agent type is introduced. Operating solely in the virtual environment of the PI, Policy-agents attempt a distributed implementation of the current strategy. Each Policy-agent represents the local load that is to be achieved.

The semantics of advice depends on the local context in the manufacturing system. The advisory system specifies a set of propagation filters in the PI (Section 3.3.1) that provide an automatic translation of advice. The chosen design demonstrates the ability of the PI to actively process information, thereby reducing the computational complexity of the agents.

4.4.1 The Policy-Agent Type

The current strategy is represented and implemented by a set of Policy-agents. There is one Policy-agent at most for each place in the PI. If there is a place without a Policy-agent, the strategy is not defined for the place and any material flow pattern is accepted there. Figure 4.10 illustrates the structure of a material flow strategy and its mapping to Policy-agents.

Figure 4.10. Distributed Representation of a Material Flow Strategy

Each Policy-agent knows the processing state specific load values required for its place, and it has access to the local PS and PP pheromones representing the local aspect of the current and the predicted material flow pattern. The goal of a Policy-agent is to match the current load values with the required ones.

The implementation of the current strategy by Policy-agents may be realized on different levels of sophistication, using reasoning ranging from simple to complex. Here the GMC system realizes a simple difference-driven approach.

The activities of a Policy-agent take the current and the predicted material flow into account. The load values of the current pattern are based on workpieces that are already in the zone or that even have left it. There is nothing a Policy-agent can do to change the behavior of the agents of these workpieces. On the other hand, the prediction of the flow is based on an approximation of the behavior of Workpiece-agents still located upstream. The Policy-agents adjust the behavior of the Ghost-agents, which mirror the routing decision process of their Workpiece-agents. Based on repeated Monte-Carlo simulations, the Ghost-agents and the Policy-agents negotiate the best configuration of the virtual environment, in which the Workpiece-agents later take their decisions.

A Policy-agent operates on the absolute load values given by the current load pattern and on relative load values predicted by the near-future pattern. The emergent prediction of a flow pattern is accurate in representing the expected relative load values in the relative strength of the respective PP pheromones. The expected absolute load is not extractable from the sum of the PP pheromones. There are too many uncertainties and abstractions in the prediction process. On the other hand, the representation of the current absolute load in


89

the PS pheromones is very accurate, as demonstrated in Section 4.5.

Figure 4.11. Two Processes of a Policy-agent

Figure 4.11 illustrates the two processes executed by a Policy-agent. One process transmits the current advice by regularly refreshing local PF pheromones according to its current intended attraction or repulsion of workpieces in specific processing states. The second process re-evaluates the advice. As the transmission of the advice, the adaptation of the advice runs in a closed loop. Starting a new adaptation cycle, the Policy-agent samples all available PS and PP pheromones first. Assuming the strength of these pheromones to be in equilibrium, it then extracts the processing state specific local load values.

With all external data available, the agent determines its next activities. In a first step, it normalizes the predicted load values. Thus all normalized load values of the predicted pattern sum up to one. Then, for each processing state, the normalized predicted load value is subtracted from the normalized load value of the goal of the Policy-agent. Thus, the required increase in share (positive subtraction result) or decrease in share (negative subtraction result) is computed. But, an increase of one relative load may be achieved by increasing the respective load or by decreasing all the others, and vice versa the decrease.

To decide how the change in the shares is achieved, the Policy-agent consults the absolute current load. If the absolute current load is smaller than the absolute load goal, the current load must increase. Thus, the load of workpieces in underrepresented processing states should be increased. If the absolute load has to decrease - a decrease of specific load values is required.

If there is no change of any processing state specific relative load value required but the absolute load is not yet as specified in the goal of the Policy-agent, the advice must be adapted for all processing states equally.

As a result of its reasoning process, the Policy-agent knows which workpieces to attract or to repel stronger than before. According to SE design principle 14, gradual change in the behavior of an agent is to be preferred to abrupt changes. Thus, a Policy-agent changes its transmitted advice only by a small and fixed amount in the adaptation process, even if the current and predicted patterns differ strongly from the given goal pattern.

After having adapted its advice, the Policy-agent has completed another adaptation cycle. The process is paused for a fixed time and then the next adaptation cycle begins. The behavior of a Policy-agent is parameterized by the refresh rate of the PF pheromones and the rate and strength of the change in one cycle of the adaptive process.

4.4.2 Context Dependence

Advice given by Policy-agents depends on the local context of the manufacturing


90

system. Spatial propagation of input events to PF might leave the local context the advice is given for. The local context of an elementary zone in the manufacturing system is set by the processing state of the workpieces passing through it. For advice to be effective, it must be stated in relation to these workpieces.

Figure 4.12. Local Context in the Manufacturing System

The following example (Figure 4.12) illustrates the context dependence of advice. Assume that there is a sequence of three places in the PI (px, py, pz) with the material flow running from px to py and on to pz. Further assume that there is a Processing-agent at py and Switch-agents at px and pz. The only processing capability available at py is to change the processing state of a workpiece from A to B. Thus, only workpieces in state A pass px, whereas at pz there are only workpieces in state B. Then, the local context at px is A, and at pz it is B.

A Policy-agent located at pz perceives a stream of workpieces in state B. Therefore, its advice is given in the PF pheromone state=B. Inputs to this pheromone are propagated upstream. px is the next place where Workpiece-agents access the advice. But, since they are all in state A, they never sample the PF pheromone state=B because it is not relevant to them. At py the context changes because there the processing state is changed.

It is necessary to translate the advice according to the context of the respective zone. The translation takes place during the propagation of input events, realized in a specific propagation filter in the PI (Section 3.3.1).

To translate the advice expressed by PF, a change in the context must be accessible to the PI. A change of context occurs only at places of Processing-agents. The change is characterized by the transitions of the processing state of workpieces caused by the agent. Therefore, for every state transition occurring, a Processing-agent generates an input to a pheromone of the “Transition“ (PT) type.

PT has two additional data slots, both carrying a processing state. The first slot (“in“) contains the processing state, with which a workpiece has arrived, whereas the second one (“out“) takes the processing state, with which the workpiece has left. Inputs to PT do not propagate and it evaporates extremely slowly. Over a long period, the relative strength of the PT pheromones approximates the long-term yield of the processing unit.

A propagation filter, translating input events to PF during their upstream propagation, is only active where PT pheromones are available. At such a place, the propagation of an input to PF is blocked if the content of the “state“ slot of the respective PF pheromone matches the “out“ slot of a local PT pheromone. Instead, a “virtual“ input to another PF pheromone is propagated further upstream. The input refers to a PF pheromone that is specified by the value of the “in“ slot of the matching PT pheromone. The propagation of an input to PF is also changed quantitatively. The strength of the translated advice is based on the inverse of the yield, as it is perceived in the relative strength of the matching PT


91

pheromone.

More complex translations occur if there is more than one processing state permitted at the entrance of a processing unit. Assume that workpieces arrive in state A or B, and they leave in state C or D. All four possible transitions actually occur. In this case, advice relevant for D is translated to advice for A and for B.

Figure 4.13. Example of Context-Filtering

The translation is realized by splitting the strength of the original advice according to the relative strength of the and the transitions (PT pheromones) first. Then, the resulting strength is divided by the relative strength of the and , or the and transition respectively (Figure 4.13).

The following equations specify the required computation. The terms F(A) and F(B) denote the strength of the resulting advice relevant to the respective processing states (PF(state=A), PF(state=B)). Similarly, T(x,y) denotes the strength of a PT pheromone with “in“ set to x and “out“ set to y.

With the PT pheromones in place the Ghost-agents may not have to interact with the Processing-agents directly. Instead they may determine the outcome of a simulated processing themselves, based on the yield represented in these pheromones.

4.5 Demonstration and Evaluation

Based on the specification presented in the previous sections, the operation of the GMC system is discussed in a small but realistic demonstration. The manufacturing system is abstracted from the paint shop problem (Section 4.4.1) with adaptations for demonstration purposes.

Traversing the system architecture from bottom up, the structure of the PI is derived from the assumed manufacturing system first. Then, in the following sections, the operation of the reactive layer, the interface layer, and finally the strategy implementation layer is discussed and evaluated using the results gained in the analysis of the formal model of the PI.

In the evaluation of the layers, the numerically computed predictions of the resulting global behavior and of the pheromone patterns are compared with observations in a


92

prototypical implementation of the GMC system.

Besides evaluating the system at hand, the demonstration also serves as an example for the general approach to tuning and evaluation of multi-agent coordination on the basis of the PI.

4.5.1 From Reality to the PI

Figure 4.14 depicts the PI as it is described in the following discussion. Each icon of a place shows the task fulfilled in the respective zone (Load, Switch, Process, Unload), and the time it takes a workpiece take to pass the zone. The places of the processing units also display the yield of the respective unit.

Figure 4.14. The PI in the Demonstration

There is only one processing step executed in the manufacturing system. The workpieces enter it in a processing state “A“ and they are permitted to leave only if they are in state “B“. Segments of the paint shop application matching this more abstract demonstration are repair units like “Spot-Repair“ or “Repair-Preparation“.

There are two processing units (“P1“, “P2“). Both accept “A“-state workpieces and out of both units emerge workpieces that are in state “A“ when no processing happened. Workpieces leave the units in state “B“ if the processing was successful.

Each processing unit has a yield (“A“ vs. “B“) and specific processing times. After passing unit “P1“, an average of 90% of the processed workpieces is in state “B“ and only 10% remain in state “A“, while for unit “P2“ the yield is only 70% state “B“ versus 30% state “A“. But, on the other hand, unit “P1“ takes longer (300 seconds) to process a workpiece than unit “P2“ (240 seconds).

The workpieces all enter the manufacturing system through one entry, and they all leave through the same exit. The average loading rate is assumed to be one workpiece every 60 seconds.

The flow of workpieces coming from the entry is split in front of the processing units. After processing, the flows join to be split up again according to the processing state of the workpieces. All workpieces in state “B“ have to go to the exit. All remaining state “A“ workpieces return to the zone in front of the processing units.

Following the given restrictions for allocating elementary zones, the manufacturing system is divided into six zones. There is a zone for each processing unit. Additionally, there is a small zone for the entry and one for the exit. Finally, an elementary zone between the entry and the processing units and one after the processing units is identified.


93

“L“ denotes the entrance zone and it takes a workpiece 60 seconds to pass it. It then moves into the zone where the decision for one of the processing units is taken (“S1“). The workpiece emerges at the entrance of the respective zone of one of the processing units after 120 seconds.

After passing the processing units in either zone “P1“ or “P2“, the flow of workpieces merges again in zone “S2“. 120 seconds later they leave “S2“ again to enter “U“, the zone of the exit, or “S1“ according to the respective processing state. Finally, unloading is completed after 60 seconds.

Each elementary zone in the manufacturing system is mapped to a separate place in the PI. The places are linked according to the layout of the transport system.

Each zone is given one Resource-agent according to the local activities. A Loader-agent is created for the entrance zone “L“. “S1“ and “S2“ are controlled by Switch-agents, and “P1“ and “P2“ are covered by Processing-agents. The exit zone “U“ is assigned an Unloader-agent. For simplicity, the places and the agents too are named after their respective elementary zone.

4.5.2 Reactive Layer Operation

The reactive layer is made up of Resource-agents and Workpiece-agents. The Resource-agents are already placed in the PI as specified in the previous section. A Workpiece-agent is created by the single Loader-agent whenever a workpiece is successfully loaded into the manufacturing system.

All Workpiece-agents carry the processing state of their workpiece. Initially, the state is “A“. It is eventually changed to “B“ during processing. Only “B“-state workpieces are permitted to proceed to zone “U“.

The central coordination mechanism of the reactive layer is the attraction of workpieces to the processing units and later to the exit. The attraction is communicated in two PA pheromones. The first pheromone (ability=“A2B“) represents the capability of the two processing units to take in workpieces of state “A“ and process them into state “B“. The Unloader-agent, on the other hand, refreshes the standard PA pheromone (ability=“unloading“).

Each Processing-agent (“P1“, “P2“) regularly refreshes the PA pheromone “A2B“ whenever the processing ability is available. The refresh rate and the refresh strength are specified by the two global parameters “AbilityRefreshRate“ and “AbilityRefreshStrength“. The emerging spatial strength pattern depends on the evaporation parameter and on the propagation parameter of PA.

An input to PA propagates upstream to the flow of workpieces. Thereby, places upstream from the respective processing resource receive routing information.

In Figure 4.15 the PA pattern emerging for a specific set of parameters is shown. The parameters “AbilityRefreshRate“ and “AbilityRefreshStrength“ are both set to a value of one. The evaporation parameter is set to 0.99 (percent remaining after one second), indicating a slow evaporation, and a propagation parameter of 0.5 (percent remaining after one propagation step) resulting in a small attractive radius.


94

Figure 4.15. Spatial PA Pattern

At place “S1“ the Workpiece-agents all carry state “A“. Hence, they need to know, which direction to take to a processing unit that provides the ability “A2B“. The upstream propagation of input events from the Processing-agents and the direction-specific aggregation of PA pheromones at “S1“ point Workpiece-agents to downstream directions where the required ability is available. If both processing units are online, the selection is taken randomly.

The next routing decision is required at “S2“. The regular refresh of the PA pheromone ability=“unloading“ by the Unloader-agent provides Workpiece-agents in state “B“ with guidance. But, if a workpiece is still in state “A“, the agent is led by the two-step upstream propagation (“P1“/“P2“ to “S1“ to “S2“) of the processing ability “A2B“.

Workpiece-agents are created at place “L“. They pass into “S1“ when their workpiece is loaded. At “S1“ they select randomly “P1“ or “P2“. The selection results in a transport request to the Switch-agent. The workpiece is sent to the zone of one of the processing units.

After the transport is completed by the Switch-agent, the Workpiece-agent passes on to the next place. There it encounters a Processing-agent (“P1“ or “P2“) and requests the processing of its workpiece using the capability “A2B“. The Processing-agent realizes the processing and tells the Workpiece-agent the new state of its workpiece. The new state of the workpiece depends on the yield of the processing unit. “P1“ offers a ninety percent chance for a successful processing (result: “B“). At “P2“ the chance is only seventy percent. After the processing result is transmitted, the Workpiece-agent moves to the next downstream place, which is “S2“ in the demonstration.

At “S2“ the transport decision is based on the state of the workpiece. Workpieces in state “B“ enter the zone “U“ and their Workpiece-agents meet the Unloader-agent. Whereas, workpieces in state “A“ return to zone “S1“, taking their agents to meet Switch-agent “S1“ again.

At place “U“ a Workpiece-agent requests the unloading of its workpiece. After completion, the Workpiece-agents are notified, telling them that their task is fulfilled and they are permitted to die.

4.5.3 Pattern Generation in the Interface Layer

Two patterns are generated to provide the advisory system with information. The spatial pattern of PS pheromones represents the current material flow whereas PP pheromones provide a prediction of the near future.


95

The PS pattern is generated by the Workpiece-agents, refreshing the pheromone that matches the current processing state of the workpiece. All Workpiece-agents show such a refresh behavior at all places. It is specified by the global parameters “StateRefreshRate“ and “StateRefreshStrength“.

Figure 4.16 shows the pattern generated in the manufacturing system of the demonstration. The global refresh parameters are set to “StateRefreshRate“=10 seconds and “StateRefreshStrength“=1. The evaporation parameter is set to 0.99 (percent remaining after one second). Simulating the manufacturing system of the demonstration while running the agents generates the data. But, it may be predicted analytically too, as the following discussion shows.

Workpiece-agents enter the system at a rate of 1 agent per 60 seconds. Assuming complete availability of the processing units, the flow of workpieces is split evenly at “S1“. Hence statistically, every two minutes an agent arrives at “P1“ as well as at “P2“.

Figure 4.16. Simulated PS Pattern

For each processing unit there is a fixed yield. At “P1“ ninety percent of all arriving workpieces leaves in state “B“, and only ten percent leave in state “A“. Hence, the flow of “A“-state workpieces out of “P1“ is 10 percent the strength of the inflow.

Because of the fifty-fifty split of the flow between the two processing units, and because of their processing yield, the inflow of Workpiece-agents into place “S2“ is 80 percent “B“-state and 20 percent “A“-state workpieces. The strength of the inflow is the same as the outflow strength of “S1“.

At this stage, there are 0.8 Workpiece-agents in state “B“, entering “S2“ every minute. “A“-state agents arrive in a rate of 0.2 agents per minute. They continue further to “S1“ where they enter the flow of one agent per minute generated by the Loader-agent. Hence, the output of “S1“ adds up to 1.2 agents per minute split evenly between the processing units.

Of the 1.2 agents per minute, twenty percent return to “S1“ eventually. Repeatedly adding the fed back flow yields the following term for the rate of Workpiece-agents passing “S1“: .

Knowing the absolute flow at “S1“, the rest of the pattern of flow rates may be computed. The following table lists the computed flow rates for all places (in agents/minute) specific to the processing states:


96

Table 4.1. The Current Pattern of Load-Values.

 

“L“

“S1“

“P1“

“P2“

“S2“

“U“

inflow “A“

-

1.25

0.625

0.625

0.25

0.0

inflow “B“

-

0.0

0.0

0.0

1.0

1.0

outflow “A“

1.0

1.25

0.0625

0.1875

0.25

-

outflow “B“

0.0

0.0

0.5625

0.4375

1.0

-

From the strength of the flow and the time an agent is present at a place, the number of agents statistically present at a place at any time is computed by simple multiplication. With the number of agents known, the pheromone equilibrium is computed for each place and each processing state (Equation 3.26). As Table 4.2 shows, the predicted strength of PS pheromones in equilibrium is very closely approximated by the respective average strength in Figure 4.16.

Table 4.2. Prediction of the Pattern of PS Pheromones.

 

“L“

“S1“

“P1“

“P2“

“S2“

“U“

PS(state=“A“)

10.0

25.0

31.25

25.0

5.0

0.0

PS(state=“B“)

0.0

0.0

0.0

0.0

20.0

10.0

The deviation of the actual pheromone strength from the computed prediction results from the non-deterministic routing behavior at “S1“, introducing perturbations in the strength values. The visibility of a perturbation depends on its strength, its duration, and on the evaporation parameter. Slower evaporation in the same scenario results in less fluctuation, as illustrated in Figure 4.17 where the strength of PS at “P1“ is shown in the same scenario for different evaporation parameters.

Figure 4.17. PS at “P1“ with Different Evaporation Parameters (E)

The analytic prediction of the average pheromone strength also provides the argument for the perception mechanism of the Policy-agents of the strategy implementation layer. Knowing the fixed refresh behavior of a single Workpiece-agent, the parameters of PS, and the average transport or processing times, the local load may be perceived in the PS pattern. The evaporation parameter determines how up-to-date the aggregated information is.


97

The pattern generated by the interface layer in the PP pheromones represents a prediction of the relative load in the material flow in the near future. Like PS, processing state information specifies PP pheromones.

The mechanism that anticipates the near future simulates the material flow. Each Ghost-agent emulates the behavior of the Workpiece-agent by which it was created. It takes transport decisions based on the same information and using the same algorithm. But, since a Ghost-agent does not accompany a workpiece, it does not have to wait at each place for the handling of the workpiece to be completed. Instead, it just moves on to the next place at “electronic“ speed.

Processing steps need to be simulated during the run of a Ghost-agent. Processing-agents keep a floating average of the yield of their processing unit. On request they determine a result of a simulated processing step according to the probabilities given by the yield. Passing Ghost-agents make the request and its outcome changes their internal state.

A Ghost-agent refreshes the PP pheromone matching its current internal state. There is only one refresh after every move from one place to another.

The prediction process is influenced by similar parameters as the generation of the current pattern. To generate a regular refresh of PP, Workpiece-agents regularly create Ghost-agents at a fixed rate specified by the global parameter “GhostCreationRate“. “GhostRefreshStrength“ sets the refresh strength of Ghost-agents. An additional parameter influencing the accurateness of the prediction is the number of moves, each Ghost-agent is permitted to make in the simulation. This parameter determines how far into the future the behavior of a Workpiece-agent is emulated.

Figure 4.18. Simulated PP Pattern

Figure 4.18 shows the PP pattern emerging in the simulation. The “GhostCreationRate“ of Workpiece-agents is set to one Ghost-agent every 10 seconds. The “GhostRefreshStrength“ has a value of one. Each Ghost-agent is permitted to make ten moves at most. Again, the evaporation of PP pheromones is set to 0.99 (percent remaining after one second).

Based on the average load values of each place and the even split of the material flow at “S1“, the average PP pattern may be predicted analytically too. The following argument presents the approach.

There are on average 3.125 Workpiece-agents at place “P1“. Together, they create 18.75 Ghost-agents per minute. Taking the simulated processing at “P1“ into account, 1.875 Ghost-agents leave “P1“ in state “A“ while 16.875 agents emerge in state “B“ every minute. The input to PP starts when entering “S2“, because this is the first move of the


98

Ghost-agents that are created at “P1“.

Ghost-agents in state “B“ move on from “S2“ to place “U“, whereas “A“-state agents continue to “S1“. At place “U“ they encounter the Unloader-agent and die. At “S1“ they emulate the transport decision of Workpiece-agents and split evenly between “P1“ and “P2“. Thus 0.9375 Ghost-agents re-enter “P1“ per minute.

With a maximum of ten moves, the longest run of Ghost-agents created at “P1“ is: “P1“-“S2“-“S1“-“P1“/“P2“-“S2“-“S1“-“P1“/“P2“-“S2“-“S1“-“P1“/“P2“-“S2“. The path of Ghost-agents has to be followed to describe the complete flow pattern emitting from “P1“. The overall flow pattern of Ghost-agents in the demonstration is calculated by tracking the Ghost-agents that are generated at each place. The volumes of the flows add up since there are no dependencies among Ghost-agents. The following table depicts the resulting relevant load rates at each place:

Table 4.3. The Predicted Pattern of Load-Values.

 

“L“

“S1“

“P1“

“P2“

“S2“

“U“

Load “A“

0.0

22.857

18.8925

18.8925

13.908

0.0

Load “B“

0.0

0.0

0.0

0.0

57.507

69.303

Each Ghost-agent refreshes a PP pheromone once when it enters a new place. Hence, the global flow rates are equal to the resulting average refresh rates of PP. With the refresh strength and the evaporation parameter given, the equilibrium values are computed as listed in the following table:

Table 4.4. Prediction of the Pattern of PP Pheromones.

 

“L“

“S1“

“P1“

“P2“

“S2“

“U“

PP(state=“A“)

0.0

38

31

31

23

0.0

PP(state=“B“)

0.0

0.0

0.0

0.0

96

116

The discussion also shows that the resulting equilibrium values of the PP pheromones depend strongly on the parameters of the simulation, especially on the permitted number of moves. Hence, the absolute strength values cannot provide a load prediction in the same way the strength of the PS pheromones does for the current pattern. But the relative strength in the mix provides useful information. The anticipated load split between “P1“ and “P2“ is represented in the relative strength of PP pheromones at “P1“ and “P2“ (fifty-fifty), while the predicted combined yield of “P1“ and “P2“ with 20 percent state “A“ and 80 percent state “B“ is given in the pheromone mix (Section 3.2.4) at “S2“.

4.5.4 Heeding Advice

Advice is transmitted in the local strength of PF specific for each processing state. Workpiece-agents heed the advice when taking transport decisions. The strength of the relevant PF pheromones matching the processing state of the respective workpiece is sampled. These values are then used to determine the probability for delaying the workpiece (Equation 4.1) and they bias the otherwise random selection of one of the permitted directions.


99

Figure 4.19. Probability Function for Workpiece-Delay

The delay probability Pd is used by Workpiece-agents and also by the Loader-agent to determine the probability for a delay of a transport decision for a fixed time. Figure 4.19 plots the function for specific parameter values. It is the parameter x1 that determines the steepness of the function for negative strength values. The larger x1 the weaker the PF pheromones may be to result in the same delay probability.

If the workpiece is to be routed, the Workpiece-agent selects the exit to which the workpiece should be taken. In the extended Workpiece-agent behavior specified in the interface layer, the selection is based on PA and on PF. PA pheromones reduce the set of generally available directions to exits that offer processing of the next required step - a hard constraint already fulfilled by the reactive layer.

In the reactive layer the Workpiece-agent selects a direction randomly. In the presence of PF, the selection is biased. The strength of the relevant pheromones is interpreted as attracting or repelling force specific for each exit. Positive strength attracts, whereas a negative one repels workpieces. The selection probability for each permitted direction is computed in a two-step procedure. First, all strength values for all exits are aggregated into “potential“ values where attraction towards one exit is interpreted as repulsion from all other directions.

Figure 4.20. Probability Function for Exit-Selection


100

In the second step, the “potential“ values are used to compute the selection probabilities. The probability values of all permitted exits add up to one. In the absence of any advice, each exit has the same probability of being selected, automatically returning the system to the basic behavior of the reactive layer. Figure 4.20 plots the selection probability function for one direction in a two-options choice.

In the demonstration, there is only one place where Workpiece-agents may have a two-exit choice. At “S1“ they may select the exit to “P1“ or the one to “P2“. As the discussion of the mechanisms in the reactive layer already shows, the flow pattern emerging from the transport decision and the processing yield is numerically predictable.

Table 4.5. The Predicted (Current) Pattern for a 66/34 Split.

 

“L“

“S1“

“P1“

“P2“

“S2“

“U“

inflow “A“

-

1.2

0.8

0.4

0.2

0.0

inflow “B“

-

0.0

0.0

0.0

1.0

1.0

outflow “A“

1.0

1.0

0.08

0.12

0.2

-

outflow “B“

0.0

0.0

0.72

0.28

1.0

-

PS(state=“A“)

10.0

24.0

40.0

16.0

4.0

0.0

PS(state=“B“)

0.0

0.0

0.0

0.0

20.0

10.0

Table 4.5 lists the expected flow and the resulting PS strength values. Assume a 66/34 probability for the selection of “P1“. Out of three workpieces arriving at “S1“ two are processed at “P1“ and one goes to “P2“. Positive PF strength is assumed, excluding any delay options from the prediction.

Table 4.6. The Predicted (Predictive) Pattern for a 66/34 Split.

 

“L“

“S1“

“P1“

“P2“

“S2“

“U“

Load “A“

0.0

19.3627

22.2571

11.4658

10.9880

0.0

Load “B“

0.0

0.0

0.0

0.0

56.3266

68.2013

PP(state=“A“)

0.0

32

37

19

18

0.0

PP(state=“B“)

0.0

0.0

0.0

0.0

94

114

This prediction is validated in simulations where the advice is transmitted by an agent refreshing the PF pheromone state=“A“ at “P1“ regularly. The refresh strength is set to 7.0 and the rate is one input per second. Section 4.5.5 discusses the resulting PF pattern.

Ghost-agents, which are regularly created by Workpiece-agents, emulate the behavior of their creator in the near future. Ghost-agents heed the advice given via PF. Table 4.6 lists the prediction of the flow of the Ghost-agents and the resulting PP pattern in the demonstration under a 66/34-split advice at “S1“. Again, the “GhostCreationRate“ parameter is set to ten.


101

4.5.5 Strategy Implementation

Implementing a strategy means influencing the material flow to reach and maintain a specified goal pattern. A strategy defines a goal pattern in terms of local flow requirements. For any elementary zone in the manufacturing system, goal values for the load and the mix of the local material flow may be stated.

A Policy-agent is located at a place in the PI and it tries to fulfill the given local goal. The agent runs two processes. One process transmits the advice, while the other one adapts it.

In the process of transmitting advice, PF pheromones are regularly refreshed according to the current advice of the Policy-agent. The input events are propagated upstream the material flow, influencing transport decisions of Workpiece-agents and Ghost-agents. The refresh behavior is specified by internal parameters defining the current refresh strength for each PF pheromone.

The adaptive process changes the parameters of the refresh behavior of a Policy-agent. The adaptation is guided by the difference between the current and predicted situation in the manufacturing system and the goal of the Policy-agent. Regularly, the strength of PS and PP pheromones is sampled and the current load and mix as well as the predicted mix are retrieved. Comparing these values to the goal of the agent, small changes in the advice might be deduced.

Assume that the current strategy expects a load of 4.0 workpieces in state “A“ at “P1“. There is a Policy-agent located at place “P1“ that represents a local aspect of the strategy. Initially, the agent does not give any advice. The refresh strength for the PF pheromone state=“A“ is zero. Without any advice, the control system simply operates in the basic behavior defined in the reactive layer. A 50/50 split of the flow at “S1“ results and the load at “P1“ stabilizes at 3.125 workpieces. These values are predicted and validated already in Section 4.5.3.

Figure 4.21. PF Pattern

The adaptation process of the Policy-agent perceives a load value that is too low. The agent needs to attract more workpieces. The advice is changed towards positive PF in the regular refresh. The change of the advice occurs very slowly and gradually, because it takes a while for the change in the advice to become visible in the PF pheromones, and some more time has to pass before the change in the material flow actually manifests itself in PS and PP. The dynamics of the adaptive process may be tuned manually on the basis of the formal model. Alternatively, a further process may be added that adapts the dynamics of the adaptation process to the system at hand.


102

The adaptation process changes the advice so that the observed material flow eventually matches the current strategy. In the demonstration, the Policy-agent at “P1“ refreshes the PF pheromone state=“A“ finally with a strength of seven every second. The resulting PF pattern is depicted in Figure 4.21. The PS strength at “P1“ stabilizes at forty, encoding a load of four workpieces at “P1“ as it was required by the strategy.

The goal to achieve and maintain a load of four at “P1“ results in a 66/34 split of the flow at “S1“. More workpieces are processed at “P1“ than at “P2“, improving the combined yield of the two processing units to a “A“:“B“=17:83 ratio, and reducing the flow back from “S2“ into “S1“. The required overall processing capacity is reduced to 1.2 workpieces per minute instead of 1.25 as it was without the advice.


© 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