Normative multi-agent systems offer the ability to integrate social and individual factors to provide increased levels of fidelity with respect to modelling social phenomena, such as cooperation, coordination, group decision making, organization, in both human and artificial agent systems. An important open research issue refers to group norms, i.e. norms that govern groups of agents. Depending on the interpretation, group norms may be intended to affect the group as a whole, each member of a group, or some members of the group. Moreover, upholding group norms may require coordination among the members of the group. We have identified three sets of agents affected by group norms, namely, i) the addressees of the norm, ii) those that will act on it, and iii) those that are responsible for ensuring norm compliance. We present a formalism to represent these, connecting it to a minimalist agent organisation model. We use our formalism to develop a reasoning mechanism which enables agents to identify their position with respect to a group norm, so as to further support agent autonomy and coordination when deciding on possible courses of action.
Distributed stream processing applications are structured as graphs of interconnected modules able to ingest high-speed data and to transform them in order to generate results of interest. Elasticity is one of the most appealing features of stream processing applications. It makes it possible to scale up/down the allocated computing resources on demand in response to fluctuations of the workload. On clouds this represents a necessary feature to keep the operating cost at affordable levels while accommodating user-defined QoS requirements. In this paper we study this problem from a game-theoretic perspective. The control logic driving elasticity is distributed among local control agents capable of choosing the right amount of resources to use by each module. In a first step, we model the problem as a non-cooperative game in which agents pursue their self-interest. We identify the Nash equilibria and we design a distributed procedure to reach the best equilibrium in the Pareto sense. As a second step, we extend the non-cooperative formulation with a decentralized incentive-based mechanism in order to promote cooperation by moving the agreement point closer to the system optimum. Our control strategies have been evaluated in a simulation environment, by confirming the results of the theoretical analysis.
This paper presents an approach for the efficient and transparent parallelization of a large class of swarm algorithms, specifically in the cases where the multi-agent paradigm is used to implement the functionalities of bio-inspired entities, e.g., ants, birds etc. Parallelization is achieved by partitioning the space on which agents operate on multiple regions, and assigning each region to a different computing node. Data consistency and conflict issues, which may arise when several agents concurrently access shared data, are handled using a purposely developed notion of logical time. This approach enables a transparent porting onto parallel/distributed architectures, as the developer is only in charge of defining the behavior of the agents, without coping with issues related to parallel programming and performance optimization. The approach has been evaluated in a very popular application domain, the ant-based spatially clustering of items, and results show good performance and scalability.
Underwater wireless sensor networks (UWSNs) have been developed for a set of underwater applications, including resource exploration, pollution monitoring, tactical surveillance, and so on. The complexity and diversity of underwater environments differentiate them significantly from terrestrial environments. Thus, the coverage requirements (coverage degrees) at different regions are possibly different as well. However, few efforts have so far been made on the topology control of UWSNs for the diverse coverage requirements. This paper proposes two algorithms for the diverse coverage problem: Traversal Algorithm for Diverse Coverage (TADC) adjusts the sensing radii of nodes successively, and at every round only one node alters its radius; Radius Increment Algorithm for Diverse Coverage (RIADC) sets the sensing radii of nodes incrementally, and at every round multiple nodes may increase their sensing radii simultaneously. Mathematical analysis shows both TADC and RIADC try best to achieve diverse coverage, but they have advantages in message complexity or optimal radius, respectively. Hence, these algorithms are suitable for different scenarios. Algorithm performance is also analyzed through simulation experiments that indicate TADC and RIADC realize diverse coverage while optimizing energy consumption as much as possible.
Self-organization has potential for high scalability, adaptability, flexibility, and robustness, which are vital features for realizing future networks. Convergence of self-organizing control, however, is comparatively slow in some practical applications. It is therefore important to enhance convergence of self-organizing controls. In controlled self-organization, which introduces an external controller into self-organizing systems, the network is controlled to guide systems to a desired state. Although existing controlled self-organization schemes could achieve this feature, convergence speed for reaching an optimal or semi-optimal solution is still a challenging task. We perform potential-based self-organizing routing, and propose an optimal feedback method using a reduced-order model for faster convergence at low cost. Simulation results show that the proposed mechanism improves the convergence speed of potential-field construction (i.e., route construction) by at most 7.9 times with low computation and communication cost.
In this paper, we propose formation control of non-holonomic mobile robots avoiding obstacles in a distributed manner for cluttered environment. The introduction of virtual robot re-structures the formation control problem into a tracking control problem between virtual reference robot and follower robots. A novel obstacle avoidance approach is proposed based upon the scaling of whole (partial) formation corresponding to centralized (distributed) framework. For the distributed environment having limited communication, our approach utilized Proportional-Integral (PI) average consensus estimators, whereby information from each robot diffuses through the communication network. The theoretical contribution is to determine the time constant involved in the diffusion process which can affect overall systems' performance. The asymptotic convergence of follower robots to the position and orientation of the reference robot is ensured using the Lyapunov function. The new technique is tested with complete, limited and no information availability. Several simulation results are provided that demonstrate the formation control and obstacle avoidance for multi-robots using the proposed scheme.
Modeling Robot Swarms Using Integrals of Birth-Death Processes
Self-organised systems typically consist of distributed autonomous entities. An increasing part of such systems is characterised by openness and heterogeneity of participants; for instance, open Desktop Computing Grids provide a framework for unrestrictedly joining in. However, openness and heterogeneity present severe challenges to the overall system's stability and efficiency since uncooperative and even malicious participants are free to join. A promising solution for this problem is to introduce technical trust as basis; but, in turn, the utilisation of trust opens space for Negative Emergent Behaviour. This article introduces a system-wide observation and control loop that influences the self-organised behaviour in order to provide a performant and robust platform for benevolent participants. Thereby, the observation part is responsible for gathering information and deriving an system description. We introduce a graph-based approach to identify groups of suspicious or malicious agents and demonstrate that this clustering process is highly successful for the considered stereotype agent behaviours. In addition, the controller part guides the system behaviour by issuing norms that make use of incentives and sanctions. We further present a concept for closing the control loop and show experimental results that highlight the potential benefit of establishing such a control loop.
A Support System for Clustering Data Streams with a Variable Number of Clusters
Although a number for frameworks have been proposed for the design of autonomic systems that exhibit self-* properties, they typically fail to capture implicit features of modern autonomic systems, for example the ability to deal with large ensembles of components with no central point of control and operating in a dynamic and unpredictable world. Furthermore, existing frameworks fail to account for the need to incorporate self-expression, i.e. the capability for a system to dynamically adapt its coordination pattern during run-time. In this paper, we address these shortcomings by proposing a new framework that integrates fundamental concepts from autonomic computing with bio-inspired design principles, exploiting the fact that biological systems tend to deal implicitly with such factors. In particular, we draw inspiration from the field of cognitive immune networks to develop a framework that can be used to build an autonomic system. The framework is applied to three different scenarios, illustrating its generality; in each case, quantitative metrics are applied to show the benefit of the proposed method compared to existing approaches.