Self‐organization and selection in the emergence of vocabulary

Human language may have started from a consistent set of mappings between meanings and signals. These mappings, referred to as the early vocabulary, are considered to be the results of conventions established among the agents of a population. In this study, we report simulation models for investigating how such conventions can be reached. We propose that convention is essentially the product of self‐organization of the population through interactions among the agents and that cultural selection is another mechanism that speeds up the establishment of convention. Whereas earlier studies emphasize either one or the other of these two mechanisms, our focus is to integrate them into one hybrid model. The combination of these two complementary mechanisms, i.e., self‐organization and cultural selection, provides a plausible explanation for cultural evolution, which progresses with high transmission rate. Furthermore, we observe that as the vocabulary tends to convergence there is a uniform tendency to exhibit a sharp phase transition. © 2002 Wiley Periodicals, Inc.     

Competition Among Conventions

A convention can be seen as a way of resolving a coordination problem. If different conventions exist in various geographical, social or other entities (called &;201C;groups&;201D;) and if there is some mobility between these groups, which conventions, if any, will emerge as the successful ones? A simple evolutionary process is suggested and it is shown that the process converges to a Nash equilibrium for all games satisfying weak acyclity. Further, if the process converges, it converges to an efficient convention for all games in which the Pareto optimal symmetric equilibria are strict. Hence, the paper presents an explanation for the endogenous evolution of efficiency. In contrast to most recent studies in evolutionary game theory, the conclusions do not rely on random &;201C;mutations&;201D;. Instead, the driving force is the tendency of players to have increased interaction with member of their own group (viscosity).     

Multi-agent system model with mixed coupling topologies for pattern formation and formation splitting

In this article, a new type of multi-agent system model with mixed coupling topologies is proposed for realizing pattern formations with specific geometric shapes and formation splitting. The interactions among individual agents are assumed to be universally repulsive and selectively attractive. By designing the form of attractive coupling matrix, one can obtain a variety of formations with specific shapes in the system through self-assembly of agents. Both symmetric coupling case and asymmetric coupling case are considered. Analysis and simulation results show symmetric ones result in convergent dynamics to steady-state formations, whereas, for asymmetric case, the system exhibits complex dynamic behaviours, including collective rotation and chaotic motion. By breaking the graph defined by attractive couplings into disjoint subgraphs, one can make the formation of agents to split into small sizes. The results are relevant for the design of coordination and cooperative control for multi-agent systems.     

On effectiveness of wiretap programs in mapping social networks

Snowball sampling methods are known to be a biased toward highly connected actors and consequently produce core-periphery networks when these may not necessarily be present. This leads to a biased perception of the underlying network which can have negative policy consequences, as in the identification of terrorist networks. When snowball sampling is used, the potential overload of the information collection system is a distinct problem due to the exponential growth of the number of suspects to be monitored. In this paper, we focus on evaluating the effectiveness of a wiretapping program in terms of its ability to map the rapidly evolving networks within a covert organization. By running a series of simulation-based experiments, we are able to evaluate a broad spectrum of information gathering regimes based on a consistent set of criteria. We conclude by proposing a set of information gathering programs that achieve higher effectiveness then snowball sampling, and at a lower cost. Maksim Tsvetovat is an Assistant Professor at the Center for Social Complexity and department of Public and International Affairs at George Mason University, Fairfax, VA. He received his Ph.D. from the Computation, Organizations and Society program in the School of Computer Science, Carnegie Mellon University. His dissertation was centered on use of artificial intelligence techniques such as planning and semantic reasoning as a means of studying behavior and evolution of complex social networks, such as these of terrorist organizations. He received a Master of Science degree from University of Minnesota with a specialization in Artificial Intelligence and design of Multi-Agent Systems, and has also extensively studied organization theory and social science research methods. His research is centered on building high-fidelity simulations of social and organizational systems using concepts from distributed artificial intelligence and multi-agent systems. Other projects focus on social network analysis for mapping of internal corporate networks or study of covert and terrorist orgnaizations. Maksim’s vita and publications can be found on Kathleen M. Carley is a professor in the School of Computer Science at Carnegie Mellon University and the director of the center for Compuational Analysis of Social and Organizational Systems (CASOS) which has over 25 members, both students and research staff. Her research combines cognitive science, social networks and computer science to address complex social and organizational problems. Her specific research areas are dynamic network analysis, computational social and organization theory, adaptation and evolution, text mining, and the impact of telecommunication technologies and policy on communication, information diffusion, disease contagion and response within and among groups particularly in disaster or crisis situations. She and her lab have developed infrastructure tools for analyzing large scale dynamic networks and various multi-agent simulation systems. The infrastructure tools include ORA, a statistical toolkit for analyzing and visualizing multi-dimensional networks. ORA results are organized into reports that meet various needs such as the management report, the mental model report, and the intelligence report. Another tool is AutoMap, a text-mining systems for extracting semantic networks from texts and then cross-classifying them using an organizational ontology into the underlying social, knowledge, resource and task networks. Her simulation models meld multi-agent technology with network dynamics and empirical data. Three of the large-scale multi-agent network models she and the CASOS group have developed in the counter-terrorism area are: BioWar a city-scale dynamic-network agent-based model for understanding the spread of disease and illness due to natural epidemics, chemical spills, and weaponized biological attacks; DyNet a model of the change in covert networks, naturally and in response to attacks, under varying levels of information uncertainty; and RTE a model for examining state failure and the escalation of conflict at the city, state, nation, and international as changes occur within and among red, blue, and green forces. She is the founding co-editor with Al. Wallace of the journal Computational Organization Theory and has co-edited several books and written over 100 articles in the computational organizations and dynamic network area. Her publications can be found at: http://www.casos.cs.cmu.edu/bios/carley/publications.php     

Multi-Agent Social and Organizational Modeling of Electric Power and Natural Gas Markets

Complex Adaptive Systems (CAS) can be applied to investigate large-scale socio-cognitive-technical systems. Viewing such systems from a multi-agent social and organizational perspective allows innovative computational policy analysis. Argonne National Laboratory (ANL) has taken such a perspective to produce an integrated model of the electric power and natural gas markets. This model focuses on the organizational interdependencies between these markets. These organizational interdependencies are being strained by fundamental market transformations.     

Distributed impulsive control consensus for a class of unknown nonlinear multi-agent systems based on event-triggered scheme

In this study, we are concerned with the impulsive consensus control problem for a class of nonlinear multi-agent systems (MASs) which have unknown dynamics and directed communication topology. The neural networks (NNs) method is the first utilized to construct distributed event-triggered impulsive consensus protocol. In contrast to the existing impulsive consensus protocol, the consensus protocol proposed in this paper does not need the dynamics of agents, which enhances the system robustness, and realizes distributed event-triggered communication between agents, which can reduce unnecessary consumption of communication resources. Sufficient conditions are derived to ensure the consensus of the controlled MASs and the exclusion of Zeno-behavior. Finally, simulation examples are presented to illustrate the effectiveness of the proposed control protocol.     

有向网络下多个体系统的整体行为

研究非时变有向通讯网络背景下一阶线性多个体动力学系统的整体行为.根据通讯网络的结构,系统可以区分为独立基本子系统和非独立基本子系统.当系统的控制规则为一类平凡的线性类型时,系统的独立基本子系统将趋于自身的一致状态,也即子系统中的每个个体趋于子系统的带权中心.独立基本子系统带权中心由子系统的系数矩阵的零特征根归一化左特征向量确定.非独立子系统中个体将趋于独立基本子系统带权中心的凸集内.当且仅当系统的独立基本子系统唯一时,系统实现一致性行为.     

Multiscale decision-making: Bridging organizational scales in systems with distributed decision-makers

Decision-making in organizations is complex due to interdependencies among decision-makers (agents) within and across organizational hierarchies. We propose a multiscale decision-making model that captures and analyzes multiscale agent interactions in large, distributed decision-making systems. In general, multiscale systems exhibit phenomena that are coupled through various temporal, spatial and organizational scales. Our model focuses on the organizational scale and provides analytic, closed-form solutions which enable agents across all organizational scales to select a best course of action. By setting an optimal intensity level for agent interactions, an organizational designer can align the choices of self-interested agents with the overall goals of the organization. Moreover, our results demonstrate when local and aggregate information exchange is sufficient for system-wide optimal decision-making. We motivate the model and illustrate its capabilities using a manufacturing enterprise example.     

Computational and mathematical organization theory: Perspective and directions

Computational and mathematical organization theory is an interdisciplinary scientific area whose research members focus on developing and testing organizational theory using formal models. The community shares a theoretical view of organizations as collections of processes and intelligent adaptive agents that are task oriented, socially situated, technologically bound, and continuously changing. Behavior within the organization is seen to affect and be affected by the organization's, position in the external environment. The community also shares a methodological orientation toward the use of formal models for developing and testing theory. These models are both computational (e.g., simulation, emulation, expert systems, computer-assisted numerical analysis) and mathematical (e.g., formal logic, matrix algebra, network analysis, discrete and continuous equations). Much of the research in this area falls into four areas: organizational design, organizational learning, organizations and information technology, and organizational evolution and change. Historically, much of the work in this area has been focused on the issue how should organizations be designed. The work in this subarea is cumulative and tied to other subfields within organization theory more generally. The second most developed area is organizational learning. This research, however, is more tied to the work in psychology, cognitive science, and artificial intelligence than to general organization theory. Currently there is increased activity in the subareas of organizations and information technology and organizational evolution and change. Advances in these areas may be made possible by combining network analysis techniques with an information processing approach to organizations. Formal approaches are particularly valuable to all of these areas given the complex adaptive nature of the organizational agents and the complex dynamic nature of the environment faced by these agents and the organizations.This paper was previously presented at the 1995 Informs meeting in Los Angeles, CA.     

On Evolving Social Systems: Communication, Speciation and Symbiogenesis

In this paper we introduce three enhancements for evolutionary computing techniques in social environments. We describe the use of the genetic algorithm to evolve communicating rule-based systems, where each rule-based system represents an agent in a social/multi-agent environment. It is shown that the evolution of multiple cooperating agents can give improved performance over the evolution of an equivalent single agent, i.e. non-social, system. We examine the performance of two social system configurations as approaches to the control of gait in a wall climbing quadrupedal robot, where each leg of the quadruped is controlled by a communicating agent. We then introduce two social-level operators&2014;speciation and symbiogenesis&2014;which aim to reduce the amount of knowledge required a priori by automatically manipulating the system&2018;s social structure and describe their use in conjunction with the communicating rule-based systems. The reasons for implementing these kinds of operators are discussed and we then examine their performance in developing the controller of the wall-climbing quadruped. We find that the use of such operators can give improved performance over static population/agent configurations.     

Consensus seeking in multi-agent systems via hybrid protocols with impulse delays

This paper studies the consensus problem of multi-agent systems with both fixed and switching topologies. A hybrid consensus protocol is proposed to take into consideration of continuous-time communications among agents and delayed instant information exchanges on a sequence of discrete times. Based on the proposed algorithms, the multi-agent systems with the hybrid consensus protocols are described in the form of impulsive systems or impulsive switching systems. By employing results from matrix theory and algebraic graph theory, some sufficient conditions for the consensus of multi-agent systems with fixed and switching topologies are established, respectively. Our results show that, for small impulse delays, the hybrid consensus protocols can solve the consensus problem if the union of continuous-time and impulsive-time interaction digraphs contains a spanning tree frequently enough. Simulations are provided to demonstrate the effectiveness of the proposed consensus protocols.     

Asymptotic pinning synchronization of nonlinear multi-agent systems: Its application to tunnel diode circuit

This work proposes a pinning state-feedback control technique for synchronizing non-linear multi-agent systems (MASs) with time delays. A collection of switching-directed graphs describes the communication exchanges between all of the agents. The challenge of asymptotic stability analysis for some error systems is translated into the construction of a leader-following synchronization of the relevant MASs. The closed-loop system could be acquired by building a convenient Lyapunov–Krasovskii functional (LKF) that has two integral terms, and by using Kronecker product qualities combined with matrix inequality techniques. When these conditions are met, a state-feedback pinning controller can be built with linear matrix inequalities (LMIs), which can be derived easily from a number of efficient optimization algorithms. Further, the performance of the proposed control design system is verified based on a tunnel diode circuit (TDC) by numerical simulations.     

SDML: A Multi-Agent Language for Organizational Modelling

A programming language which is optimized for modelling multi-agent interaction within articulated social structures such as organizations is described with several examples of its functionality. The language is SDML, a strictly declarative modelling language which has object-oriented features and corresponds to a fragment of strongly grounded autoepistemic logic. The virtues of SDML include the ease of building complex models and the facility for representing agents flexibly as models of cognition as well as modularity and code reusability. Two representations of cognitive agents within organizational structures are reported and a Soar-to-SDML compiler is described. One of the agent representations is a declarative implementation of a Soar agent taken from the Radar-Soar model of Ye and Carley (1995). The Ye-Carley results are replicated but the declarative SDML implementation is shown to be much less computationally expensive than the more procedural Soar implementation. As a result, it appears that SDML supports more elaborate representations of agent cognition together with more detailed articulation of organizational structure than we have seen in computational organization theory. Moreover, by representing Soar-cognitive agents declaratively within SDML, that implementation of the Ye-Carley specification is necessarily consistent and sound with respect to the formal logic to which SDML corresponds.     

Can tools help unify organization theory? Perspectives on the state of computational modeling

Scholars engaged in the study of work group and organizational behavior are increasingly calling for the use of integrated methods in conducting research, including the wider adoption of computational models for generating and testing new theory. Our review of the state of modern computational modeling incorporating social structures reveals steady increases in the incorporation of dynamic, adaptive, and realistic behaviors of agents in network settings, yet exposes gaps that must be addressed in the next generation of organizational simulation systems. We compare 28 models according to more than two hundred evaluation criteria, ranging from simple representations of agent demographic and performance characteristics, to more richly defined instantiations of behavioral attributes, interaction with non-agent entities, model flexibility, communication channels, simulation types, knowledge, transactive memory, task complexity, and resource networks. Our survey assesses trends across the wide set of criteria, discusses practical applications, and proposes an agenda for future research and development. Michael J. Ashworth is a doctoral candidate in computational organization science at Carnegie Mellon University, where he conducts research on social, knowledge, and transactive memory networks along with their effects on group and organizational learning and performance. Practical outcomes of his work include improved understanding of the impact of technology, offshoring, and turnover on organizational performance. Mr. Ashworth has won several prestigious grants from the Sloan Foundation and the National Science Foundation to pursue his research on transactive memory networks. Journals in which his research has appeared include Journal of Mathematical Sociology, International Journal of Human Resource Management, and Proceedings of the International Conference on Information Systems. His recent work on managing human resource challenges in the electric power industry has been featured in the Wall Street Journal and on National Public Radio's ``Morning Edition.' Mr. Ashworth received his undergraduate degree in systems engineering from the Georgia Institute of Technology. Kathleen M. Carley is a professor at the Institute for Software Research International in the School of Computer Science at Carnegie Mellon University. She is the director of the center for Computational Analysis of Social and Organizational Systems (CASOS), a university-wide interdisciplinary center that brings together network analysis, computer science and organization science (www.casos.ece.cmu.edu). Prof. Carley carries out research that combines cognitive science, dynamic social networks, text processing, organizations, social and computer science in a variety of theoretical and applied venues. Her specific research areas are computational social and organization theory; dynamic social networks; multi-agent network models; group, organizational, and social adaptation, and evolution; statistical models for dynamic network analysis and evolution, computational text analysis, and the impact of telecommunication technologies on communication and information diffusion within and among groups. Prof. Carley has undergraduate degrees in economics and political science from MIT and a doctorate in sociology from Harvard University.     

Motion synchronization in unmanned aircrafts formation control with communication delays

This paper proposes a formation control strategy for unmanned aircrafts using a virtual structure. Cross coupled sliding mode controllers are introduced to cope with uncertainties in the attitude measurement systems of the unmanned aircrafts and unmeasurable bounded external disturbances such as wind effects, and also to provide motion synchronization in the multi-agent system. This motion synchronization strategy improves the agents convergence to their desired positions, and this is useful for a multi-agent system with faulty agents.Moreover, the proposed motion synchronization strategy is not restricted to specific communication topologies, and sufficient conditions are provided to guarantee the multi-agent system stability in the presence of communication delays. Numerical simulations are presented for a team of five unmanned aircrafts to make a pentagon formation and confirm the accepted performance of the proposed control strategy.     

基于马尔科夫拓扑切换和随机通信干扰的连续时间多自主体系统的趋同控制

研究了基于不可靠通信网络的连续时间多自主体系统的趋同控制.自主体间的通信信道受高斯噪声干扰;不可靠通信因素导致的网络拓扑随机切换由马氏链刻画.为克服随机噪声和马尔科夫拓扑切换的影响,设计了随机逼近型趋同协议;基于马氏跳参数随机微分方程稳定性理论、代数图理论、连续鞅和马氏链理论,证明了多自主体系统实现渐近无偏均方平均趋同...     

Consensus of heterogeneous multi-agent systems with linear and nonlinear dynamics

In this paper, we perform an in-depth study about the consensus problem of heterogeneous multi-agent systems with linear and nonlinear dynamics.Specifically, this system is composed of two classes of agents respectively described by linear and nonlinear dynamics. By the aid of the adaptive method and Lyapunov stability theory, the mean consensus problem is realized in the framework of first-order case and second-order case under undirected and connected networks.Still, an meaningful example is provided to verify the effectiveness of the gained theoretical results. Our study is expected to establish a more realistic model and provide a better understanding of consensus problem in the multi-agent system.     

Dynamically stable control of articulated crowds

The synthesis of realistic complex body movements in real-time is a difficult problem in computer graphics and in robotics. High realism requires the accurate modeling of the details of the trajectories for a large number of degrees of freedom. At the same time, real-time animation necessitates flexible systems that can adapt and react in an online fashion to changing external constraints. Such behaviors can be modeled with nonlinear dynamical systems in combination with appropriate learning methods. The resulting mathematical models have manageable mathematical complexity, allowing to study and design the dynamics of multi-agent systems. We introduce Contraction Theory as a tool to treat the stability properties of such highly nonlinear systems. For a number of scenarios we derive conditions that guarantee the global stability and minimal convergence rates for the formation of coordinated behaviors of crowds. In this way we suggest a new approach for the analysis and design of stable collective behaviors in crowd simulation.     

基于事件触发策略的多智能体系统的最优主-从一致性分析

研究了具有领导者的线性多智能体系统的主 从一致性问题.借助各智能体间的通讯拓扑所构成的无向图,提出一种基于事件触发的自适应动态规划方法,并使用神经网络的逼近性质设计出了近似最优控制.利用Lyapunov稳定性定理,分析了多智能体误差系统的稳定性,并找到一个该误差系统最终有界的充分条件.数值仿真结果进一步验证了理论分析的有效性.