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

1

Chapter 1. Introduction

The following chapter motivates the research that led up to this thesis. It sets the goal of the thesis, which is put into four questions. Finally, the structure of the thesis is presented, introducing the following chapters and major sections.

1.1 Introduction

1.1.1 Motivation and Background

In summer 1998, there arose the following task in the ESPRIT LTR project MASCADA: Given a segment of a transport system of arbitrary layout in discrete high-volume production composed of unidirectional line-buffers (e.g., conveyors) and multi-input multi-output sequential routing devices (e.g., rotation tables, lifts), and assuming that the workpieces sent through the segment are all of one product but may be differentiated on the basis of the value of one product parameter; how may the segment be controlled in a decentralized manner so that the outflow of workpieces occurs in batches of workpieces of the same product parameter value with the average batch size of the outflow being significantly higher than that of the inflow?

Businesses around the globe face a change from a supplier's market to a customer's market. As one consequence of the change flexibility makes its way into high-volume production where sequential and optimized transfer-lines previously dominated. The introduction of flexibility in products and processes requires a change in the manufacturing system as well as in its control. Traditionally, manufacturing control is organized top down. Strategical planning passes its results down to tactical planning, which in turn triggers operational planning processes. The final result of the planning process, a detailed schedule, is given to the manufacturing execution to be implemented on the shop floor. There, unforeseen disturbances are encountered that may invalidate the schedule and thus trigger a new planning cycle at the operational level.

Modern flexible flow shops require a new approach to control, one that self-organizes around the manufacturing execution. The batching problem stated at the beginning cannot be solved by a planning-scheduling-execution cycle. It is highly dynamic and it requires an ongoing concern rather than a one-time achievement. At any time, new workpieces may enter the system while others leave it. The volume of the inflow and the mix of the variants fluctuate strongly over time. It is not even known how many different variants have to be handled at a time. In addition to such short-term changes, there are changes or disturbances in the layout of the transport system. Finally, even the criteria the workpieces are sorted by may be subject to long-term change.

Social insect colonies are an example of distributed systems of locally interacting individuals. They display a wide variety of system-level properties that are also required of modern manufacturing systems and their control. Emerging from simple and often indirect interactions of individuals that are simple compared to the complexity of the system, insect colony behavior is robust, flexible, adaptive, self-organizing, intuitive, and scalable.


2

In recent years interdisciplinary research has focused on insect colonies and similar systems in physics, chemistry, economics, biology, or computer science. The research follows two major approaches: the analytic approach and the engineering approach. The analytic approach takes individual behavior and a specification of the interactions and seeks to determine what system-level properties emerge. The engineering approach starts out with a set of system level properties and asks what individuals and what interactions are required to achieve these properties.

Taking the inspiration from insect coordination mechanisms, the following simple but effective solution to the batching problem was found. Each sequential router is assigned a Router-agent. A Router-agent acts completely autonomous without even directly communicating with other agents. The simple task fulfilled by each Router-agent is to take workpieces sequentially from the entries of its router to the exits. Therefore, an agent needs to perceive the workpieces waiting at the entries and the current state of the exits (blocked or free). To achieve the required batching property at the level of the control system made up of these agents, a Router-agent has a simple memory. There it stores for each exit the value of the product parameter of the last workpiece that has passed the exit.

With multiple entries and multiple exits a Router-agent has to decide when to take which of the available workpieces to what exit. The decision is taken in a sequential execution of the following three simple rules, starting at rule one:

Sorting Rule (1).-IF at entry X there is a workpiece with a product parameter value of p and there exists a free exit Y whose related product parameter in agent memory has a value of p too, THEN take the workpiece from X to Y immediately and restart at rule one.

Extension.-IF there are currently more than one such actions possible, THEN select one of them randomly.

Blocking Rule (2).-The ratio of free entries to the overall number of entries determines a probability PB to pause the routing operation for a fixed time TB. The higher the ratio, the higher is the probability to pause. After pausing restart at rule one.

Random Rule (3).-Select one occupied entry X and one free exit Y randomly, route the workpiece from X to Y, and then restart at rule one.

These rules are based on the assumption that every workpiece may be routed from any entry to any exit at each router. As a consequence, the following two requirements for the layout of the transport system are set:

„Open“ Layout.-In the segment of the transport system under consideration, every entering workpiece must be permitted to leave through any exit.

„Directed“ Layout.-There must be no cycles in any path from an entry to an exit of the segment.

There exist extensions to the Router-agent behavior that provide an explicit global routing in addition to the sorting of workpieces. But these extensions are outside of the scope of this introduction.

The inspiration for the design of the Router-agents came from the coordinated nest construction of ants, termites, or bees. The basic principle that governs the coordination is sematectonic stigmergy. In stigmergy in general, there are mechanisms that trigger individual work (Greek: „ergon“) through signs (Greek: „stigmata“) in the environment. If these signs are aspect of the task itself (e.g., form of an arc in a termites nest) then it is the


3

sematectonic form of stigmergy. In sign-based stigmergy on the other hand, the task fulfillment is coordinated through additional markers (e.g., pheromones). Stigmergy requires agents to act upon changes in their environment that are caused by the agents themselves. These repetitions in space and time of small-scale activities in the environment result in a stable and self-organized system-level behavior.

A Router-agent takes decisions on the current configuration of its local environment. Through its actions it changes not only its own environment, but also the environment of other downstream and upstream Router-agents is changed too. The emergence of coordinated system-level behavior (here batching) requires the individual activities to be repeated as often as possible. As a consequence the quality of the task fulfillment by the agent system depends on the individual behavior as well as on the structure of the stigmergetic interactions as it is given by the layout of the transport system. Good batching behavior emerges if the following requirements for the layout are fulfilled:

„Alternative“ Layout.-There are many possible paths from an entry to an exit of the segment and these paths should intersect as often as possible to provide a large number of local routing points.

„Homogeneous“ Layout.-Most sequential routers have the same number of entries and exits to permit a homogeneous setting of agent parameters.

Figure 1.1. Layout of Router-agents with a High Batching Quality

The Router-agents have been implemented and they have proven themselves in several different layouts. One of the most effective layouts for batching is the matrix layout as it is shown in Figure 1.1. The illustrated segment has only one entry (lower left) and one exit (upper right). The different shades indicate different product parameter values. The distributed control system self-organizes to sort a random inflow into a high-quality outflow.

The design of a self-organizing control system that creates batches in an initially random material flow was at that time spontaneous and intuitive. But its success raised the question whether there is a systematic approach to the design. What underlying (bio-)logic has to be employed to successfully engineer an agent system of industrial strength that yields global properties comparable to those of complex natural systems? What specific support may be given to an engineer who eventually implements such an agent society? Finally, in addition to the engineering aspect, the analytic aspect also comes into play. Is


4

there a way to support the tuning and the evaluation of coordination mechanisms that give rise to emerging global properties?

Insect societies and the coordination mechanisms they employ have not been designed. They are the result of million years of evolution. In the course of evolution the individual behavior and the interactions had been selected to yield an optimal colony behavior. It is not the single insect behavior that is evaluated for its fitness because the individual cannot survive without the colony. The „goal“ of the optimization process is to achieve the best system-level properties in the given environment by tuning the individual behavior only. The ordering force of self-organization supports the process [Kauffman, 1995].

The engineering of agent systems follows the same goal - the resulting system is evaluated by its global properties. Hence, engineering could also try to design all required properties into a homogeneous set of agents, employing, for instance, artificial evolution. But more intuitive, and hence easier to realize and to change, is it to split the system into clusters of different agents, each cluster providing different aspects in the overall system-level behavior.

When considering the general requirements for modern manufacturing, two different kinds of system-level properties are identified. Primarily, the operation of the manufacturing system must be robust, agile, and flexible in the face of changes and disturbances. But, when these primary goals are reached, the system is also required to fulfill the production goals as good as possible. The clustering in the design of an agent system for manufacturing control may occur following such a distinction of properties. Therefore, the following question is raised: How should one design the interplay between the agents that achieve robustness and flexibility and those that seek to optimize the operation according to external production goals?

1.1.2 Goal and Structure of the Thesis

The work presented in this thesis aimed to answer the following four questions:

Design.-What principles should be followed if a distributed system of locally interacting individuals is designed so that it yields global properties like robustness, flexibility, agility, scalability, or intuitiveness?

Realization.-How may the services of a runtime environment that executes software-agents be extended so that it supports general sign-based stigmergetic interactions?

Evaluation.-Is there a formal approach to the prediction, the tuning, and the evaluation of stigmergetic multi-agent coordination mechanisms?

Application.-Given a set of design principles, an extended agent runtime environment, and a formalism for sign-based stigmergy, how is a self-organizing system for manufacturing control designed, tuned, and evaluated that combines robustness and flexibility with optimization according to production goals?

The thesis is structured as follows. Chapter 2 provides the context into which the work is set. Section 2.1 reviews concepts and techniques related to the interdisciplinary research into distributed systems of locally interacting individuals, while Section 2.2 presents the chosen application domain of manufacturing control with its requirements and approaches.

The Chapters 3, 4, 5, and 6 present the main contribution of the thesis. In Section 3.1 an extensive set of design principles are stated, motivated, and discussed in their implications


5

for manufacturing control. To support the design of stigmergetic agent coordination mechanisms the pheromone infrastructure, an extension to agent runtime environments, is introduced. The remainder of the section discusses how the deployment of a pheromone infrastructure eases the application of the proposed design principles.

After the informal introduction of the pheromone infrastructure in Section 3.1, the following Section 3.2 sets up a formal model of the infrastructure, proves the general global stability of the infrastructure, and demonstrates in a variety of scenarios how the model serves to predict, tune, and evaluate stigmergetic agent interactions.

The chapter ends with the presentation of an agent-based implementation of the pheromone infrastructure in Section 3.3. First, two additional extensions to the infrastructure are introduced that help to unload computations from the agents to local servers. Then, the agents comprising the implementation are specified in detail. Finally, requirements for an agent runtime environment that supports the pheromone infrastructure are stated.

In Chapter 4, the design, tuning, and evaluation of a self-organizing manufacturing control system is demonstrated. The guided manufacturing control (GMC) system for discrete flexible flow-shops is designed to combine robustness and flexibility with optimization for production goals. The design of the agents and their interactions follows the proposed design principles. The pheromone infrastructure is used in multi-agent coordination.

The guided manufacturing control system is discussed in the context of a car-body paint-shop application. Section 4.1 shortly presents the characteristics of the application. The designer is guided in distributing the agents in the manufacturing system and the system architecture is specified. In the Sections 4.2, 4.3, and 4.4 the agents and their interactions in the three bottommost layers are specified in detail and in the following Section 4.5 the emerging behavior of these layers is discussed and evaluated in a demonstration taken from the paint-shop application. The first layer realizes a reactive control of the manufacturing process, the second layer prepares the coupling of the reactive control with an advisory system, and the third layer translates global material flow goals into local advice.

Chapter 5 points the way to future extensions of the guided manufacturing control system, introducing concepts and deriving an agent model. Section 5.1 adds two more layers to the advisory system, providing strategy ranking, strategy evaluation, and strategy generation. The visualization system in Section 5.2 guides the system operator to critical locations in the production system.

The „synthesis“ (Chapter 6) visits the major issues of the thesis again, taking a more general perspective. In Section 6.1 the occurrence and relevance of the design principles proposed in Section 3.1 is systematically considered in the example of the previously presented manufacturing control system. Section 6.2 discusses the implications of the pheromone infrastructure and its formal model for the general evaluation of emergent global properties. Finally, Section 6.3 returns to the subject of manufacturing control in an attempt to classify different levels of sophistication in control by considering the manufacturing operation in state space.

The thesis concludes in Chapter 7 with a summary of the presented research and an outlook to further research directions.


© 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