Infrastructures and tools for multiagent systems for the new generation of distributed systems

In order for multiagent systems to be included in real domains (media and Internet, logistics, e-commerce, and health care), infrastructures and tools for multiagent systems should provide efficiency, scalability, security, management, monitoring, and other features related to building real applications. Thus, infrastructures and tools that support multiagent systems are needed, especially those that promote the adoption of agent-based systems by designers and programmers in both academia and industry. This special issue is a selection of contributions whose preliminary versions were presented at the ITMAS 2010 workshop, which was held in conjunction with the International Conference on Autonomous Agents and Multi-agent Systems.     

Zeus: A toolkit for building distributed multiagent systems

The multiagent systems approach of knowledge- level cooperation between autonomous agents promises significant benefits to distributed systems engineering, such as enhanced interoperability, scalability, and reconfigurability. However, thus far, because of the innate difficulty of constructing multiagent systems, this promise has been largely unrealized. Hence there is an emerging desire among agent developers to move away from developing point solutions to point problems in favor of developing methodologies and toolkits for building distributed multiagent systems. This philosophy led to the development of the ZEUS Agent Building Toolkit, which facilitates the rapid development of collaborative agent applications through the provision of a library of agent- level components and an environment to support the agent-building process. The ZEUS toolkit is a synthesis of established agent technologies with some novel solutions to provide an integrated collaborative agent-building environment.     

Optimal control of distributed multiagent systems with finite-time group flocking

The flocking of multiple intelligent agents, inspired by the swarm behavior of natural phenomena, has been widely used in the engineering fields such as in unmanned aerial vehicle (UAV) and robots system. However, the performance of the system (such as response time, network throughput, and resource utilization) may be greatly affected while the intelligent agents are engaged in cooperative work. Therefore, it is concerned to accomplish the distributed cooperation while ensuring the optimal performance of the intelligent system. In this paper, we investigated the optimal control problem of distributed multiagent systems (MASs) with finite-time group flocking movement. Specifically, we propose two optimal group flocking algorithms of MASs with single-integrator model and double-integrator model. Then, we study the group consensus of distributed MASs by using modern control theory and finite-time convergence theory, where the proposed optimal control algorithms can drive MASs to achieve the group convergence in finite-time while minimizing the performance index of the intelligence system. Finally, experimental simulation shows that MASs can keep the minimum energy function under the effect of optimal control algorithm, while the intelligent agents can follow the optimal trajectory to achieve group flocking in finite time.     

High-level debugging of distributed systems: The behavioral abstraction approach

Most extant debugging aids force their users to think about errors in programs from a low-level, unit-at-a-time perspective. Such a perspective is inadequate for debugging large complex systems, particularly distributed systems. In this paper, we present a high-level approach to debugging that offers an alternative to the traditional techniques. We describe a language, edl, developed to support this high-level approach to debugging and outline a set of tools that has been constructed to effect this approach. The paper includes an example illustrating the approach and discusses a number of problems encountered while developing these debugging tools.     

基于自适应分布式滤波观测器的多智能体系统编队控制

本文考虑了全局指令系统输出信息受到信道扰动情况下线性多智能体系统的编队控制问题.首先,基于协作式输出调节理论框架对线性多智能体系统的编队控制问题进行数学建模.其次,针对受到信道扰动的全局指令系统输出信息,提出了一类基于受扰输出的自适应分布式滤波观测器,在降低网络信息交换量的同时消除扰动的影响.最后,设计了输出反馈确定等价控制律,解决了线性多智能体系统的分布式编队控制问题.给出了数值仿真结果检验控制性能.     

具有复杂动力学的多智能体系统分布式优化综述

多智能体系统分布式优化由于其高效性、灵活性和可靠性等特点吸引了大量学者的关注,在多机器人协同控制、无线传感器网络、能源系统等领域具有广泛的应用前景.分布式优化的基本目标是利用智能体的个体目标函数梯度、自身及其邻居状态信息设计分布式控制协议,驱动所有智能体的状态或输出到全局目标函数的最优解,系统动力学是影响智能体状态演化的重要因素.鉴于此,在回顾现有连续时间分布式优化算法的基础上,根据系统动力学分类,尽可能全面地评述具有复杂动力学的多智能体系统分布式优化问题的最新研究进展,并对未来发展方向进行展望.     

Fully distributed consensus for fuzzy multiagent systems with jointly connected topology

This paper investigates the problem of fully distributed consensus for polynomial fuzzy multiagent systems (MASs) under jointly connected topologies. First, a polynomial fuzzy modeling method is presented to characterize the error dynamics that is constructed by one leader and multiple followers. Then, using the relative state information and the agents' dynamics, a distributed adaptive protocol is designed to guarantee that MASs under jointly connected topologies can achieve consensus in a fully distributed fashion. Utilizing the Lyapunov technique, a relaxed sufficient criterion is proposed to ensure consensus for fuzzy MASs under jointly connected topologies. Moreover, the adaptive coupling weights between neighboring agents can converge to certain values. The derived condition is transformed into a sum-of-squares form, which can be solved numerically. We provide an example to illustrate the proposed distributed adaptive consensus technique's validity.     

Biotope: an integrated framework for simulating distributed multiagent computational systems

The study of distributed computational systems issues, such as heterogeneity, concurrency, control, and coordination, has yielded a number of models and architectures, which aspire to provide satisfying solutions to each of the above problems. One of the most intriguing and complex classes of distributed systems are computational ecosystems, which add an "ecological" perspective to these issues and introduce the characteristic of self-organization. Extending previous research work on self-organizing communities, we have developed Biotope, which is an agent simulation framework, where each one of its members is dynamic and self-maintaining. The system provides a highly configurable interface for modeling various environments as well as the "living" or computational entities that reside in them, while it introduces a series of tools for monitoring system evolution. Classifier systems and genetic algorithms have been employed for agent learning, while the dispersal distance theory has been adopted for agent replication. The framework has been used for the development of a characteristic demonstrator, where Biotope agents are engaged in well-known vital activities-nutrition, communication, growth, death-directed toward their own self-replication, just like in natural environments. This paper presents an analytical overview of the work conducted and concludes with a methodology for simulating distributed multiagent computational systems.     

Monitoring and debugging distributed realtime programs

In this paper we describe the design and implementation of an integrated monitoring and debugging system for a distributed real-time computer system. The monitor provides continuous, transparent monitoring capabilities throughout a real-time system's lifecycle with bounded, minimal, predictable interference by using software support. The monitor is flexible enough to observe both high-level events that are operating system- and application-specific, as well as low-level events such as shared variable references. We present a novel approach to monitoring shared variable references that provides transparent monitoring with low overhead. The monitor is designed to support tasks such as debugging realtime applications, aiding real-time task scheduling, and measuring system performance. Since debugging distributed real-time applications is particularly difficult, we describe how the monitor can be used to debug distributed and parallel applications by deterministic execution replay.     

A framework for distributed debugging

The authors provide a general picture of current research in distributed debugging. Rather than an exhaustive survey of the area, they present a view of the issues and solutions based on a proposed framework for distributed debugging systems. They concentrate on runtime debugging. However, they stress that static debugging and runtime debugging complement each other and that neither should be overlooked     

Visualization and debugging in a heterogeneous environment

The authors' experiences with visualization and debugging of parallel virtual machine (PVM) applications and two of the tools they have devised to facilitate these tasks are described. One of the tools is a graphical monitoring package called Xab that can visually display PVM activities inside an application running across a network. The other is a graphical programming environment called Hence, which helps the user write, compile, execute, and trace heterogeneous distributed programs. The authors discuss their early work, the present research, and the future directions of these experimental projects     

On load balancing for distributed multiagent computing

Multiagent computing on a cluster of workstations is widely envisioned to be a powerful paradigm for building useful distributed applications. The agents of the system span across all the machines of a cluster. Just like the case of traditional distributed systems, load balancing becomes an area of concern. With different characteristics between ordinary processes and agents, it is both interesting and useful to investigate whether conventional load-balancing strategies are also applicable and sufficient to cope with the newly emerging needs, such as coping with temporally continuous agents, devising a performance metric for multiagent systems, and taking into account the vast amount of communication and interaction among agent. This paper discusses the above issues with reference to agent properties and load balancing techniques and outlines the space of load-balancing design choices in the arena of multiagent computing. In view of the special agent characteristics, a novel communication-based load-balancing algorithm is proposed, implemented, and evaluated. The proposed algorithm works by associating a credit value with each agent. The credit of an agent depends on its affinity to a machine, its current workload, its communication behavior, and mobility, etc. When a load imbalance occurs, the credits of all agents are examined and an agent with a lower credit value is migrated to relatively lightly loaded machine in the system. Quasi-simulated experiments of this algorithm show load-balancing improvement compared with conventional workload-oriented load-balancing schemes.     

Testing and debugging distributed programs using global predicates

Testing and debugging programs are more involved in distributed systems than in uniprocessor systems because of the presence of the communication medium and the inherent concurrency. Past research has established that predicate testing is an approach that can alleviate some of the problems in this area. However, checking whether a general predicate is true in a particular distributed execution appears to be a computationally hard problem. This paper considers a class of predicates called conjunctive form predicates (CFP) that is quite useful in distributed program development, but can be tested efficiently. We develop fully-distributed algorithms to test CFP's, prove that these algorithms are correct, and analyze them for their message complexity. The analysis shows that our techniques incur a fairly low overhead on the distributed system     

Opportunities for multiagent systems and multiagent reinforcement learning in traffic control

The increasing demand for mobility in our society poses various challenges to traffic engineering, computer science in general, and artificial intelligence and multiagent systems in particular. As it is often the case, it is not possible to provide additional capacity, so that a more efficient use of the available transportation infrastructure is necessary. This relates closely to multiagent systems as many problems in traffic management and control are inherently distributed. Also, many actors in a transportation system fit very well the concept of autonomous agents: the driver, the pedestrian, the traffic expert; in some cases, also the intersection and the traffic signal controller can be regarded as an autonomous agent. However, the “agentification” of a transportation system is associated with some challenging issues: the number of agents is high, typically agents are highly adaptive, they react to changes in the environment at individual level but cause an unpredictable collective pattern, and act in a highly coupled environment. Therefore, this domain poses many challenges for standard techniques from multiagent systems such as coordination and learning. This paper has two main objectives: (i) to present problems, methods, approaches and practices in traffic engineering (especially regarding traffic signal control); and (ii) to highlight open problems and challenges so that future research in multiagent systems can address them.     

Declarative representations of multiagent systems

This paper explores the specification and semantics of multiagent problem-solving systems, focusing on the representations that agents have of each other. It provides a declarative representation for such systems. Several procedural solutions to a well-known test-bed problem are considered, and the requirements they impose on different agents are identified. A study of these requirements yields a representational scheme based on temporal logic for specifying the acting, perceiving, communicating, and reasoning abilities of computational agents. A formal semantics is provided for this scheme. The resulting representation is highly declarative, and useful for describing systems of agents solving problems reactively     

Controllability of heterogeneous multiagent systems

The existing results on controllability of multiagent systems (MASs) are mostly based on homogeneous nodes. This paper focuses on controllability of heterogeneous MASs, where the agents are modeled as two types. One type is that the agents have the same high‐order dynamics, and the interconnection topologies of the information flow in different orders are supposed to be different; the other type is that the agents have generic linear dynamics, and the dynamics are supposed to be heterogeneous. For the first type, the necessary and sufficient condition for controllability of heterogeneous‐topology system is derived via combination of Laplacian matrices. For the second type, the contribution also has two parts. The first part supposes that the agents have the same dimensional states and proves that controllability of this kind of MASs is equivalent to the controllability of each node and the whole interconnection topology, while the last parameter of the state feedback vector must not be 0. The second part supposes that the agents may have different dimensional states. For this kind of systems, the concept of β‐controllability is proposed. The necessary and sufficient condition for β‐controllability of heterogeneous‐dynamic systems is also derived and it is also proved that the feedback gain vectors have the effect to improve controllability. Different illustrative examples are provided to demonstrate the effectiveness of the theoretical results in this paper.     

Multi‐layer distributed protocols for robust cooperative tracking in interconnected nonlinear multiagent systems

We develop a mixed graph and optimal control theoretic formulation to design a robust cooperative control protocol for a large‐scale multiagent system with partially known interconnected first‐, second‐, or mixed first‐ and second‐order dynamics. In each case, we transform the control protocol design task to a robust communication graph design problem, which, from a cyber‐physical perspective, is interpreted as the control layer design problem for an interconnected system with unknown agent layer dynamics. According to this viewpoint, each state variable has its own control layer communication topology separate from the other state variable's communication topology and the unknown agent layer interconnection topologies. We prove that all cooperative, decentralized, and centralized tracking protocols can be treated as a single design problem and, by deriving closed‐form solutions for the robust control layer topologies, we further provide a simpler design procedure, which is only based on the matrix manipulations. Aside from the linear implementation of the protocol and the connection of the proposed formulation to the well known rules‐of‐thumb in optimal control theory, this creates a higher potential to transfer ideas to industry. Modeling uncertainties tolerable by a given control layer topology is analyzed, and a preliminary performance‐oriented analysis and design approach for large‐scale interconnected systems is discussed. We show that exactly the same steps can be followed to design appropriate control layers for both tracking and stabilization.     

Data race avoidance and replay scheme for developing and debugging parallel programs on distributed shared memory systems

Distributed shared memory (DSM) allows parallel programs to run on distributed computers by simulating a global virtual shared memory, but data racing bugs may easily occur when the threads of a multi-threaded process concurrently access the physically distributed memory. Earlier tools to help programmers locate data racing bugs in non-DSM parallel programs are not easily applied to DSM systems. This study presents the data race avoidance and replay scheme (DRARS) to assist debugging parallel programs on DSM or multi-core systems. DRARS is a novel tool which controls the consistency protocol of the target program, automatically preventing a large class of data racing bugs when the parallel program is subsequently run, obviating much of the need for manual debugging. For data racing bugs that cannot be avoided automatically, DRARS performs a deterministic replay-type function on DSM systems, faithfully reproducing the behavior of the parallel program during run time. Because one class of data racing bugs has already been eliminated, the remaining manual debugging task is greatly simplified. Unlike previous debugging methods, DRARS does not require that the parallel program be written in a specific style or programming language. Moreover, DRARS can be implemented in most consistency protocols. In this paper, DRARS is realized and verified in real experiments using the eager release consistency protocol on a DSM system with various applications.     

Tools and strategies for debugging distributed stream processing applications

Distributed data stream processing applications are often characterized by data flow graphs consisting of a large number of built‐in and user‐defined operators connected via streams. These flow graphs are typically deployed on a large set of nodes. The data processing is carried out on‐the‐fly, as tuples arrive at possibly very high rates, with minimum latency. It is well known that developing and debugging distributed, multi‐threaded, and asynchronous applications, such as stream processing applications, can be challenging. Thus, without domain‐specific debugging support, developers struggle when debugging distributed applications. In this paper, we describe tools and language support to support debugging distributed stream processing applications. Our key insight is to view debugging of stream processing applications from four different, but related, perspectives. First, debugging the semantics of the application involves verifying the operator‐level composition and inspecting the flows at the logical level. Second, debugging the user‐defined operators involves traditional source‐code debugging, but strongly tied to the stream‐level interactions. Third, debugging the deployment details of the application require understanding the runtime physical layout and configuration of the application. Fourth, debugging the performance of the application requires inspecting various performance metrics (such as communication rates, CPU utilization, etc.) associated with streams, operators, and nodes in the system. In light of this characterization, we developed several tools such as a debugger‐aware compiler and an associated stream debugger, composition and deployment visualizers, and performance visualizers, as well as language support, such as configuration knobs for logging and tracing, deployment configurations such as operator‐to‐process and process‐to‐node mappings, monitoring directives to inspect streams, and special sink adapters to intercept and dump streaming data to files and sockets, to name a few. We describe these tools in the context of Spade —a language for creating distributed stream processing applications, and System S —a distributed stream processing middleware under development at the IBM Watson Research Center. Published in 2009 by John Wiley & Sons, Ltd.