|Brückner, Sven: Return From The Ant Synthetic Ecosystems for Manufacturing Control |
The concluding chapter returns to the four questions raised in the introduction of the thesis (Chapter 1). It summarizes the presented results, evaluates how they succeed in answering the questions, and it points the way to future research.
Consider again the initially raised problem of creating batches by local routing activities in a distributed transport system. The solution to the problem presented in Section 1.1.1 is the result of an empirical design process. This thesis presents an extensive set of design guidelines to enable a systematic design of synthetic ecosystems when combined with a general agent-system design method as for instance in [Burmeister, 1996].
Do the guidelines of Section 3.1 match the empirically designed successful solution of Section 1.1.1? The Router-agents represent physical entities, they are small in size and impact, they sense and act locally, they interact indirectly, their decisions contain a random element, and the control of the transport system and the fulfillment of the batching goal emerges from bottom up. Many important principles are covered by the intuitive solution already. Other principles, as for instance the suggested diversity of agents or the clustering of the agent system, are not included because the selected application is too small.
The functionality and applicability of the self-organized batching solution is extended when the workpieces are moved according to their specific routing goals. The Router-agent behavior as it is specified in Section 1.1.1 requires an open and directed layout. At each local routing point every workpiece arriving at any of the entries may be taken to any of the exits. If the layout is not open, some exits of a router may be explicitly forbidden for some workpieces. If directedness cannot be guaranteed, local routing has to differentiate between globally forward and globally backward directions in some way in order to prefer the forward direction on average. To include directed routing, more information has to be provided and incorporated into the decision processes of the agents.
A general solution to the directed routing problem follows the approach taken in the reactive layer of the GMC system (Section 4.2). The agents of the control system are embedded in the pheromone infrastructure. There is a separate place for each Router-agent, and there is an upstream or downstream link to another place for each entry or exit linking the router to other transport units. The advantage of including sign-based stigmergy into the agent coordination is that global information is made locally available in respect to the local context. In the case of the routing problem, the global information concerns the paths from the current position to the exits of the segment. The global information is translated into a local one that provides guidance in reference to the different local exits.
Assume that there are pheromones perceived separate for each downstream exit of a place of a Router-agent. The different pheromone types indicate the different global exits available to the workpieces that leave the system. Therefore, if a pheromone concentration larger than zero is perceived for a local exit, a step in such a direction leads towards the global exit indicated by the pheromone. Assume further that of any two local exits the one with the stronger concentration of a pheromone is part of the shorter path to the global exit. Hence, the global routing problem may be solved by local hill climbing alone.
127To combine the sign-based stigmergy of the routing mechanism with the sematectonic stigmergy coordinating the creation of batches, every workpiece is assigned an agent. The task of a Workpiece-agent is to make sure its workpiece eventually reaches the correct global exit. To that end it interacts with the local Router-agent that currently handles its workpiece, and tells it the preferred local exit. The additional information reduces the choice of the Router-agent when selecting the next transport. If there was an exit Y that matches the product parameter value of the workpiece but at the same time Y is currently not preferred by the Workpiece-agent, the Router-agent is not permitted to send the workpiece to exit Y. With the creation of the Workpiece-agent the agent system diversifies.
There is a performance tradeoff between a direct routing of the workpieces and the creation of batches. Batching requires a delay of some workpieces while others overtake them on alternative paths. Hence, a Workpiece-agent has to permit the Router-agent to take the workpiece on a less optimal path as long as the path still leads the workpiece to the global goal. Introducing randomization in the outcome of a decision of an agent, the Workpiece-agent selects the preferred local exit probabilistically from the set of exits that offer a path to the correct global exit. The probability for an exit to be selected is linked to the relative strength of the pheromone concentration of the exit. The more dominating the pheromone concentration of one exit is, the more probable is its selection. The decision is also randomized in time. There is a timeout set for the preference choice of the Workpiece-agent after which the agent again has to select an exit. The explicit randomization prevents deadlocks and eventually covers all available routing alternatives.
The extension of the control of a transport system as it is sketched here again underlines the importance and usefulness of the design principles stated in this thesis. These principles are motivated in a general argument in Section 3.1 and on the basis of the GMC system in Section 6.1. The systems considered in respect to the design principles all show global properties such as robustness, adaptivity, or scalability. The first question (Design) stated in the goals of the thesis in Section 1.1.2 is answered.
Future research may change the set of design principles adding newfound principles or removing those that prove themselves not founded enough. But in addition, research effort must be invested into quantitative constraints of self-organization. Particularly, the effectiveness of stigmergetic coordination strongly depends on the number of individuals participating. If there are too less or too many agents, coordination may fail. As there are now qualitative design principles, stating what the agents are, how they interact, or what the system architecture should look like, there must be rules supporting the design and tuning of coordination mechanisms on the basis of the number of participating agents or the quantitative dynamics of the environment.
Section 3.3 answers the second question (Realization) concerning the support for the implementation of stigmergetic agent coordination mechanisms in software systems. There, a specification for the implementation of the pheromone infrastructure in an agent runtime environment is given. The pheromone infrastructure extends the services of a runtime environment and provides the agents of an application with generic services required to implement sign-based stigmergetic coordination.
The formal model of the pheromone infrastructure (Section 3.2) aims at the third question (Evaluation) this thesis should answer. In general scenarios in Section 3.2 and specifically in the discussion of the emerging behavior of the GMC system in Section 4.5 the formal model is used to predict, tune, and evaluate specific agent interactions and pheromone-based coordination mechanisms. Finally, it is argued in Section 6.2 that such a bottom up approach may eventually lead to the formal evaluation of emerging agent
The fourth question (Application) is different from the other three. It states an engineering problem that is to be solved applying the design principles, the pheromone infrastructure, and its formal model. The GMC system presented in Chapter 4 is a manufacturing control system that combines robustness and flexibility with optimization on the basis of production goals. Three components of the system (control system, interface layer, advisory system) are specified in detail (Sections 4.2-4.4) and their emerging behavior is evaluated in a small but realistic example of a manufacturing system (Section 4.5).
The actual optimization process runs outside of these three layers. Section 5.1 proposes concepts that should realize an automatic on-line optimization of the material flow in the manufacturing system according to the production goals. These concepts have yet to be translated into detailed specifications before they may be evaluated in the same way the lower layers are evaluated.
Another path for future research is opened up in Section 5.2. Distributed self-organizing manufacturing systems require new approaches to visualization. The visualization methods should intuitively integrate into the control system. Robustness, adaptability, self-organization, and scalability are requirements not only for the control system itself, but also for the visualization. The architecture of the GMC system provides a basis to follow a new approach to visualization too.
In Future Research I (Chapter 5), concepts for the further extension of the GMC system are presented in detail. The following section suggests additional research activities. It proposes the exploration of quantitative principles for the design of synthetic ecosystems, an extension of the PI, and the improvement of the support for tuning and evaluation of the system-level features that emerge.
Chapter 3 proposes a number of qualitative design principles for synthetic ecosystems. It is a qualitative characteristic of the agents to be small and heterogeneous, to share knowledge, or to sense and act locally. Quantitative characteristics of the resulting agent system are only an effect of the application of these qualitative principles. For instance, if the agents are small, simple, and localized and if the control is emergent, then the resulting system often comprises a large number of agents. But, the designer still does not know what granularity to choose, and hence the actual number of agents and the employed coordination mechanisms may vary widely for the same application problem.
Future research into design principles should focus on quantitative support for the designer. The emergence of multi-agent coordination depends on the number of agents participating. For every chosen coordination mechanism there may be a minimum and a maximum number of agents beyond which the intended system-level behavior fails to appear. If there are not enough agents, then the influence of the single individual is too strong and the required statistical or probabilistic abstraction is not given (Section 6.2.1). On the other hand, if there are too many agents, important differences in the states of the
129system may not be perceived anymore because they all blur into one or two major states. Furthermore, too many agents at one place may overload the local server.
Quantitative design principles do not only refer to the number of agents, they should also support the setup of the dynamics of the system. For instance, the response time is an important feature in real-world application systems. The numerical analysis of the PI includes a prediction of the time required for pheromone patterns to stabilize in a given scenario (Section 3.2). Such results should be extended to characterize specific emergent coordination mechanisms.
The PI is a generic extension of runtime environments for software agents that enables the agents of the application to sense pheromone patterns and to place pheromones in arbitrary quantities. Neither the infrastructure, nor its formal model implies a specific input behavior of the agents. Any input pattern in space and time is permitted.
The analysis of the PI focuses on a specific local input pattern generated by a repeated input of a fixed amount of a pheromone (Section 3.2). A regular input pattern is the basic assumption for a number of numerical predictions of pheromone patterns and it occurs in the GMC system many times.
An extension of the PI may provide specific support to the agents for their regular refresh. An application agent might want to register the parameters of the regular refresh (input strength, input rate) instead of regularly sending input messages to its current Place-agent. In turn the Place-agent registers a weaker regular refresh with its neighbors in the propagation direction of the pheromone. The registration is spread recursively as long as the registered input strength has not fallen below a fixed threshold. If the application agent decides to stop the input, it de-registers the regular refresh.
The emulation of regular refresh activities by the network of Place-agents requires a change in the local pheromone management. In the implementation proposed in Section 3.3, a Place-agent computes the current pheromone strength whenever a new input occurs or when an agent accesses the pheromone. Therefore, the Place-agent only has to know the time that has passed since the last update and it just applies the simple evaporation function . But, the new transition function is much more complex if the Place-agent should compute the new pheromone strength asynchronously, incorporating all emulated regular refresh actions that would have occurred since the last update.
A regular refresh activity is not intended to provide its inputs at specific points in time. It rather sets off the evaporation to some degree. Such an interpretation already permitted a significant reduction of the complexity of the numerical predictions in Section 3.2 and it may also reduce the complexity of the new transition function when regular refresh activities are emulated. The Place-agent just determines the offset to the evaporation parameter, which results from the currently registered regular refresh activities.
The statistical emulation of regular refresh activities has a positive sideffect. The pheromone strength oscillates as long as the application agents provide the input themselves, especially when the parameters of the refresh behavior are set to widely spaced strong inputs. As a consequence, the error in sampling the intended pheromone strength may be large. In the statistical emulation the error is gone, because all refresh activities are normalized to one input per unit time. With the inherent normalization of the impact of the
130single agent, the minimally required number of agents for emergence (see previous section) may actually be lower. But in any case, the communication between the application agents and the PI is significantly reduced.
The development of quantitative design principles and the proposed extension of the PI have consequences for the tuning and the evaluation of the emerging system-level behavior. It should be a goal to have a theory of emergence that formally predicts the effectiveness of a coordination mechanism in the face of a given problem by the number of agents employed. Such a theory should also tell a designer the optimal parameter settings. For example, the tradeoff between the longest path of a Ghost-agent and the quality of the emerging prediction of a future pattern in the GMC system should be balanced.
On the other hand, the agents could be made more adaptive. Instead of tuning every parameter of a coordination mechanism, each agent should learn the best parameter setting for the application at hand. Future research should specify a generic extension of agents that operate in the PI to support learning of agent parameters, and reinforcement learning may be an attractive candidate.
The PI has some similarities to artificial neural networks. Neural networks also specify a set of spatial locations (neurons) where activation levels are stored and there is also a propagation of activation events among these locations. The transition function in the PI differs from the activation function in neurons. Future research should investigate if the similarities between artificial neural networks and the PI are sufficient to adapt findings.
Results gained in the research into complex dynamical systems should be applied to support the designer in the tuning and evaluation process. The stability of emergent system-level features in the face of external changes and disturbances is an important issue in the evaluation of an application system. Self-organization often includes multi-stability and the behavior of the interacting individuals may be non-linear. The stable state of the system is identified with a number of features that are observed. The stable states of a given application system and their respective features are determined in the evaluation as well as the requirements for transitions from one stable state to another.
© 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||
der Humboldt-Universität zu Berlin
|HTML - Version erstellt am:|
Fri Jun 15 12:30:34 2001