Formations are often seen in nature, and bring many benefits for the group as a whole. They can allow a group to explore a large area more effectively, can ease movement of the group through the environment, and can increase group perceptual coverage and increase defensive capabilities, for example. The benefits of any particular formation vary and are obtained from the structure the formation provides. Robotic formations can have similar applications. To date, the techniques used and formations employed in robotic applications are significantly simpler than those seen in nature. Current techniques often require some level of global knowledge, central processing or other unrealistic assumptions. We seek to develop a formation control technique that has as few of these limitations as possible. Each agent under our approach has only local knowledge of the environment, uses no broadcast communication, and can communicate only over a limited range. Formations are achieved by organizing agents into a graph structure, where agents occupying the vertices take on the role of maintaining an appropriate number of agents on each edge, thus preserving the formation's shape and scale. We do not assume a known or static population: the evolving formation acts as a physical data structure to assist in placing and rearranging agents as the population changes. This approach does not require a global coordinate system, fixed positions within the formation, or any single lead agent. All agents within our approach are peers, and any can adopt any role within the formation.

If computational social science is to find practical application in informing policy decisions and proportionately analyzing courses of action, then it will have to make progress in the area of composition of social models.  Since a single simulation cannot hold a world of information, policy makers need to switch in and out modules in federations of simulations to test policies against all possible social environments.  Voting processes as they occur in nature, both in the form of cognition in a human mind of disparate world views, and in the form of equilibria seeking coevolution of species, inform how to combine model results externally and deeply, respectively.  These algorithms, which use the same principles of soft computation found in nature, enable any models to mesh together, even if they have different ontologies, or their data conflict, regardless of the degree they overlap.  A whiteboard architecture in which models report in their own ontologies how other models may inform them and what they have to offer other models, is a framework for the arbitrary meshing of social models.

Many approaches have been introduced for representing and solving multiagent coordination problems. Unfortunately, these methods make assumptions that limit their usefulness when combined with human operators and real-life hardware and software. In this paper, we discuss the problem of using agents in conjunction with human operators to improve coordination as well as possible models that could be used in these problems. Our approach — Space Collaboration via an Agent Network (SCAN) — enables proxy agents to represent each of the stakeholder agencies in a space setting and shows how the SCAN agent network could facilitate collaboration by identifying opportunities and methods of collaboration. We discuss this approach as well as the challenges in extending models to 1) take advantage of human input, 2) deal with the limited and uncertain information that will be present and 3) combat the scalability issues in solution methods for a large number of decentralized agents. As a first step toward providing rich models for these domains, we describe a method to bound the solution quality due to bounded model uncertainty.

In Artificial Intelligence with Coalition Structure Generation (CSG) one refers to those cooperative complex problems that require to find an optimal partition, maximising a social welfare, of a set of entities involved in a system into exhaustive and disjoint coalitions. The solution of the CSG problem finds applications in many fields such as Machine Learning (covering machines, clustering), Data Mining (decision tree, discretization), Graph Theory, Natural Language Processing (aggregation), Semantic Web (service composition), and Bioinformatics. The problem of finding the optimal coalition structure is NP-complete. In this paper we present a greedy adaptive search procedure (GRASP) with path-relinking to efficiently search the space of coalition structures. Experiments and comparisons to other algorithms prove the validity of the proposed method in solving this hard combinatorial problem.

Despite the increasing diffusion of the Internet technology, TV remains the principal medium of communication. People's perceptions, knowledge, beliefs and opinions about matter of facts get (in)formed through the information reported on by the mass-media. However, a single source of information (and consensus) could be a potential cause of anomalies in the structure and evolution of a society. Hence, as the information available (and the way it is reported) is fundamental for our perceptions and opinions, the definition of conditions allowing for a good information to be disseminated is a pressing challenge. In this paper starting from a report on the last Italian political campaign in 2008, we derive a socio-cognitive computational model of opinion dynamics where agents get informed by different sources of information. Then, a what-if analysis, performed trough simulations on the model's parameters space, is shown. In particular, the scenario implemented includes three main streams of information acquisition, differing in both the contents and the perceived reliability of the messages spread. Agents' internal opinion is updated either by accessing one of the information sources, namely media and experts, or by exchanging information with one another. They are also endowed with cognitive mechanisms to accept, reject or partially consider the acquired information.

We propose a simple model of network co-evolution in a game-dynamical system of interacting agents that play repeated games with their neighbors, and adapt their behaviors and network links based on the outcome of those games. The adaptation is achieved through a simple reinforcement learning scheme. We show that the collective evolution of such a system can be described by appropriately defined replicator dynamics equations. In particular, we suggest an appropriate factorization of the agents strategies thats results in a coupled system of equations characterizing the evolution of both strategies and network structure, and illustrate the framework on two simple examples.

This paper describes Maryland Virtual Patient (MVP), a simulation and tutoring environment developed to support training cognitive decision making in clinical medicine. MVP is implemented as a society of agents, with one role – that of the trainee – played by a human and other roles played by artificial intelligent agents. In order to make the trainee’s experience as similar as possible to the traditional medical training environment, MVP is implemented as a collection of knowledge-based models of simulated human-like perception, reasoning and action processes. MVP operation involves metacognition: for example, the MVP virtual patient is aware of the physiological state of its body, of its physiological and character traits as well as of lacunae in its knowledge about the world and about language. This self-awareness influences the virtual patient’s reasoning and actions. In this paper we illustrate the role of metacognitive self-awareness in the overall operation of MVP.

We intend to develop auction-like algorithms for the allocation It is often important to coordinate teams of cooperative of complex tasks, similar to SSI auctions for the allocation agents in a distributed manner. We study how to assign of simple tasks. SSI auctions assign simple tasks to tasks to cooperative agents so that the resulting team cost agents in multiple rounds. In each round, each agent bids on is small (that is, team performance is high). Market-based each unassigned task the minimal increase in its agent cost mechanisms are promising distributed task-allocation methods. in case it has to perform this task in addition to all tasks already Robotics researchers have recently studied how to use assigned to it in previous rounds.

Coalition formation is a fundamental problem in multi-agent systems. In characteristic function games (CFGs), each coalition C of agents is assigned a value indicating the joint utility those agents will receive if C is formed. CFGs are an important class of cooperative games; however, determining the optimal coalition structure, partitioning of the agents into a set of coalitions that maximizes the social welfare, currently requires O (3 n ) time for n agents. In light of the high computational complexity of the coalition structure generation problem, a natural approach is to relax the optimality requirement and attempt to find an approximate solution that is guaranteed to be close to optimal. Unfortunately, it has been shown that guaranteeing a solution within any factor of the optimal requires Ω(2 n ) time. Thus, the best that can be hoped for is to find an algorithm that returns solutions that are guaranteed to be as close to the optimal as possible, in as close to O (2 n ) time as possible. This paper contributes to the state-of-the-art by presenting an algorithm that achieves better quality guarantees with lower worst case running times than all currently existing algorithms. Our approach is also the first algorithm to guarantee a constant factor approximation ratio, 1/8, in the optimal time of O (2 n . The previous best ratio obtainable in O (2 n ) was 2/ n .

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a Coalition Structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might assume that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve n-th power of 2 DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w*+1), 2k/n) of the optimal CS, where w* is the tree width of a constraint graph. When k=1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.