Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems

Joshua Holder, Natasha Jaques, Mehran Mesbahi · 2024

Read Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems by Joshua Holder, Natasha Jaques, Mehran Mesbahi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15573.txt.

Introduction

Joshua Holder, Natasha Jaques, and Mehran Mesbahi teach a team of agents to hand out tasks over time, in a setting drawn from satellite fleets. A single hand-out can be solved fast by known methods, but in real fleets the worth of a match shifts with the state of the whole system.

Their method learns from a known greedy solver first, then from more trial and error. Choices are made by a shared optimal hand-out step, not picked one by one. The authors say the design is backed by theory and dodges traps that snare other learning methods. It beat past methods, even with hundreds of agents.

Catalog record

CREATORJoshua Holder, Natasha Jaques, Mehran Mesbahi
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15573

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems Joshua Holder, Natasha Jaques, Mehran Mesbahi Abstract 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. 1 Department of Aeronautics and Astronautics, University of Washington, Seattle, WA 98195 2 Department of Computer Science, University of Washington, Seattle, WA 98195 [email protected], [email protected], [email protected] Code — https://github.com/Rainlabuw/rl-enabled-distributed-assignment Introduction Large-scale distributed systems like the power grid, transportation networks like Uber and Lyft, and satellite internet constellations are increasingly integrated in and critical to every aspect of our day-to-day lives, and will only become more so as time goes on. We can model these systems as a large group of agents working together to achieve broader goals - individual batteries and power plants working to satisfy grid-wide demand ( Giovanelli et al. 2019 ) , requested rides being distributed between cars ( Qin, Zhu, and Ye 2022 ) , or satellites working together to provide internet across the Earth ( Lin et al. 2022 ) . In order to operate these systems efficiently, it is often necessarily to solve optimization problems at a massive scale. Given n agents and m tasks, one of the most natural optimization questions to ask is “How can agents be optimally assigned to tasks?” While we will see later that the simplest version of this question admits efficient solutions, most realistic problems are more complex. Specifically, in real systems, assignments must be made repeatedly rather than at a single instant. Furthermore, these problems are often state dependent - when an assignment is made, the state of the system changes, which affects the value of future assignments (i.e. a satellite has to change its orientation to complete a task). These more complex problems are often NP-hard ( Gerkey and Matarić 2004 ) and thus difficult to approach with classical methods. The temporal nature of this problem suggests that sequential decision-making techniques like reinforcement learning (RL) may be an attractive solution. However, as the number of agents in the environment grows, so too does the complexity of solving the problem with a centralized algorithm ( Albrecht, Christianos, and Schäfer 2024 ) . For this reason, we look to multi-agent reinforcement learning (MARL) to enable our solution to scale up to the massive problem size required in realistic problem domains. Naive application of MARL is difficult for several reasons; rewards must be specified such that cooperation on the global objective is guaranteed, and actions taken by individual MARL agents must attempt to satisfy the constraint that each agent is assigned to a unique task (i.e. to avoid conflicting assignments). Figure 1: Architecture of REDA. 1) Calculate independent estimates of future utility for each agent, combine into a matrix. 2) Select joint assignment x_{k}=\alpha(\mathbf{Q}_{k}^{\pi}) which maximizes social utility, not utility for any given agent. 3) Execute x_{k} in environment and observe results. 4) Train agents’ independent value estimates based on minibatch from replay buffer. In this work, we present a novel, theoretically justified algorithm that addresses both of these challenges. Rather than having agents learn to assign themselves to tasks directly, we have each agent learn the expected value of an assignment, and use these learned values as the input to an optimal distributed task assignment mechanism. This allows agents to execute joint assignments that satisfy assignment constraints and avoid selfishness, while learning a joint policy which is near-optimal on the level of the entire system. This architecture is depicted in Figure 1 . While prior work has used MARL in a similar fashion to address assignment problems, this work often focused on variants of the problem specific to ride-sharing ( Shah, Lowalekar, and Varakantham 2020 ; Azagirre et al. 2024 ) . Throughout this work, we will take a far more general approach, and focus instead on satellite internet constellations as a novel motivating example (i.e. agents are satellites, and tasks are regions on Earth to provide internet to). This is a compelling application for a few reasons. First, satellite assignment problems are uniquely complex in that orbital mechanics dictates that a satellite cannot accomplish the same task indefinitely, and thus that frequent transitions between tasks must be considered. Second, these systems have exploded in size in just a few years to contain thousands of agents, with few existing algorithms which can provide the high degree of autonomy, efficiency, and resilience required in this environment. Finally, these systems are incredibly expensive, with the marginal cost of a satellite approaching \$500 , 000 . If more efficient planning enables reducing the size of the constellation by even a few satellites out of thousands, it could save tens of millions of dollars. As such, we apply our algorithm to a highly realistic satellite constellation management scenario, complete with high-fidelity orbital mechanics and hundreds of satellites and tasks, a scale which is extremely uncommon among non-heuristic approaches in the literature ( Wang et al. 2021 ) . Despite this, we find that our approach outperforms other state-of-the-art approaches by 20-50\% across both multi-agent reinforcement learning (COMA ( Foerster et al. 2018 ) , IQL ( Matignon, Laurent, and Le Fort-Piat 2012 ) , IPPO ( De Witt et al. 2020 ) ) and classical optimization (HAAL, ( Holder, Kraisler, and Mesbahi 2024 ) ). In summary, the contributions of this paper are: • A MARL approach for assignment problems which seamlessly integrates existing greedy planners into MARL, but improves upon their solution for better long-term planning. • Novel insight into the workings of the method through simple experiments, direct comparison with state-of-the-art RL methods, and theoretical analysis that provides intuition on global convergence properties. • Empirical results on a real satellite assignment problem that show a vastly improved ability to manage long-term resource constraints even when planning in complex environments with hundreds of satellites and tasks. Technical Preliminaries Mathematically, we can formulate the simplest version of an assignment problem with n agents and m tasks as: \alpha(\beta)=\underset{x\in X}{\argmax}\ \sum_{i=1}^{n}\sum_{j=1}^{m}\beta_{ij}x_{ij} (1) where: • \beta\in\mathbb{R}^{n\times m} is the benefit matrix , where \beta_{ij} corresponds to the utility of agent i completing task j . • x\in X\subset\{0,1\}^{n\times m} is the assignment matrix , where x_{ij}=1 if agent i is assigned to task j , and x_{ij}=0 otherwise. • X:=\{x\in\{0,1\}^{n\times m}\ |\

Read the complete text