Mesoscopic Stochastic Models for Validating Self–organizing Multi–Agent Systems

Wolfgang Renz and Thomas Preisler

Hochschule fur Angewandte Wissenschaften HamburgFakultat Technik und Informatik, Labor fur Multimediale Systeme

Berliner Tor 7, 20099 Hamburg, Germany{wolfgang.renz, thomas.preisler}@haw-hamburg.de

Jan Sudeikat

Hamburg Energie GmbH, Produktion, IKTBillhorner Deich 2, 20539 Hamburg, Germany

jan.sudeikat@hamburgenergie.de

Abstract—The construction of self–organizing Multi–AgentSystems (MAS) is still short of systematic validation meth-ods. These are crucial for acceptance of self–organization inmainstream software engineering. Validation of such systemsrequires the use of formal descriptions of the underlyingcoordinating process during the engineering process. The hereproposed approach is based on stochastic validation methodsapplied to the microscopic states under an ergodicity assump-tion. Thus, we propose in this paper Mesoscopic StochasticModels as a novel methodological artefact for validating self–organizing multi–agent systems. To demonstrate the power ofthis method we apply it to a self–healing resource–flow system,in which a decentralized coordination process is used to restorethe system’s functionality after a failure. Information about theerror is propagated through an overlay until the system is ableto restore its original functionality.

Keywords-multi–agent system; self–organizing; self–healing;decentralized coordination; agent oriented software engineer-ing; mesoscopic stochastic model

I. INTRODUCTION

Self–healing systems are a special class of self-adaptive

systems suitable to self-maintain and recover after failure

conditions. In some real applications it is desirable to equip

an existing manually maintained system with a self–healing

expansion to raise system availability. One way to realize

the self–healing process is to identify redundant capabilities

in different system components and to enable the actors to

help each other by exchanging or allowing access to their

redundant capabilities. Such a process might not be very

successful in a small system with little redundancy but could

be enhanced when systems join a larger group of systems

with redundant capabilities for failure recovery. The devel-

opment of the self–healing process requires several steps

of validation addressed in this paper. We have developed

an approach generally applicable to self–organizing systems

and apply it here to a self-healing resource–flow system as

a representative of a specific class of self-adaptive systems.

The goal of this paper is to present the MEsoscopicStochastic (MES) model as a suitable novel methodological

artefact for validating self–organizing multi–agent systems

(MAS). For validating such systems, mathematical analysis,

stochastic simulation or inspection of the agent coaction, are

established techniques usually based on macroscopic system

state observables like Running, Interrupted, Waiting for re-

configuration or Reconfiguring. These techniques were also

introduced as methodological artefacts in agent–oriented

methodologies [1], [2]. Here we argue that self–organizing

MAS should be validated with respect to certain systemobservables. Since the underlying coordinating process that

is responsible for the self–organizing behavior introduces

new microscopic variables (and corresponding states), the

macroscopic artefacts are not sufficient to validate the system

with respect to observables related to these states, i.e. to vali-

date the systems self-organization. Thus, the MES model, as

an artefact related to these microscopic variables can than be

used to validate the system with respect to its self–organizing

behavior. The MES model is called mesoscopic since it

approximates transition probabilities for the microscopic

states of an agent by values calculated from an averaged

behavior of the rest of the system (ergodicity assumption).

The rest of the paper is organized as follows. In sec-

tion 2 related work is presented. Section 3 describes the

methodology of the integration of decentralized coordination

and introduces the MES model. Section 4 describes the

application to self–healing resource–flow systems, where

the reconfiguration mechanism is presented and the MES

model constructed. Section 5 shows the validation of the

self-healing process based on the MES model. Finally a

conclusion is drawn and future work discussed.

II. RELATED WORK

An other approach on how to validate agent based systems

is presented in [3]. There the authors present a frame-

work for the validation of agent based simulations using

a virtual overlay MAS to validate the underlying agent

based simulation model. Their goal is it to present a new

single validation technique applicable to all agent based

models. Therefore the virtual overlay MAS can comprise

various types of agents which form an overlay on top

of the agent based simulation model that needed to be

validated. Therefore although being based on a different

validation technique then the one proposed in this paper,

both approaches aim at the same direction to be able to

validate all kind of agents based systems and simulations.

The work presented in [4] is based on the same application

2012 IEEE Sixth International Conference on Self-Adaptive and Self-Organizing Systems Workshops

978-0-7695-4895-1/12 $26.00 © 2012 IEEE

DOI 10.1109/SASOW.2012.29

119

context as the case study presented in this paper due to

previous joint publications [5]. The authors introduce a

software engineering guideline for self–organizing resource–

flow systems along with an elaborated pattern that describes

the elements of the system under construction and their

collaborations. The guideline and patterns form the basis

for a well–defined approach for the design and construction

of resource–flow and similar systems. An overview about

current work in the field of software engineering for self–

organizing systems is given in [6]. While this paper proposes

the use of mesoscopic stochastic models for the validation of

self–organizing MAS and integrates the usage into a Coor-

dinating Integration process following software engineering

principles, the review in [6] surveys current work in this

field and outlines the main themes, identifies challenges

for future research and addresses the continuity between

software engineering in general and techniques appropriate

for self–organizing systems. Related work has be done in

[7] where a general overview about the area of Software

Process Engineering (SPE) and recent developments of SPE

in the agent–oriented software–engineering field is given.

The authors argue that process engineering is one of the most

stimulating research lines in software engineering today and

is also a hot topic in agent oriented software engineering

research. They present a number of designed methodologies

and describe the current proposed approach to take benefits

to all existing methodologies and to reuse those parts that are

the most relevant during the development process in order

to build a new process engineering. These approach seams

also to be suitable for the design of self–organizing MAS

like the case study described in this paper.

III. THE SYSTEMATIC INTEGRATION OF

DECENTRALIZED COORDINATION

The here proposed use of MES models for the validation

of self–organizing MAS is integrated in the CoordinationIntegration process described in [8]. The there proposed

software engineering process provides five additional activ-

ities to well known software engineering processes, which

support the development of decentralized MAS. Major parts

of the application development follows conventional de-

velopment practices. These additional activities guide the

conception and integration of decentralized coordination into

MAS. The definition of the development process follows the

Software & Systems Process Engineering Metamodel Spec-

ification (SPEM)1 terminology. It is pooled in a CapabilityPattern. Fig. 1 illustrates the control flow of the outlined

development activities. Particularly, the artefacts accessed,

modified and created are indicated.

The Adaptivity Requirements precedes the definition of a

Coordinating Process. In this activity the context of the ap-

plication is examined and the required adaptivity at the sys-

1http://www.omg.org/spec/SPEM/2.0/

tem is identified. The application context is given by an in-

formal Domain Description. When available, initial models

of the systems structure, e.g. an Organizational MAS Modelor an Environment Model are processed. Subsequently,

the Coordinating Process Definition is concerned with the

derivation of a scheme for the decentralized coordination.

In this activity, optional descriptions of the system design,

e.g. the Environment Model, Organizational MAS Modeland Agent Model(s) are processed. This activity results in

an abstract process description (Coordinating Process (MASDynamics Model)). This model excludes implementation–

specific details of the agent models but describes a minimal

set of fundamental interdependencies which constitute the

decentralized process among system elements that is able

to show the intended level of adaptivity. The next step

is the optional Coordination Validation (Qualitative) using

stochastic simulation techniques and formal modeling. The

previously derived Coordinating Process (MAS DynamicsModel) may be used as input for this validation. When it is

shown that the conceived Coordinating Process is capable

to meet the systems adaptivity requirements, the process is

integrated into a concrete system realization. The Activity

Coordinating Process Integration addresses the joining of

implementation–specific details to the process specification

in order to prepare the enactment of the process. The output

is a set of agent models that are prepared to participate in the

Coordinating Process. As final activity the resulting system

must be validated (Coordination Validation (Quantitative)).System simulations are required to check whether the Co-

ordinating Process has the intended effects on the systems

behavior.

A. The Mesoscopic Stochastic Model

An addition to this systematic integration of coordina-

tion as given in [8] is the MES model. The MES model

is derived from the Coordinating Process Definition and

describes the Coordinating Process as a stochastic model,

based on a microscopic characteristic that describes the

Coordinating Process. The creation and usage of a MES

model is illustrated as an UML2 activity diagram in Fig.

2. The first step is the identification of the microscopic

variables relevant for the Coordinating Process. This activity

requires an abstract description of the Coordinating Processas an input artefact. As shown in Fig. 1 both this artefact

and the MES model itself result form the CoordinatingProcess Definition development activity as part of the sys-

tematic integration of decentralized coordination. To find

the microscopic variables that characterize the CoordinatingProcess one has to analyze the Coordinating Process Modeland identify the variables which characterize the overall

quality of the process. The next step is to determine the

transition probabilities of the system based on a mean value

2http://www.uml.org/

120

Figure 1. Systematic integration of coordination with the Mean–Field Stochastic Model.

approach (ergodicity). The macroscopic information which

are required here are the same that can be used to construct

an Agent Causal Behavior Graph (ACBG) [9]. These models

contains macroscopic information about the participating

agents in the system (System Actors), their interactions

among each other (System Interactions) and the environment

in which the agents are situated (System Environment). But

unlike modeling techniques like an ACBG which offer a

macroscopic view on the Coordinating Process, the MES

model offers a mesoscopic view by also providing informa-

tion about microscopic characteristics of the CoordinatingProcess (see artefact Microscopic Variable in Fig. 2). Based

on this approach, average probabilities are used to construct

the mean MAS to provide that information. Therefore,

the MES model allows to retrieve much more detailed

information about the Coordinating Process Dynamics than

macroscopic models like an ACBG or similar artefacts. An

example for the creation of a MES model is given in section

IV-B as part of this paper’s case study on a self–healing

resource–flow system.

The MES model can be used for the qualitative and quan-

titative validation of the Coordinating Process. Modeling

the Coordinating Process Definition as an mathematical

model makes sure that the Coordinating Process is correctly

understood by the system engineer and allows to calculate

the excepted results of the Coordinating Process before the

process is implemented and integrated. Thus allowing a

qualitative validation of the Coordinating Process before

further integration effort is invested [2]. If the validation

shows flaws in the operation of the process, the conception

of the Coordinating Process can be iteratively refined until

the calculated results match the requirements. When the

Coordinating Process meets the Adaptivity Requirements

a system engineer can proceed to the next Coordinating

Process development activity, i.e. the Coordinating ProcessIntegration.

After the Coordinating Process Integration, the MES model

can also be used for the quantitative Coordination Validation.

For the purpose of validation, system observables have to

defined suitable to comparison of results from the actual

implementation and the MES model. If the results match

within the required accuracy, the actual implementation is

valid with respect to the defined observables. To validate

the Coordinating Process quantitatively, a large number of

tests has to be performed with the actual implementation.

These values then can be compared with the theoretically

calculated values based on the MES model. This allows

to validate the Coordinating Process quantitatively by com-

paring a large number of actual measured result values

with the theoretically based MES model measurements.

The validation process itself may be iterative. After the

comparison of the results from the actual system and the

MES model results it may be suitable to refine the MES

model as shown in Fig. 1. This refinement may include

the the definition of other system observables (microscopic

characteristics of the Coordinating Process) to ensure the

systems rightful behavior even if the results match within the

required accuracy, because it validates the implementation

only with respect to the defined observables. It also may

include a refinement of the MES model itself, if it was

not yet suitable to model the Coordinating Process prop-

erly, possibly due to a simplified model. If the results do

121

Figure 2. UML Activity diagram: Creation and Use of the MES Model.

not match the Coordinating Process may also have to be

redefined as shown in Fig. 1. The usage of this validation

technique is exemplified in section V where the created MES

model for this papers case study is used to validate the actual

implementation.

IV. DECENTRALIZED COORDINATING PROCESS FOR

RESOURCE–FLOW SYSTEMS

The case study for this paper is based on previous work in

the field of Self–Organizing Resource–Flow Systems systems

to demonstrate the power of the MES model. An overview

about this domain and how it benefits from self–organizing

principles is given in [5]. In the implemented system re-

sources are processed by robots and transported from one

robot to an other by autonomous guided vehicles (AGVs).

It is based on the assumption that robots may have multiple

capabilities they can apply to resources. Therefore if the

required capabilities for processing resources are redundant

available in the system, it is possible to apply self–healing

mechanisms which allows a reconfiguration of the robot’s

assigned capabilities in case of a failure. The information

which capability a robot has to apply to a received resource

is stored in its role. The role also contains information about

from which AGV the robot should receive a resource, to

which AGV it should give it after processing it and the state

the resource should have before and after the processing.

The system was implemented as a multi–agent based sim-

ulation using the freely available Jadex3 agent framework.

3http://jadex-agents.informatik.uni-hamburg.de/

Both the robots which process the resources and the AGV

which transport the resources between the robots where

implemented as Jadex micro agents. An addition to the

system model, as described in previous publications is the

possibility for a robot to have more than one role. So a

robot may process different resources in different resource–

flows or process a resource multiple times at different states

of the overall manufacturing process. An other addition to

the system model cohering with the previous addition is the

inclusion of output buffers for the robots, so that loops in

the resource–flow could be modeled. A condition for this,

with importance to the following reconfiguration process is

the invariant that for every role a robot owns, at least one

place in its buffer has to be reserved. So the amount of roles

a robot owns can not be larger than the size of its buffer.

The ratio of the number of roles and the buffer size is called

workload and the maximum value for this ratio is one.

A. Reconfiguration ProcessThe completely decentralized reconfiguration approach

for the given resource–flow system is based on the idea that

reallocations run through the system like a wave in order

to re–establish a correct resource–flow. A failure leads to

one or more incapacitated robots that can not apply certain

capabilities. Therefore the affected robots can no longer

apply their roles, thus the decentralized reconfiguration

process is triggered. If the system would not have a self–

healing feature the production of resources has to stop. But

when every robot is capable to exhibit a set of different

capabilities, i.e. is able to reconfigure itself, it is possible

122

to re–establish a correct resource flow by swapping of roles

among the robots. Deficient robots dispense their affected

roles to other robots and in exchange adopt roles from

these robots. The wave of reallocation is emitted by the

deficient robot by sending so called help request messages

along a predefined token ring. The usage of a token ring

is based on the idea that the help request messages are

sent along a resource-flow like the processed resources and

therefore are emitted like a wave through the system. Robots

which receive these message decide locally whether they

are capable to swap roles with a deficient robot. Swaps

include the reconfiguration of robots and the adjustment of

the resource–flow between robots by also reconfiguring the

affected AGVs. A swap of roles is called direct or single if

one swap of roles is enough to get the system back into a

working state. Such a swap is characterized by the fact that

the receiving robot can apply all the roles from the deficient

robot, meaning that he owns the required capabilities and

also the deficient robot can apply all the roles the other

robot has to swap with him in order to reconfigure. But

not in all cases is such a direct swap of roles possible. In

some cases the deficient robot is not able to apply the roles

which the other robot has to swap with him. In this case a

so called transitively swap is performed. The robot which

receives a help request still gives up its roles and adopts the

roles from the deficient robot, even if the deficient robot can

not apply them. The deficient robot then stays in a deficient

state, but now tries to find an other robot with which it

can swap its new but still deficient roles. An indicator for

the likeliness of a role swap is called redundancy rate. It

measures the percentage of how often a certain capability

is represented in the system. A redundancy rate value of

100% means that every robot can apply every capability.

The implementation of the Coordinating Process made use

of the Decentralized Coordination for Multi–agent Systems

(DeCoMAS) framework [9]. Currently, the framework uses

so called Coordination Spaces [10] to distribute the coordi-

nation information (help request and reply messages) among

the agents. Based on a coordination space a coordination

medium is used to facilitate the distribution of the coordina-

tion information. A coordination medium encapsulates the

coordination logic and decides how coordination information

should be published among the agents. As mentioned before,

for this case study a coordination medium was realized that

routes the help request messages and the according help

replies along a token ring. Via this medium, all agents were

virtually aligned in a circle so all agents can be reached

without regarding their location in the resource–flow. While

the alignment on a circle still followed the same distribution

metaphor for coordination information as for the processing

of the resources in the resource-flow. The coordination logic

to reconfigure the agents and to interact via the medium was

encapsulated in so called Coordination Endpoints. These

observe the agents and initiate the reconfiguration by sending

a help request message if one agent becomes deficient. As

described in [5] the help request is forwarded through the

medium and each endpoint along its path locally decides if

the deficient role should be adopted or if the help request

should be forwarded further on. If the deficient role is

adopted a reply is sent backwards though the medium until

all affected agents are informed. Also for the replies the

endpoints decide locally whether they have to change the

agent’s configuration if it is affected by the swap or not.

Multiple received coordination information are queued and

processed in their order of arrival.

Based on this coordination medium approach a reconfig-

uration interface was implemented to allow the integra-

tion of different reconfiguration strategies. These strategies

encapsulate the local decisions of endpoints during the

reconfiguration process, whether they should adopt deficient

roles from a help request and dispense roles of their own

in exchange. Following an iterative development process

a reconfiguration strategy consisting of three round was

developed. In the first round if a robot receives a help request

it tries to apply as much roles as possible from the deficient

robot under the condition that it can dispense the same

among of roles to the deficient agent for a direct swap. In the

second round if its workload has not reached 100% and the

help request still contains deficient roles, it overtakes these

roles until either its workload reaches 100% or all deficient

roles from the help request are taken. This of course may

lead to an increase in the robots workload and therefore a

possible bottleneck in the resource–flow but it guaranties

that this system is brought back to a working state as fast as

possible. If the first two rounds do not suffice to solve the

problem, the third and last round tries swapping transitively.

B. Creating the MES Model

To create the MES model for the Coordinating Process of

the previously described model, following the Creation part

of UML activity diagram for the creation and usage of the

MES model (see Fig. 2) the first activity is the identification

of the characteristic variables for the Coordinating Process.

In this case the MES model should give information about

the probability of a certain reconfiguration process result

depending on the system’s parameters. In case of the here

presented system this is the probability with which a robot

can process a help request and derived from this, the

information how far a help request has been forwarded until

it is answered. These are the microscopic variables needed

to construct the MES model.

As described before a help request passes stepwise

through the system. If a robot is not able to process it,

it is forwarded further on. The probability with which a

robot can process a help request is called p. Based on a

geometric distribution in form of P (X = n) = p(1− p)n−1

it is possible to calculate the probability with which a help

request is processed after n steps.

123

The described strategy contains of three rounds each with a

different behavior. Therefore, the probability mass function

of the geometrical distribution P (X = n) needs to be de-

fined stepwise. The probabilities of success for the different

rounds are defined as p1 to p3, resulting in the following

function:

P (ψ = n) =

⎧⎪⎪⎪⎨⎪⎪⎪⎩

p1(1− p1)n−1, n < r

(1− p1)r−1p2(1− p2)n−r−1, r < n < 2r

(1− p1)r−1(1− p2)r−1p3(1− p3)n−2r−1, 2r < n < 3r

(1− p1)r−1(1− p2)r−1(1− p3)r−1, n = 3r

The definition of the strategy is one of the three needed

macroscopic information artefacts as shown in Fig. 2 needed

for the determination of the transition probabilities. Be-

cause the strategy defines how the robots interact during

the reconfiguration process it maps the System Interactionsand is used to create the geometrical distribution function

P (ψ = n). The geometrical distribution of the function is

mapped by the first three cases. The probability of a failure

in the first round has to be considered while calculating the

probability of a success in the second round. Accordingly

the probabilities of a failure in the first and second round

have to be considered in the calculation for the third round.

The forth part of the function described the probability of

a failure in all three rounds. The random variable of this

model is the distance a help request travels before being

answered and is called Ψ. The number of robots present in

the system is called r. Ψ is a discrete finite set of steps

which can occur during the reconfiguration which does not

include the values r and 2r. Because a deficient robot can

not adopt roles from his own help request. But Ψ contains

the value 3r which marks an reconfiguration error when

no robot could process the help request. So Ψ is defined

as: Ψ = {j ∈ N|1 ≤ j ≤ 3r ∧ j �= r ∧ j �= 2r}.Because the probability mass function returns a value for

every event from Ψ and also maps the failure at 3r steps,

it is normalized. The number of robots r is the needed

macroscopic information about the System Actors (see Fig.

2). In this case only the information about the number of

System Actors is needed.

According to the strategy, the probabilities for p1 to p3 have

to be defined round wise. In the first round a partner for

a direct swap of roles is searched. The probability that a

robot is able to replace the deficient capability is equivalent

to the earlier mentioned redundancy rate ρ. But for a direct

swap of roles between two robot it is also necessary that

the deficient robot is able to apply the capability which is

currently used by the other robot. This probability is again

ρ. So the probability for a direct swap of roles between two

robots is defined as: p1 = ρ2. This is actually a simplification

because this consideration leaves out the fact that a robot not

only has to own the required capability but he also has to

apply this capability in one of his roles. The simplification

was considered suitable because the focus of this paper is

to show how the MES model can be integrated into the

development process of a self–organizing system and not

how to build a perfectly fitting stochastic model.

As described before the second round makes use of the

robot’s buffers and only searches for a robot which can

adopt the deficient role additionally to his own. Therefore

the probability that the robot owns the required capability

is still ρ. But it is also necessary that the robot has enough

space in this buffer to adopt additional roles. This is modeled

with the system’s mean workload ω. Which results in an

overall probability for the second round of: p2 = ρ · (1−ω).The probability for the third round is p3 = ρ because in

this round the strategy only searches a robot suitable for a

transitive role swap and therefore only the probability that

the receiving robot owns the required capability has to be

considered. In this case study the mean redundancy rate ρand the mean workload ω are the macroscopic information

about the System Environment needed for the determination

of the transition probabilities in order to construct the MES

model (see Fig. 2).

With the probabilities for the single rounds it is now possible

to calculate the probabilities for specific distances. The

distribution function F (n) can be used to calculate the

probabilities that a role swap would be successful in the first

n steps. Therefore, all the probabilities from Ψ a summed

up to:

F (n) = P (Ψ ≤ n) =∑

ψ∈Ψ∧ψ≤nP (ψ)

The expectation value for a specific ψ in Ψ can be calculated

with:

E(Ψ) =∑ψ∈Ψ

ψ · P (ψ)

For the case study the distribution function F (n) and the

formula for the expectation value E(Ψ) are the results of the

Determinate Transition Probabilities activity and describe

the MES model. They were created by using macroscopic

information about the System Actors, in this case the number

of robots present in the system, the System Interactions,

defined by the used reconfiguration strategy, the SystemEnvironment, which in this case gave information about the

mean redundancy rate and workload of the system and can

be used to calculate mesoscopic results for characteristic

microscopic variables of the Coordinating Process. These

mesoscopic results are used in the next section to validate

the implemented system by comparing them to the actual

microscopic results from the actual system.

V. VALIDATION

The Coordinating Process of the developed self–healing

resource–flow system described in Section IV was validated

quantitatively based on the MES model to ensure that the

124

Coordinating Process meets the adaptivity requirements as

described in section III. As described in section III-A and

shown in the Validation part of Fig. 2 the first validation

activity was to define the observables from the implemented

MAS. In this case the actual number of steps needed for

the reconfiguration will be compared with the calculated

expectation value based on the MES model to validate it

quantitatively with respect to the observables. Therefore

seven different scenarios were simulated. The number of

robots in the scenarios grew from 20 over 30, 40, 50, 70,

100 up to 200. For each scenario different redundancy rate

and workload values, each in a range from 10% to 100%

in 10% steps were used and for each redundancy rate and

workload value pair 50 simulation runs were performed.

Totalling in 5000 simulation runs for each of the seven

scenarios and a overall total of 35000 simulation runs for

the quantitative validation. In each of the 35000 simualtions

runs the reconfiguration process was started due to a random

error.

The next validation activity (see Fig. 2) was to gather the

mean value of the needed number of help request steps

for the reconfiguration process. Therefore for every value

pair of redundancy rate and workload in each of the seven

scenarios the results form the 50 simulation runs were

middled. The third validation activity according to Fig. 2

was the comparison of these mean values with the calculated

expectation values based on the MES model. Therefore the

relative difference between the expectation value and the

mean simulation results were calculated by subtracting the

simulation result values from the MES model expectations

values. To normalize it, the result then was divided by the

according expectation value. In Fig. 3(a) the results for the

scenario with 100 robots are shown. If the relative difference

value is positive it means that the simulated system found

a reconfiguration faster than the MES model predicted it

and vice versa. The results in the relative difference maps

did not show any trends which could lead to any systematic

deviations between the simulated system and the MES model

with respect to the defined observables.

The final quantitative validation step based on the MES

model was to calculate the mean value of the previously

mentioned relative difference between the MES model and

the simulation results for specific redundancy rate and num-

ber of robots values. Therefore the values for the different

workloads were averaged. The results illustrated in Fig. 3(b)

showed that only for a low number of robots and a low

redundancy rate (20 robots in case of a redundancy rate

from 10% to 30% and 30 robots in case of a redundancy

rate of 10%) a significant deviation of more than 10%

between the MES model and the actual system exists. Thus,

for the parameter pairs composed of the number of robots

and the redundancy rate, where no significant deviation

between the MES model and the actual system exits, the

developed Coordinating Process is valid with respect to

(a) Values for 100 Robots.

(b) Workload averaged Values.

Figure 3. Relative Difference of the Number of Steps.

the observables in terms of the observed number of help

requests based on a quantitative analysis. No conclusion

can be drawn for the validation of the Coordinating Process

based on the MES model for the parameter pairs where a

significant deviations exits. In this case it is not possible

to draw a conclusion whether the Coordinating Process is

invalid because of the deviation or because the MES model

does not model the Coordinating Process properly for small

system sizes in case of a low redundancy rate. Drawing

the final conclusion that the proposed MES model artefact

can be used to validate the Coordinating Process in a self–

organizing MAS quantitatively, but it can not be used to

identify an invalid Coordinating Process, because it can not

be determined if in this case the Coordinating Process is

invalid or just modelled improperly.

Of course as stated out before this is not a validation

based on formal analysis but a quantitatively validation with

respect to certain system observables, which showed that

the implemented Coordinating Process showed the expected

behavior based on the MES model. Based on the results it is

now possible to redefine the Coordinating Process if needed

or to alter the MES model and to define other observables

to validate the implemented MAS furthermore.

VI. CONCLUSION AND FUTURE WORK

In this paper we presented the Mesoscopic Stochastic

Model as a novel methodological artefact for validating self–

125

organizing MAS. Following the ergodicity assumption that

the decentralized operation of a MAS can be represented by

a mean field approximation based on stochastic methods.

We argued that self–organizing MAS should be validated

with respect to certain system observables in those cases,

where the underlying coordinating process that is responsible

for the self-organizing behavior, introduces new microscopic

variables. The MES model, as an artefact related to these

microscopic variables can be used to validate the system

with respect to the self-organizing behavior. The MES

model is called mesoscopic since it approximates transition

probabilities for the microscopic states of an agent by

values calculated from an averaged behavior of the rest

of the system (ergodicity assumption). We described how

the artefact can be embedded in the systematic integration

of decentralized Coordinating Processes and applied this

method to equip a self–healing resource–flow system with

a decentralized Coordinating Process to restore the system’s

functionality after a failure. The construction of the MES

model was described in general and demonstrated on a

case study MAS. Finally, the MES model was used to

quantitatively validate the developed self–organizing MAS.

To construct the MES model it is important that all relevant

microscopic variables have been identified.

The validation of the case study showed that MES models

are suitable to validate the Coordinating Process in self–

organizing with respect to certain system observables. Al-

though the MES model themselves are a target for failure,

as they have to be modeled by a system engineer. Therefore

if not modeled correctly one may receive false validation

results. On the other hand MES models can be used to

validate all kinds of different MAS and the modeling process

of a MES model helps engineers to qualitatively validate that

their understanding of the Coordinating Process is correct.

Future work on this topic will include further research on

the class of systems for which MES models may be suitable.

Therefore different types of self–organizing systems will

be reviewed with regards to the possibility to describe and

analyze them with MES models. The goal is to identify the

classes of system that can be described with a MES model,

to find out if the MES model is suitable to describe different

kind of self–organizing systems or if it is just suitable for

a small class of specific systems. Also formal methods

to define these class of systems have to be developed.

Furthermore a systematic construction of MES models for

arbitrary systems has to be found and described. Other

work will include extended research on related work where

stochastic models are used to describe MAS to classify and

compare them with the here presented approach.

ACKNOWLEDGMENT

We would like to thank the Deutsche Forschungsgemein-

schaft (DFG) for supporting this work in a project on

”Self–organisation based on decentralized Coordination in

Distributed Systems” (SodekoVS).

REFERENCES

[1] J. J. Gomez-Sanz, R. Fuentes-Fernandez, and J. Pavon,“Understanding Agent Oriented Software EngineeringMethodologies,” in Proc. of the 12th International Workshopon Agent-Oriented Software Engineering, 2011, pp. 81–91. [Online]. Available: http://distrinet.cs.kuleuven.be/events/aose/2011/contents/papers/gomez-sanz.pdf

[2] J. Sudeikat and W. Renz, “Qualitative modeling of masdynamics,” in Agent-Oriented Software Engineering X, ser.LNCS, 2011, vol. 6038, pp. 80–93.

[3] M. Niazi, A. Hussain, and M. Kolberg, “Verification &validation of agent based simulations using the vomas (vir-tual overlay multi-agent system) approach.” in MALLOW’09,2009.

[4] H. Seebach, F. Nafz, J.-P. Steghofer, and W. Reif, “A SoftwareEngineering Guideline for Self-Organizing Resource-FlowSystems,” in 2010 Fourth IEEE International Conferenceon Self-Adaptive and Self-Organizing Systems. IEEE, 2010,pp. 194–203. [Online]. Available: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5630159

[5] J. Sudeikat, J.-P. Steghofer, H. Seebach, W. Reif, W. Renz,T. Preisler, and P. Salchow, “On the combination oftop-down and bottom-up methodologies for the designof coordination mechanisms in self-organising systems,”Information and Software Technology, pp. 1–15, 2011.[Online]. Available: http://linkinghub.elsevier.com/retrieve/pii/S0950584911001959

[6] H. V. D. Parunak and S. A. Brueckner, “Softwareengineering for self-organizing systems,” in Proceedings ofthe 12th International Workshop on Agent-Oriented SoftwareEngineering, 2011. [Online]. Available: http://distrinet.cs.kuleuven.be/events/aose/2011/contents/papers/parunak.pdf

[7] M. Cossentino, M.-P. Gleizes, A. Molesini, and A. Omicini,“Processes engineering and aose,” in Proceedings ofthe 10th international conference on Agent-orientedsoftware engineering, ser. AOSE’10, 2011, pp. 191–212. [Online]. Available: http://dl.acm.org/citation.cfm?id=1965954.1965972

[8] J. Sudeikat and W. Renz, “Programming adaptivity by com-plementing agent function with agent coordination: A sys-temic programming model and development methodologyintegration,” Communications of SIWN, vol. 7, pp. 91–102,2009.

[9] ——, “Masdynamics: Toward systemic modeling of decen-tralized agent coordination,” in Proceedings of KIVS 2009 -Kommunikation in Verteilten Systemen, K. G. K. David, Ed.Springer, 2009, pp. 79–90.

[10] A. Vilenica, J. Sudeikat, W. Lamersdorf, L. Braubach, andA. Pokahr, “Coordination in multi-agent systems: A declar-ative approach using coordination spaces,” in Proceedingsof the 20th European Meeting on Cybernetics and SystemsResearch (EMCSR 2010) - International Workshop FromAgent Theory to Agent Implementation (AT2AI-7), 2010, pp.441–446.

126