=Paper=
{{Paper
|id=None
|storemode=property
|title=Design and Simulation of a Wave-like Self-Organization Strategy for Resource-Flow Systems
|pdfUrl=https://ceur-ws.org/Vol-627/mass_9.pdf
|volume=Vol-627
|dblpUrl=https://dblp.org/rec/conf/mallow/SudeikatSSRRPS10
}}
==Design and Simulation of a Wave-like Self-Organization Strategy for Resource-Flow Systems==
https://ceur-ws.org/Vol-627/mass_9.pdf
Design and Simulation of a Wave-like Self-
Organization Strategy for Resource-Flow Systems
Jan Sudeikat, Jan-Philipp Steghöfer, Hella Seebach
Wolfgang Renz, Thomas Preisler and Peter Salchow and Wolfgang Reif
Multimedia Systems Laboratory (MMLab), Institute for Software and Systems Engineering,
Faculty of Engineering and Computer Science, Augsburg University,
Hamburg University of Applied Sciences, Universitätsstrasse 6a, 86135 Augsburg, Germany
Berliner Tor 7, 20099 Hamburg, Germany Email: {steghoefer, seebach,
Email: {jan.sudeikat, wolfgang.renz, reif}@informatik.uni-augsburg.de
thomas.preisler, peter.salchow}@haw-hamburg.de
Abstract—In resource-flow systems, e.g. production lines, This paper also shows how to pragmatically combine a top-
agents are processing resources by applying capabilities to them down approach for the design of agent-based systems with a
in a given order. Such systems profit from self-organization as bottom-up approach for the design of inter-agent coordination.
they become easier to manage and more robust against failures.
This paper proposes a decentralized coordination process that While the exact interplay of the two concepts is not fully
restores a system’s functionality after a failure by propagating elaborated here, it already becomes clear that both approaches
information about the error through the system until a fitting are not necessarily orthogonal but that it is beneficial to
agent is found that is able to perform the required function. The combine both views.
mechanism has been designed by combining a top-down design This paper is structured as follows: in the following section,
approach for self-organizing resource-flow system and a systemic
modeling approach for the design of decentralized, distributed the ODP, as a conceptual model for self-organizing resource-
coordination mechanisms. The systematic conception of the inter- flow systems, is discussed and a prominent application sce-
agent process is demonstrated. Evaluations of convergence as well nario, i.e. production automation, is introduced. In Section
as performance are performed by simulations. III, a programming model for self-organization is introduced.
Subsequently, the intended coordination dynamics of self-
I. I NTRODUCTION organizing resource-flow systems are presented (see Section
IV) and the realization of a decentralized role allocation
A key driver in the development of autonomous and auto- strategy is discussed and evaluated (Section V). Finally, we
nomic systems is the handling of complexity in large appli- conclude and give prospects for future work.
cations that consist of a great number of interacting entities.
Traditional management and failure-handling approaches are II. D ESIGN OF S ELF -O RGANIZING R ESOURCE -F LOW
no longer applicable as they do not scale well with the size S YSTEMS
of the systems and the communication required by a central In production automation systems, resources are transported
management becomes prohibitive, even with modern high- between machines to subject these work peaces to a specific
speed networks. Therefore, engineers and computer scientists sequence of work steps. The sequence of machines is typically
turn to self-organization as a means to deal with large complex static. The machines that process the resources are highly
systems and to keep up with the growth of such applications. specialized and only have one particular capability, i.e. an
In this paper, we present a self-organizing process for the individual operation, they can apply to the resources. The
class of self-organizing resource-flow systems. This class can transport of resources is fixed as well, e.g. by a static layout of
be applied to a great variety of domains such as production conveyor belts. This rigid structure simplifies the management
automation and logistics and systems in it can be modeled but has far-reaching implications, since reconfigurations are
with the Organic Design Pattern (ODP) [1]. The decentralized obstructed. The complete system has to be halted when
process proposed here is analyzed and modeled with the internal errors make a single system component inoperable.
tools provided by the SodekoVS project [2]. Changes in the Adjustments of the production process have to be carried out
configurations of agents propagate through the system like by stopping the system and retooling machines.
a wave until the system in its entirety has restored a stable A visionary alternative are flexible, agent-based production
state. During reconfiguration, parts of the system that are not lines that enable failure tolerance. Machines can autonomously
affected by the process or have already been reconfigured are reconfigure and transports of resources are carried out by au-
still able to resume their normal work. Evaluations show the tonomous guided vehicles (AGVs). Such a scenario is depicted
quick convergence to stable states and the reconfigurations in Fig. 1 where robots process a car body which is transported
only affect system partitions. between the processing stations by autonomous carts.
Fig. 1. Robots with different capabilities (icons to the right of the robot)
process a car by applying one of their capabilities each (highlighted icon).
There are other domains where similar resource-flows occur,
e.g., logistic scenarios or web service orchestration, we call
this class of systems Self-Organizing Resource-Flow Systems.
Their basic structure can be described with the ODP [3]
which defines the elements that constitute the system and
their relationship as shown in Fig. 2. Task define the required
processing of resources. Processing steps are carried out by Fig. 2. The elements of the ODP for Resource-Flow Systems.
agents. The states of resources are modified by applying
capabilities. Agents have a set of capability available and
exchange resources, based on the shop layout (inputs and hold during the entire runtime of the system. Whenever the
outputs). Which capability an agent applies and with which invariants are violated, the system has to be reconfigured to
agents it exchanges resources is determined by a role1 . Roles fulfill the invariants again (Restore Invariant Approach [3]).
have a precondition that describes where the resource is The individual agents are able to monitor local invariants and
coming from, which state it has, and which task has to be thus implement the observation part of the O/C. The controller
performed on it. They also have a postcondition that describes part of the O/C is then responsible to calculate a new allocation
to which agent the resource has to be given and which state and of roles that restore the resource-flow and ensure that each
task it has after the agent has processed it. Most importantly, agent has a role that fits its capabilities and its input/output
the role defines the capabilitiesToApply, i.e., what an agent is relationship with other agents. How this calculation is done,
supposed to do with the resource. however, is not specified at this point.
To fulfill the tasks for a resource (i.e., to apply the correct
III. S YSTEMIC P ROGRAMMING OF S ELF -O RGANIZATION
capabilities in the correct order), a resource-flow is established
by the allocation of roles to agents that determines how the In the research project ”Selbstorganisation durch Dezentrale
resource is moved through the system and processed on the Koordination in Verteilten Systemen”2 (SodekoVS) [2], a
way. This means the combination of the roles of the agents by programming technique is developed that allows to equip
their pre- and postconditions respectively, is a connected chain software systems with self-organizing features. The self-
of agents along which resources in the system are forwarded organizing inter-agent process is described by discrete design
and processed. There is usually one such chain or resource- elements [6]. This enforces a conceptual separation of the
flow for each task that has to be fulfilled in a system. Each agent functioning and the coordination, i.e. the correlation of
agent, however, can participate in more than one resource-flow agent activities.
and thus be involved in several tasks at the same time. First, a modeling level for the description of inter-agent
The interactions between the agents to handle resources are self-organization is provided. This modeling level supplements
also defined on the abstract system class level and can be agent-oriented software engineering practices with an orthog-
inherited by applications based on the ODP. They describe, onal description level that concerns the dynamic properties of
amongst other things, the handover of resources and the agent-based software systems [6]. The driving force of self-
detection of agent failures with a heartbeat mechanism. This organizing dynamics are distributed feedback loops among
way, both a formal analysis of the system class [3], generalized system elements [7]. These result from the mutual influences
mechanisms to deal with problems in the system class such among system elements and control how fluctuations in the
as deadlocks [4] as well as a generic runtime environment [5] system context are disseminated and collectively responded to.
become feasible. The systemic modeling level addresses the description of these
The ODP also contains an Observer/Controller (O/C). This networks of influences and it has been found that the visual-
element of the system structure is the abstract extension ization of the mutual interdependencies of system elements
point for the self-organization or reconfiguration mechanism. is useful for the anticipation of the dynamics that software
Correct system behavior is defined by invariants that have to systems are able to exhibit [8], [6]. Using a graph-based
modeling approach, System Dynamics [9] modeling concepts
1 Please note that some of the terminology used in ODP has a slightly are specialized for describing Multi-agent systems (MAS).
different semantics than the same terms in agent-oriented software engineering
due to the historic roots of ODP. 2 Self-Organisation by Decentralized Coordination in Distributed Systems
These models are given as an Agent Causal Behavior Graph
(ACBG) [10]. The nodes in this graph-based modeling level
represent system variables that characterize the macroscopic
state of a MAS. These describe the number of agents that show
a specific behavior, e.g. play a role. In addition, the current
value of an interaction rate can be denoted with a specific
node type. The links among these variables denote mutual
influences and interdependencies. In this respect, influences
denote additive or subtractive contributions to node values,
e.g. when the activity of an agent increases or decreases Fig. 3. The SodekoVS-Architecture for the embedding of decentralized
the stock of a warehouse. Interdependencies describe causal coordination in MAS [17].
relations where the activities of agents are mutually linked,
e.g. the number of hypothetical service requesters in a system
is expected to be positively linked to the number of activations coordination is exemplified in the Sections IV and V. A
of service providers. When the number of requesters increases, configuration language [10] allows to map ACBGs to agent-
the number of activations increases as well and vice versa. based software systems. These mappings describe the realiza-
Secondly, a programming model that allows the enactment tion of influences among agents, i.e. the coordination-related
of ACBG-based prescriptions of self-organization processes logic that controls the initiation, participation, and reaction to
[11], [10] facilitates application development. The key element interactions as well as the media that mediate interactions. The
is a distributed architecture for the enactment of decentralized detailing of these models, as a systematic programming effort,
inter-agent processes (cf. Fig. 3) [11]. This architecture serves is not discussed in this article but details on the configuration
as a reference model for the integration of ACBG-based of process enactments can be found in [17].
processes in MAS. It provides a conceptual framework for
fitting in different self-organization mechanisms and follows IV. S YSTEMIC M ODEL OF A DAPTATION DYNAMICS
a layered structure. The topmost layer (Application Layer) In [18], the systematic integration of decentralized coordi-
contains the realization of an agent-based application. The nation strategies in MAS has been discussed. The conception
contained agents are understood as self-contained providers of the appropriate coordination is approached by modeling the
of functionalities (Application Functionality). The contained problematic, unintended behavior of applications. Based on the
agents individually control their activities and an underlying identification of the Problematic Dynamic, a corresponding
Coordination Layer enables the purposeful affecting of agents Solution Dynamic is derived that supplements the application
to concert the localized activities and establish collective behavior with additional interdependencies and inter-element
behaviors. feedbacks to correct the system behavior and alleviate unin-
The Coordination Layer describes an event-based dis- tended effects.
tributed system [12], which allows to realize mutual influ- The Problem Dynamic of an ODP-based resource-flow
ences among system elements. These influences correspond systems is illustrated in Fig. 4 (right). Initially, agents are
to relations in ACBG-based models of inter-agent processes, running and one or several roles are allocated to them which
thus the layer is a means to enact the described processes in are executed in order to process resources. Random errors
MAS. The establishment of inter-agent influences, particularly make it impossible for the agent to apply one or more of
for the construction of self-organizing systems, is based on its roles. The adoption of roles that can not be applied is
two types of mechanisms [13], i.e. techniques for the infor- controlled by a fluctuating rate (RF interrupt) that is positively
mation exchange among agents (e.g. reviewed in [14]) and influenced by the availability of running, thus breakable,
mechanisms for the (adaptive) adjustments of agents (among agents and the changing number of error events (Error). This
others classified in [15]), due to the perceived information rate describes the resource-flows (RF) that are interrupted, due
(see Section VI). The Coordination Layer contains two types to the breaking of agents. These failures within individual
of functional elements for the encapsulation of these aspects. agents limit the number of running agents (negative link), thus
Coordination Media are conceptual containers of so-related the problematic system behavior is dominated by a negative
interaction infrastructures. Specific interaction modes, e.g. the feedback loop (α).
mediation by an environment [16] or Linda-like tuple spaces, If not handled, this dynamic causes the number of agents
are encapsulated and reused by a generic interface [11]. Coor- that are not running to increase over time. The design of
dination Endpoints interact on behalf of agents via these media an appropriate Solution Dynamic concerns the derivation of
and are able to influence the agent execution. These elements agent behaviors that counteract this unintended effect. A very
are used to encapsulate and automate the coordination-related general structure is given on the left hand side of Fig. 4.
activities. These activities concern the interactions vie Media, Agents that have roles they can no longer apply are Waiting
i.e. the invitation and participation of interactions, as well as for Reconfiguration. The rate of interrupts positively influences
the affectation of modifications in the agent models. the increase of this variable. The system is equipped with
The ACBG-based modeling of dynamics of inter-agent a reconfiguration mechanism, and for each of the waiting
to play a role that involves Cap. 1 but may also apply Cap.
3. Two types of Cart agents represent the initial provision
(Producer) and the final collection of the processed workpieces
(Consumer). Due to an error Robot1 can no longer apply Cap.
1 and sends a request for assistance (2). This request is routed
along the resource flow till it reaches an agent that is capable
to execute the needed capability, here Robot 2 which replies
to the request (3). The reply is routed to the requesting Robot
as well as the Carts that are connected to the swapping robots.
Consequently, the Robots and Carts reconfigure their local
Fig. 4. The Problem and Solution Dynamic of the ODP.
roles. The robots update their roles and the resource flow
is reestablished by adjusting the ports in the pre- and post-
conditions of the roles of the connected Carts to ensure that
agents a new configuration is determined. Thus the system workpieces reach the robots in the intended sequence. In the
shows a causal relation. In absence of waiting agents, no best case, the originating and the receiving agents can just
reconfigurations take place. Occurrences of waiting agents switch their roles, thus restoring the resource-flow.
enforce subsequent reconfigurations (Reconfigure) to restore a In Fig. 5, Robot 2 is able to provide capability Cap. 1 but
set of executable roles. The reconfigurations thus increase the Robot 1 is not able to replace Robot 2 as it is missing the
number of Running agents by complementing a counteracting currently utilized Cap. 2 (3). Thus after the swap, Robot 1
feedback loop (β). remains in a problematic state and requests assistance (4).
This Solution Dynamic deliberately omits the concrete This request is propagated again till it reaches a robot with
mechanism with which new role allocations are determined. the required capability (Robot 3) and the swap proceeds as
Also the locally applied techniques to the enactment of recon- above (5). Since Robot 1 is able to replace the currently active
figurations are abstracted. A method to express the problem of capability of Robot 3, i.e. Cap. 3, the correct sequence of ca-
finding a fitting role allocation as a constraint-solving problem pabilities is finally reestablished (6). Here, the reconfiguration
has been presented in [19] and solved with a centralized logic has been described for agents that only play on role at a
approach. Whenever an agent can no longer apply one of time and the subsequent simulations concerns this simplified
its roles or whenever an agent breaks, the resource-flow is scenario. In principle, agents can be part of several resource-
interrupted. When the interruption is detected, the system flows and in that case, the agents only reconfigure for roles that
reconfigures in order to restore the flow. During the course of include the broken capability and keep processing resources
the reconfiguration process, a new allocation of roles to agents of other tasks. Consequently, the informed Carts change only
is calculated and the roles are communicated to the agents the ports of the affected roles accordingly.
which then apply them again. The next section describes A detailed ACBG of the outlined reconfiguration algorithm
an alternative reconfiguration mechanisms in which new role is illustrated in Fig. 6. This description refines the previously
allocations are found in a decentralized fashion by propagating given Solution Dynamic (cf. Fig. 4) as it illustrates how the
the demand for local reconfigurations through the system. decentralized strategy relates to the dynamics of ODP. In
addition, it indicates the system-level effects of the decentral-
V. WAVE - LIKE D ECENTRALIZED R ECONFIGURATION ized reconfiguration that are examined in Section V-A. When
A completely decentralized reconfiguration approach is agents are Waiting for Reconfiguration due to error events,
based on the idea that a wave of role re-allocation runs through they show two behaviors. First, they are Deficient as one or
the system in order to re-establish the resource-flow. Assuming more roles, which are required for the processing of resources,
that each agent is capable to exhibit a set of capabilities (see are inoperable. These roles are distinguished by the reason for
Section II), a correct resource flow can be (re-)established by deficiency. Agents can be rendered deficient by error events
the appropriate swapping of roles. Failing agents adopt actable (By Break) or they deliberately decided to abandon a role in
roles and in return other agents help out by providing the order to adopt another role on behalf of another agent (By
unactable roles. The failing agent emits a wave of reallocations Change). In the former case, the agents are rendered inefficient
by sending requests for assistance along the resource flow. and in the latter case agents assist other agents. Secondly,
Each recipient has to decide locally if it is capable and will these agents are considered to be Non-Active, i.e. they have
swap roles. Generally, a single swap of roles is not enough to the capacity to play another role. Agents can concurrently play
reestablish the full sequence of activities and transitive changes several roles, therefore, the non-activity only denotes that the
of roles are required. agent is underutilized, i.e. is capable to exhibit another role.
The operating principle is exemplified in Fig. 5 for a simple This means that in agents that can play several roles, the
scenario that requires a transitive swap of roles. Three Robots Running and Non-Active roles do not exclude each other, but
are connected in series (1). For each agent the set of actable an agent can be associated to an active role (Running) and
capabilities are listed and the topmost capability is used in still have the capacities to play additional roles (Non-Active).
the currently active role, e.g. Robot 1 is currently configured Agents are equipped with the ability to autonomously
Fig. 5. Exemplification of the decentralized reconfiguration.
changing agents (source) commit to. Another commonality
is that the adjustment of a role entails the restoring of the
flow of resources among the agents (Restore RF). When
an agent has adjusted its role, those agents that received
resources from it or gave resources to it need to adapt as
well. This activity is separated from the role change as the
agents do not deliberately decide about these changes. These
are reconfigurations within connected agents that are enforced
as they are consequences of the deliberate changes. These
reconfigurations may as well by transmitted via Coordination
Media (see Section III).
Assisting another agent introduces new deficiencies, as the
assisting agent is giving up one role that needs to be played
by another agent (Deficient by Change). Thus the net amount
of Non-Active agents is unaffected. However, these changes
may be necessary in settings where agents can not swap
roles directly and transitive changes of roles are required (as
exemplified in Fig. 5). When Non-Active agents Resume to
adopt a role, the number of Non-Active agents is reduced.
Still, this requires the availability of Non-Active agents.
The changing activities of agents control the overall negative
Fig. 6. ACBG for the Solution Dynamic of the wave-like, decentralized feedback (β) that increases the number of operational agents
reconfiguration algorithm and reduces the number of deficient agents. Three auxiliary
feedbacks influence the exhibited system dynamics (δ,γ,ǫ).
First, agents that assist others create a reinforcing feedback
change their allocation (Change Role). Deficient robots in- loop (δ), which originates from the fact that an assisting agent
dicate their shortcoming to other agents (communicate de- adds additional deficiencies to the system. If an agent resumes
ficiency) via a Coordination Medium (cf. Section III). The its activities, deficiencies and non-active agents are removed
medium controls the sequential reception of the request along instead, thus instituting a balancing feedback (γ). The ability
the flow of resources in the production line. Recipients de- to resume is limited by the amount of Non-Active agents,
cide locally whether to change their role-allocation or not, leading to a third balancing feedback (ǫ).
based on their individual abilities. The changing behavior is
distinguished by the receiving agent that adjusts the local A. Estimating the Effects of Adaptation Dynamics
configuration. Non-Active agents Resume the executions since The outlined Solution Dynamic (cf. Fig. 4) denotes an inter-
these become operational. Running agents that adjust their role agent process that can be implemented with the systemic pro-
Assist the requesting agent. These roles have different effects gramming model (see Section III). Prior to the detailed design
on the agent population. All changes remove deficiencies and and embedding of this process, the effected system behavior
the annotation source.targetRole == destination.Role indicates is anticipated. One approach to estimate the dynamics of
that only those deficiencies are removed (destination) that self-organizing MAS is their simulation in stochastic process
algebra models [20]. It is important to note that the resulting the assisting adjustment. Deficiency ends when another agent
stochastic models abstract from the agent implementations and processes the request for a role change, communicated via the
their internal reasoning. Instead, stochastic terms are used channel reqc . This simulation model abstracts from the agents
to describe the dynamics with which specific behaviors are that participate in the system. The time needed to restore the
adopted or left. The number of currently active process terms resource flow (cf. Fig. 6), i.e. the adjustments of the roles of
resembles the number of agents that show specific behavior, the directly connected agents to reestablish the correct flow of
i.e. the variable-values of an ACBG-based process description. resources among machines, is part of the time delay τrc . We
Fig. 7 illustrates the simulation model used to anticipate assume that the rerouting of resource transportations is always
the Solution Dynamic. The model is given in stochastic π- possible.
calculus [21] and simulated with the Stochastic Pi Machine3 Simulations indicate that, at a high enough level of redun-
(SPIM). Details on the simulation language and graphical dancy, the system reliably recovers due to the decentralized
notation can be found in [22]. Agents are modeled as processes switching of agent roles. This process describes a structure
that communicate/interact via channels. The stochastics of formation as the system maintains the operational system
interactions are given by annotating processes with delays configuration. The fraction of recovering situations is predicted
(τ ) and assigning interaction rates to channels [21], [22]. The by this simulation to depend on the redundancy level in a
notation x denotes the sending of data on the channel x and similar way as is shown in the results section below.
x denotes the reception of data via the channel x.
B. Agent-based Realization
After the anticipation of the affected system behavior, this
reconfiguration strategy has been integrated in a MAS by using
systemic programming model (see Section III). The system
implementation (Application Layer, see Figure 3) makes use
of the freely available Jadex4 agent framework. The Robots
and Carts within production lines are represented by Jadex-
agents and the exchanged workpieces are mimicked by objects
that are exchanged via FIPA Agent Communication Language
(ACL) messages. A realization of the Coordination Layer (see
Fig. 3) for this agent platform is utilized [11].
For this application scenario a tailored Medium realization
is utilized that routes request and reply messages along the
Fig. 7. Simulation Model of the Solution Dynamic in Stochastic π-Calculus. resource flow. Conceptually though, agents are aligned in
a circle thus all agents can be reached independent of the
In the simulation model, the number of agent behaviors that location of the incapacitated agent. Endpoints encapsulate the
are exhibited are expressed by the number of active processes. logic to coordinate the reconfiguration process and interact
Processes communicate via two channels. The channel reqb is via the Medium. Endpoints observe the agent-operation and
used to communicate requests for a role-switch, due to an initiate the reconfiguration process by sending a help request
internal error, i.e. the internal breaking of the requester. When if an agent becomes deficient. The help request is forwarded
roles are requested to be switched in order to assist an agent, through the medium. Each endpoint along the message path
these requests are send via the channel reqc . Operative agents decides whether to adopt the deficient agent’s role or continues
are denoted by the running process. Internal errors occur with forwarding the help request. If the endpoint decides to adopt
a fixed rate, as defined by the delay τb . Inoperative robots the role, a reply is sent. The reply is sent in both directions
are represented the concurrent execution of the def icientb through the medium to inform all agents which are affected
and non-active processes. Deficient processes end when a (robots and connected carts) by the reconfiguration process.
request for re-assignment of the affected role is processed by a Again, each endpoint receiving the reply decides to change the
recipient. The non-active processes become resume processes agent configuration. The reply is sent backward through the
when they receive any request for re-allocation. The time delay medium until all affected agents are informed. If an endpoint
τrc resembles the time needed to reconfigure. Afterwards, the receives multiple coordination messages these messages are
agent is in operation, i.e. exhibits the running process. When queued and processed in the order of their arrival.
running agents receive a request to switch roles, they convert
C. Implementation Test Results
to the concurrent execution of the assist and def icientc
processes. The assistance transforms back to the running The example system illustrated in Fig. 5 has been imple-
process, delayed by the time to reconfigure the agent (τrc ). The mented and tested for measuring the handling of breaking
def icientc processes describe the search for another agent that capabilities. When the robot is rendered incapacitated by such
is able to play the role that an assisting agent possessed before an event, the associated endpoint notices this and initiates
3 http://research.microsoft.com/en-us/projects/spim/ 4 http://jadex-agents.informatik.uni-hamburg.de/
an interaction via the Coordination Medium that triggers the However, these papers from operations research focus on
swapping of roles. The first swap involves the incapacitated optimization of a shop floor and do not take into account
agent that is Deficient by Break. In this system configuration, robustness and reconfiguration that happens at run-time. Also,
a second swap is required that resolves a transient Deficient only partial problems are investigated, either focusing on the
by Change agent behavior. routing of carts or the scheduling of production machines.
In addition, we examine the relation of the redundancy The work presented here concerns the run-time reconfig-
within agents with the effectiveness of the reconfigurations. uration by self-organization. The maintained structure is a
The effectiveness of the reconfiguration procedure is in- correct sequence of agents that are perturbed by individual
fluenced by the number of alternative capabilities that are failures that incapacitate agents. Prominent alternatives to the
available to the individual agents. This level of redundancy process presented here are centralized/distributed constraint
is measured by the ratio of the number of individual ca- solving techniques and market-based mechanisms. The correct
pabilities (Ci ), to the absolute number of capabilities (C) configuration is described with constraints and an approach
that are required for the processing of a workpiece ( CCi ). to use centralized constraint solving to restore functionality
In the following, we assume a homogeneous setting, where after a failure has already been published [19]. Consequently,
the robots are equipped with an equal number of redundant distributed constraint solving techniques [26] can be used as
capabilities. The composition of these capabilities is normally well, e.g. as studied in [27]. An example for market-based
distributed. In Fig. 8, measuring results for a simple scenario mechanisms is given in [28]. A manufacturing line is provided
with 10 different capabilities and agents are shown. Each with a flexible transport mechanism and work pieces and
single run processes of a fixed number of workpieces while, machine agents negotiate for the execution of working steps.
at two fixed instances of time, a randomly selected agent In a way, the algorithm proposed in this paper is an optimistic
is incapacitated. A first estimate of the effectiveness of the and minimalistic version of a distributed constraint solver. By
reconfigurations is the number of exchanged messages (see exchanging roles, the agents collectively restore the invariants
Fig. 8). The number of messages increases quickly when the of the system. The strategy is minimalistic since the number
number of redundancies decreases. This measurement can be of required messages and the amount of shared information is
analytically fitted with (c1 ∗(1−x))2 +c2 .5 . A complementary reduced. It is optimistic because the assisting role changed are
measurement is the number of hops that requests for assistance carried out before the complete solution is calculated. Its main
travel before a swapping agents is found. This describes the advantage over traditional distributed constraint solvers is the
logical distance between the swapping agents. The results for minimal amount of calculation that is involved at the agents.
this measurement have shown the same characteristics like the They can therefore be very small with only minimal CPU
message count and can be fitted with the same function (but power and RAM, making them cheap and easily replaceable.
different constants). Thus the decentralized reconfiguration Here, these design alternatives are qualitatively character-
strategy is particularly suited for production lines where the ized by a subset of criteria from [29]. Their quantitative com-
capability types are often available. parison is left for future work. A first aspect is the necessary
communication. The presented process minimizes the message
content and only the information that immediately necessary
to resolve a local failure is communicated. The number of
messages ranges from a single role swap (best case) to the
successive swapping of roles by all agents (worst case). The
dependence of this measure on structural properties is shown
in Figure 8. The communications are only carried out when
failures are present. Alternatives involve that coordination-
related messages have to be exchanged during the normal
system operation, e.g. as workpieces constantly negotiate their
Fig. 8. Measurement results. The averaged number of messages are plotted further processing [28]. Also the amount of computations and
over the redundancy of capabilities. the considered/exchanged knowledge about the system state
is minimized. The participation in the process involves only
VI. R ELATED W ORK the local consideration whether an agent is capable to play a
required role. Now further information about the global system
Ant Colony Optimization has been used for decentralised
state is processed. Centralized constraint solvers require the
control in production systems. [23] uses the mechanism to
full knowledge about the system and decentralized solvers
control autonomous vehicles, similar to our carts. The distri-
require the information from neighboring agents. In addition,
bution of jobs to production machines has not been a concern
the adaptations are carried out concurrently to the system
there. The more complex problem of scheduling jobs to run
operation. Unaffected partitions of the production line continue
on certain machines has, e.g., been tackled in [24] and [25].
to work. Finally, the accuracy of the quality of the found
5 c , c are application dependent constants. In this case, these are 10 and
1 2
solution, i.e. stable configuration, varies. The process follows
12 respectively. the heuristic that role swaps of nearby agents are favored over
the swaps of (logically) distant agents. The explicitly treatment [6] J. Sudeikat and W. Renz, “Qualitative modeling of mas dynamics -
of the underlying constraint problem allows in principle to using systemic modeling to examine the intended and unintended con-
sequences of agent coaction,” in Agent-Oriented Software Engineering
prepare the optimization of the found solutions. X. Springer, 2009, to be published.
[7] Y. Brun, G. di Marzo Serugendo, C. Gacek, H. Giese, H. Kienle,
VII. C ONCLUSIONS M. Litoiu, H. Müller, M. Pezzè, and M. Shaw, Software Engineering
for Self-Adaptive Systems. Springer-Verlag, 2009, ch. Engineering Self-
In this paper, we have described a decentralized recon- Adaptive Systems through Feedback Loops, pp. 48–70.
[8] W. Renz and J. Sudeikat, “Modeling feedback within mas: A systemic
figuration process to restore valid system configurations in approach to organizational dynamics,” in Organised Adaptation in Multi-
self-organizing resource-flow systems. The reconfiguration al- Agent Systems, 2008, pp. 72–89.
gorithm works by exchanging roles with neighboring agents [9] J. D. Sterman, Business Dynamics – Systems Thinking and Modeling for
a Complex World. McGraw-Hill, 2000.
and by propagating change requests in a wave-like manner [10] J. Sudeikat and W. Renz, “MASDynamics: Toward systemic modeling
until all of them could be satisfied. The mechanism has of decentralized agent coordination,” in Kommunikation in Verteilten
been developed by combining a top-down process for the Systemen, ser. Informatik aktuell, 2009, pp. 79–90.
[11] ——, “Decomas: An architecture for supplementing mas with systemic
description of resource-flow systems and a bottom-up process models of decentralized agent coordination,” in Proc. of the 2009
for the design of agent coordination. Its performance has been IEEE/WIC/ACM Int. Conf. on Intel. Agent Tech., 2009, pp. 104–107.
demonstrated with a number of simulations. [12] G. Mühl, L. Fiege, and P. Pietzuch, Distributed Event-Based Systems.
Springer-Verlag New York, Inc., 2006.
The most interesting feature of the decentralized process [13] J. Sudeikat and W. Renz, Applications of Complex Adaptive Systems.
proposed here is that reconfigurations are organized locally in IGI Global, 2008, ch. Building Complex Adaptive Systems: On Engi-
the production line, i.e. the rest of the system is not impaired neering Self–Organizing Multi–Agent Systems, pp. 229–256.
[14] T. DeWolf and T. Holvoet, “Decentralised coordination mechanisms as
by a failure. Thus, parts of the system that are not involved into design patterns for self-organising emergent systems,” in Engineering
a local reconfiguration can continue to run normally. The way Self-Organising Systems, vol. 4335/2007, 2007, pp. 28–49.
the reconfiguration propagates also ensures that only a small [15] G. D. M. Serugendo, M. P. Gleizes, and A. Karageorgos, “Self-
organisation and emergence in mas: An overview,” in Informatica,
amount of agents is in a state of non-processing resources vol. 30, 2006, pp. 45–54.
at an instance of time. This feature will be prominent also [16] H. V. D. Parunak and S. Brueckner, “Engineering swarming systems,” in
when using the wave-like algorithm in non-linear production Methodologies and Software Engineering for Agent Systems. Kluwer,
2004, pp. 341–376.
situations, which is a straight-forward generalization instance. [17] J. Sudeikat and W. Renz, “Programming adaptivity by complementing
Local heuristics taking into account exchange–success rates agent function with agent coordination: A systemic programming model
could be predefined or evolved using learning algorithms. and development methodology integration,” Communications of SIWN,
vol. 7, pp. 91–102, may 2009, iSSN 1757-4439.
Future work includes a more detailed study on the combination [18] ——, “On the modeling, refinement and integration of decentralized
of bottom-up design of coordination methods as proposed in agent coordination – a case study on dissemination processes in net-
SodekoVS and of top-down design methodologies as promoted works,” in Self-Organizing Architectures, 2010, pp. 251–274.
[19] F. Nafz, F. Ortmeier, H. Seebach, J.-P. Steghöfer, and W. Reif, “A
with the ODP. This will also include a comparison of their universal self-organization mechanism for role-based Organic Comput-
respective advantages and problems that occur when both ing systems,” in Proceedings of the Sixth International Conference on
worlds are combined. Autonomic and Trusted Computing (ATC-09), 2009.
[20] M. Casadei, L. Gardelli, and M. Viroli, “Simulating Emergent Properties
of Coordination in Maude: the Collective Sorting Case,” in 5th Int.
ACKNOWLEDGMENT Workshop on the Foundations of Coordination Languages and Software
Architectures (FOCLASA), 2006.
This research is partly sponsored by the German research [21] C. Priami, “Stochastic π–calculus,” Computer Journal, vol. 6, pp. 578–
foundation (DFG) in the project SodekoVS and in the DFG 589, 1995.
special priority program “Organic Computing” (SPP 1183) in [22] A. Phillips, Symbolic Systems Biology: Theory and Methods. Jones and
Bartlett Publishers, 2010, ch. A Visual Process Calculus for Biology.
the project SAVE ORCA. [23] V. A. Cicirello and S. F. Smith, “Ant colony control for autonomous
decentralized shop floor routing,” in International Symposium on Au-
R EFERENCES tonomous Decentralized Systems, 2001.
[24] N. Liouane, I. Saad, S. Hammadi, and P. Borne, “Ant systems & local
[1] H. Seebach, F. Ortmeier, and W. Reif, “Design and Construction of search optimization for flexible job shop scheduling production,” Int.
Organic Computing Systems,” IEEE Congress on Evolutionary Compu- Journal of Comp., Comm. & Control, vol. 2, no. 2, pp. 174–184, 2007.
tation, 2007, pp. 4215–4221, Sept. 2007. [25] C. Gagné, M. Gravel, and W. L. Price, “Solving real car sequencing
[2] J. Sudeikat, L. Braubach, A. Pokahr, W. Renz, and W. Lamersdorf, problems with ant colony optimization,” European Journal of Opera-
“Systematically engineering selforganizing systems: The sodekovs ap- tional Research, vol. 174, no. 3, pp. 1427 – 1448, 2006.
proach,” Electronic Communications of the EASST, vol. 17, 2009. [26] M. Yokoo, E. Durfee, T. Ishida, and K. Kuwabara, “The distributed
[3] M. Güdemann, F. Nafz, F. Ortmeier, H. Seebach, and W. Reif, “A spec- constraint satisfaction problem: Formalization and algorithms,” IEEE
ification and construction paradigm for Organic Computing systems,” Transactions on Knowledge and Data Engineering, vol. 10, no. 5, pp.
in Proceedings of the Second IEEE International Conference on Self- 673–685, 1998.
Adaptive and Self-Organizing Systems, 2008, pp. 233–242. [27] G. Clair, E. Kaddoum, M.-P. Gleizes, and G. Picard, “Self-regulation in
[4] J.-P. Steghöfer, P. Mandrekar, F. Nafz, H. Seebach, and W. Reif, “On self-organising multi-agent systems for adaptive and intelligent manu-
Deadlocks and Fairness in Self-organizing Resource-Flow Systems,” in facturing control,” in SASO ’08: Proc. of the 2008 Sec. IEEE Int. Conf.
Proceedings of the 30th International Conference on Architecture of on Self-Adaptive and Self-Organizing Systems, 2008, pp. 107–116.
Computing Systems (ARCS), LNCS 5974. Springer, 2010, pp. 97–100. [28] N. R. Jennings and S. Bussmann, “Agent-based control systems,” IEEE
[5] F. Nafz, F. Ortmeier, H. Seebach, J.-P. Steghöfer, and W. Reif, “A generic Control Systems, vol. 23, no. 3, pp. 61–74, 2003.
software framework for role-based Organic Computing systems,” in [29] E. Kaddoum, M.-P. Gleizes, J.-P. Georgé, and G. Picard, “Characterizing
SEAMS 2009: ICSE 2009 Workshop Software Engineering for Adaptive and evaluating problem solving self-* systems,” in COMPUTATION-
and Self-Managing Systems, 2009. WORLD ’09: Proc. of the 2009 Computation World, 2009, pp. 137–145.