International audience

In this paper, we propose a novel algorithm to address the Coalition Structure Generation (CSG) problem. Specifically, we use a novel representation of the search space that enables it to be explored in a new way. We introduce an index-based exact algorithm. Our algorithm is anytime, produces optimal solutions, and can be run on large-scale problems with hundreds of agents. Our experimental evaluation on a benchmark with several value distributions shows that our representation of the search space that we combined with the proposed algorithm provides high-quality results for the CSG problem and outperforms existing state-of-the-art algorithms.

Organizing agents into disjoint groups is a crucial challenge in artificial intelligence, with many applications where quick runtime is essential. The Simultaneous Coalition Structure Generation and Assignment (SCSGA) problem involves partitioning a set of agents into coalitions and assigning each coalition to a task, with the goal of maximizing social welfare. However, this is an NP-complete problem, and only a few algorithms have been proposed to address it for both small and large-scale problems. In this paper, we address this challenge by presenting a novel algorithm that can efficiently solve both small and large instances of this problem. Our method is based on a new search space representation, where each coalition is codified by an index. We have developed an algorithm that can explore this solution space effectively by generating index vectors that represent coalition structures. The resulting algorithm is anytime and can scale to large problems with hundreds or thousands of agents. We evaluated our algorithm on a range of value distributions and compared its performance against state-of-the-art algorithms. Our experimental results demonstrate that our algorithm outperforms existing methods in solving the SCSGA problem, providing high-quality solutions for a wide range of problem instances.

Coalition formation is a central approach for multiagent coordination. A crucial part of coalition formation that is extensively studied in AI is coalition structure generation: partitioning agents into coalitions to maximize overall value. In this paper, we propose a novel method for coalition structure generation by introducing a compact and efficient representation of coalition structures. Our representation partitions the solution space into smaller, more manageable subspaces that gather structures containing coalitions of specific sizes. Our proposed method combines two new algorithms, one which leverages our compact representation and a branch-and-bound technique to generate optimal coalition structures, and another that utilizes a preprocessing phase to identify the most promising sets of coalitions to evaluate. Additionally, we show how parts of the solution space can be gathered into groups to avoid their redundant evaluation and we investigate the computational gain that is achieved by avoiding that redundant processing. Through this approach, our algorithm is able to prune the solution space more efficiently. Our results show that the proposed algorithm is superior to prior state-of-the-art methods in generating optimal coalition structures under several value distributions.

Coalition Formation (CF) aims at finding the opti-mal coalition structure that maximizes social welfare. However, the search space of coalition structures is often too large to be fully explored. In this paper, we propose a novel algorithm to address the Coalition Structure Generation (CSG) problem. Specifically, we use a novel representation of the search space that enables it to be explored in a new way. We introduce an index-based exact algorithm. Our algorithm is anytime, produces optimal solutions, and can be run on large-scale problems with hundreds of agents. Our experimental evaluation on a benchmark with several value distributions and an electric vehicle allocation problem shows that our representation of the search space that we combined with the proposed algorithm provides high-quality results for the CSG problem and outperforms existing state-of-the-art algorlthms.

Coalition structure generation, i.e., the problem of optimally partitioning a set of agents into disjoint exhaustive coalitions to maximize social welfare, is a fundamental computational problem in multi-agent systems. In this paper, we provide a new algorithm for optimal coalition structure generation. We analyze how parts of the solution space can be searched individually with guarantees of fully searching them. We introduce a new algorithm that searches the entire solution space using dynamic programming with a branch-and-bound technique both focused on solution subspaces. With experiments over several common value distributions, we show that dividing the search process enables our algorithm to rapidly search the solution subspaces and outperform current state-of-the-art for several value distributions.

In this paper, we propose a new algorithm for the Coalition Structure Generation (CSG) problem that can be run with more than 28 agents while using a complete set of coalitions as input. The current state-of-the-art limit for exact algorithms to solve the CSG problem within a reasonable time is 27 agents. Our algorithm uses a novel representation of the search space and a new code-based search technique. We propose an effective heuristic search method to efficiently explore the space of coalition structures using our code based technique and show that our method outperforms existing state-of-the-art algorithms by multiple orders of magnitude.

Finding the optimal coalition structure is an NP-complete problem that is computationally challenging even under quite restrictive assumptions. In this paper, we propose a new algorithm for the Coalition Structure Generation (CSG) problem, which provides good enough quality solutions and that can be run with hundreds of agents. The Fast code-based Algorithm for Coalition Structure generation (FACS) uses a novel representation of the search space of coalition structures and a new code-based search technique. We devise an effective heuristic search method to efficiently explore the space of coalition structures using our code-based technique. Results show that our method outperforms existing state-of-the-art algorithms by multiple orders of magnitude while providing high-quality solutions.

Contract Net Protocol (CNP) is probably the most widely used task allocation protocol in distributed multi-agent systems (MAS). To cope with real-world applications, this protocol must be expanded by addressing some major challenging issues in the current distributed systems. Temporal interaction aspects and reliability issues of such systems, critical to guaranteeing performance, are the focus of this paper. Many researchers have proposed various methods to expand and to improve CNP but those challenges have not been much addressed in a formal way. To cope with these limitations, this paper proposes a Petri net-based model that extends the conventional contract net with real time constraints, often defined as interaction duration and message deadlines, and fault tolerance to handle the agent death exception. Our aim is, hence, to devise an extended CNP that achieves the reliability of the manager agent in the case of contractor crash failure while operating in an open and large scale multi-agent system under time constraints. To address the challenge problem of crash failure detection of the contractor in CNP, we propose to formally model the watchdog/heartbeat mechanism into the communication between the manager and the contractor. Using such mechanism, the manager can detect the crash failure on time and may hence trigger an appropriate recovery procedure to move the system into a safe and a consistent state. The proposed extended CNP model is developed using stochastic timed colored Petri nets which include systematic specification, design and implementation of components of the system. Various useful results will be drawn by simulation as well as state space analysis. This formal analysis shows that the protocol terminates correctly either in a safety case or in a failure situation. It also proves that the protocol meets the key properties namely model correctness, deadline respect, absence of deadlocks and livelocks, absence of dead code, agent terminal states consistency, concurrency, and validity.