The paper considers a class of multi-agent Markov decision processes (MDPs), in which the network agents respond differently (as manifested by the instantaneous one-stage random costs) to a global controlled state and the control actions of a remote controller. The paper investigates a distributed reinforcement learning setup with no prior information on the global state transition and local agent cost statistics. Specifically, with the agents' objective consisting of minimizing a network-averaged infinite horizon discounted cost, the paper proposes a distributed version of $Q$-learning, $\mathcal{QD}$-learning, in which the network agents collaborate by means of local processing and mutual information exchange over a sparse (possibly stochastic) communication network to achieve the network goal. Under the assumption that each agent is only aware of its local online cost data and the inter-agent communication network is \emph{weakly} connected, the proposed distributed scheme is almost surely (a.s.) shown to yield asymptotically the desired value function and the optimal stationary control policy at each network agent. The analytical techniques developed in the paper to address the mixed time-scale stochastic dynamics of the \emph{consensus + innovations} form, which arise as a result of the proposed interactive distributed scheme, are of independent interest.

We give the analysis of the computational complexity of coalition structure generation over graphs. Given an undirected graph G = (N,E) and a valuation function v : P(N) → R over the subsets of nodes, the problem is to find a partition of N into connected subsets, that maximises the sum of the components values. This problem is generally NPcomplete; in particular, it is hard for a defined class of valuation functions which are independent of disconnected membersthat is, two nodes have no effect on each others marginal con- tribution to their vertex separator. Nonetheless, for all such functions we provide bounds on the complexity of coalition structure generation over general and minorfree graphs. Our proof is constructive and yields algorithms for solving corresponding instances of the problem. Furthermore, we derive linear time bounds for graphs of bounded treewidth. However, as we show, the problem remains NPcomplete for planar graphs, and hence, for any K_k minorfree graphs where k ≥ 5. Moreover, a 3-SAT problem with m clauses can be represented by a coalition structure generation problem over a planar graph with O(m^2) nodes. Importantly, our hardness result holds for a particular subclass of valuation functions, termed edge sum, where the value of each subset of nodes is simply determined by the sum of given weights of the edges in the induced subgraph.

This paper presents a scalable Bayesian technique for decentralized state estimation from multiple platforms in dynamic environments. As has long been recognized, centralized architectures impose severe scaling limitations for distributed systems due to the enormous communication overheads. We propose a strictly decentralized approach in which only nearby platforms exchange information. They do so through an interactive communication protocol aimed at maximizing information flow. Our approach is evaluated in the context of a distributed surveillance scenario that arises in a robotic system for playing the game of laser tag. Our results, both from simulation and using physical robots, illustrate an unprecedented scaling capability to large teams of vehicles.

Ten Years of AAMAS: Introduction to the Special Issue

We present a brief survey of logics for reasoning about multiagent systems. We focus on two paradigms: logics for cognitive models of agency, and logics used to model the strategic structure of a multiagent system.

This article gives an introduction to agent-based modeling and simulation (ABMS). After a general discussion about modeling and simulation, we address the basic concept of ABMS, focusing on its generative and bottom-up nature, its advantages as well as its pitfalls. The subsequent part of the article deals with application-oriented aspects, including selected tools and well-known applications. In order to illustrate the benefits of using ABMS, we focus on several aspects of a well-known area related to simulation of complex systems, namely traffic.

Multiagent systems (MAS) are widely accepted as an important method for solving problems of a distributed nature. A key to the success of MAS is efficient and effective multiagent learning (MAL). The past twenty-five years have seen a great interest and tremendous progress in the field of MAL. This article introduces and overviews this field by presenting its fundamentals, sketching its historical development and describing some key algorithms for MAL.

Robots (and roboticists) increasingly appear at the Autonomous Agents and Multi-Agent Systems (AAMAS) conferences because the community uses robots both to inspire AAMAS research as well as to conduct it. In this article, I submit that the growing success of robotics at AAMAS is due not only to the nurturing efforts of the AAMAS community, but mainly to the increasing recognition of an important, deeper, truth: it is scientifically useful to roboticists and agent researchers to think of robots as agents.

A key feature of the AAMAS conference is its emphasis on ties to real-world applications. The focus of this article is to provide a broad overview of application-focused papers published at the AAMAS 2010 and 2011 conferences. More specifically, recent applications at AAMAS could be broadly categorized as belonging to research areas of security, sustainability and safety. We outline the domains of applications, key research thrusts underlying each such application area, and emerging trends.

He has been chairman/president the MIT Artificial Intelligence Lab. Board of Trustees, as well as treasurer 100 Americans most likely to shape Manuela Veloso, incoming AAAI President, of SSAISB and ECCAI. He is presently the next century; TIME Digital selected and Eric Horvitz, AAAI Past editor-in-chief of the AAAI Press, Spatial her as a member of the Cyber-Elite; President and Awards Committee Cognition and Computation, and the World Economic Forum honored Chair, presented the AAAI Awards in the Artificial Intelligence Journal. He was her with the title Global Leader for Tomorrow; August at AAAI-12 in Toronto. She holds bachelor's and or 1-650-328-3123.)