Forming effective coalition is a central research challenge in AI and multi-agent systems. The Coalition Structure Generation (CSG) problem is well-known as one of major research topics in coalitional games. The CSG problem is to partition a set of agents into coalitions so that the sum of utilities is maximized. This paper studies a CSG problem for partition function games (PFGs), where the value of a coalition differs depending on the formation of other coalitions generated by non-member agents. Traditionally, in PFGs, the input of a coalitional game is a black-box function called a partition function that maps an embedded coalition (a coalition and the coalition structure) to its value. Recently, a novel concise representation scheme called the Partition Decision Trees (PDTs) has been proposed. The PDTs is a graphical representation based on multiple rules. In this paper, we propose new algorithms that can solve a CSG problem by utilizing PDTs representation. More specifically, we modify PDTs representation to effectively handle negative value rules and apply the depth-first branch and bound algorithm. We experimentally show that our algorithm can solve a CSG problem well.

We study the Stable Invitations Problem (SIP) in which an event organizer is to invite a subset of agents (from a group of agents) to an event, subject to certain rationality criteria. In SIP, the agents have friends, enemies, and preferences on the number of attendees at the event; an agent is willing to attend the event if all friends of the agent attend, no enemy of the agent attends, and the number of attendees is acceptable to the agent. We consider two solution concepts: (1) individual rationality (everyone who is invited is willing to attend) and (2) (Nash) stability (no agent wants to deviate from the given invitation).It is known that finding an invitation of given size for either concept is NP-complete. In this work, we study the complexity of SIP on a finer scale, through the lense of parameterized complexity.For the two solution concepts and the special cases where the number of friends and/or enemies is bounded above by a constant, we show that the problems belong to different complexity classes when parameterized by the size of solutions.For instance finding an individually rational invitation of size k is W[1]-complete, yet finding a stable invitation is W[2]-complete.Moreover, when all friend and enemy relations are symmetric, finding a solution of either of the concepts becomes fixed-parameter tractable unless agents have unbounded number(s) of enemies.

We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. Pareto optimal solutions have been already considered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximizing the social welfare is NP-hard in bounded degree graphs, a 2 min{Delta,sqrt n}-approximating one can be determined in polynomial time, where n is the number of agents and Delta the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combinations: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.

Context-recognition and activity recognition systems in multi-user environments such as smart homes, usually assume to know the number of occupants in the environment. However, being able to count the number of users in the environment is important in order to accurately recognize the activities of (groups of) agents. For smart environments without cameras, the problem of counting the number of agents is non-trivial. This is in part due to the difficulty of using a single non-vision based sensors to discriminate between one or several persons, and thus information from several sensors must be combined in order to reason about the presence of several agents. In this paper we address the problem of counting the number of agents in a topologically known environment using simple sensors that can indicate anonymous human presence. To do so, we connect an ontology to a probabilistic model (a Hidden Markov Model) in order to estimate the number of agents in each section of the environment. We evaluate our methods on a smart home setup where a number of motion and pressure sensors are distributed in various rooms of the home.

The Teachable Agents Project combines research from computer science, psychology, and education to develop computer-based learning environments. These environments utilize animated pedagogical agents to facilitate science learning and the development of self-regulated learning skills. The use of animated agents allows us to extend the cognitive scaffolding provided by various computer tools and representations (e.g., searchable text, simulations, concept maps, etc.) by embedding them in productive and motivating social-constructive interactions (e.g., peer teaching, collaboration, and assessment). Current projects include Betty's Brain, a learning-by-teaching environment for science learning; CTSiM, an environment for understanding science through a computational thinking framework; SimSelf, a relatively new project that focuses on teaching students about self-regulation and metacognition in the context of science learning; and C3STEM, a community-situated, challenge-based, collaborative STEM learning environment. Our learning environments also include extensive logging of students' interactions with the system and agents.

Many tasks in AI require the collaboration of multiple agents. Typically, the communication protocol between agents is manually specified and not altered during training. In this paper we explore a simple neural model, called CommNet, that uses continuous communication for fully cooperative tasks. The model consists of multiple agents and the communication between them is learned alongside their policy. We apply this model to a diverse set of tasks, demonstrating the ability of the agents to learn to communicate amongst themselves, yielding improved performance over non-communicative agents and baselines. In some cases, it is possible to interpret the language devised by the agents, revealing simple but effective strategies for solving the task at hand.

Distributed constraint optimization problems enable the representation of many combinatorial problems that are distributed by nature. An important motivation for such problems is to preserve the privacy of the participating agents during the solving process. The present paper introduces a novel privacy-preserving branch and bound algorithm for this purpose. The proposed algorithm, P-SyncBB, preserves constraint, topology and decision privacy. The algorithm requires secure solutions to several multi-party computation problems. Consequently, appropriate novel secure protocols are devised and analyzed. An extensive experimental evaluation on different benchmarks, problem sizes, and constraint densities shows that P-SyncBB exhibits superior performance to other privacy-preserving complete DCOP algorithms.

Coalition formation typically involves the coming together of multiple, heterogeneous, agents to achieve both their individual and collective goals. In this paper, we focus on a special case of coalition formation known as Graph-Constrained Coalition Formation (GCCF) whereby a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network. We propose a novel representation of this problem based on the concept of edge contraction, which allows us to model the search space induced by the GCCF problem as a rooted tree. Then, we propose an anytime solution algorithm (CFSS), which is particularly efficient when applied to a general class of characteristic functions called $m+a$ functions. Moreover, we show how CFSS can be efficiently parallelised to solve GCCF using a non-redundant partition of the search space. We benchmark CFSS on both synthetic and realistic scenarios, using a real-world dataset consisting of the energy consumption of a large number of households in the UK. Our results show that, in the best case, the serial version of CFSS is 4 orders of magnitude faster than the state of the art, while the parallel version is 9.44 times faster than the serial version on a 12-core machine. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems of agents (i.e., with more than 2700 agents).

We propose a formal design framework to automatically synthesize coordination and control schemes for cooperative multi-agent systems by combining a top-down mission planning with a bottom-up motion planning. The multi-agent system is assigned a global mission, specified as regular languages over all the agents’ capabilities, whereas basic motion controllers for each agent shall be designed with respect to given environment description. On one hand, a mission planning layer sits on the top of the proposed framework, decomposing the global mission into local tasks that are in consistency with each agent’s individual capabilities, and compositionally verifying the joint effort of the agents via an assume guarantee paradigm. On the other hand, corresponding to these local missions, motion plans associated with each agent are synthesized by composing basic motion primitives, which are verified safe by differential dynamic logic (dL), through a Satisfiability Modulo Theories (SMT) solver that searches feasible solutions in face of constraints due to local task requirements and the environment description. It is shown that the proposed framework can handle changing environments as the motion primitives are reactive in nature, making the motion planning adaptive to local environmental changes. Furthermore, on-line mission reconfiguration can be triggered by the motion planning layer once no feasible solutions can be found through the SMT solver. The effectiveness of the overall design framework is demonstrated by an automated warehouse case study.