An official website of the United States government
Coalition structure generation (CSG) is a critical problem in multiagent systems, involving the optimal partitioning of agents into disjoint coalitions to maximize social welfare. This paper introduces SALDAE, a novel multiagent path finding algorithm for CSG on a coalition structure graph. SALDAE employs various heuristics and strategies for efficient search, making it an anytime algorithm suitable for handling large-scale problems
more »
« less
Efficient Size-based Hybrid Algorithm for Optimal Coalition Structure Generation
Coalition Structure Generation (CSG) involves dividing agents into coalitions in such a way as to coordinate them into solving problems together efficiently. In this paper, we revisit the CSG problem and propose a new search method that introduces an offline phase to speed up the search process, where the best coalition sets to search are preprocessed. These sets are calculated only once regardless of the coalition values and can be reused each time a CSG instance is to be solved. Then our search in the online phase combines dynamic programming with integer partition-based search in a novel way.
more »
« less
- Award ID(s):
- 1901403
- PAR ID:
- 10549983
- Publisher / Repository:
- AAMAS24
- Date Published:
- Format(s):
- Medium: X
- Location:
- Auckland, New Zealand
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Coalition structure generation (CSG), i.e. the problem of optimally partitioning a set of agents into coalitions to maximize social welfare, is a fundamental computational problem in multiagent systems. This problem is important for many applications where small run times are necessary, including transportation and disaster response. In this paper, we develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures. Our algorithm utilizes a variety of heuristics and strategies to perform the search and guide it. It is an anytime algorithm that can handle large problems with hundreds and thousands of agents. We show empirically on nine standard value distributions, including disaster response and electric vehicle allocation benchmarks, that our algorithm enables a rapid finding of high-quality solutions and compares favorably with other state-of-the-art methods.more » « less
-
Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based SearchCoalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions.more » « less
-
Shapley value provides a unique way to fairly assess each player's contribution in a coalition and has enjoyed many applications. However, the exact computation of Shapley value is #P-hard due to the combinatoric nature of Shapley value. Many existing applications of Shapley value are based on Monte-Carlo approximation, which requires a large number of samples and the assessment of utility on many coalitions to reach high quality approximation, and thus is still far from being efficient. Can we achieve an efficient approximation of Shapley value by smartly obtaining samples? In this paper, we treat the sampling approach to Shapley value approximation as a stratified sampling problem. Our main technical contributions are a novel stratification design and two sample allocation methods based on Neyman allocation and empirical Bernstein bound, respectively. Experimental results on several real data sets and synthetic data sets demonstrate the effectiveness and efficiency of our novel stratification design and sampling approaches.more » « less
-
null (Ed.)Articulation, emotion, and personality play strong roles in the orofacial movements. To improve the naturalness and expressiveness of virtual agents(VAs), it is important that we carefully model the complex interplay between these factors. This paper proposes a conditional generative adversarial network, called conditional sequential GAN(CSG), which learns the relationship between emotion, lexical content and lip movements in a principled manner. This model uses a set of spectral and emotional speech features directly extracted from the speech signal as conditioning inputs, generating realistic movements. A key feature of the approach is that it is a speech-driven framework that does not require transcripts. Our experiments show the superiority of this model over three state-of-the-art baselines in terms of objective and subjective evaluations. When the target emotion is known, we propose to create emotionally dependent models by either adapting the base model with the target emotional data (CSG-Emo-Adapted), or adding emotional conditions as the input of the model(CSG-Emo-Aware). Objective evaluations of these models show improvements for the CSG-Emo-Adapted compared with the CSG model, as the trajectory sequences are closer to the original sequences. Subjective evaluations show significantly better results for this model compared with the CSG model when the target emotion is happiness.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
