用多智能体强化学习解决动态卫星任务分配，效果优于现有方法。
Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems
- 结合贪心求解器与强化学习，通过经验迭代优化分配策略。
- 在数百个任务和智能体的场景下，性能显著优于已有方法。
- 适用于实时动态系统，如卫星星座、电网调度等复杂场景。
分配问题是经典的组合优化问题，需在满足约束条件下使总效用最大化。传统方法可在多项式时间内解决静态分配问题，但在现代应用中（如卫星星座、电网调度、移动机器人编排），分配随时间演变，效用高度依赖系统状态。本文采用多智能体强化学习，利用已知的多项式时间贪心求解器作为初始价值估计，并通过后续经验持续学习。采用分布式最优分配机制进行决策，而非直接选择动作。理论证明该方法有效规避了其他强化学习算法在此类问题中的常见陷阱。实验表明，该方法在真实规模场景（数百个智能体与任务）下显著优于现有方法。
原文摘要 · Abstract (English)
Assignment problems are a classic combinatorial optimization problem in which a group of agents must be assigned to a group of tasks such that maximum utility is achieved while satisfying assignment constraints. Given the utility of each agent completing each task, polynomial-time algorithms exist to solve a single assignment problem in its simplest form. However, in many modern-day applications such as satellite constellations, power grids, and mobile robot scheduling, assignment problems unfold over time, with the utility for a given assignment depending heavily on the state of the system. We apply multi-agent reinforcement learning to this problem, learning the value of assignments by bootstrapping from a known polynomial-time greedy solver and then learning from further experience. We then choose assignments using a distributed optimal assignment mechanism rather than by selecting them directly. We demonstrate that this algorithm is theoretically justified and avoids pitfalls experienced by other RL algorithms in this setting. Finally, we show that our algorithm significantly outperforms other methods in the literature, even while scaling to realistic scenarios with hundreds of agents and tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。