Decentralized, Decomposition-Based Observation Scheduling for a Large-Scale Satellite Constellation

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 00:35:25

Abstract: Deploying multi-satellite constellations for Earth observation requires coordinating potentially hundreds or thousands of spacecraft. Centralized approaches to observation scheduling rely on a single controller planning the actions of each satellite. With increasing on-board capability for autonomy, we can view the constellation as a multi-agent system (MAS) and employ decentralized scheduling solutions. We formulate the problem as a distributed constraint optimization problem (DCOP) and desire limited inter-agent communication. Due to the scale and structure of the problem, existing DCOP algorithms are inadequate for this application. We develop a scheduling approach that employs a well-coordinated heuristic to decompose the global DCOP into sub-problems as to enable the application of DCOP algorithms. Building on previous work, we present the Neighborhood Stochastic Search (NSS) algorithm, a decentralized algorithm to effectively solve the Earth observing multi-satellite constellation scheduling problem. In this paper, we identify the roadblocks of deploying DCOP solvers to a large-scale, real-world problem, propose a decomposition-based scheduling approach that is effective at tackling large scale DCOPs, empirically evaluate the approach against other baselines to demonstrate the effectiveness, and discuss the generality of the approach.

Main paper: 
 : 
 formulate the problem as a distributed constraint optimization problem (DCOP) and desire scalable inter-agent communication. The problem consists of millions of variables which, coupled with the structure, make existing DCOP algorithms inadequate for this application. We develop a scheduling approach that employs a well-coordinated heuristic, referred to as the Geometric Neighborhood Decomposition (GND) heuristic, to decompose the global DCOP into sub-problems as to enable the application of DCOP algorithms. We present the Neighborhood Stochastic Search (NSS) algorithm, a de-Large-scale, Earth observing satellite constellations with hundreds of spacecraft are becoming increasingly prominent in order to monitor Earth phenomena. Spire, Satellogic, Canon, SatRev, Spacety, Planet Lab's Dove, and SkySat are several examples (NewSpace 2023). Observation scheduling for a large-scale constellation requires fusing information from many sources and tasking space assets that have varying constraints, capabilities, and visibility of Earth targets. In addition to Earth observation, satellites are deployed for a variety of applications, including forming large internet constellations (SpaceX 2023). Any multi-satellite constellation that requires coordinating agents poses a challenging planning and scheduling problem.In practice, satellite observation scheduling is typically done in a centralized fashion, where a single controller develops a single schedule that specifies the actions of every 40 satellite (Shah et al. 2019) . Even most non-operational technology efforts are centralized (Boerkoel et al. 2021; Nag, Li, and Merrick 2018) . While centralized approaches can pro-vide high-quality solutions, reliance on a single computing source makes the approaches vulnerable to single point failures and can increase communications burden.Framing the constellation as a multi-agent system (MAS) enables the application of decentralized scheduling solutions. Decentralized scheduling addresses both the system's robustness and the vulnerabilities of a central controller (Bonnet and Tessier 2008; Phillips and Parra 2021) . Many MAS problems are framed to optimize a global cost function where individual agents control the parameters of the function. Typically, the agents in the system communicate to coordinate their parameter assignments.In many applications, communication may be unreliable for large message volume. For example, orbiters around a comet or the sun may experience communication interference or infrequent line of sight with each other. For an Earth orbiting constellation, satellites may have limited cross-link capability. For this reason, we desire algorithms that procure a limited amount of messaging. Formulating the problem as a distributed constraint optimization problem (DCOP), we aim to produce high quality scheduling solutions.The problem requires agents to coordinate the assignments of millions of variables and the desire for limited communication make the direct application of DCOP algorithms inadequate. However, by decomposing the global problem, we can deploy DCOP algorithms to solve smaller sub-problems. We construct a heuristic, called the Geometric Neighborhood Decomposition heuristic (GND), that partitions the agents and requests in a coordinated fashion as to instantiate sub-problems that are advantageous to solve. Each agent individually computes the heuristic using only knowledge of the requests to schedule and the configuration of the constellation. The heuristic is grounded in geometric computation and is composed of three layers that partition the agents and requests into sub-problems. The goal is for the constellation to maximize the number of requests satisfied, while adhering to downlinks and memory constraints.The heuristic is parameterized such that the sub-problems produced can be of arbitrary size. Through this decomposition, we can deploy DCOP algorithms on constant sized sub-problems rather than the global problem that scales with the number of agents and requests. To solve each sub-problem using communication, we build on the Broadcast Decentralized algorithm (BD) (Parjan and Chien 2023) , an adaptation of two incomplete DCOP algorithms, Maximum Gain Messaging (MGM) and Distributed Stochastic Search Algorithm (DSA) (Zhang et al. 2005) , for the application of multi-satellite observation scheduling. We refer to our developed algorithm as Neighborhood Stochastic Search (NSS). Our algorithm extends the BD algorithms in two major aspects: (1) it is scalable to large problem instances in both computational complexity and communication complexity, and (2) it enables constraint reasoning, such as resource constrained scheduling.Empirical results demonstrate the efficacy of our approach on small and large problem instances compared to decentralized and centralized baselines. On small problem 100 instances, we show the gap to optimal solutions, while large problem instances enforce the performance at scale, including run-time results. We aim to close the gap between decentralized solutions and centralized solutions while precluding an infeasible amount of messaging.Our contributions in this paper are hence:1. uncovering the obstacles in applying existing DCOP techniques to the large-scale, multi-satellite decentralized scheduling problem, 2. introducing a decomposition-based heuristic approach to 110 solve the scheduling problem and presenting the NSS algorithm, and 3. demonstrating the efficacy of our approach on realistic problem instances.There are many aspects of satellite observation planning ranging from visibility computation, to downlink scheduling, to constraint based task allocation. This paper is mostly concerned with the last subject. Previous work has predominantly focused on centralized solutions to the multi-satellite, resource-constrained scheduling problem (Augenstein et al. 2016; Nag, Li, and Merrick 2018; Shah et al. 2019; Squillaci, Roussel, and Pralet 2021; Boerkoel et al. 2021; Squillaci, Pralet, and Roussel 2023; He et al. 2018; Eddy and Kochenderfer 2021; Globus et al. 2004 ). More recently, de- Each agent exchanges a polynomial (in the requests) number of messages with the auctioneer. Removing the central auctioneer is possible, but results in an explosion of the communication complexity depending on the network topology.We build on the approach presented by Parjan and Chien (2023) , which attempts to address some of the limitations of the auction-based methods. In their approach, referred to as BD, each agent uses globally communicated satisfaction information as a search heuristic. The main limitation is that this approach requires each agent to send a high volume of messages to every other agent, resulting in a communication complexity at each iteration that is polynomial in the number of agents and requests.Multi-satellite observation scheduling has been framed as a DCOP previously (Picard 2021; Parjan and Chien 2023) . DCOP algorithms tend to suffer from significant computational complexity or a large reliance on communication. Solving a DCOP optimally is known to be NP-Hard (Modi et al. 2005) . Complete algorithms, such as SyncBB (Hirayama and Yokoo 1997), ADOPT (Modi et al. 2005) , or OptAPO (Mailler and Lesser 2004) are computationally infeasible for our problem scale.On the other hand, incomplete DCOP algorithms, such as Max-Sum (Stranders et al. 2009) , Maximum-Gain Messaging (MGM) (Maheswaran et al. 2004 ), Distributed Stochastic Search (DSA) (Zhang et al. 2005) , or Distributed Gibbs (D-Gibbs) (Nguyen, Yeoh, and Lau 2013) , which trade off optimality for scalability, require notable messaging. MGM and DSA are two search algorithms that are the foundation of BD, and hence NSS. MGM and DSA perform local search to iteratively improve the global solution. Genetic algorithms have also been applied, incurring similar complexity as MGM and DSA (Mahmud et al. 2019) .NSS is motivated by Region-optimal algorithms (Pearce and Tambe 2007). These algorithms solve sub-problems optimally, reducing the cost of complete algorithms, albeit to the size of sub-problems. NSS extends Region-optimal algorithms by obtaining incomplete solutions to sub-problems, reducing the complexity when sub-problems remain large. Another divide-and-conquer method for solving DCOPs is the application of the distributed large neighborhood search (DLNS) framework to DCOPs (Hoang et al. 2018 ).In the next sections, we discuss the challenges of applying these algorithms to the multi-satellite constellation observation scheduling problem, and show how heuristically decomposing the problem can overcome the hurdles in their deployment while still providing high quality solutions.In this section, we outline the multi-satellite constellation observation scheduling problem (COSP). The main application of COSP is for Earth observation, however the formulation extends to orbits around other bodies. We start by formally defining the problem. Then, we present the problem as a DCOP and discuss theoretical properties of the problem, including the barriers to applying current DCOP algorithms.The components of COSP are defined below.1. H " rh s , h e s: the scheduling horizon. 2. K : the set of orbital planes. An orbital plane defines the geometric plane that contains a collection of satellite orbits. We denote K P K as an orbital plane, and k P K for the specific orbit of a satellite within that plane. Figure 1 shows the orbits defined by a single orbital plane with 5 satellites.3. A: the set of agents. Each a i P A is a satellite in the constellation. We define a i " pk, mq where k is the orbit of the satellite and m P R `is the memory capacity. The notation kpa i q and mpa i q denote these values for agent a i , and will use the same notation for equivalent indexing. 4. T : the set of point targets on Earth. Each t i P T is defined as t i " plat, lonq. 5. R: the set of requests. Each r i P R is defined as r i " pt, hq which denotes the target to observe, t P T , and when to observe, h Ă H.val of the observation (including processing and slewing time), and m P R `is the amount of memory required. X ai : the set of Boolean decision variables for agent a i .For each s j P S ai we define the Boolean decision variable x j P X ai where x j " 1 ðñ agent a i schedules task s j . We denote xps j q " x j for agent a i . D ai : the set of downlinks for agent a i . A downlink, d j P D ai , is defined as d j " ph, mq where m P R ìs the maximum amount of data that can be downlinked, and the interval h Ă H is the time window for the down- xps l q ¨mps l q ď MINpmpa i q, mpd j qq.Here, S dj ai denotes the set of possible tasks for which the soonest downlink window in the future is d j . This constraint enforces that agent a i never exceeds its memory capacity and all taken observations can be downlinked at the soonest opportunity. We defineC Sa i " ď sj ,s l PSa i c sj ,s l ,where c sj ,s l " rxps j q ¨xps l q `Iphps j q X hps l q ‰ Hq ď 1s . This constraint ensures that no tasks are scheduled to overlap. Here, I denotes the indicator function.The goal of the optimization problem is to maximize the number of requests satisfied while not violating the constraints of any agent. A solution, X, is the assignment of each x P X ai such that C ai is satisfied for all a i .We can formulate the above problem structure as a distributed constraint optimization problem (DCOP), similar to previous work (Picard 2021; Parjan and Chien 2023) . The DCOP is a five-tuple xA, X , D, F, αy which we define for our problem below.• A: the set of satellites as previously defined.• X " Ť aiPA X ai : the set of Boolean decision variables for every agent's possible task set as previously defined.• D " Ť xPX t0, 1u: all variable domains are Boolean. • FpXq " Ť aiPA f ai pX ai q Y Ť rj PR f rj pX rj q where f ai pX ai q " " 0 C ai satisfied by X ai ´8 else and f rj pX rj q " 1 ´ź xPXr j p1 ´xq.Here, X ai is the set of variables in the solution, X, such that αpxq " a i , and X rj is the set of variables such that x " xps l q and rps l q " r j . See that f rj pX rj q " 1 iff there exists a satellite satisfying request r j and f ai pX ai q " 0 iff agent a i has a schedule that satisfies its constraints. • αpxq " a i ðñ x P X ai maps a variable to the agent that can schedule the associating request fulfillment.The goal of a DCOP is to obtain an assignment of all variables as to maximize (or minimize) the sum of the utility functions, X ˚" argmax X ř f PF f `XS ˘. While the problem can be represented as a DCOP, there exist roadblocks to applying existing DCOP algorithms. The constraint graph defined by this formulation has a minimum of |A| `|R| « 10 3 complete sub-graphs derived from f ai , f rj . Each a i P A contributes a clique of size |X ai |, and each r j P R contributes a clique of size |X rj |. In many problem instances, request durations are long enough such that the majority of agents are able to satisfy any particular request. This results in |X ai | " Ωp|R|q and |X rj | " Ωp|A|q. In addition, most of these cliques are highly connected to each other, resulting in a cyclic graph. Figure 2 shows an example of the structure we discuss for a problem instance with 3 agents and 4 requests. Recall that we consider constellations with hundreds of agents and thousands of requests. Therefore, since each agent a i controls all variables in X ai , the neighborhood of variables for an agent is Ωp|A| ¨|R|q « 10 5 variables. The problem scale coupled with the structure make it unsuitable for many DCOP algorithms. Complete DCOP algorithms are simply infeasible for the problem size, having a computational complexity of Op2 |A|¨|R| q « 10 30102 . Incomplete DCOP algorithms, such as Max-Sum (Stranders et al. 2009) or Maximum Gain Messaging (MGM) (Maheswaran et al. 2004 ), require many iterations, where at every iteration, each agent would exchange Ωp|A|q messages, each with size Ωp|R|q, which is on the order of 10 7 total volume if agents send direct messages to each other (Fioretto, Pontelli, and Yeoh 2018) . Finally, we mention that the DLNS and region-optimal approaches, require defining sub-problems. One application of our approach is outlining methods for sub-problem selection. However, the above two algorithms still incur substantial costs when sub-problems remain large.We mention one distinction between the scheduling problem we will examine in this paper and a traditional DCOP. In standard DCOPs, agents know the variables and constraints of neighboring agents (Fioretto, Pontelli, and Yeoh 2018 ).An agent is unaware of the values of the variables that other agents control, but is privy to their existence. In our multisatellite constellation, we only assume that agents are aware of the existence of other agents, but have no knowledge of the request fulfillments (variables) other agents are attempting to schedule. The implication is that an agent does not know the full structures of the utility functions for which its variables are affiliated. Note, it takes one broadcast for each agent to share their request fulfillments before the problem becomes a standard DCOP as outlined in the previous section. This small nuance is motivated by the requirements of the application, but does not impact the approach significantly from applying to other problems.In this section, we outline the construction of the Geometric Neighborhood Decomposition heuristic (GND) that decomposes the global problem. GND, which is computed individually by each agent, inherently coordinates agents without communication. This heuristic is grounded in geometry, and is composed of three layers: (1) the global supply layer, (2) the inter-neighborhood delegation layer, (3) and the intraneighborhood delegation layer.The first layer addresses the nuance of the scheduling problem mentioned in the previous section, while the latter two layers act to partition the agents and requests into sub-problems. An agent computes the heuristic values only relevant to itself, remaining unaware of the heuristic computation of other agents.In our application, supply, or the number of agents capable of satisfying a request, is important as there are observations for which only a few satellites have visibility, as well as requests that the entire constellation can service. Identifying supply enables agents to make informed decisions as to minimize redundant observations and collectively service more requests. The lack of knowledge of other agent variables results in agents being unaware of the global supply.In the traditional DCOP, the supply is trivial to compute. For a request, r, the supply is the number of agents that have a variable x " xps j q such that s j " pr, h, mq, which is 325 known since these agents all share a constraint.We use the geometry of the satellite orbits to estimate the visibility of a ground target for each orbital plane, obtaining an approximation of the supply. Specifically, the supply of a request, r, provided by an orbital plane, K, is determined 330 as the duration of time that the request is in the longitudinal cross-tracks of the plane times the number of agents that pass over a point per epoch. The longitudinal cross-tracks are the intervals in which the target is within a visible range of an orbital plane. This is determined by the point of closest 335 approach, satellite slewing capabilities, and field of view.Figure 3 illustrates the geometric interval that a ground target is in the cross-tracks. In the figure, Z ECI denotes the rotation axis of Earth. P 1 and P 2 are the bounding planes of the cross-tracks either side of the orbital plane. The green 340 area then depicts the region for which any ground target might be within visibility of a satellite in the orbital plane. The right ascension bounds depict the interval of potential visibility for a specific ground target. Combining that interval with the number of agents that pass over a point per 345 epoch, we obtain the estimate of supply. The latter piece of information is determined by the fixed amount of time it takes any satellite in the orbital plane to complete one full orbit and the number of agents in the plane. Whether the supply is estimated or known exactly makes 350 little difference to the approach. However, in this application, knowing the supply is an unrealistic assumption.The supply layer provides a global view of the problem to each satellite. Considering the number of satellites that can 355 service an observation request puts the contention into perspective. The inter-neighborhood heuristic delegates a request to a fixed subset of agents.Each orbital plane, K P K, provides a natural grouping of agents into a neighborhood. Satellites in the same or-360 bital plane experience similar relative geometries of Earth targets, making their view of the problem homogeneous.They typically share the ability to satisfy the same requests, making orbital planes a logical choice of neighborhoods. We acknowledge that this neighborhood selection exploits specifics of our domain, and that neighborhood selection in other domains is not always as clear-cut.In this section, and future sections, we use the term orbital plane and neighborhood interchangeably. It is important to note that our use of the term neighborhood is different from the typical notion of a neighborhood in DCOPs. In a DCOP, the neighborhood refers to agents that share a constraint. Agents in an orbital plane typically share many constraints, however, they also share constraints with agents in other orbital planes. At an abstract level, this layer of the heuristic delegates control of each utility function, f rj , to a partition of agents.We define the inter-neighborhood delegation heuristic based on properties of an orbital plane and the request. For a given request, r, the neighborhood delegated to it is determined as the orbital plane with the most agents for which there is non-zero supply. Ties are broken by selecting the plane with the minimum distance to the request target, tprq, over the request window. The minimum distance is estimated using three points over the continuous interval of the request horizon, hprq: the start, the end, and the midpoint. This tie-breaking can be viewed as a unique secondary estimate of the supply.The inter-neighborhood delegation serves as a complete partitioning of the global problem into sub-problems. For each request, r, there exists exactly one plane, K, such that the request will be delegated. Consider that agent a i disregards all variables, x, for which the associated request is not delegated to the neighborhood of a i . We can then remove the factors containing x from each f rj and f ai . The problem has now been decomposed such that an agent is only neighbors (by the DCOP notion) with other agents in the same neighborhood. From this we obtain a partitioning into |K| sub-problems in which the agents of each sub-problem are the agents in an orbital plane, K, and the variables are determined by the inter-neighborhood delegation heuristic.Later, we will present the constellation, but as a consideration we note here that |K| " 4 in our evaluations. Therefore, while this partitioning is substantial, it is not necessarily sufficient to reduce the problem scale to a desired level.The value of the supply heuristic and the inter-neighborhood heuristic are not unique for agents in the same orbital plane. The final layer in the decomposition further partitions neighborhoods into smaller problems. The intra-neighborhood heuristic is driven by agent biases, where agents with the same biases form a subset of the partition.First, we define the bias of an agent, denoted b. A bias is parameterized by a periodicity, ρ P N. The periodicity both determines the number of unique biases and the number of agents for which the bias repeats in a neighborhood. To compute the bias, we index each agent in an orbital plane, K, by arbitrarily selecting an agent 0 and ordering all the agents in the plane from 0 to |K| ´1 by moving counterclockwise. The bias, b P r0, ρq, is computed as an integer -Sub-neighborhood agent -Orbital plane agent The periodicity of the bias means all agents indexed i `n ¨ρ possess the same bias for all n P N. Increasing the periodicity creates more sub-groups of agents with the same bias. The motivation for spacing agents with the 425 same bias as opposed to selecting consecutive agents is to diversify the sub-neighborhood's collective visibilities and geometries. This creates more advantageous sub-problems to solve by enabling a wider birth of opportunities for observation. The bias for a single agent is fixed, therefore we 430 assume it is known by all agents apriori with the configuration of the satellite constellation.We consider two biases. The supply bias sub-divides the original supply thresholds into ρ partitions, and an agent with bias, b, will be biased towards requests that fall into the 435 sub-bucket indexed b. The request target position bias examines the latitude and longitude of the ground target, tprq. For both coordinates, we add a bias if the degree times ten modular ρ is equivalent to the agent bias b. We multiply by ten to give more precision to the bias. Targets tend to be clustered 440 in small geographic regions, so using more precision provides more diversity in this bias. We mentioned previously that many agents experience similar relative geometry with targets in terms of time and space. The latitude and longitude bias aims to disrupt that homogeneity across agents. A 445 request is delegated to the sub-neighborhood of agents for which the shared bias has the highest value.The intra-neighborhood delegation partitions the agents in an orbital plane into ρ sets, where a set is defined by agents with the same bias. Tuning ρ enables us to create partitions 450 of arbitrary size, but at a potential reduction of coordination among agents.The GND heuristic, Υ ai : R Ñ t0, 1u, is a function computed by an agent that maps a request fulfillment to a 455 Boolean value. The heuristic identifies the subset of requests assigned to the partition containing an agent. Iff Υ ai prq " 1, then the request r is within agent a i 's partition. The agent's within the partition are fixed based on the geometry of the constellation and the parameter ρ. We tuned ρ and take the 460 value ρ " 5. We mention that small deviations in ρ had minimal effect on the overall performance, but drastic changes did worse. Taking ρ " 5 results in all sub-problem having less than 20 agents, reducing the size from the global problem by an order of magnitude.In this section, we present the algorithms we evaluate, including Neighborhood Stochastic Search (NSS).By fully decentralized solutions, we refer to decentralized algorithms that do not rely on inter-agent communication. We present three baseline algorithms.1. Random. Each agent shuffles its set of request fulfillments, S ai . The shuffled request fulfillments are iterated through and scheduled if they do not violate constraints.2. Greedy Start Time. Each agent sorts its request fulfillments based on increasing start time. The sorted request fulfillments are iterated through and scheduled if they do not violate constraints. 3. Portfolio Greedy. Each agent samples a heuristic from the portfolio of heuristics, Π, uniformly at random. The heuristic defines the greedy insertion order into the schedule. The portfolio consists of four heuristics: random, start time, memory usage, and off-nadir angular separation. The random heuristic assigns a random value to each request fulfillment. We note that each heuristic was evaluated individually, and the portfolio does not contain a dominating heuristic.In addition, to demonstrate the effectiveness of the partitioning, we also evaluate the Greedy Start Time algorithm, but each agent first computes the decomposition using GND and only considers the partitioned requests. We call this fully decentralized approach Decomposition Heuristic.The centralized algorithm we employ is an adaptation of Squeaky Wheel Optimization (SWO) (Joslin and Clements 1999) . SWO is an incomplete centralized search algorithm. Over the course of iterations, SWO heuristically creates schedules based on priorities assigned over previous iterations. In our implementation, SWO sorts the requests based on their priority, breaking ties with the exact supply. It then randomly selects an available satellite to schedule the request. Requests that are not scheduled on previous iterations have their priorities increased. In subsequent iterations, requests that were not previously scheduled are attempted to be satisfied first.The Neighborhood Stochastic Search algorithm (NSS) extends the request satisfaction variation of BD (Parjan and Chien 2023) to scale to large problem instances and enable scheduling with resource constraints. We present the pseudo-code in algorithm 1 and mention key subprocedures. The first step for an agent is to compute, using GND, the sub-problem the agent is involved in solving. We denote this sub-problem as N , which is itself a DCOP consisting of agents, ApN q Ď A, and requests, RpN q Ď R.The procedure INITIALSOLUTION constructs an initial schedule for agent a i . We consider two variations of this relying on fully decentralized algorithms: Algorithm 1: Neighborhood Stochastic Search for agent a i Input: H, A, R, S ai , D ai , C ai , Υ ai Output: Schedule for agent a i 1: N " COMPUTESUBPROBLEMpa i , A, R, S ai , Υ ai q 2: sched = INITIALSOLUTIONpN , S ai , D ai , C ai q 3: while not converged do 4:com " MESSAGEpApN q, sched) 5:shuffle RpN q 6:for r P RpN q do 7:isAssigned " STOCHASTICUPDATEpr, sched, comq 8:if isAssigned " TRUE then 9:isScheduled " SCHEDULEpr, sched, S ai q 10: end if 11:UPDATEDATASTRUCTS(isAssigned, isScheduled)12:end for 13: end while 14: return sched 1. NSS-Random. Agents construct random initial schedules, 520 the typical initialization scheme for DSA. 2. NSS-Decomposition. The Decomposition Heuristic algorithm is used for the initial schedule.The procedure MESSAGE encapsulates the communication between agents in a sub-problem. Each agent a i mes-525 sages the subset of R that it satisfied in the previous iteration to each agent in its sub-problem, ApN q, and receives the subsequent broadcast from those agents. The data structure com encapsulates these messages. The heuristic search is carried out in STOCHASTICUPDATE, which is adapted from 530 the BD algorithm (Parjan and Chien 2023) . This procedure updates the assignment of the agent and the request based on the communicated information. By assignment, we refer to whether or not the request should be scheduled by this agent. Let m be the number of agents that satisfied request r 535 according to the broadcast. The assignment of a request r is stochastically updated in the following ways.• If agent a i is not assigned to r and r was not scheduled in the previous iteration, a i assigns to r. • If agent a i is not assigned to r and r was scheduled in the 540 previous iteration, a i remains unassigned to r. • If agent a i is assigned to r and r was not scheduled in the previous iteration, a i will unassign with probability P u . • If agent a i is assigned to r and r was scheduled in the previous iteration, a i will unassign with probability 1 m .In the procedure SCHEDULE, if an assigned request fulifllment satisfies C ai it is immediately inserted into the schedule. Otherwise, the scheduler can remove a conflicting request fulfillment from the schedule to free up resources. The removed request fulfillments are selected as the closest start 550 time to the request fulfillment to insert. Allowing agents to de-schedule requests enables the algorithm to overcome getting stuck at local minima. Note that this algorithm relies on the parameter P u . We use P u " 0.7 as published by the authors of the BD algorithm (Parjan and Chien 2023) .The stochastic search performed in NSS mimics the search of BD with some key distinctions: the use of de-composition to reduce size, de-allocating to overcome localminima, the variation in initial schedule construction, and scheduling with resource constraints.We summarize the computational and communication complexity of the algorithms in the table below. Note that it is assumed that all agents have knowledge of the requests. Therefore, the fully decentralized algorithms incur no communication. To more exactly capture the complexity, we define L, the maximum size of a satellite's schedule. The value of L is driven by the size of the horizon, H, the requests, R, and an agent's capabilities, C ai . We parameterize it to capture more exactly the complexity of our algorithms, but in practice L ăă |R|. Checking if a request fulfillment satisfies C ai and inserting into a schedule are both Oplog Lq operations. We omit the L factors in the computational complexity of NSS and SWO as it is subsumed by larger factors. The communication and computation of the decentralized algorithms is shown per agent. The centralized algorithm, Squeaky Wheel Optimization (SWO), gives the complexity required of the centralized node. Centralized algorithms require communicating the final schedules to each agent, resulting in the OpL ¨|A|q communication cost. The NSS algorithm incurs a communication cost proportional to the size of the sub-problem. Here, ApN q is the largest set of agents in a sub-problem and RpN q is the largest set of requests in a sub-problem. For both NSS and SWO, we define k, the number of iterations of the algorithm.The complexity analysis clearly shows that the fully decentralized algorithms are substantially more efficient than either NSS or SWO, and depending on the size of the subproblems, NSS can be much more efficient than SWO, but incurs more communication. In comparison to MGM, DSA, or BD, NSS achieves a complexity parameterized by |ApN q| and |RpN q| in each iteration as opposed to |A| and |R|.The satellite constellation we simulate is modelled on a low Earth orbit Planet constellation (Planet 2023). There are 200 agents divided across 4 orbital planes. The constellation has two near sun-synchronous orbital planes at 95 ˝inclinations composed of 95 satellites each. There are an additional two orbital planes at 52 ˝inclinations with 5 satellites each. Each satellite has a single sensor that can slew to 60 ˝off of nadir and an on-board memory capacity of 125 GB. Figure 5 shows the constellation centered around a sphere. We define the communication network topology such that each satellite messages the nearest agent in its neighborhood, and that agent must relay the message. This avoids satellites messaging without line-of-sight. We consider two ground stations for downlinks: the ASF Near Space Network Satellite Tracking Ground Station and the Guam Remote Ground Terminal System. A downlink is modelled as a constant bit stream of 62.5 MB/s for the dura-610 tion of visibility of the ground stations.The target set, T , is composed of 634 globally distributed ground targets (cities and volcanoes). We generate a campaign by selecting a random periodicity in the range r4, 12s. A periodicity of n means each target is requested to be 615 observed once within n evenly spaced intervals during the scheduling horizon. For small problem instances, we reduce the periodicity to 2 and randomly remove requests to obtain a smaller set. The start of the scheduling horizon is randomly initialized during a week long simulation and the end of the 620 horizon is fixed at 24 hours after the start time. We remove unsatisfiable requests based on satellite visibility during the horizon. The amount of memory required by a request fulfillment is sampled from a normal distribution with mean 50 MB and standard deviation 10 MB. The interval of time re-625 quired to schedule a request fulfillment is fixed at 63 seconds (3 seconds for the observation and 30 seconds either side for slewing and processing).Generating campaigns in this manner produces hard problem instances. By hard, we refer to the constraint graph 630 structure discussed previously. Despite fixing the scheduling horizon at one day, it is the density of requests during the window (i.e. requests per epoch) that drives the difficulty of the scheduling problem. Large problem instances refer to problems with thousands of requests, resulting in millions 635 of variables, whereas small problem instances contain less than 500 requests. We intend to release supplemental datasets containing problem instances when published.We compare the performance of the algorithms on small 640 problem instances to an optimal solution, as well as the BD algorithm (Parjan and Chien 2023) . We use a branch and bound search to obtain an optimal schedule for the constellation. The branch and bound algorithm can only execute on small problem instances due to computational constraints 645 and the BD algorithm, likewise, due to communication constraints. We report the average gap in satisfaction to the optimal solution, the average execution time (per agent), and the average total messages exchanged over 50 randomly generated small problem instances in the table below. The results show that the centralized solution, SWO, achieves near-optimal performance. The NSS algorithms also achieve close to optimal performance, while the fully decentralized solutions are significantly further from the optimal solutions. Notably, the decomposition heuristic scheduling algorithm outperforms the other fully decentralized algorithms and the BD algorithm. In comparison to BD, the NSS algorithms achieve higher request satisfaction while possessing faster run-times and procuring an order of magnitude less messages. This supports the efficacy of GND in generating advantageous sub-problems and the theoretical analysis of the cost of NSS.We evaluate each scheduling algorithm against 100 randomly generated large problem instances. Note, solving a large problem instance optimally would likely take longer than the age of the universe. Figures 6 and 7 show the performance of the varying approaches. The horizontal lines in figure 6 represent the medians of the simulations. The NSS algorithms outperform the other decentralized solutions and are comparable in performance to the centralized approach, averaging just a %3 satisfaction decrease. In addition, the results enforce the effectiveness of the decomposition as the the fully decentralized approach outperforms the other baselines, and NSS-Decomposition slightly outperforms NSS-Random. Figure 7 also shows that as the density of requests grow, problem instances become more difficult. The constellation cannot satisfy all the requests, therefore coordinating to reduce redundancy of observations becomes crucial. centralized approaches. The centralized approach is another two orders of magnitude slower than the NSS algorithms. These results support the theoretical analysis.While centralized algorithms will nearly always provide 690 higher quality solutions, our GND-based solution is highly effective in the decentralized context, outperforming all the decentralized baselines. This demonstrates that high-quality schedules can be produced in very large-scale constellations by utilizing problem decomposition.A major barrier to applying existing DCOP algorithms to large-scale, real-world problems is their computation and communication complexities, specifically when dealing with highly connected constraint graphs. We pro-700 pose a decomposition-based approach to the multi-satellite scheduling problem that is efficient in both time and message complexity and can scale to problems orders of magnitudes larger. Despite no quality guarantees, we have shown that solving well-constructed sub-problems can generate 705 high quality global solutions while reducing the overall costs burdened by each agent. NSS can be adapted to other domains with different decomposition.Beyond the application of scheduling a satellite constellation, many large multi-agent systems posses limiting con-710 straints, and developing algorithms that work within those constraints is essential. Partitioning the global problem is one strategy to enable the broader application of DCOP solutions that have varying complexity. 
 
 Appendix:  


Decision: Positive points:
- Inspiring modeling as a distributed constraint optimization problem, with the help of the decomposition
- Neighborhood Stochastic Search algorithm is proposed, representing a promising approach
- Scalable approach demonstrated on large-scale instances
- Well-done presentation
- Valuable theoretical and experimental analysis

Negative points:
- The claim about the accommodation of more complex slewing models via intra-agent constraints is not true from the optimization point of view. So, there is still a gap between the proposed techniques and the actual application. Please reflect it in the paper's final version (see reviewer Xvmc's detailed comments).
- The proposed approach should be generalized. The reviewers recommend it as an important future work.

We further ask the authors to reflect on the reviews' comments in the final version of the paper in case of final acceptance.

Reviews: review: strength_weakness: strength_weakness: * The downlink constraints are restrictive: there is a requirement to empty the memory during each downlink window, forbidding the possibility to wait for the next downlink window to download some remaining data. This restriction allows the authors to avoid propagating memory constraints over the whole horizon. 

* The observation constraints are restrictive. More precisely, the time interval associated with an observation is assumed to be fixed beforehand (no temporal flexibility). This allows the authors to deal with selection constraints (constraints c_{s_j,s_l} on page 2) instead of scheduling (no-overlap) constraints over temporally flexible tasks. One issue is that the fixed observation interval h includes the slewing time, as mentioned at Line 211, but this slewing time should depend on the previous observation. This can have a strong impact in practice since the experiments consider a “pessimistic” 30 seconds either side for slewing and processing.

* The partitioning performed never considers the total load of each orbital plane or the load of each group of satellites within an orbital plane. For large-size instances, there may be so many requests that this is not an issue, since the satellites always have candidate observations, or in other words all groups of satellites are overloaded. But it is not clear how the algorithm behaves when the load must actually be shared or when observations have priorities or weights (more general than just maximizing the number of observations performed). 

* Concerning the comparison with optimal methods, optimal schedules are obtained based on a branch and bound algorithm over the global problem. It is not clear why a MILP solver is not directly used for the small instances to try and get lower computation times. Also, in a MILP model, the observation constraints could be expressed in an aggregated form by enforcing constraints like sum_{s_j \in S} x(s_j) \leq 1 for sets of observations that pairwise overlap. Moreover, to better compare the relative contributions of GND and NSS, each subproblem produced by GND may be solved exactly using a MILP solver for the smallest instances.  

* The features of the subproblems obtained in the experiments should be further detailed, such as the distribution of the number of candidate requests and satisfied requests in the subproblems, and the distribution of the number of candidate requests and satisfied requests between two downlink windows. 

* There are some writing issues at some points: 
   - in the definition of the DCOP, alpha is defined at Line 245 but used at Line 240
   - I do not see any difference between X_{a_i} and \mathcal{X}_{a_i}, since if we read the definition of alpha, X_{a_i} is the set of variables x such such x \in \mathcal{X}_{a_i}.
   - Line 249: why X^S and not X?
   - Writing O(2^{|A| |R|}) \simeq 10^{30102} is not sound.
   - The notion of distance between an orbital plane and a target is unclear: if the request window is large, is it meaningful to consider only the start, end and midpoints of window h(r)? Should the windows of the request fulfillment be considered instead?
   - Lines 490-491: “we also evaluate […] but” : the formulation could be improved.
   - Line 501: breaking ties with the exact supply : highest supply or lowest supply?
   - Line 545: what is m?
   - Algorithm 1: Line 11 is not detailed (function UpdateDataStructs). 
   - First the bias is defined at Line 421, and then the authors write that there are two biases. The corresponding paragraph at Lines 433- 447 is unclear.
questions: questions: (1) Could you deal with slewing times and temporally flexible observations? 
(2) Please provide some features of the subproblems obtained.
(3) Did you use a MILP solver for the branch-and-bound method?
(4) How does the algorithm behave when the load must be shared? (see comments above)
strength_weakness: strength_weakness: Clearly, the decomposition method takes advantage of the geometric properties of the problems:
-having two different orbital planes involve different observation opportunities
-cyclic partitioning within an orbital plane can match the periodic observation opportunities of agent satellites.
The fact that the decomposition method is consistent with the problem structure is not discussed. This is an important point to mention, in spite of being part (even unconsciously) of the methodology. 
The mathematical notation and the problem formulation are difficult to follow with several level of indexing. In particulat, the f() utility function seems to be semantic-free and is not really well presented. Concrete examples for f() would help the reader.
More generally, the paper lacks of concrete examples and illustrative data to help the reader.
The paper does not really exploit planning and scheduling background and contributes on distributed search techniques.
Other distributed approaches could be used (such as agreement protocols or argumentation techniques) but are not discussed.
questions: questions: How the communications between satellites could be performed? inter-satellite links (laser, radio) or others?
For your evaluations, problem instances are generated randomly, but how far they are from real data (downlink bandwidth, orbital periods LEO, latencies...)?
How the values on the utility functions can be interpreted in your results?
strength_weakness: strength_weakness: While the partitioning of requests provides good performance on the chosen benchmark instances, there is reason to believe that this may not generalize well to other instances, or problem variants:
- The inter-neighborhood delegation does not consider the number of requests already assigned to a plane - this might lead to e.g. some planes without any assigned requests, while other are completely overloaded. Consider e.g. the extreme case of two (nearly) parallel orbital planes, with satellites orbiting at slightly different heights. Those two planes provide supply to (roughly) the same requests, so according to the given delegation scheme, the one with the highest number of satellites will be assigned all of them, while the other one will remain empty.
- The description of the intra-neighborhood delegation is a bit hard to understand, but it seems to boil down to an arbitrary / random partitioning of requests into sub-planes. This works only if for each (or nearly each) request, at least one satellite of the appropriate "bias" (a better word might be "index" or "subgroup designation") will be in range within the request's time window. If request time windows become more narrow (such that less than \rho satellites are in range during the window), it gets increasingly more likely that none of the satellites from the subgroup assigned to the request is able to satisfy it at all. An intra-neighborhood delegation scheme that takes individual satellite and request timing information into account might fare better, but also require a different partition strategy since successive satellites are more similar with regards to their timing.

In the Theoretical Analysis, the comparison with the centralized algorithm is misleading. The given communication cost applies only to the central agent (which typically has arbitrarily high computation power and low computation cost compared to the others), all others have cost 0. Similar for computation costs. It would be better to list the maximum and average costs separately to allow for a fair comparison.

Minor issues:
- Problem formulation: Notation k(a_i) and m(a_i) might be confusing with function notation - why not use k_i or k_{a_i}? This notation is already in use for other parameters.
- Problem formulation: Difference between X and \mathcal{X} should be clarified
- Problem formulation, line 249: Set X^S is undefined 
- The tables are hard to read due to font size. I propose using booktabs and floating tables across columns (table* environment)

Typos:
- line 429: "wider birth" -> "berth", even better "range"
- line 458: "the agent's" -> "the agents"
- line 672: "%3" -> "3%"
- line 673f: "as the the fully" -> duplicate "the"

Update after the response: 
The fact that the "no request fulfillment during downlink" constraint is handled exclusively during the instance generation further makes the approach instance-specific, although this could be easily changed by adding appropriate constraints to the model.
For the final version, the authors should make it clear that their approach exploits characteristics of the specific instances (orbital configuration and request distribution) they evaluate it on and instances with other characteristics may require totally different partitioning schemes.

I would also suggest adding a reference to the Picard 2021 and/or Parjan and Chien 2023 papers to the problem definition, so that it is immediately clear where this specific COSP formulation originates from.
questions: questions: Questions
----------
1) Does the model allow for different orbits along the same plane?
2) Is the COSP as described a new problem? If not, please add a reference in the appropriate section. If it is, what are the differences to prior literature?
3) Are request observation times contiguous intervals or arbitrary subsets of the scheduling period? (Same for request fulfillment intervals). Can a single satellite have multiple fulfillment opportunities for a single request?
4) Memory constraint: What happens if satellites are allowed to download data on later downlinks (and store it in between)?
5) The constraints do not enforce the requirement of "no task during downlink". Is this guaranteed by the input (i.e. no tasks exist that overlap downlink)?
6) How many iterations were used for SWO and NSS in the experimental evaluation?
7) line 459: How did you tune \rho? The resulting value 5 must be specific to the individual instance(s) used, I would suggest moving this result to the Experimental section.