A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation

• URL: http://arxiv.org/abs/2502.10226v1
• Date: Fri, 14 Feb 2025 15:21:27 GMT
• Title: A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation
• Authors: Redha Taguelmimt, Samir Aknine, Djamila Boukredera, Narayan Changder, Tuomas Sandholm,
• Abstract summary: Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
• Score: 61.08720171136229
• License:
• Abstract: 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.

Related papers

• Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems [5.896440476510869]
  Assignment problems are a classic optimization problem in which a group of agents is assigned to a group of tasks. In many modern-day applications such as satellite, power grids, and mobile robot scheduling, assignment problems unfold over time. We apply multi-agent reinforcement learning to this problem, learning the value of assignments by bootstrapping from a known RL-time greedy solver. We demonstrate that our algorithm is theoretically justified and avoids pitfalls experienced by other algorithms in this setting.
  arXiv  Detail & Related papers  (2024-12-20T05:10:34Z)
• Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks [60.085771314013044]
  Low-altitude economy holds significant potential for development in areas such as communication and sensing. We propose a Clustering-based Multi-agent Deep Deterministic Policy Gradient (CMADDPG) algorithm to address the multi-UAV cooperative task scheduling challenges in SAGIN.
  arXiv  Detail & Related papers  (2024-12-14T06:17:33Z)
• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  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. Our techniques bring a new way of approaching the problem and a new level of precision to the field.
  arXiv  Detail & Related papers  (2024-07-22T23:24:03Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  State-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS) We revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case.
  arXiv  Detail & Related papers  (2021-04-18T07:46:28Z)
• Scalable Anytime Planning for Multi-Agent MDPs [37.69939216970677]
  We present a scalable tree search planning algorithm for large multi-agent sequential decision problems that require dynamic collaboration. Our algorithm comprises three elements: online planning with Monte Carlo Tree Search (MCTS), factored representations of local agent interactions with coordination graphs, and the iterative Max-Plus method for joint action selection.
  arXiv  Detail & Related papers  (2021-01-12T22:50:17Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits [15.609414012418043]
  Cooperative multi-agent decision making involves a group of agents cooperatively solving learning problems while communicating over a network with delays. We consider the kernelised contextual bandit problem, where the reward obtained by an agent is an arbitrary linear function of the contexts' images in the related kernel reproducing Hilbert space (RKHS) We propose textscCoop- KernelUCB, an algorithm that provides near-optimal bounds on the per-agent regret.
  arXiv  Detail & Related papers  (2020-08-14T07:37:44Z)
• A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
  This paper is the conception and implementation of a multi-agent system that is applicable in various problem domains. We simulate a NP-hard scheduling problem to demonstrate the validity of our approach. This paper highlights the advantages of the agent-based approach, like the reduction in layout complexity, improved control of complicated systems, and extendability.
  arXiv  Detail & Related papers  (2020-04-20T14:04:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.