Gerrit Anders

Florian Siefert

Jan-Philipp Steghöfer

Wolfgang Reif

Trust-Based Scenarios -Predicting Future Agent Behavior in Open Self-Organizing Systems

Keywords: Scenarios, Trust, Robustness, Resilience, Uncertainty, Self-Organizing Systems, Adaptive Systems, Open Multi-Agent Systems 1 Uncertainties

Agents in open self-organizing systems have to cope with a variety of uncertainties. In order to increase their utility and to ensure stable operation of the overall system, they have to capture and adapt to these uncertainties at runtime. This can be achieved by formulating an expectancy of the behavior of others and the environment. Trust has been proposed as a concept for this purpose. In this paper, we present trust-based scenarios as an enhancement of current trust models. Trust-based scenarios represent stochastic models that allow agents to take different possible developments of the environment's or other agents' behavior into account. We demonstrate that trust-based scenarios significantly improve the agents' capability to predict future behavior with a distributed power management application.

able to adapt to changing conditions quickly and autonomously. In [START_REF] Anders | Structuring and Controlling Distributed Power Sources by Autonomous Virtual Power Plants[END_REF], we introduced the concept of Autonomous Virtual Power Plants (AVPPs) that embodies such a control scheme in the context of a self-organizing system structure. Each AVPP controls a group of power plants. The structure changes in response to new information and changing conditions to enable each AVPP to balance its power demand and production. For this purpose, each AVPP calculates schedules that stipulate the output of controllable power plants for future points in time. The scheduled output of controllable power plants has to satisfy the "residual load" which arises as the difference between the power demand and the production of the non-controllable power plants like weather-dependent generators. To approximate the residual load, AVPPs have to rely on predictions about the future demand as well as the future output of non-controllable power plants. However, these predictions are subject to uncertainties: consumers and power plants can behave arbitrarily since they pursue individual goals and are exposed to their environment, resulting in (un)intentionally inaccurate predictions; the behavior is variable since it depends on external conditions (e.g., if snow covers the solar panels); and the behavior is time-dependent since prior good predictions are usually an indicator for future good ones. If these uncertainties are known and thus a model of the consumers' and power plants' underlying stochastic processes is available, an AVPP can use demand and power predictions to predict the corresponding predictor's expected behavior. Incorporating uncertainties into the schedule creation then allows AVPPs to prevent or mitigate imbalances between energy production and demand that are caused by inaccurate predictions.

As a way to deal with uncertainties, trust models have been proposed (see Sect. 2). They allow agents to measure and quantify other agents' behavior by means of a trust value. The value captures the experiences with that particular agent and allows to derive whether or not the interactions where beneficial in the past. If a trust value is regarded as a measure of uncertainty, it can in turn be used to make evidence-based assumptions about an agent's future behavior. However, in general, trust values do not capture the stochastic process underlying the observed behavior. This information is lost when the trust metric derives the value. Instead, an average over the last experiences is formed that, at best, allows to predict with which probability a future interaction will again be beneficial.

In the domain of operations research, scenarios are a well-known concept to mirror a system's underlying stochastic process [START_REF] Hochreiter | Financial scenario generation for stochastic multi-stage decision processes as facility location problems[END_REF]. It is expressed by different possible developments of the system. As each scenario has a certain probability of occurrence, an agent can, e.g., choose the most likely scenario and optimize for the future the scenario predicts. However, current approaches usually use predetermined scenarios and probabilities [START_REF] Zhang | Electricity auctions with intermittent wind generation[END_REF]. In an open self-organizing system, it is not possible to determine possible scenarios beforehand. As self-interested agents come and go and interaction patterns change, no assumptions can be made about the individual agent's behavior. It is thus essential that scenarios and their probabilities are determined at runtime with up-to-date data. These characteristics imply several challenges that an approach to measure uncertainties and predict future behavior has to deal with:

1. Arbitrary behavior: No assumptions about agent behavior can be made.

The stochastic model must depict behavior that can be described by continuous or discrete random variables as well as different probability distributions. 2. Subjective behavior: Because agents can behave differently towards different interaction partners, each agent has to build its individual stochastic model of others. 3. Variable behavior: An agent's behavior can vary and completely change over time as it can adapt to changes in its environment and, e.g., adjusts its objectives accordingly. The stochastic model must be flexible enough to reflect these changes, e.g., by a mechanism that allows for forgiveness. 4. Time-dependent behavior: An agent's current behavior might depend on its behavior in the past. A stochastic model should thus be able to mirror time-dependent behavior.

In this paper, we propose to meet these challenges by dynamically calculating trust-based scenarios and their probabilities at runtime. They provide a stochastic model of sources of uncertainty, allowing agents to predict and deal with them by making informed and robust decisions. With regard to AVPPs, i.e., our running example, this increases the system's resilience against mispredictions. Sect. 2 gives an overview of existing trust models, while Sect. 3 introduces trustbased scenarios. Our running example is then used to evaluate our approach in Sect. 4. In Sect. 5, we conclude the paper and give an outlook on future work.

Advantages and Limitations of Current Trust Models

Trust is a multi-faceted concept that allows agents to appraise their interaction partners' behavior. Among others, trust includes the facets reliability and credibility [START_REF] Steghöfer | Trustworthy Organic Computing Systems: Challenges and Perspectives[END_REF]. An agent's reliability specifies its availability, while an agent's credibility indicates its willingness to participate in an interaction in a desirable manner and corresponds to the original notion of trust in MAS [START_REF] Ramchurn | Trust in multi-agent systems[END_REF]. We focus on credibility in this paper. In principle, an agent a's trust in an interaction partner b results from experiences with b. Each gathered experience stems from a contract in which the desired result of a's interaction with b was stipulated. The experience is created after the interaction is completed. It contains the stipulated and the actual result of the interaction. Trust is highly subjective as an agent can show different behavior towards its interaction partners. Because of an agent's capabilities and objectives, trust further depends on the context, e.g., the environmental circumstances, in which an interaction takes place. For the sake of simplicity, we deliberately abstain from trust context considerations here.

If it is valid to assume that an agent's prior behavior is indicative for its future behavior, trust can be used to predict this future behavior and is thus a measure to cope with uncertainties as shown in Sect. 2.1 and Sect. 2.2.

Predicting Agent Behavior by Means of Trust Values

Because an interaction can last multiple time steps, we define a contract C i t = (c i t+0 , ..., c i t+n ) as an (n+1)-tuple that comprises multiple stipulated results c i t+j , where j, n, t ∈ N + 0 , i ∈ N + is a unique identifier, and t + j identifies the time step in which the interaction partner should behave as stated in c i t+j . t and t + n thus specify the time frame in which C i t is valid. With respect to power, i.e., residual load, predictions in AVPPs (see Sect. 1), n + 1 is the length of the prediction. For instance, if the power prediction covers a time frame of 8 hours in which the residual load is predicted in 15 minute intervals, we have n + 1 = 32. In the following, let [X] j denote the j-th element of a tuple X. An atomic experience e i t+j = (c i t+j , r comprise n + 1 so-called time slots, e.g., [E i t ] j was gained in the j-th time slot. If an agent a evaluates the trustworthiness of an agent b, it uses a trust metric M : E × ... × E → T to evaluate a number of experiences with b (E is the domain of experiences). The metric returns a trust value τ ∈ T and relies on a rating function R : → T that appraises atomic experiences ( is the domain of atomic experiences). The result of R is a rating π ∈ T . T usually is an interval [0, 1] or [-1, 1]. Regarding T = [0, 1], a trust value τ = 0 or τ = 1 states that agent b either never or always behaves beneficially [START_REF] Mayer | An integrative model of organizational trust[END_REF]. However, b behaves predictably in both cases. If the trust value is around the interval's midpoint, b's behavior is highly unpredictable and thus induces a high level of uncertainty.

Because the residual load can be over-or underestimated, we use T = [-1, 1] so that positive and negative deviations from predictions can be captured. A rating π = 0 states that the residual load is predicted exactly, whereas π = -1 or π = 1 state that the residual load is greatly under-or overestimated (i.e., the actual residual load is far higher or lower than predicted).

A trust value has to be semantically sound to allow valid predictions of an agent's future behavior. This property depends on the metric M. M can, e.g., calculate the mean deviation between the stipulated c i t+j ∈ R and actual result r i t+j ∈ R of atomic experiences [E i h t h ] j contained in a list of m experiences E i1 t1 , ..., E im tm (k ∈ R equals the maximum possible or, if not available, observed deviation from a contract and thus normalizes the result to a value in [-1, 1]):

M(E i1 t1 , ..., E im tm ) = m h=1 n j=0 R([E i h t h ] j ) m • (n + 1) ; R([E i t ] j ) = c i t+j -r i t+j k (1)
Based on M, a trust value τ , and a contract C i t , an agent can predict the expected behaviors B i t = (b i t+0 , ..., b i t+n ) of its interaction partner during C i t 's validity. With respect to Eq. 1, the agent's expected behavior [B i t ] j in time step t+ j is defined as the difference between [C i t ] j and the expected deviation τ • k:

[B i t ] j = [C i t ] j -τ • k (2)
For example, if k = 10 MW, τ = 0.1, and the power prediction's stipulated results are C i t = (5 MW, 6 MW), the expected residual load can be predicted as

B i t = (4 MW, 5 MW).
If the AVPP schedules its subordinate controllable power plants on the basis of B i t instead of C i t , it is expected that the deviation between the power plants' output and the actual residual load can be decreased. However, the prediction of the residual load's future behavior with Eq. 2 can be imprecise because we disregard that an agent's behavior can be arbitrary and that it might be time-dependent (see Sect. 1). Since agents can behave arbitrarily, one and the same trust value can stem from very different experiences, e.g., τ = 0.1 could be based on experiences in which the residual load was always 1 MW lower than stipulated or a situation in which 25% of the predictions were overestimated by 2 MW and 75% of the predictions were underestimated by -2 MW. With regard to time-dependent behavior, the prediction of the residual load for a time step t could, e.g., tend to be rather precise if the prediction for the previous time step t -1 is accurate. A similar dependence could exist for inaccurate predictions.

As a trust value is usually just a mean value, it is not applicable to predict an agent's behavior in this case. Regarding an agent's underlying stochastic process, which can be represented by a probability distribution, the mean value simply does not capture enough information to approximate and describe it sufficiently.

Other Trust Models to Predict Agent Behavior

In the body of literature, various trust models have been presented that can be used to predict the environment's or other agents' behavior in specific situations.

In [START_REF] Kiefhaber | Confidence as a Means to Assess the Accuracy of Trust Values[END_REF], confidence is proposed as a concept that indicates the degree of certainty that a trust value mirrors an agent's actual observable behavior. Among others, it depends on the standard deviation of experiences used to assess the trust value. The combined information given by the trust value (i.e., the mean behavior) and the standard deviation is still insufficient to approximate an arbitrary stochastic process underlying an agent's behavior though. The concrete probability distribution an agent's behavior follows must still be assumed.

In [START_REF] Hussain | Markov model for modelling and managing dynamic trust[END_REF], an agent's trust value in the next time step is predicted on the basis of a Markov model. States mirror an agent's trustworthiness. The probability associated with a state change is determined at runtime, dependent on how often this transition was observed. While this model includes a basic mechanism to reflect time-dependent behavior (the trust value in the next time step depends on the current trust value), it is not applicable in situations that need predictions for more than a single time step or in situations in which too few data is available (e.g., there might be no transitions for the current trust value).

To be able to consider (in)regularities when predicting future trust values (such a behavior is shown by strategic agents), [START_REF] Hussain | A robust methodology for prediction of trust and reputation values[END_REF] presents several metrics that can determine the trust value for the next time step dependent on such properties. However, the applicability of the metrics depends on the characteristic of the agent's behavior and it is not possible to predict different possible developments of the trust value. Apart from this, these metrics basically exhibit similar drawbacks as the Markov chain method presented in [START_REF] Hussain | Markov model for modelling and managing dynamic trust[END_REF].

Another trust model that is based on a Markov chain is introduced in [START_REF] Chang | Markov chain-based trust model for analyzing trust value in distributed multicasting mobile ad hoc networks[END_REF]. In a mobile ad-hoc network, events, i.e., new experiences, trigger state changes in the Markov chain, i.e., changes in the trust value. While the Markov chain is used to analyze the trust model, it remains unclear how agents use information like transition probabilities to make decisions or predict future behavior.

Finally, [START_REF] Li | Fuzzy regression based trust prediction in service-oriented applications[END_REF] presents a fuzzy regression-based approach to predict uncertainties in the field of service-oriented applications. Predictions are made on the basis of a trust value, a trust trend, and the performance consistency that reflects the trust value's stability. While this model can predict behavioral changes and trends in an e-service environment, the stochastic model an agent can derive from it can not be applied in the domain of open self-organizing systems as the challenges mentioned in Sect. 1 are not completely met.

Trust-Based Scenarios

Scenarios are a proven concept to approximate a stochastic process by taking several possible developments of a system into account (see, e.g., [START_REF] Pappala | Power System Optimization under Uncertainties: A PSO Approach[END_REF]). These developments are often represented by a scenario tree which can be annotated with probabilities that the system develops in a specific direction. Scenario trees then serve as input for solving optimization problems under uncertainty such as stochastic programming [START_REF] Sahinidis | Optimization under uncertainty: state-of-the-art and opportunities[END_REF]. These techniques are applied, e.g., in the domain of power management systems (see, e.g., [START_REF] Densing | Hydro-electric power plant dispatch-planning-multi-stage stochastic programming with time-consistent constraints on risk[END_REF][START_REF] Bouffard | Stochastic security for operations planning with significant wind power generation[END_REF][START_REF] Zhang | Electricity auctions with intermittent wind generation[END_REF]). In literature, scenarios are generated, e.g., by solving an optimization problem on the basis of a system model, gathered historical data, and expert knowledge [START_REF] Hochreiter | Financial scenario generation for stochastic multi-stage decision processes as facility location problems[END_REF]. The scenario tree's structure, the number of scenarios, or probability distributions are often predefined (see, e.g., [START_REF] Densing | Hydro-electric power plant dispatch-planning-multi-stage stochastic programming with time-consistent constraints on risk[END_REF][START_REF] Bouffard | Stochastic security for operations planning with significant wind power generation[END_REF]). Due to the computational complexity, scenarios are often determined off-line [START_REF] Zhang | Electricity auctions with intermittent wind generation[END_REF]. In [START_REF] Zhang | Electricity auctions with intermittent wind generation[END_REF], a Markov process is introduced as a simple mechanism to generate scenarios as input to solve a power plant scheduling problem. However, the authors act on the assumption that the scenarios and transition probabilities are predetermined at design time and not adapted at runtime. Further, simple scenario generation mechanisms, like the one presented in [START_REF] Zhang | Electricity auctions with intermittent wind generation[END_REF], often lack the ability to mirror time-dependent behavior. Scenario generation is thus often based on assumptions that do not meet the challenges outlined in Sect. 1.

In the following, we present an approach to generate trust-based scenarios (TBSs) at runtime which can in turn be used to predict the environment's or an agent's behavior on the basis of experiences gained in prior interactions.

Generating Trust-Based Scenarios

Our approach to generate TBSs is similar to the creation of a histogram or a Markov chain with variable transition probabilities. We assume that an agent's behavior can be assessed by a rating function like the one given in Eq. 1 and that an agent's prior behavior is indicative of its future behavior. Basically, we categorize atomic experiences according to their rating into classes of equivalent behavior and thus approximate an agent's underlying stochastic process. The TBSs originate from experiences that have been identically classified and serve as input to generate a trust-based scenario tree (TBST). If we have contracts and experiences of length n + 1, an agent can predict the behavior of an interaction partner or its environment in up to n + 1 future time steps. The probability that an agent changes its behavior from one class to another depends on the number of experiences in which this transition was actually observed. In the following, we explain in more detail how TBSs are generated.

Classifying Experiences: As mentioned above, we categorize rated atomic experiences into classes. For each regarded time slot j ∈ {0, ..., n}, these classes are consecutive and non-overlapping intervals ∆π j ∈ ∆T j that only contain elements in T so that each possible rating π can be assigned to an interval, i.e., ∀π ∈ T : ∃∆π j ∈ ∆T j : π ∈ ∆π j . Suitable sizes of these intervals depend on the application. To mirror time-dependent behavior, there is a set ∆T j for each time slot j so that an atomic experience [E i t ] j is classified into an interval ∆π j ∈ ∆T j . By assigning each rated atomic experience R([E i t ] j ) contained in an experience E i t ∈ E to such an interval ∆π j ∈ ∆T j , E i t is converted into a classified experience Ξ i ∈ E * (E * denotes the set of classified experiences). A classified experience Ξ i = (∆π 0 , ..., ∆π n ) is thus an (n+1)-tuple, i.e., a sequence, of intervals ∆π j ∈ ∆T j that contain the corresponding rated atomic experience R([E i t ] j ) of E i t (see Eq. 3). In Fig. 1, steps 1 and 2 illustrate how experiences are classified.

Ξ i :⇔ ∀j ∈ {0, ..., n} : R([E i t ] j ) ∈ [Ξ i ] j ∧ [Ξ i ] j ∈ ∆T j (3)
Determining Trust-Based Scenarios: A trust-based scenario (TBS) Ξ = (∆π 0 , ..., ∆π n ) arises from classified experiences Ξ i = (∆π 0 , ..., ∆π n ). More precisely, each group of experiences that were classified into the same sequence of intervals forms a TBS (the set S = ∆T 0 × ... × ∆T n contains all possible TBSs). Note that in contrast to Ξ i , Ξ has no identifier i. For each Ξ, a probability of occurrence p Ξ can be calculated. It is the ratio of the number of classified experiences Ξ i that feature the same sequence of intervals as defined by Ξ (∀j ∈ {0, ..., n} : [Ξ i ] j = [Ξ] j ) to the number of all classified experiences |E * |:

p Ξ := 1 |E * | • Ξ i ∀Ξ i ∈ E * : ∀j ∈ {0, ..., n} : [Ξ i ] j = [Ξ] j (4)
Hence, each generated TBS Ξ has a probability p Ξ > 0. These TBSs form the set S + ⊆ S. If Ξ is used to predict an agent's behavior, it thus represents a corridor of expected behavior. In Fig. 1, steps 2 and 3 show how TBSs are created. Deriving a Trust-Based Scenario Tree: The TBSs can now be used to derive an agent's stochastic model, the trust-based scenario tree T BST = (Θ, Φ), where Θ is the set of nodes and Φ the set of edges. The TBST is based on all generated TBSs (i.e., all Ξ ∈ S + ). A node θ ρ ∈ Θ is defined by an interval θ and a sequence of intervals ρ. Let [Ξ] j = ([Ξ] 0 , ..., [Ξ] j-1 ) specify the first j elements [Ξ] j of the interval sequence defined by a TBS Ξ, i.e., a prefix of length j (if j < 1, [Ξ] j is the empty sequence "∅"). Then, for each j ∈ {0, ..., n} and each TBS Ξ ∈ S + , there is a node θ ρ ∈ Θ with θ = [Ξ] j and ρ = [Ξ] j . A node θ ρ ∈ Θ thus states that an agent showed a behavior classified as θ after having shown behaviors classified as ρ in the given order. Additionally, Θ contains the tree's root R. If there are two nodes θ ρ1

1 and θ ρ2 2 with ρ 1 = [Ξ] j-1 and ρ 2 = [Ξ] j , there

is an edge (θ ρ1

1 , θ ρ2 2 ) ∈ Φ. Note that ρ 2 is equal to the concatenation ρ 1 ⊕ θ 1 . Further, for each TBS Ξ, Φ contains an edge (R, θ ∅ ) from R to the interval θ = [Ξ] 0 at time slot 0. More precisely, nodes and edges are defined as follows:

Θ := R ∪ θ ρ ∃Ξ ∈ S + : ∃j ∈ {0, ..., n} : θ = [Ξ] j ∧ ρ = [Ξ] j (5)
Φ := (R, θ ρ ) ∃Ξ ∈ S + : θ = [Ξ] 0 ∧ ρ = ∅ ∪ {(θ ρ1 1 , θ ρ2 2 ) |∃θ ρ1 1 , θ ρ2 2 ∈ Θ : (6) ∃Ξ ∈ S + : ∃j ∈ {1, ..., n} : ρ 1 = [Ξ] j-1 ∧ ρ 2 = [Ξ] j
As all leafs are at depth n+1, each path from the TBST's root to a leaf represents a TBS, and each TBS with non-zero probability is represented by such a path.

In a TBST, each edge (θ ρ1 1 , θ ρ2 2 ) has a probability p(θ ρ1 1 , θ ρ2 2 ) that indicates the conditional probability that the agent will show a behavior classified as θ 2 if it showed behaviors specified by ρ 2 in the previous time steps. This probability is the ratio of the number of classified experiences that start with the sequence

ρ 1 ⊕ θ 1 ⊕ θ 2 (ρ 2 = ρ 1 ⊕ θ 1 )
to the number that start with ρ 2 . Similarly, the probability of edges (R, θ ∅ ) is the probability that the agent shows a behavior as described in θ in the first time step of the contract's validity. The probability p(θ ρ1 1 , θ ρ2 2 ) with θ ρ1 1 = R is calculated as follows (J = {1, ..., n}):

p(θ ρ1 1 , θ ρ2 2 ) := Ξ i ∃Ξ i ∈ E * : ∃j ∈ J : ρ 2 = [Ξ i ] j ∧ θ 2 = [Ξ i ] j |{Ξ i |∃Ξ i ∈ E * : ∃j ∈ J : ρ 2 = [Ξ i ] j }| (7)
As each TBS with non-zero probability is represented by a path in the TBST, the TBS's probability is the product over all conditional probabilities assigned to the edges of its path. In Fig. 1, steps 3 and 4 depict how a TBST is generated.

Predicting Agent Behavior by Means of Trust-Based Scenarios

A TBST can now be used to predict an agent's behavior. Given a TBST, a rating function R (see Sect. 2.1), and a contract C i t , several scenarios for an agent's expected behavior can be determined. For this purpose, each interval θ = [θ, θ] that is represented by a node θ ρ in the TBST with lower and upper endpoints θ and θ is transformed into a corridor of expected behavior [b j , b j ], similar to Eq. 2. If R and k are defined as in Eq. 1, this is done as follows:

[b j , b j ] = [([C i t ] j -θ • k), ([C i t ] j -θ • k)] (8)
Consequently, the TBST reflects different possible future developments of an agent's or the environment's behavior. Obviously, the smaller the size of the intervals ∆π j used to classify the atomic experiences, the narrower these corridors and the higher the accuracy of predicted behavior. However, this accuracy heavily depends on the number of gathered experiences the TBST is based on.

To make decisions, an agent can take the whole TBST, a subtree, or a single TBS into account. In case a single TBS is preferred, the agent could choose the TBS represented by a path that is obtained by, starting at the root, choosing the edge with the highest conditional probability. This TBS is not necessarily the most likely TBS, but, under the assumption that it is more important to predict an agent's behavior in the near future than in the distant future, this procedure yields very precise predictions (see Sect. 4).

As agents might show time-dependent behavior, predictions can be improved by selecting relevant TBSs on the basis of an agent's behavior in recent time steps. The TBST is then derived from these TBSs. For example, if the accuracy of the prediction of the residual load depends on the accuracy of predictions of the last x time steps, then it would be beneficial to take the prediction quality of the last x time steps into account when predicting the expected residual load's behavior by means of TBSs. This is achieved as follows: Whenever a contract C i t is concluded, the last x atomic experiences gained before the current time step are recorded. Regarding the experience E i t gained for C i t as a list, these recorded atomic experiences are then added to the front of E i t . When a TBST is generated to predict an agent's expected behavior during the validity of a contract, its behavior in the last x time steps is then used to select a subset of relevant TBSs from the set of TBSs with non-zero probability. Relevant TBSs are those whose intervals' midpoint in the first x time slots is closest to the rated atomic experiences in the last x time steps. In the course of deriving the TBST from the selected TBSs, these additional atomic experiences are ignored. We show in Sect. 4 that this selection process yields very good results.

For evaluation, we regarded a setting of a single AVPP and an agent, called predictor, that represented all consumers as well as the AVPP's subordinate stochastic power plants. Power plant models and power demand are based on real-world data. In each time step, the predictor predicted the residual load the AVPP had to satisfy in the next n + 1 = 32 time steps (a single time step represented 15 minutes). For each time slot, the residual load prediction was created by adding a generated prediction error to the actual residual load. Therefore, in each time step, the predictor generated 32 prediction errors at random, using a gaussian distribution. To reflect time-dependent behavior, prediction errors depended on previous prediction errors. The AVPP's objective was to minimize the deviation between the actual residual load and the residual load it expected. To predict the expected residual load, the AVPP used TBSs and a trust value for comparison. The TBSs and the trust value were determined on the basis of the last m = 50 experiences (see Eq. 1) because we identified in preliminary tests that m = 50 allows the trust value to achieve good results. The AVPP rated experiences and determined the trust value by means of Eq. 1 with T = [-1, 1] and k = 9125 kW (the AVPP's maximum output/residual load). The AVPP preselected relevant TBSs on the basis of the prediction error of the last two time steps and selected a single TBS to predict the expected behavior as explained in Sect. 3.2. For each parametrization, we performed 100 simulation runs over 1000 time steps. Fig. 2(a) depicts the predictor's mean behavior over time. Fig. 2(b) shows the mean prediction error for each of the 32 time slots of a prediction.

The predictions of the expected residual load are significantly improved when using TBSs instead of a trust value (see Tab. 1 and Fig. 2(a)). Compared to the situation in which the AVPP relied on the residual load prediction, the mean deviation µ ∆ between the expected and the actual residual load can be reduced by approximately 70% when using trust values compared to approximately 84% when using TBSs with ∀j ∈ {0, ..., n} : |∆T j | = 183. TBSs thus reduce the trust value's µ ∆ by 46%. In the power grid, it is of utmost importance to reduce the maximum deviation max ∆ between the expected and actual residual load. Trust values reduce max ∆ by 61%. TBSs obtain 78% and thus max ∆ is 44% lower than the trust value's max ∆ . While we expected that TBSs benefit from a high number of classes |∆T j |, one can see in Tab. 1. Deviations between the actual and the expected residual load: the expected residual load is 1) equivalent to the predictor's residual load prediction ("unmodified prediction"), 2) based on a trust value (see Sect. Summarizing, compared to trust values, TBSs significantly increased the AVPP's ability to predict the residual load's behavior. Moreover, the risk the AVPP is exposed to, i.e., the maximum deviations, decreases considerably and the variation in prediction quality, i.e., the standard deviation σ ∆ (see Tab. 1), declines. The latter increases the confidence in the predicted expected behavior.

Conclusion and Future Work

In this paper, we present trust-based scenarios (TBSs) as an instrument to precisely measure, predict, and deal with uncertainties introduced by agents and their environment. Agents generate TBSs by categorizing and grouping experiences gained in the past. Each TBS gives information about an agent's or the environment's possible future behavior and the probability of occurrence. As agents can take several TBSs into account, they are well-equipped to make informed and robust decisions in and to adapt to an uncertain and possibly malevolent environment. In contrast to the majority of current trust models, TBSs make less assumptions about the agent's behavior. TBSs further mirror time-dependent behavior -a prerequisite for coping with strategic agents.

We illustrated our investigations on the basis of a self-organizing power management system that consists of AVPPs. This mission-critical system relies on predictions to ensure stable operation and availability. The evaluation showed that AVPPs benefit from TBSs since TBSs approximate the stochastic process underlying other agents' or the environment's behavior. Compared to the results achieved using trust values, TBSs reduce uncertainties by 46% on average.

In future work, we will devise an algorithm AVPPs use to calculate power plant schedules on the basis of TBSs, apply the concept of TBSs to the trust facet reliability, and investigate in which way TBSs can be used to proactively trigger reorganization in a self-organizing system in order to improve its resilience.

Fig. 1 .

 1 Fig.1. Trust-based scenarios approximate an agent's underlying stochastic process by classifying gathered experiences, determining trust-based scenarios (TBSs), and thereupon deriving a trust-based scenario tree (TBST). The TBST is then used to predict future behavior on the basis of a stipulated contract. In this example, T = [-1, 1] and ∀j ∈ {0, ..., n} : ∆Tj ={[-1.0,-0.9),[-0.9,-0.7),...,[-0.3,-0.1),[-0.1,0.1],(0.1,0.3], ..., (0.7,0.9],(0.9,1.0]}. Atomic experiences are rated using the rating function given in Eq. 1 with k = 10. The length of experiences is n+1 = 3. Tuples (a, b) represent atomic experiences [E i t ]j. In step 4, the values at the TBST's edges indicate the conditional probabilities to change from one behavior to another.

Fig. 2 .

 2 Fig. 2. Mean deviation of the expected residual load (unmodified residual load prediction, trust value, TBSs) from the actual residual load. Fig. 2(a) depicts this deviation over time. Fig. 2(b) shows the accuracy of the expected behavior the 32 time slots.

  1 that 183 classes were sufficient

	Predicted Behavior	Number of Classes Size of Classes µ∆ σ∆ min∆ max∆
	1) Unmodified Prediction	-	-	629.1 32.8 573.6 707.3
	2) Trust Value	-	-	188.9 34.9 121.2 273.2
		|∆Tj| = 365	≈ 50 kW	100.4 14.6 69.0 160.6
	3) Trust-Based Scenarios	|∆Tj| = 183 |∆Tj| = 91	≈ 100 kW 101.7 14.0 73.0 152.5 ≈ 201 kW 109.0 14.7 76.5 165.6
		|∆Tj| = 45	≈ 405 kW 130.2 17.5 91.6 185.0
	Table

Acknowledgments This research is partly sponsored by the German Research Foundation (DFG) in the project "OC-Trust" (FOR 1085). The authors would like to thank F. Nafz, H. Seebach, and O. Kosak for the valuable discussions.


Panagiotis Pantazopoulos

Merkourios Karaliopoulos

Ioannis Stavrakakis
email: ioannis@di.uoa.gr

On the Local Approximations of Node Centrality in Internet Router-level Topologies *

In many networks with distributed operation and self-organization features, acquiring their global topological information is impractical, if feasible at all. Internet protocols drawing on node centrality indices may instead approximate them with their egocentric counterparts, computed out over the nodes' ego-networks. Surprisingly, however, in router-level topologies the approximative power of localized ego-centered measurements has not been systematically evaluated. More importantly, it is unclear how to practically interpret any positive correlation found between the two centrality metric variants. The paper addresses both issues using different datasets of ISP network topologies. We first assess how well the egocentric metrics approximate the original sociocentric ones, determined under perfect network-wide information. To this end we use two measures: their rank-correlation and the overlap in the top-k node lists the two centrality metrics induce. Overall, the rank-correlation is high, in the order of 0.8-0.9, and, intuitively, becomes higher as we relax the ego-network definition to include the ego's r-hop neighborhood. On the other hand, the top-k node overlap is low, suggesting that the high rank-correlation is mainly due to nodes of lower rank. We then let the node centrality metrics drive elementary network operations, such as local search strategies. Our results suggest that, even under high rank-correlation, the locally-determined metrics can hardly be effective aliases for the global ones. The implication for protocol designers is that rank-correlation is a poor indicator for the approximability of centrality metrics.

Introduction

Computer networks are generally complex systems, typically owing their complexity to their topological structure and its dynamic evolution but also the heterogeneity of their nodes. Social Network Analysis (SNA) [START_REF] Wasserman | Social network analysis[END_REF] has been lately viewed as a solid analytical framework for understanding their structural properties and the interactions of their elements. The expectation within the networking community is that socio-analytical insights can benefit the analysis of network structure and the design of efficient protocols. Indeed, there has been evidence that such insights can improve network functions such as content-caching strategies in wired networks [START_REF] Chai | Cache "less for more" in information-centric networks[END_REF] and routing/forwarding in opportunistic networks [START_REF] Daly | Social network analysis for information flow in disconnected delaytolerant manets[END_REF].

Common denominator to these efforts is the use of SNA-driven metrics for assessing the relative centrality (i.e., importance) of individual network nodes, whether humans or servers. The computation of these metrics, however, typically demands global information about all network nodes and their interconnections. The distribution and maintenance of this information is problematic in large-scale networks. In self-organized environments lacking centralized management operations, in particular, it may not even be an option at all. A more realistic alternative for assessing node centrality draws on its ego network, i.e., the subgraph involving itself, its 1-hop neighbors, and their interconnections. Egocentric measurements, carried out within their immediate locality, let nodes derive local approximations of their centrality.

Lending to simpler computations, egocentric 1 metrics have, in fact, found their way into protocol implementations [START_REF] Daly | Social network analysis for information flow in disconnected delaytolerant manets[END_REF], [START_REF] Chai | Cache "less for more" in information-centric networks[END_REF]. Nevertheless, the capacity of these local approximations to substitute the globally computed sociocentric metrics is almost always taken for granted rather than evaluated. Over Internet router-level topologies, in particular, a systematic study of the approximative power of egocentric metrics is missing.

In this paper, we focus on node centrality metrics, which are the most commonly used in networking protocols. Besides the well known Betweenness Centrality (BC) metric, we consider the Conditional BC (CBC), the destination-aware BC variant proposed in [START_REF] Pantazopoulos | Efficient social-aware content placement for opportunistic networks[END_REF], which is particularly suited to many-to-one communication and data flow typologies. We first question how well do sociocentric metrics, computed under global topological information, correlate with their egocentric variants, as computed locally over the nodes' ego networks. Since in most protocol implementations, it is the ranking of the metric values that matters rather than their absolute values, we measure this correlation over the node rankings they produce, via their full rank-correlation and the overlap in the top-k node sets in the two rankings. Then, contrary to previous works, we proceed to study what the measured correlation coefficients can reveal regarding the capacity of rank-preserving local centrality metrics to substitute the original global metrics in protocol primitives.

Related work: Computing centrality values typically requires global topological information. BC computations, in particular, can be carried out by exact yet efficient [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF] or approximation algorithms [START_REF] Brandes | Centrality Estimation in Large Networks[END_REF]. The latter seek to provide accurate sampling methods over the considered network node pairs. Some recently proposed random walk schemes that reveal high BC [START_REF] Lim | Online estimating the k central nodes of a network[END_REF] or central nodes in a general sense [START_REF] Kermarrec | Second order centrality: Distributed assessment of nodes criticity in complex networks[END_REF], provide distributedfashion approaches but require gathering beyond-local-scope information. The efforts to devise local approximations of the global centrality metrics span various disciplines and usually study whether do the former correlate with the latter. From a networking standpoint, local approximations of centrality metric have been proposed for the bridging [START_REF] Nanda | Localized bridging centrality for distributed network analysis[END_REF] and closeness centrality [START_REF] Wehmuth | Distributed assessment of the closeness centrality ranking in complex networks[END_REF]. Both works report high positive rank-correlation scores between the two counterparts over synthetic and real world networks, but do not explore whether this is sufficient to benefit networking operations. Betweenness Centrality, on the other hand, is locally approximated over real-world network topologies with the node degree, or Degree Centrality (DC), due to the evidenced linear correlation between the mean BC and DC metrics [START_REF] Vázquez | Large-scale topological and dynamical properties of the Internet[END_REF]. However, this holds for AS-level Internet maps that can exhibit different connectivity properties compared to the router-level topologies; or, in the case of load, a BC variant, for scale-free networks [START_REF] Goh | Universal behavior of load distribution in scale-free networks[END_REF]. Finally, some social studies provide experimental evidence for positive correlation between sociocentric and egocentric BC over small social and synthetic networks [START_REF] Marsden | Egocentric and sociocentric measures of network centrality[END_REF], [START_REF] Everett | Ego network betweenness[END_REF].

Our contribution: We report on the BC vs. egoBC, BC vs. DC, CBC vs. egoCBC correlation over synthetic topologies and then focus on real-world router-level topologies of sizes up to 80K nodes, coming from 20 different ISPs (Section 3). Our synthetic networks yield significant rank-correlation that weakens as their size increases. In router-level topologies, in almost all cases, we measure high rank correlation (0.8-0.9), which becomes even higher when we compute the egocentric betweenness variants over generalized ego networks, corresponding to their 2-hop neighborhoods. In each case, we analyze the time complexity and message overhead related to the computation of the metrics. (Section 2).

On the contrary, the top-k overlap is found low prompting us to study whether the rank-preserving local metrics can in practice substitute the global ones. Our experiments with basic network functions such as the centrality-driven content search, show (Section 4) that high rank-correlation values between the two BC variants are poor predictors for the capacity of the local approximations to substitute the original global metrics in actual network protocol operations.

Sociocentric vs.egocentric centrality metrics

The sociocentric metrics of betweenness centrality (BC) and the conditional betweenness centrality (CBC), along with their egocentric counterparts2 are first presented. Then, the complexity savings achieved by the latter, are discussed.

Globally computed centrality indices

Consider an arbitrary node pair (s, t) over a connected undirected graph G = (V, E). If σ st is the number of shortest paths between s and t and σ st (u) those of them passing through node u ̸ = t, then the betweenness centrality of node u, equals BC(u) = ∑ s,t∈V s<t σst(u) σst . Effectively, BC(u) assesses the importance of a network node for serving information that flows over shortest paths in the network [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF]. Whereas BC(u) is an average over all network node pairs, the conditional betweenness centrality index (CBC), captures the topological centrality of node u ̸ = t with respect to a specific destination node t [START_REF] Pantazopoulos | Centrality-driven scalable service migration[END_REF] and is given by: CBC(u

; t) = ∑ s∈V s̸ =t σst(u)
σst , with σ st (s) = 0. Therefore, CBC is particularly suited to settings where information is directed towards a particular node with discrete network functionality.

Locally computed centrality metrics -ego networks

Computing the above metrics requires information about the whole network topology and implies computational and message load overheads. In distributed settings, where nodes may be energy constrained or no explicit centralized network management be available, these computations are not favorable or not an option at all. Instead, techniques for locally assessing the centrality of network nodes can be borrowed from the SNA concepts. In the so-called ego-network structure of social studies the person we are interested in is referred to as the "ego" and its ego-network comprises itself together with those having an affiliation or friendship with it, known as "alters". Alters may as well share relations with each other (Fig. 1.a).

Hereafter, we generalize the ego-network definition to include nodes (alters) lying r hops away from u and the edges (links) between them. Formally, we can define the r th -order ego network as follows. Let N u r be the set of nodes that form the r-hop neigborhood around u, i.e., N u r = {n ∈ G : 1 ≤ h(n, u) ≤ r}, where h(a, b) denotes the minimum hopcount between nodes a and b. The r th -order ego network of node u is the graph

G u r = (V u r , E u r )
, where the set of nodes and edges are V u r = N u r ∪ {u} and

E u r = {(i, j) ∈ E : i, j ∈ V u r }, respectively. For r = 1 the network G u 1 corresponds to the original ego network definition and consists of |V u 1 | = DC(u) + 1 nodes and |E u 1 | = DC(u) + CC(u) • ( DC(u) 2 )
edges, where CC(u) is the clustering coefficient [START_REF] Newman | The Structure and Function of Complex Networks[END_REF] of node u and DC(u) its degree centrality. Practically, values of r > 2 would tend to cancel the advantages that local ego-centered measurements induce.

Accordingly, BC metrics of a certain node can be defined with respect to its ego network. For the egocentrically measured betweenness centrality (egoBC) of node u, it suffices to apply the typical BC formula over the graph

G u r : egoBC(u; r) = BC(u) |V =V u r .
We further detail the computation formula of egoBC(u, 1). In Fig. 2 the ego-node u is connected to DC(u)=5 first-neighbor nodes which are partially interconnected with each other. The maximum egoBC value that u can attain, when no links between its neighbors are present, equals (

)

. From this value we need to subtract the number of pairs (like nodes 2-5 or 3-4) that share a direct link and therefore communicate without traversing u; their number equals the numerator of the clustering

-6 10 ) -[2(1 -1 2 ) + 2(1 -1 3 )] = 5 3 coefficient CC(u)
. Finally, we need to carefully account for those node pairs that share no direct link but are connected with multiple 2-hop paths, such as nodes 2 and 4 that are connected via the paths 2-3-4, 2-u-4 and 2-5-4. The idea is that only one of those paths will cross u; thus, we need to discount the original contribution (i.e., unit) of each non-directly connected node pair i, j ∈ N u 1 by as much as the inverse of the number of competing 2-hop paths connecting i and j. This number corresponds to the element (i, j) of matrix A 2 , where A is the adjacency matrix for G u 1 . Summing up, we have:

egoBC(u; 1) = { ( DC(u) 2 ) (1 -CC(u)) - ∑ i,j∈N u 1 :h(i,j)=2 (1 -1 A 2 i,j ) if DC(u) > 1 0 if DC(u) = 1 (1)
The egocentric counterpart of conditional betweenness centrality (egoCBC), on the other hand, is less straightforward. For each ego network and for a given destination node t, we need to identify the set of exit nodes e r (u;

t) = {t ′ ∈ N u r : h(u, t ′ ) + h(t ′ , t) = h(u, t)}, i.
e., all nodes r hops away from the ego node u that lie on the shortest path(s) from u to t. This set is effectively the projection of the remote node t on the local ego network and may be a singleton but never the null set. In Fig. 1, for example, we have e 1 (u; 11) = {6}, e 1 (u; 9) = {4, 6} for the G u 1 (left graph) and e 2 (u; 11) = {10}, e 2 (u; 14) = {5, 8} for the G u 2 (right graph). For each node s ∈ G u r , we need to calculate the fraction of shortest paths from s towards any of the nodes in e r (u; t) that traverse the ego node. Thus the egocentric variant of CBC is given by

egoCBC(u; t, r) = ∑ s∈V u r t ′ ∈er(u;t) σ st ′ (u) σ st ′ 1 {h(s,t ′ )≤h(s,l), l∈er(u;t)} (2)
Again, in Fig. 1a, node 4 contributes to the egoCBC(u, 11) value since its shortest path to the single exit node 6 traverses u, although it has a shorter path to node 11, via nodes {5,10} that lie outside the ego network. Likewise, its contribution is a full unit, rather than 1/2, since the second shortest path to node 6 passes through node 5, a node outside the ego network of u. This is the price egocentric metrics pay for being agnostic of the world outside their r-neighborhood.

Although, the definitions of both ego-and sociocentric metrics are valid under weighted and unweighted graphs, we focus on the latter ones. The way link weights affect the correlation operations is clearly worth of a separate study.

Complexity comparison of betweenness counterparts

We briefly discuss how the two types of metrics compare in terms of message overhead and time complexity required for their computation. Message overhead is measured in messages times number of edges they have to travel. In both cases, we can distinguish two metric computation phases: the collection of topological information and the execution of computations.

Sociocentric computation of centrality. ). The time required for the distribution of information is of no concern, O(1). The egoBC and egoCBC computation for r = 1 can be carried out as in [START_REF] Everett | Ego network betweenness[END_REF]. The computation involves a multiplication of an O(d max )-size square matrix and trivial condition checks. For r = 2, we can employ [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF] replacing |V | with d 2 max . Finally, DC is considered to be immediately available to every node.

egoBC (r=1) O(d 3 max ) O(2 • |E|) egoBC (r=2) O(d 4 max ) O(2 • dmax • |E|) CBC O(|V | 3 ) O(D • |V |) egoCBC(r=1) O(d 3 max ) O(2 • |E|) egoCBC(r=2) O(d 4 max ) O(2 • dmax • |E|) DC O(1) -
As expected, since d max is typically much smaller than |V |, the use of local metrics bears apparent computational benefits. The question of whether these metrics correlate well with the sociocentric ones is considered next.

3 Experimental correlation-operations study between socio-and egocentric centrality metrics

Correlation coefficients and network topologies

In comparing the ego-with sociocentric metrics, we are concerned with (rank) correlationoperations. Protocol implementations that utilize highly central nodes, usually care more about the way the metric ranks the network nodes rather than their absolute metric values; this is how a degree-based search scheme explores unstructured P2P networks [START_REF] Adamic | Search in power-law networks[END_REF] or egoBC is used in DTN forwarding [START_REF] Daly | Social network analysis for information flow in disconnected delaytolerant manets[END_REF]. Alternatively, we may need to employ only a subset of k nodes with the top centrality values [START_REF] Pantazopoulos | Centrality-driven scalable service migration[END_REF] and therefore, we also study the ovelap scores between the top-k nodes determined with ego-and sociocentric counterparts, respectively. We capture the rank correlation in the non-parametric Spearman measure ρ, which assesses how monotonic is the relationship between the ranks of the two centrality variables. For the sake of completeness we also measure the well-known Pearson correlation (see [START_REF] Pantazopoulos | On the local approximations of node centrality in Internet routerlevel topologies[END_REF] for the relevant formulas). The r P rs coefficient also assesses a straight-line relationship between the two variables but now the calculation is based on the actual data values. Both ρ and r P rs lie in [-1,1] and mark a significant correlation between the considered metrics when they are close to 1. For the target-node-dependent CBC values, we present the correlation averages along with the 95% confidence intervals estimated over an at least 7% of the total locations, sample.

Regarding the networks we experiment with, our emphasis is on the real-world intradomain Internet topologies. Nevertheless, synthetic graphs with distinct structural properties such as the rectangular grid have been also employed to provide insights. The router-level ISP topologies do not have the predictable structure of the synthetic ones and typically size up to a few thousand nodes. Yet, over these topologies networking protocols designed to cope with self-organization requirements, will seek to utilize local centrality metrics [START_REF] Pantazopoulos | Centrality-driven scalable service migration[END_REF]. We have experimented with three sets of router-level topologies:

mrinfo topologies: The dataset we consider includes topology data from 850 distinct snapshots of 14 different AS topologies, corresponding to Tier-1, Transit and Stub ISPs [START_REF] Pansiot | Extracting intra-domain topology from mrinfo probing[END_REF]. The data were collected daily during the period 2004-08 with the help of a multicast discovering tool called mrinfo, which circumvents the complexity and inaccuracy of more conventional measurement tools. Herein we experiment with a representative subset of Tier-1 and Transit topologies.

Rocketfuel topologies: The Rocketfuel technique [START_REF] Spring | Measuring ISP topologies with rocketfuel[END_REF] has been shown to collect high-fidelity router-level maps of ISPs and therefore has been widely used despite its old, around 2002, publication. The considered dataset includes measurements from 800 vantage points serving as traceroute sources. Innovative techniques such as BGP directed probing and IP identifiers, have been applied to reduce the number of probes, and discover the different interface IP addresses that belong to the same router (i.e., alias resolution), respectively.

CAIDA topologies: The most recent of our datasets [START_REF]The CAIDA UCSD Macroscopic Internet Topology Data Kit[END_REF] was collected during Oct-Nov 2011 by CAIDA performing traceroute probes to randomly-chosen destinations from 54 monitors worldwide. Parsing the provided separate file that heuristically assigns an AS to each node found, we have determined the router-to-AS ownership and subsequently have extracted out of the raw data files the topologies of the nodes operated by certain ASes. Our effort was to discover the largest ISP networks in the dataset. With all three datasets we avail a rich experimentation basis of a diverse Internet topologies' set that can minimize the effect of measurement technique errors.

Experimental results

We choose to spend more effort experimenting on the BC-egoBC, BC-DC correlation debates, expected to attract more interest (see Section 4) than the limited-scope of CBC. egoBC vs.BC : In grid topologies, ego networks have fixed size depending on their position, i.e., corner, side, or internal nodes. Thus, the egoBC index may only exhibit a small number of different values (e.g., 1, 3 and 6 with respect to the node's location when r = 1). When grid dimensions grow larger, the number of shortest paths between any node pair grows exponentially, resulting in a richer spectrum of BC values over the grid nodes. On the other hand, the possible egoBC values remain the same; only the distribution of grid nodes over these values changes (see Fig. 3a-d). Consequently, in Table 2, ρ values decrease monotonically with the grid size. Same behavior and reasoning also holds for the line network.

Our findings for the real-world ISP topologies are listed in Table 3. Even with measurements within the first-order ego network, there is high positive rank correlation between BC and egoBC. On the other hand, the Pearson coefficient suggests looser yet positive association. When egoBC is computed in the second-order ego network, both correlation coefficients become even higher and also more similar with each other. The structural characteristics of the considered ISP topologies differ from the grid topologies; their diameter and clustering coefficients attain many different values as their size scales. Provably there is enough asymmetry throughout the topology to yield a wide range of BC and egoBC values that favors high correlation. A notable exception is the mrinfo Level-3 ISP topology (IDs 12,13) which we comprehensively study (and visualize) in [START_REF] Pantazopoulos | On the local approximations of node centrality in Internet routerlevel topologies[END_REF]. Herein, we provide only a brief explanation. Datasets 12,13 were found to avail some clustered structures of nodes that, interestingly, exhibit higher egoBC than global BC values; it is these nodes that distort the desired linear relation between the centrality counterparts. Finally, note that Table 3 results imply that the localized bridging centrality [START_REF] Nanda | Localized bridging centrality for distributed network analysis[END_REF], which uses egoBC to approximate BC, is also highly correlated with its global counterpart in these topologies. DC vs.BC: In grid topologies we have observed the same correlation degradation with the network size, explained along the aforementioned BC-spectrum arguments. In all router-level topologies (Table 3) we find high Pearson and even higher Spearman correlation although consistently lower than the corresponding egoBC vs.BC one, at least for the Spearman ρ. As such, the previously reported [START_REF] Vázquez | Large-scale topological and dynamical properties of the Internet[END_REF] DC-BC correlation over AS-level topologies is extended, by our results, to the router-level ones. Finally, the earlier observed egoBC-BC rank correlation can be further justified on the grounds of the high DC-BC Spearman values; the router-level topologies exhibit vanishing clustering coefficients and thus, the egoBC metric attains similar values to DC (see Eq. 1). This is depicted in Fig. 3.e where the egoBC-DC correlation scales linearly with the mean clustering coefficients, especially in the CAIDA set.

egoCBC vs.CBC : We now assess the ego variant of the CBC metric (r=1). Table 4 suggests significant positive rank correlation in all studied ISP topologies, even for the outlier case of the mrinfo Level-3 networks. Intuitively, the correlation between CBC counterparts is expected to be higher than the one between BC counterparts; by neglecting the world outside of the ego network, the egoBC inaccuracies (compared to the globally determined BC) may arise anywhere across the network. On the contrary, egoCBC(u; t, r) considers only the paths that lead to the target t, somehow focusing on an angle that encompasses t; thus, it may differ from the CBC(u;t) view only across that certain angle.

top-k nodes overlap : Finally, we assess the extent to which the nodes with the topk values of local centrality metrics coincide with the corresponding ones determined by the global BC. Interestingly, Table 5 shows that this overlap is low, at least for the first-order ego network measurements. This does not actually contradict our previous results since correlation is determined over all network nodes rather than a subset of cardinality k. Clearly, the observed high rank-correlation is mainly due to nodes of lower rank; for instance, those with already zero values for both centrality counterparts (i.e., DC=1) have been reported to drastically contribute to the high egoBC-BC correlation [START_REF] Everett | Ego network betweenness[END_REF]. Along this thread, our comprehensive study [START_REF] Pantazopoulos | On the local approximations of node centrality in Internet routerlevel topologies[END_REF] has shown that the actual association between the two metric variants is not determined solely by the degree distribution. Finally, the low top-k overlap scores serve as a warning sign as to what the high coefficients can reveal about the practical implications of local centrality metrics.

Practical utility of local centrality metrics

We now study basic network operations where local centrality metrics are employed, encouraged by the high corresponding correlation, to substitute the global ones. Our aim is to assess whether such options can actually be effective in networking practice.

A local-centrality-driven navigation scheme: In unstructured power-law P2P networks, it has been shown [START_REF] Adamic | Search in power-law networks[END_REF] that a high-degree (file) seeking strategy is more efficient than a random-walk strategy. The former, at each step, passes a single query message to a neighboring node of higher degree exploiting the great number of links pointing to high degree nodes. We have implemented a similar navigation scheme that crawls the network following a MAX or MAX-MIN pattern with respect to node centrality; each time, the crawler moves to the neighbor with the maximum(minimum) centrality out of those that exhibit higher(lower) values than the current node, utilizing a self-avoiding path. We randomly select 20% of the network nodes as starting points and execute 10 runs (i.e., crawlings) for each one but with no destinations predetermined. Effectively, we seek to compare the navigation patterns and final locations achieved by using the different centrality variants as drivers. α-hops overlap measures the percentage of the final locations lying within α hops away from those the global metric yields. Zero-hop overlap refers to the destinations' exact matching. Regarding the final locations, figs. 4a-d) show that the local metrics (r=1) can hardly be effective aliases for the global ones. The crawler, driven by local metrics, is measured [START_REF] Pantazopoulos | On the local approximations of node centrality in Internet routerlevel topologies[END_REF] to consistently take from 0.4 up to 2.3 on average less hops than when it is BC-driven, failing to identify the same navigation pattern i.e., sequence of central nodes. In view of the high correlation between the involved metrics, we have tried to shed some light on the somewhat counterintuitive, poor navigation performance [START_REF] Pantazopoulos | On the local approximations of node centrality in Internet routerlevel topologies[END_REF]. Removing sequentially four nodes from a toy topology of initially perfect rank correlation (i.e., ρ =1) between the two counterparts, we measured it reducing to 0.9953. At the same time the zero-hop overlap for the MAX pattern drastically diminished from 100% to 61.90%. Clearly, the numerical summaries the coefficients provide, fail to capture in micro-level the relative significance of each node which determines the scheme's performance.

A local-centrality-driven search scheme: As the conditional centrality metrics involve a target node, we are enabled to compare CBC and egoCBC essentially over a (content) search scheme. For each starting location we randomly select a target node and seek to reach it utilizing a MAX search pattern. Fig. 4.e shows low ovelap between the final locations achieved by the two counterparts while the hopcount to the final location is again measured consistently lower (i.e., 0.3 to 1.5 hops) for the egoCBC case; driven by the local variant the search fails to track closely the route that the global one induces.

In terms of the one-hop overlap between the achieved final locations and the targets (i.e., hit-rates), which is also reported in [START_REF] Adamic | Search in power-law networks[END_REF], figure 4.e (two rightmost bars) shows that the egoCBC-driven search indeed hits significantly less targets than the CBC-driven does. The number of targets reached by the local CBC variant is in good agreement with the discovered P2P nodes in [START_REF] Adamic | Search in power-law networks[END_REF], using DC as a driver; there, a networkwide path of the query may cumulatively hit up to 50% of either the targets or their first neighbors. On the contrary, we obtain high overlap values when the global metric drives the MAX search pattern, since the closer node u lies to the target t the higher its CBC(u; t).

Conclusions

The paper has questioned to what extent the original centrality metrics can be substituted by their computationally friendly local approximations in router-level topologies. First, the metrics are shown to exhibit high rank-correlation with their local counterparts across all datasets (20 ISPs) but one. On the other hand, the match between the two variants is much worse when we compare the top-k nodes selected by each of them. Then, we tried to assess what the algebraic values of the correlation coefficients reveal regarding the performance of network functions, when the original metrics are substituted by their local approximations. Both a simple navigation and a search scheme employing local centrality metrics produce significantly different navigation patterns and lower hitrates, respectively, than their counterparts with the original global metrics. These results suggest that, despite the positive correlations, local variants can hardly offer effective approximations to the original metrics. Our work essentially warns against relying on the correlation indices for assessing the substitutability of ego-and sociocentered variants of centrality metrics.

Fig. 1 .

 1 Fig. 1. a) Nodes 2, 3 and 4 contribute to egoCBC(u; 11, 1) = 2 with contributions 1/2, 1/2 and 1, respectively. b) Node 8 reaches the exit node 10 for destination node 11 through five different paths, two of which pass through node u, thus contributing 2/5 to egoCBC(u; 11, 2).

Fig. 2 .

 2 Fig. 2. Toy-example computation: egoBC(u; 1)= 10(1 -6 10 ) -[2(1 -1 2 ) + 2(1 -1 3 )] = 5

Fig. 3 .

 3 Fig. 3. a)-d) Probability distribution of BC and egoBC values for scaling size of a grid network. e) egoBC-DC correlation scales linearly with <CC> values.

  k=10 k=30 ID egoBC(r=1) egoBC(r=2) DC egoBC(r=1) egoBC(r=2) DC 50

Fig. 4 .

 4 Fig. 4. a-e) Overlap between the final locations achieved with local and global centrality as driver; in e) the two rightmost bars of each dataset show the egoCBC/CBC-driven search hit-rates.

  The network nodes need to collect global information about the overall network topology; hence, each one of the |V | network nodes has to inform the other |V | -1 about its neighbors. This generally requires O(|E f |) message copies and O(D) time steps for each node's message, where D is the network diameter and |E f | the number of edges in the flooding subgraph. In the best case, the flooding takes place over the nodes' spanning trees, hence the message overhead is O(|V | -1). For the distribution of one round of messages by all nodes, the overhead becomes O(|V | 2 ); the time remains O(D) assuming that the process evolves in parallel. With knowledge of the global topology, each node can compute the BC values of all other nodes in the network. An efficient way to do this is to invoke Brandes' algorithm [3], featuring O(|V | • |E|) complexity for unweighted graphs and O ( (|E| + |V |) • |V |log|V | ) complexity for weighted graphs. Interestingly, the CBC values of each network node with respect to all other network nodes, emerge as intermediate results of Brandes' algorithm for the BC computation 3 . Egocentric computation of centrality. Intuitively, the egocentric variants save complexity. The message overhead over the whole network is O(2 • |E|) for the ego network with r = 1 and O(2•d max |E|) for the ego network with r = 2, where d max is the maximum node degree; for dense graphs this overhead becomes O(|V | 2

Table 1 .

 1 Complexity comparison of sociovs.ego-centric metrics

	Metric	Time complexity Message overhead
	BC	O(|V | 3 )	O(D • |V |)

Table 2 .

 2 Correlation study between BC and egoBC on grid networks

							Grid size Diameter / Mean degree		Spearman ρ
												ego-network (r=1) ego-network (r=2)
							5x5		8 / 3.200		0.9195					0.9679
							10x10	18 / 3.600		0.8400					0.9556
							20x20	38 / 3.800		0.6802					0.8459
							50x50	98 / 3.920		0.2429					0.2942
							60x8	66 / 3.717		0.5735					0.6336
							90x8	96 / 3.728		0.5390					0.5870
							150x8	156 / 3.737	0.4584					0.4181
							400x8	406 / 3.745	0.1633					0.2213
	fraction of nodes	0 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4	20 betweenness values 40 60	80	fraction of nodes	0 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08	200 betweenness values 400 600	800	fraction of nodes	0 0 0.1 0.2 0.3 0.4 0.5	1	2 betweenness values 3 4 5	6	7	fraction of nodes	0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8	1	2 betweenness values 3 4 5	6	7	Mean Clustering Coefficient	0.85 0 0.1 0.2 0.3 0.4	0.9 Spearman ρ (egoBC -DC) 0.95 CAIDA mrinfo Rocketfuel	1
			a. BC (5x5)				b. BC (10x10)					c. egoBC (5x5)					d. egoBC (10x10)		e. scatter-plot for each dataset

Table 3 .

 3 Correlation study between BC-egoBC and BC-DC on router-level ISP topologies

	DataSet ID	ISP(AS number)	<CC> Diameter Size <degree>		BC vs.ego-BC		BC vs.DC
								Spearman ρ	Pearson rP rs
								ego-net. r=1 ego-net. r=2 ego-net. r=1 ego-net. r=2 Spearman ρ Pearson rP rs
		35 Global Crossing(3549) 0.479	9	100	3.78	0.9690	0.9853	0.7029	0.9255	0.8506	0.6714
	m	33 NTTC-Gin(2914)	0.307	11	180	3.53	0.9209	0.9565	0.7479	0.8561	0.8180	0.6664
	r	13	Level-3(3356)	0.169	25	378	4.49	0.2708	0.9393	-0.0918	0.7982	0.1953	-0.0813
	i	12	-//-	0.149	28	436	4.98	0.2055	0.9381	-0.1217	0.7392	0.1696	-0.1128
	n	20	Sprint(1239)	0.287	16	528	3.13	0.9866	0.9928	0.5805	0.8488	0.8543	0.6815
	f	38	Iunet(1267)	0.231	12	645	3.75	0.8790	0.9516	0.9094	0.9568	0.8549	0.7708
	o	44 Telecom Italia(3269) 0.037	13	995	3.65	0.7950	0.9828	0.3362	0.8699	0.7733	0.4852
		50 TeleDanmark(3292) 0.058	15	1240	3.06	0.9569	0.9738	0.5475	0.9025	0.9388	0.5538
	R	61	Ebone(1755)	0.115	13	295	3.68	0.9736	0.9860	0.6856	0.8895	0.9443	0.7457
	O	62	Tiscali(3257)	0.028	14	411	3.18	0.9522	0.9659	0.6073	0.9281	0.9464	0.7103
	C	63	Exodus(3967)	0.273	14	353	4.65	0.9125	0.9792	0.6100	0.9061	0.8204	0.6241
	K	64	Telstra (1221)	0.015	15	2515	2.42	0.9990	0.9990	0.3336	0.7565	0.9783	0.5172
	E	65	Sprint(1239)	0.022	13	7303	2.71	0.9980	0.9990	0.4770	0.7977	0.9562	0.6537
	T	66	Level-3(3356)	0.097	10	1620	8.32	0.9841	0.9923	0.6346	0.9075	0.9655	0.7045
	F	67	AT&T(7018)	0.005	14	9418	2.48	0.9988	0.9994	0.3388	0.5302	0.9882	0.4483
	L	68	Verio (2914)	0.071	15	4607	3.28	0.9904	0.9969	0.4729	0.8044	0.9315	0.6718
		70	UUNet (701)	0.012	15	18281 2.77	0.9841	0.9886	0.5430	0.8752	0.9694	0.7544
	C	71 COGENT/PSI(174) 0.062	32	14413 3.09	0.9638	0.9599	0.7272	0.9354	0.8940	0.8791
	A	72 LDComNet(15557) 0.021	40	6598	2.47	0.9674	0.9245	0.3782	0.7676	0.9479	0.6634
	I	74 ChinaTelecom(4134) 0.083	19	81121 3.97	0.8324	0.8986	0.7861	0.9714	0.7370	0.8795
	D	75 FUSE-NET(6181) 0.018	10	1831	2.38	0.9903	0.9763	0.6205	0.8574	0.9536	0.7445
	A	76	JanetUK(786)	0.031	24	2259	2.26	0.9819	0.9834	0.4444	0.8506	0.9450	0.5765

Table 4 .

 4 Rank-correlation between CBC and ego-CBC (r=1).

	ID	35	33	13	12	20	44
	Spearman ρ 0.9489 0.9554 0.7336 0.7035 0.9847 0.9902
	Conf. Interv. 0.013 0.003 0.007 0.005 0.003 0.001
	ID	50	61	62	63	75	76
	Spearman ρ 0.9739 0.8423 0.9321 0.7641 0.9961 0.9853
	Conf. Interv. 0.009 0.027 0.016 0.023 0.005 0.002

Table 5 .

 5 Overlap(%) between nodes with the top-k local centrality and BC values.

The terms egocentric and local as well as sociocentric and global are used interchangeably in the paper.

The degree centrality (DC) is by default an egocentric centrality metric.

The algorithm in[START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF] effectively visits successively each node u ∈ V and runs augmented versions of shortest path algorithms. By the end of each run, the algorithm has computed the |V | -1 CBC(v; u) values, v ∈ V ; while the |V | BC(v) values result from iteratively summing these values as the algorithm visits all network nodes u ∈ V .

* This work has been partially supported by the National & Kapodistrian University of Athens Special Account of Research Grants no 10812 and the European Commission under the Network of Excellence in Internet Science project EINS (FP7-ICT-288021).


István Fehérvári

Wilfried Elmenreich

Evolution as a Tool to Design Self-organizing Systems

Keywords: self-organizing systems, evolutionary design, emergence, complexity

Self-organizing Systems exhibit numerous advantages such as robustness, adaptivity and scalability, and thus provide a solution for the increasing complexity we face within technical systems. While they are attractive solutions, due to their nature, designing self-organizing systems is not a straightforward task. Artificial evolution has been proposed as a possible way to build self-organizing systems, but there are still many open questions on how an engineer should apply this method for this purpose. In this paper we propose a design methodology for evolving self-organizing systems, that marks the major cornerstones and decisions the designer has to face, thus providing a practical set of guidelines.

Introduction

Self-organizing systems are inherently scalable, adaptive and tend to be very robust against single-point failures, which made them an appealing choice in the technical domain [START_REF] Elmenreich | Self-organizing networked systems for technical applications: A discussion on open issues[END_REF]. Typically, a design procedure of such systems would be to find the local, microlevel interactions that will result in the desired global behavior. Unfortunately, there is no straightforward way for the design of these rules yet so that the overall system will show the desired macro-level properties.

There exist different approaches to design self-organizing systems. Gershenson [START_REF] Gershenson | Design and Control of Self-organizing Systems[END_REF] introduces a notion of "friction" between two components as a utility to design the overall system iteratively. Auer et al. [START_REF] Auer | A method to derive local interaction strategies for improving cooperation in self-organizing systems[END_REF] deduce the local behavior by analyzing a hypothetical omniscient "perfect" agent. The usefulness of evolutionary algorithms to evolve cooperative behavior is demonstrated by Quinn et al. [START_REF] Quinn | Evolving teamwork and role allocation with real robots[END_REF] by evolving teamwork strategies among a set of robots. The examples are not limited to robotic applications; Arteconi [START_REF] Arteconi | Evolutionary methods for self-organizing cooperation in peer-to-peer networks[END_REF] applies evolutionary methods for designing self-organizing cooperation in peer-to-peer networks. A generic, universal approach to tackle the aforementioned design issues is to use some kind of an automated search, namely evolution to find the right set of local rules that will drive the system into the desired macro behavior.

In the domain of mathematical optimization or artificial intelligence metaheuristics, evolutionary methods have been already proven to be especially useful and so are still widely applied. Emergence and evolution have been studied by many scientists from different disciplines, like biology [START_REF] Donaldson | The evolution of functionally referential meaning in a structured world[END_REF], mathematics [START_REF] Cucker | The mathematics of emergence[END_REF], physics [START_REF]Physics of Emergence and Organization[END_REF], social systems [START_REF] Fehr | Human nature and social cooperation[END_REF], and economic systems [START_REF] Axtell | The emergence of firms in a population of agents: Local increasing returns, unstable nash equilibria, and power law size distributions[END_REF]. However, most work describes mechanisms, but does not give answers as to how to use those mechanisms to achieve an intended technical effect.

With respect to this question, the work by Belle and Ackley on evolvable code [START_REF] Van Belle | Code factoring and the evolution of evolvability[END_REF] and the work on learning for multi-agent systems [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF] by Shoham and Leyton-Brown are of special interest for the research goals of the proposed project.

The idea of using this technique to design self-organizing systems has already been mentioned [START_REF] Koza | Genetic programming: on the programming of computers by means of natural selection[END_REF], however a deeper, step-by-step guide tailored for this domain is still missing. In this paper, we are presenting a practical set of guidelines in order the fill this gap and support engineers and scientist using evolutionary design.

In the following section, we give reference to related work on design of self-organizing systems with a special focus on evolutionary design. The basic idea of using evolution as a design tool is introduced in Section 2. In Section 3, we present a design methodology for evolving self-organizing systems that marks the major aspects of the approach. In the following subsection, we discuss each aspect of our design approach and introduce guidelines for practical application. The robot soccer case study described in Section 4 shows the application of the mentioned principles in practice. The paper is concluded in Section 5.

Design by Evolution

Typically, problems based on bio-inspired principles such as self-organization call for bio-inspired solutions. An approach would be to cope with the high complexity is to use some kind of guided automated search, namely evolutionary computation.

The main idea is to create an appropriate system model with its environment, where the components are represented in such a way, that their individual behaviors (i.e. set of local rules) can be iteratively improved via a heuristic algorithm. In other words, the components have to be evolvable.

Although the concept of evolutionary design is fairly simple, when it comes to application, it starts to become increasingly complex. In general, the whole process can be decomposed into three major steps: modeling the system and its environment; an iterative search, that explores new solutions; and a final validation phase (see Figure 1).

From an engineering point of view, the modeling phase is the upmost priority, where the crucial decisions have to be made in order to obtain useful results. Among many things this includes selecting the right computation model, the way of interactions and the whole evolutionary model (genotype to phenotype mapping, search algorithm, etc.). The next step is to let the whole system run on its own, thus gradually developing a viable solution with no or very little user interaction. The last phase for any design process is to verify the obtained results. Usually, this means a set of white or black box testing, but in the case of complex networked systems, novel approaches are necessary. Fortunately, there is a lot of ongoing research on how to evaluate such systems [START_REF] Renz | Mesoscopic stochastic models for validating selforganizing multi-agent systems[END_REF].

Design Methodology

As mentioned in the previous section, building a proper system model is essential for a successful evolutionary design. In this paper we propose a methodology for the evolutionary design of self-organizing systems, that identifies the major decisions and considerations that the designer must face during the modeling process. As can be seen in Figure 2, we distinguish 6 major components: Typically, every engineering problem starts with a task description that properly identifies the objectives and constraints in detail. In other words, this can be seen as a contract that describes the expectations of the desired system on a high abstraction level. Consequently, the task description has a high influence on the applied simulation model and naturally on the objective function.

The next step is then to specify a system model based on the task description that is not only efficient, but accurately represents the important aspects of the system to be modeled while abstracting unnecessary factors. However, this step should not include how the components are represented or the way they interact with each other, since these would involve several further important decisions. For this purpose we separate them into an interaction interface unit and to an evolvable decision unit. In the former, one should plan the way the components of the system can interact with each other and their environment, thus not only defining the communication possibilities (i.e. sensors), but also their underlying interfaces (i.e. protocols).

The latter is focused on the actual representation of the components of the system. This might include one or more types of models depending on the homogeneity of the system. The reason why this part is separated from the system model is that the evolutionary method requires evolvable representations. There is, however, a vast set of such representations out there with their own advantages and disadvantages, so a careful decision has be made here.

In order for the evolutionary process to be operational there must be a valid and efficient search algorithm that iteratively optimizes the candidate solutions. While theoretically it can be completely separated from the representation of the evolvable components, it has to be noted that choosing the right algorithm has a significant overall effect on the convergence speed and on the quality of the results.

Last but not least the driving force of evolution must be also designed. While a good objective function has a key role in the process, there are unfortunately no guidelines available as to make a good function that not only ensures the desired behavior, but also makes the system avoiding unwanted states.

Case Study: Simulated Robot Soccer

The following case study describes an application of our design approach for a multirobot scenario. The main focus lies on the aspects of the respective design methodology, the particular results of the case study are described separately in [START_REF] Fehervari | Evolving neural network controllers for a team of selforganizing robots[END_REF].

In this case study, an algorithm for simulated robot soccer teams was sought. Robot soccer players should learn to successfully play soccer without being given explicit instructions as to how a soccer team should behave. The robots all have the same hardware, and within a team, each robot has the same neural network. With respect to our design methodology, the following aspects have been tackled in the modeling process:

Simulation Model: The simulation model was based on existing abstractions from real robot soccer to provide a playground for a simulated robot soccer league. This model abstracts over mechanical aspects like slacking wheels or sophisticated sensor models for ball detection, while still providing a realistic interface for testing a distributed algorithm for making the robots play soccer. In particular, our simulation was based on the Robocup Soccer Simulation League without the features for centralized control via a coach.

Interaction Interface: Experiments with different set-ups showed that the sensor interface needs to be reduced to a few vectors indicating the position of the ball, the closest opponent and the closest teammate relative to the robot. In order to score a goal, the robots need to know where they are relative to the goal, so we added sensors indicating their relative field position. We tested the performance of evolved teams using a cartesian and a polar coordinate system representing the vectors. Results show that the cartesian coordinate system can be evolved to a better solution. Decision Unit: Since there exists no particular theory, on how an evolvable decision unit for a soccer robot should be constructed, we experimented with several types of neural networks and varied the network size. Results indicate that a recursive neural network model, though being harder to analyze for a human observer, provides better capabilities than a feed forward model. The network size had less impact on the results than expected -solutions with 2, 4 or 6 neurons did not differ significantly in their performance (see Figure 3. Objective Function: Playing soccer involves complex coordination of all team members based on variables of high dynamics like the position and momentum of the ball and all players. Therefore, we identified separate performance indicators, namely field coverage, ball possession, playing the ball actively, getting the ball near the opponents goal and scoring goals. Putting these factors hierarchically into an objective function enabled a smooth evolution of game-play 1A thorough description of the results is given in [START_REF] Fehervari | Evolving neural network controllers for a team of selforganizing robots[END_REF]. The robot soccer experiment was conducted with the tool FRamework for Evolutionary Design (FREVO) [START_REF] Sobe | FREVO: A tool for evolving and evaluating selforganizing systems[END_REF]. 2 .

Conclusions and Future Work

This paper discusses the basic building blocks for applying evolutionary algorithms to the design of self-organizing systems for technical applications. Our survey of existing literature has revealed that despite the many reports on applying this approach to generate a self-organizing system, there is a need for a generic description of the underlying system engineering process. We therefore introduced several vital cornerstones of such an approach. In particular, we identified the task description, simulation setup, interaction interface, decision unit, search algorithms and fitness function.

The paper makes two main contributions: It supports the design process by defining the system aspects that must be considered. Its second contribution is that this approach may provide the basis for a qualified engineering process for self-organizing systems in technical applications. In future work we will elaborate our proposed methodology with detailed guidelines and principles for task description, simulation setup, interaction interface, decision unit, search algorithms and fitness function.

Figure 1 :

 1 Figure 1: Basic flowchart of the evolutionary design

Figure 2 :Figure 3 :

 23 Figure 2: Proposed design methodology

see http://www.youtube.com/watch?v=cP035M_w82s for a video demo.

FREVO including the robot soccer simulation described above are available as open source at http://frevo.sourceforge.net/

Acknowledgments

This work was supported by the Austrian Science Fund (FFG) grant FFG 2305537 and the Lakeside Labs GmbH, Klagenfurt, Austria, and funding from the European Regional Development Fund and the Carinthian Economic Promotion Fund (KWF) under grant KWF 20214|21532|32604, and KWF 20214|22935|34445. We would like to thank Lizzie Dawes for proofreading the paper.