提出高效算法求解大规模联盟结构生成问题。
A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation
- 基于联盟结构图的多智能体路径搜索，结合多种启发式策略。
- 可在数百至数千智能体场景下快速找到高质量解。
- 适合需快速决策的运输与灾备等实时应用。
联盟结构生成（CSG）是多智能体系统中的基础计算问题，旨在将一组智能体最优划分为联盟以最大化社会福利。该问题在运输、灾后响应等需要快速求解的应用中至关重要。本文提出SALDAE算法，一种基于联盟结构图的多智能体路径搜索方法，融合多种启发式与策略进行搜索引导。该算法为任意时间算法，可处理包含数百至数千智能体的大规模问题。在九种标准价值分布（包括灾备和电动汽车分配基准）上的实验表明，SALDAE能快速获得高质量解，性能优于现有主流方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。