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

Satellite Constellation
Itai Zilberstein1 , Ananya Rao1,2 , Matthew Salis1 , Steve Chien1
1
Jet Propulsion Laboratory, California Institute of Technology, Pasadena, USA
2
Carnegie Mellon University, Pittsburgh, USA
[Link]@[Link], ananyara@[Link], [Link]@[Link], [Link]@[Link]

Abstract satellite (Shah et al. 2019). Even most research technology

efforts are centralized (Boerkoel et al. 2021; Nag, Li, and
Deploying multi-satellite constellations for Earth observation Merrick 2018). While centralized approaches can provide
requires coordinating potentially hundreds spacecraft. With
high-quality solutions, reliance on a single computing node
increasing on-board capability for autonomy, we can view the
constellation as a multi-agent system (MAS) and employ de- makes them vulnerable to single point failures and can in-
centralized scheduling solutions. We formulate the problem crease communications burden. In addition, many central-
as a distributed constraint optimization problem (DCOP) and ized approaches rely on local search or divide-and-conquer
desire scalable inter-agent communication. The problem con- algorithms, making distributed solutions natural.
sists of millions of variables which, coupled with the struc- Framing the constellation as a multi-agent system (MAS)
ture, make existing DCOP algorithms inadequate for this ap- enables the application of decentralized scheduling solu-
plication. We develop a scheduling approach that employs tions. Decentralized scheduling addresses both the system’s
a well-coordinated heuristic, referred to as the Geometric robustness and the vulnerabilities of a central controller
Neighborhood Decomposition (GND) heuristic, to decom-
(Bonnet and Tessier 2008; Phillips and Parra 2021). Many
pose the global DCOP into sub-problems as to enable the
application of DCOP algorithms. We present the Neighbor- MAS problems are framed to optimize a global cost function
hood Stochastic Search (NSS) algorithm, a decentralized al- where agents control the parameters of the function and must
gorithm to effectively solve the multi-satellite constellation communicate to coordinate their parameter assignments.
observation scheduling problem using decomposition. In full, In many applications, communication may be unreliable
we identify the roadblocks of deploying DCOP solvers to for large message volume. For example, orbiters around a
a large-scale, real-world problem, propose a decomposition- comet or the sun may experience communication interfer-
based scheduling approach that is effective at tackling large ence or infrequent line of sight with each other. For an Earth
scale DCOPs, empirically evaluate the approach against other orbiting constellation, satellites may have limited cross-link
baseline algorithms to demonstrate the effectiveness, and dis-
cuss the generality of the approach.
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
Introduction aim to produce high quality scheduling solutions.
Large-scale, Earth observing satellite constellations with The problem requires agents to coordinate the assign-
hundreds of spacecraft are becoming increasingly promi- ments of millions of variables and the desire for limited
nent in order to monitor Earth phenomena. Spire, Satellogic, communication make the direct application of DCOP al-
Canon, SatRev, Spacety, Planet Lab’s Dove, and SkySat are gorithms inadequate. However, by decomposing the global
several examples (NewSpace 2023). Observation schedul- problem, we can deploy DCOP algorithms to solve smaller
ing for a large-scale constellation requires fusing informa- sub-problems. We construct a heuristic, called the Geomet-
tion from many sources and tasking space assets that have ric Neighborhood Decomposition heuristic (GND), that par-
varying constraints, capabilities, and visibility of Earth tar- titions the agents and requests in a coordinated fashion as
gets. In addition to Earth observation, satellites are deployed to instantiate sub-problems that are advantageous to solve.
for a variety of applications, including forming large internet Each agent individually computes the heuristic using only
constellations (SpaceX 2023). Any multi-satellite constella- knowledge of the requests to schedule and the configuration
tion that requires coordinating agents poses a challenging of the constellation.
planning and scheduling problem. Satellite constellations are typically designed to optimize
In practice, satellite observation scheduling is typically the supply given the expected demand for a target set, which
done in a centralized fashion, where a single controller de- couples the scheduling problem with the constellation con-
velops a single schedule that specifies the actions of every figuration and can be solved as another search problem (Lo
1999; Schaffer et al. 2018). Constellations are typically fixed
Copyright © 2024, Association for the Advancement of Artificial relative to the number of scheduling runs they execute. GND
Intelligence ([Link]). All rights reserved. is grounded in geometric computation and designed to ex-
ploit this supply and demand relationship. GND is composed of the auction-based methods. In their approach, called BD,
of three layers that partition the agents and requests into sub- each agent uses globally communicated satisfaction infor-
problems. The goal is for the constellation to maximize the mation as a search heuristic. The main limitation is that this
number of requests satisfied, while adhering to downlinks approach requires each agent to send a high volume of mes-
and memory constraints. sages to every other agent, resulting in a communication
The heuristic is parameterized such that the sub-problems complexity at each iteration that is polynomial in the number
produced can be of arbitrary size. Through this decomposi- of agents and requests.
tion, we can deploy DCOP algorithms on constant sized sub- Multi-satellite observation scheduling has been framed as
problems rather than the global problem that scales with the a DCOP previously (Picard 2021; Parjan and Chien 2023).
number of agents and requests. To solve each sub-problem DCOP algorithms tend to suffer from significant compu-
using communication, we build on the Broadcast Decentral- tational complexity or a large reliance on communication.
ized algorithm (BD) (Parjan and Chien 2023), an adaptation Solving a DCOP optimally is known to be NP-Hard (Modi
of two incomplete DCOP algorithms, Maximum Gain Mes- et al. 2005). Complete algorithms, such as SyncBB (Hi-
saging (MGM) and Distributed Stochastic Search Algorithm rayama and Yokoo 1997), ADOPT (Modi et al. 2005), or
(DSA) (Zhang et al. 2005), for the application of multi- OptAPO (Mailler and Lesser 2004) are computationally in-
satellite observation scheduling. We refer to our developed feasible for our problem scale.
algorithm as Neighborhood Stochastic Search (NSS). Our On the other hand, incomplete DCOP algorithms, such as
algorithm extends the BD algorithms in two major aspects: Max-Sum (Stranders et al. 2009), Maximum-Gain Messag-
(1) it is scalable to large problem instances in both compu- ing (MGM) (Maheswaran et al. 2004), Distributed Stochas-
tational complexity and communication complexity, and (2) tic Search (DSA) (Zhang et al. 2005), or Distributed Gibbs
it enables constraint reasoning, such as resource constrained (D-Gibbs) (Nguyen, Yeoh, and Lau 2013), which trade off
scheduling. optimality for scalability, require notable messaging. MGM
Empirical results demonstrate the efficacy of our ap- and DSA are two search algorithms that are the founda-
proach on small and large problem instances compared to tion of BD, and hence NSS. MGM and DSA perform lo-
decentralized and centralized baselines. On small problem cal search to iteratively improve the global solution. Genetic
instances, we show the gap to optimal solutions, while large algorithms have also been applied, incurring similar com-
problem instances enforce the performance at scale, includ- plexity as MGM and DSA (Mahmud et al. 2019).
ing run-time results. We aim to close the gap between decen- NSS is motivated by Region-optimal algorithms (Pearce
tralized solutions and centralized solutions while precluding and Tambe 2007). These algorithms solve sub-problems op-
an infeasible amount of messaging. Our contributions are: timally, reducing the cost of complete algorithms, albeit to
1. uncovering the obstacles in applying existing DCOP the size of sub-problems. NSS extends Region-optimal algo-
techniques to the large-scale, multi-satellite decentral- rithms by obtaining incomplete solutions to sub-problems,
ized scheduling problem, reducing the complexity when sub-problems remain large.
Another divide-and-conquer method for solving DCOPs is
2. introducing a decomposition-based heuristic approach to the application of the distributed large neighborhood search
solve the scheduling problem and presenting the NSS al- (DLNS) framework to DCOPs (Hoang et al. 2018).
gorithm which utilizes the decomposition scheme, and In the next sections, we discuss the challenges of apply-
3. demonstrating the efficacy of our approach on realistic ing these algorithms to the multi-satellite constellation ob-
problem instances. servation scheduling problem, and show how heuristically
decomposing the problem can overcome the hurdles in their
Related Work deployment while still providing high quality solutions.
There are many aspects of satellite observation planning
ranging from visibility computation, to downlink schedul- Problem Formulation
ing, to constraint based task allocation. This paper is mostly In this section, we outline the Multi-Satellite Constellation
concerned with the last subject. Previous work has predomi- Observation Scheduling Problem (COSP). The main appli-
nantly focused on centralized solutions to the multi-satellite, cation of COSP is for Earth observation, however the formu-
resource-constrained scheduling problem (Augenstein et al. lation extends to orbits around other bodies. We start by for-
2016; Nag, Li, and Merrick 2018; Shah et al. 2019; Squil- mally defining the problem. Then, we present the problem as
laci, Roussel, and Pralet 2021; Boerkoel et al. 2021; Squil- a DCOP and discuss theoretical properties of the problem,
laci, Pralet, and Roussel 2023; He et al. 2018; Eddy and including the barriers to applying current DCOP algorithms.
Kochenderfer 2021; Globus et al. 2004). More recently, de- Similar formulations have been examined in previous work
centralized scheduling approaches have proposed auction- (Parjan and Chien 2023; Picard 2021).
based methods (Picard 2021; Phillips and Parra 2021) and
heuristic search based methods relying on broadcasting (Par- Defining COSP
jan and Chien 2023). The auction-based methods rely on a The components of COSP are defined below.
centralized controller to act as an auctioneer and has a pro-
hibitive communication and computational complexity. 1. H “ rhs , he s: the scheduling horizon.
We build on the approach presented by Parjan and Chien 2. K : the set of orbital planes. An orbital plane defines the
(2023), which attempts to address some of the limitations geometric plane that contains a collection of satellite or-
 “ ‰
csj ,sl “ xsj ¨ xsl ` Iphsj X hsl ‰ Hq ď 1 .
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 con-
straints of any agent. A solution, X, is the assignment of
each x P Xai such that Cai is satisfied for all ai . This vari-
ation of COSP simplifies both the downlink model and the
slewing model so that observations are not temporally flex-
Figure 1: A single orbital plane with 5 satellites. ible. Removing this simplification produces a challenging
variation of COSP which is subject to future work.
bits. We denote K P K as an orbital plane, and k P K for Formulating COSP as a DCOP
the specific orbit of a satellite within that plane. Figure 1
depicts an orbital plane. We can formulate the above problem structure as a dis-
tributed constraint optimization problem (DCOP). The
3. A: the set of agents. Each ai P A is a satellite in the
DCOP is a five-tuple xA, X , D, F, αy which we define for
constellation. We define ai “ pk, mq where k is the orbit
our problem below.
of the satellite and m P R` is the memory capacity. The
notation kai and mai denote these values for agent ai , • A: the set of satellites as previously defined.
Ť
and we use the same notation for equivalent indexing. • X “ ai PA Xai : the set of Boolean decision variables
4. T : the set of point targets on Earth. Each ti P T is defined for every agent’s possible task set as previously defined.
as ti “ plat, lonq.
Ť
• D “ xPX t0, 1u: all variable domains are Boolean.
5. R: the set of requests. Each ri P R is defined as ri “
Ť Ť
• FpXq “ ai PA fai pXai q Y rj PR frj pXrj q where
pt, hq which denotes the target to observe, t P T , and
when to observe, h Ă H.
"
0 Cai satisfied by Xai
6. For each agent, we define the following sets. fai pXai q “
´8 else
Sai : the set of possible request fulfillments for agent ai . A
request fulfillment, sj P Sai , is a task that can be sched- and ź
uled to satisfy a request. We define sj “ pr, h, mq where frj pXrj q “ 1 ´ p1 ´ xq.
r P R is the request being satisfied, h Ă hr is the inter- xPXrj

val of the observation (including processing and slewing Here, Xrj is the set of variables such that x “ xsl and
time), and m P R` is the amount of memory required. rsl “ rj . See that frj pXrj q “ 1 iff there exists a satellite
Xai : the set of Boolean decision variables for agent ai . satisfying request rj and fai pXai q “ 0 iff agent ai has a
For each sj P Sai we define the Boolean decision vari- schedule that satisfies its constraints.
able xsj P Xai where xsj “ 1 iff ai schedules task sj . • αpxq “ ai ðñ x P Xai maps a variable to the agent
Dai : the set of downlinks for agent ai . A downlink, that can schedule the associating request fulfillment.
dj P Dai , is defined as dj “ ph, mq where m P R`
The goal of a DCOP is to obtain an assignment of all
is the maximum amount of data that can be downlinked,
variables as to maximize (or minimize) the sum of the util-
and the interval h Ă H is the time window for the down- ř
ity functions, X ˚ “ argmaxX f PF f pXq. For COSP, this
link. No possible tasks occur during a downlink, and all
downlinks are mandatory. corresponds to maximizing the number of requests satisfied.
There exist roadblocks to applying existing DCOP algo-
Cai “ CDai Y CSai : the set of constraints where rithms to this formulation. The constraint graph has a mini-
CDai “
ď
cdj , and mum of |A| ` |R| complete sub-graphs derived from fai and
frj . Each ai P A contributes a clique of size |Xai |, and each
dj PDai
rj P R contributes a clique of size |Xrj |. In many problem
instances, request durations are long enough such that the
ÿ
cdj “ xsl ¨ msl ď MINpmai , mdj q.
d
majority of agents are able to satisfy any particular request.
sl PSaij This results in |Xai | “ Ωp|R|q and |Xrj | “ Ωp|A|q. In ad-
d
Here, Saij denotes the set of possible tasks for which the dition, most of these cliques are highly connected to each
soonest downlink window in the future is dj . This con- other, resulting in a cyclic graph. Figure 2 shows an exam-
straint enforces that agent ai never exceeds its memory ple of the structure we discuss.
capacity and all taken observations can be downlinked at We consider constellations with hundreds of agents and
the soonest opportunity, which is a desired constraint of thousands of requests. Therefore, since each agent ai con-
the application. We define trols all variables in Xai , the neighborhood of variables for
ď an agent is Ωp|A| ¨ |R|q, which is on the order of 105 vari-
CSai “ csj ,sl , where ables. This scale and structure make the problem unsuitable
sj ,sl PSai for many DCOP algorithms. Complete DCOP algorithms
 Global Supply
In our application, supply, or the number of agents capable
a0 a1 of satisfying a request, is important as there are observations
for which only a few satellites have visibility, as well as re-
quests that the entire constellation can service. Identifying
supply enables agents to make informed decisions as to min-
a2 imize redundant observations and collectively service more
requests. The lack of knowledge of other agent variables re-
sults in agents being unaware of the global supply.
Figure 2: Constraint graph with |A| “ 3 and |R| “ 4. Nodes In the traditional DCOP, the supply is trivial to compute.
denote the variables, and edges denote a shared constraint. For a request, r, the supply is the number of agents that have
a variable x “ xsj such that sj “ pr, h, mq, which is known
since these agents all share a constraint.
are simply infeasible for the problem size, having a com- We use the geometry of the satellite orbits to estimate the
putational complexity of Op2|A|¨|R| q, which is on the or- visibility of a ground target for each orbital plane, obtaining
der of 1030102 . Incomplete DCOP algorithms, such as Max- an approximation of the supply. Specifically, the supply of
Sum (Stranders et al. 2009) or Maximum Gain Messaging a request, r, provided by an orbital plane, K, is determined
(MGM) (Maheswaran et al. 2004), require many iterations, as the duration of time that the request is in the longitudinal
where at every iteration, each agent would exchange Ωp|A|q cross-tracks of the plane times the number of agents that
messages, each with size Ωp|R|q, which is on the order of pass over a point per epoch. The longitudinal cross-tracks
107 total volume (Fioretto, Pontelli, and Yeoh 2018). Fi- are the intervals in which the target is within a visible range
nally, we mention that the DLNS and region-optimal ap- of an orbital plane. This is determined by the point of closest
proaches, require defining sub-problems. One application of approach, satellite slewing capabilities, and field of view.
our approach is outlining methods for sub-problem selec- Figure 3 illustrates the geometric interval that a ground
tion. However, the above two algorithms still incur substan- target is in the cross-tracks. In the figure, ZECI denotes the
tial costs when sub-problems remain large. rotation axis of Earth. P1 and P2 are the bounding planes of
We mention one distinction between the scheduling prob- the cross-tracks either side of the orbital plane. The green
lem we will examine in this paper and a traditional DCOP. In area depicts the region for which any ground target might
standard DCOPs, agents know the variables and constraints be within visibility of the orbital plane. The right ascension
of neighboring agents (Fioretto, Pontelli, and Yeoh 2018). bounds depict the interval of potential visibility for a spe-
An agent is unaware of the values of other agents’ variables, cific ground target. Combining that interval with the number
but is privy to their existence. In our constellation, we as- of agents that pass over a point per epoch, we obtain the es-
sume that agents are aware of the existence of other agents, timate of supply. The latter piece of information is derived
but have no knowledge of the request fulfillments (variables) from the orbital period and size of a plane.
other agents are attempting to schedule. The implication is This computation is an estimate as other constraints may
that an agent does not know the full structures of the utility impede a satellite’s ability to observe a target, despite having
functions for which its variables are affiliated. Note, it takes visibility. Whether the supply is estimated or known exactly
one broadcast for each agent to share their request fulfill- makes little difference to the approach. However, in this ap-
ments before the problem becomes a standard DCOP. This plication, knowing the supply is an unrealistic assumption.
small nuance is motivated by the requirements of the appli-
cation, but does not impact the approach significantly. Inter-Neighborhood Delegation
This layer of the heuristic delegates control of each utility
function, frj , to a partition of agents. Each orbital plane,
Heuristic Decomposition
In this section, we outline the construction of the Geometric
Neighborhood Decomposition heuristic (GND) that decom-
poses the global problem. GND, which is computed individ-
ually 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 intra-
neighborhood delegation layer.
The first layer addresses the nuance of the scheduling
problem mentioned in the previous section, while the lat-
ter 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 compu- Figure 3: The right ascension bounds show the interval a
tation of other agents. target is within potential visibility of the orbital plane.
K P K, provides a natural grouping of agents into a neigh-
borhood. Satellites in the same orbital plane experience sim-
ilar relative geometries of Earth targets, making their view of
the problem homogeneous. This makes orbital planes a log- - Sub-neighborhood agent
ical choice to be neighborhoods. We acknowledge that this - Orbital plane agent

neighborhood selection exploits specifics of our domain, and

that neighborhood selection in other domains is not always
clear-cut. In subsequent 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 Figure 4: Partition within an orbital plane with ρ “ 10.
the DCOP notion of a neighborhood. In a DCOP, the neigh-
borhood refers to agents that share a constraint. Agents in an
orbital plane typically share many constraints, however, they bias as opposed to selecting consecutive agents is to diver-
also share constraints with agents in other orbital planes. sify the sub-neighborhood’s collective visibilities and ge-
We define the inter-neighborhood delegation heuristic ometries. This creates more advantageous sub-problems to
based on properties of an orbital plane and the request. For solve by enabling a wider range of opportunities for obser-
a request, r, the orbital plane with the most agents for which vation. The bias for all agents is fixed, therefore we assume
there is non-zero supply gets delegated r. Ties are broken by it is known by all agents apriori.
selecting the plane with the minimum estimated distance to We map a request fulfillment to a bias using two heuris-
the request target, tr , over the request window. We estimate tics. The sub-supply heuristic divides the original supply
this value using three points over the the request horizon, thresholds into ρ partitions, and an agent with bias, b, will
hr : the start, the end, and the midpoint. This tie-breaking is be biased towards requests that fall into the sub-bucket in-
a unique secondary estimate of the supply. dexed b. The target position heuristic examines the latitude
The inter-neighborhood delegation serves as a complete and longitude of the ground target, tr . For each coordinate,
partitioning of the global problem into sub-problems. For an agent posses bias for the target if the degree times ten
each request, r, there exists exactly one plane, K, such that modulo ρ is equivalent to b. Targets tend to be clustered
the request will be delegated. Consider that agent ai disre- in small geographic regions, hence multiplying by ten adds
gards all variables, x, for which the associated request is not more diversity to this bias. A request is delegated to the sub-
delegated to the neighborhood of ai . We can then remove neighborhood of agents for which the bias has the highest
the factors containing x from each frj and fai . The problem value according to the two heuristics.
has now been decomposed such that an agent is only neigh- The intra-neighborhood delegation partitions the agents in
bors (by the DCOP notion) with other agents in the same an orbital plane into ρ sets, where a set is defined by agents
neighborhood. From this we obtain a partitioning into |K| with the same bias. Tuning ρ enables us to create partitions
sub-problems in which the agents of each sub-problem are of arbitrary size, but at a potential reduction of coordination.
the agents in an orbital plane, K, and the variables are deter-
mined by the inter-neighborhood delegation heuristic. Later, Complete Heuristic
we will present the constellation, but as a consideration we
note here that |K| “ 4 in our evaluations. Therefore, while The GND heuristic, Υai : R Ñ t0, 1u, is a function
this partitioning is substantial, it is not necessarily sufficient computed by an agent that maps a request fulfillment to a
to reduce the problem scale to a desired level. Boolean value. The heuristic identifies the subset of requests
assigned to the partition containing an agent. Iff Υai prq “ 1,
Intra-Neighborhood Delegation then the request r is within agent ai ’s partition. The agents
within the partition are fixed based on the geometry of the
The value of the previous two heuristics are not unique for
constellation and the parameter ρ.
agents in the same orbital plane. The final layer further
partitions neighborhoods into smaller problems. The intra-
neighborhood heuristic is driven by agent biases, where Scheduling Solutions to COSP
agents with the same biases form a partition. In this section, we present the algorithms we evaluate, in-
First, we define the bias of an agent, denoted b. A bias is cluding Neighborhood Stochastic Search (NSS).
parameterized by a periodicity, ρ P N. The periodicity both
determines the number of unique biases and the number of Fully Decentralized
agents for which the bias repeats in a neighborhood. To com- By fully decentralized solutions, we refer to decentralized
pute the bias, we index each agent in an orbital plane, K, by algorithms that do not rely on inter-agent communication.
arbitrarily selecting an agent 0 and ordering all the agents in We consider three baseline algorithms.
the plane from 0 to |K| ´ 1 by moving counter-clockwise.
The bias, b P r0, ρq, is computed as an integer based on the 1. Random. Each agent shuffles its set of request fulfill-
index, i, of the agent: b ” i mod ρ. The periodicity of the ments, Sai . The shuffled request fulfillments are iterated
bias means all agents indexed i ` n ¨ ρ possess the same through and scheduled if they do not violate constraints.
bias for all n P N. Increasing the periodicity creates more, 2. Greedy Start Time. Each agent sorts its request fulfill-
smaller sub-groups of agents. The motivation for spacing the ments based on increasing start time. The sorted request
 fulfillments are iterated through and scheduled if they do The procedure INITIAL S OLUTION constructs an initial
not violate constraints. schedule for agent ai . We consider two variations of this re-
3. Portfolio Greedy. Each agent samples a heuristic from lying on fully decentralized algorithms:
the portfolio of heuristics, Π, uniformly at random. 1. NSS-Random. Agents construct random initial schedules,
The heuristic defines the greedy insertion order into the the typical initialization scheme for DSA.
schedule. The portfolio consists of four heuristics: ran- 2. NSS-Decomposition. The Decomposition Heuristic algo-
dom, start time, memory usage, and off-nadir angular rithm is used for the initial schedule.
separation. The random heuristic assigns a random value
to each request fulfillment. We note that the portfolio The procedure MESSAGE encapsulates the communica-
does not contain a dominating heuristic. tion between agents in a sub-problem. Each agent ai mes-
sages the subset of R that it satisfied in the previous iteration
We evaluate an additional fully decentralized approach, to each agent in its sub-problem, ApN q, and receives the
called Decomposition Heuristic to demonstrate the effec- subsequent broadcast from those agents. The data structure
tiveness of the partitioning. In this algorithm, each agent first com encapsulates these messages. The heuristic search is
computes the decomposition using GND and then runs the carried out in STOCHASTIC U PDATE, which is adapted from
Greedy Start Time, but using the partitioned requests. the BD algorithm (Parjan and Chien 2023). This procedure
updates the assignment of the agent and the request based
Centralized Algorithm on the communicated information. By assignment, we refer
The centralized algorithm we employ is an adaptation of to whether or not the request should be scheduled by this
Squeaky Wheel Optimization (SWO) (Joslin and Clements agent. Let m be the number of agents that satisfied request r
1999). SWO is an incomplete centralized search algorithm. according to the broadcast. The assignment of a request r is
Over the course of iterations, SWO heuristically creates stochastically updated in the following ways.
schedules based on priorities assigned over previous itera- • If agent ai is not assigned to r and r was not scheduled
tions. In our implementation, SWO sorts the requests based in the previous iteration, ai assigns to r.
on their priority, breaking ties with the least supply. It then • If agent ai is not assigned to r and r was scheduled in the
randomly selects an available satellite to schedule the re- previous iteration, ai remains unassigned to r.
quest. Requests that are not scheduled on previous iterations
have their priorities increased. In subsequent iterations, re- • If agent ai is assigned to r and r was not scheduled in the
quests that were not previously scheduled are attempted to previous iteration, ai will unassign with probability Pu .
be satisfied first. • If agent ai is assigned to r and r was scheduled in the
1
previous iteration, ai will unassign with probability m .
Neighborhood Stochastic Search In the procedure SCHEDULE, if an assigned request fulifll-
The Neighborhood Stochastic Search algorithm (NSS) ex- ment satisfies Cai it is immediately inserted into the sched-
tends the request satisfaction variation of BD (Parjan ule. Otherwise, the scheduler can remove a conflicting re-
and Chien 2023) to scale to large problem instances and quest fulfillment from the schedule to free up resources. The
enable scheduling with resource constraints. We present removed request fulfillments are selected as the closest start
the pseudo-code in algorithm 1 and mention key sub- time to the request fulfillment to insert. Allowing agents to
procedures. The first step for an agent is to compute, using de-schedule requests enables the algorithm to overcome get-
GND, the sub-problem the agent is involved in solving. We ting stuck at local minima. Note that this algorithm relies on
denote this sub-problem as N , which is itself a DCOP con- the parameter Pu . We use Pu “ 0.7 as published by the
sisting of agents, ApN q Ď A, and requests, RpN q Ď R. authors of the BD algorithm (Parjan and Chien 2023).
The stochastic search performed in NSS mimics the
Algorithm 1: Neighborhood Stochastic Search for agent ai search of BD with some key distinctions: the use of de-
composition to reduce size, de-allocating to overcome local-
Input: H, A, R, Sai , Dai , Cai , Υai
minima, the variation in initial schedule construction, and
Output: Schedule for agent ai
scheduling with resource constraints.
1: N “ COMPUTE S UB P ROBLEMpai , A, R, Sai , Υai q
2: sched = INITIAL S OLUTIONpN , Sai , Dai , Cai q Theoretical Analysis of Algorithms
3: while not converged do
We summarize the computational and communication com-
4: com “ MESSAGEpApN q, sched) plexity of the decentralized algorithms in the table below. It
5: shuffle RpN q is assumed that all agents have knowledge of the requests.
6: for r P RpN q do Therefore, the fully decentralized algorithms incur no com-
7: isAssigned “ STOCHASTIC U PDATEpr, sched, comq munication. We define L, the maximum size of a satellite’s
8: if isAssigned “ TRUE then schedule to more exactly capture the complexity. The value
9: isScheduled “ SCHEDULEpr, sched, Sai q of L is driven by the horizon, H, the requests, R, and an
10: end if agent’s constraints, Cai . In practice L ăă |R|. Checking if
11: end for a request fulfillment satisfies Cai and inserting into a sched-
12: end while
ule are both Oplog Lq operations. We omit the L factors in
13: return sched
the complexity of NSS as it is subsumed by larger factors.
 Algorithm Computation (per agent) Communication
Random Op|R| log Lq N/A
Greedy Start Time Op|R| log |R|q N/A
Greedy Portfolio Op|R| log |R|q N/A
Decomposition Heuristic Op|R| ` |RpN q| log |RpN q|q N/A
NSS Op|R| ` k|RpN q||ApN q|q Opk|RpN q||ApN q|q

The centralized algorithm, SWO, has a computational

complexity of Orkp|R|2 ` |R||A|qs. This cost is incurred by
the centralized node which has arbitrary computing power.
Centralized algorithms require sending the final schedules Figure 5: Visualization of the satellite constellation. Dots
to each agent, resulting in an OpL ¨ |A|q communication represent a satellite in an orbital plane.
cost. The NSS algorithm incurs a communication cost pro-
portional 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 one day, it is the density of requests during the window that
largest set of requests in a sub-problem. For both NSS and drives the difficulty of the problem. Large problem instances
SWO, we define k, the number of iterations. refer to problems with thousands of requests, resulting in
The complexity analysis clearly shows that the fully de- millions of variables, whereas small problem instances con-
centralized algorithms are the most efficient. In comparison tain less than 500 requests.
to MGM, DSA, or BD, NSS achieves a complexity parame- We tuned ρ using a grid search, taking ρ “ 5. Small devia-
terized by |ApN q| and |RpN q| in each iteration as opposed tions in ρ had minimal effect on the performance, but drastic
to |A| and |R|. changes did worse. Taking ρ “ 5 results in all sub-problems
having less than 20 agents, reducing the size from the global
Experimental Setup and Results problem by an order of magnitude. In addition, we set each
The satellite constellation we simulate is modelled on a 5 agent orbital planes as a neighborhood. All algorithms had
low Earth orbit Planet constellation and shown in figure 5 their maximum iterations set to 20.
(Planet 2023). There are 200 agents divided across 4 or-
bital planes. The constellation has two near sun-synchronous Results on Small Problem Instances
orbital planes at 95˝ inclinations composed of 95 satellites We compare the performance of the algorithms on small
each, and two orbital planes at 52˝ inclinations with 5 satel- problem instances to an optimal solution, as well as the BD
lites each. The constellation is constructed to observe the algorithm (Parjan and Chien 2023). We use a branch and
target set T , defined below. Each satellite has a single sensor bound search to obtain an optimal schedule for the constel-
that can slew to 60˝ off of nadir and an on-board memory lation. The branch and bound algorithm can only execute
capacity of 125 GB. on small problem instances due to computational constraints
We consider two ground stations for downlinks: the ASF and the BD algorithm, likewise, due to communication con-
Near Space Network Satellite Tracking Ground Station and straints. We report the average gap in satisfaction to the opti-
the Guam Remote Ground Terminal System. A downlink is mal solution, the average execution time (per agent), and the
modelled as a constant bit stream of 62.5 MB/s for the dura- average total messages exchanged over 50 randomly gener-
tion of visibility of the ground stations. ated small problem instances in the table below.
The target set, T , is composed of 634 globally distributed The results show that the centralized solution, SWO,
ground targets (cities and volcanoes). We generate a cam- achieves near-optimal performance. The NSS algorithms
paign by selecting a random periodicity in the range r4, 12s. also achieve close to optimal performance, while the fully
A periodicity of n means each target is requested to be decentralized solutions are significantly further from the
observed once within n evenly spaced intervals during the optimal solutions. Notably, the decomposition heuristic
scheduling horizon. For small problem instances, we reduce scheduling algorithm outperforms the other fully decentral-
the periodicity to 2 and randomly remove requests to obtain ized algorithms and the BD algorithm. In comparison to BD,
a smaller set. The start of the scheduling horizon is randomly the NSS algorithms achieve higher request satisfaction while
initialized during a week long simulation and the end of the possessing faster run-times and procuring an order of mag-
horizon is fixed at 24 hours after the start time. We remove nitude less messages. This supports the efficacy of GND in
unsatisfiable requests based on satellite visibility during the generating advantageous sub-problems and the theoretical
horizon. The amount of memory required by a request ful- analysis of NSS.
fillment is sampled from a normal distribution with mean 50
MB and standard deviation 10 MB. The interval of time re-
quired to schedule a request fulfillment is fixed at 63 seconds Algorithm Average Gap to Optimal (%) Average Execution Time (ms) Average Messages
Random 4.427 ă1 0
(3 seconds for the observation and 30 seconds either side for Greedy Start Time 5.158 ă1 0
Greedy Portfolio 3.807 ă1 0
slewing and processing). Decomposition Heuristic 2.271 1.42 0
BD 2.373 169.84 756, 200
We produce hard problem instances through this genera- NSS-Random 0.580 43.24 66, 690
tion. By hard, we refer to the constraint graph structure dis- NSS-Decomposition
SWO
0.409
0.012
39.66
2338.04
63, 180
ă 500
cussed previously. Despite fixing the scheduling horizon at Branch and Bound 0.0 6, 670, 695 ă 500
Results on Large Problem Instances
We evaluate each scheduling algorithm against 100 ran-
domly generated large problem instances. Note, solving a
large problem instance optimally would likely take longer
than the age of the universe. Figure 6 depicts the problem
size reduction from the global problem. The percent of re-
quests delegated to a sub-problem is substantially lower than
the requests the agents in a partition would consider in the
global problem. However, this distribution is not uniform.
Further work would examine how to improve GND to bal-
ance the load of requests across sub-problems. Figures 7 and
8 show the performance of the varying approaches. The hor-
izontal lines in figure 7 represent the medians of the simu- Figure 8: Satisfied requests (%) across 100 large problems
lations. The NSS algorithms outperform the other decentral-
ized solutions and are comparable in performance to the cen-
tralized approach, averaging just a 3% satisfaction decrease.
In addition, the results enforce the effectiveness of the de-
composition as the fully decentralized approach outperforms
the other baselines, and NSS-Decomposition slightly outper-
forms NSS-Random. Figure 8 also shows that as the density
of requests grow, problem instances become more difficult.
The constellation cannot satisfy all requests, therefore coor-
dinating to reduce redundancy becomes crucial.

Figure 9: Execution time (ms) across 100 large problems.

The centralized approach is another two orders of magni-

tude slower than the NSS algorithms. These results support
the theoretical analysis.
While centralized algorithms will nearly always provide
higher quality solutions, our GND-based solution is highly
Figure 6: The percent of total requests delegated to each sub- effective in the decentralized context, outperforming all the
problem (according to GND) relative to the global percent of baselines. This demonstrates that high-quality schedules can
satisfiable requests by agents in the sub-problem. be efficiently produced in very large-scale constellations by
utilizing problem decomposition.

Conclusion
A major barrier to applying existing DCOP algorithms
to large-scale, real-world problems is their computation
and communication complexities, specifically when deal-
ing with highly connected constraint graphs. We pro-
pose a decomposition-based approach to the multi-satellite
scheduling problem that is efficient in both time and mes-
sage complexity and can scale to problems orders of magni-
tudes larger. Despite no quality guarantees, we have shown
Figure 7: Spread of percentage satisfied requests over 100 that solving well-constructed sub-problems can generate
large problem instances. high quality global solutions while reducing the overall costs
burdened by each agent.
Figure 9 shows the execution time of the algorithms Beyond the application of scheduling a satellite constel-
across problem instances. The simulations are executed in lation, many large multi-agent systems posses limiting con-
Java. Notice the non-linearity of the y-axis. The execution straints, and developing algorithms that work within those
time of the decentralized approaches are reported as aver- constraints is essential. Partitioning the global problem is
age time per agent. The NSS algorithms are an order of one strategy to enable the broader application of DCOP so-
magnitude slower than the fully decentralized approaches. lutions that have varying complexity.
 Acknowledgments Modi, P. J.; Shen, W.-M.; Tambe, M.; and Yokoo, M. 2005.
This work was performed at the Jet Propulsion Laboratory, ADOPT: Asynchronous distributed constraint optimization
California Institute of Technology, under a contract with the with quality guarantees. Artificial Intelligence, 161(1-2):
National Aeronautics and Space Administration. 149–180.
Nag, S.; Li, A. S.; and Merrick, J. H. 2018. Scheduling algo-
References rithms for rapid imaging using agile Cubesat constellations.
Augenstein, S.; Estanislao, A.; Guere, E.; and Blaes, S. Advances in Space Research, 61(3): 891–913.
2016. Optimal scheduling of a constellation of earth- NewSpace. 2023. NewSpace Constellations. [Link]
imaging satellites, for maximal data throughput and efficient [Link]. Accessed: 2023-09-19.
human management. In Proceedings of the Intl Conf. on Au- Nguyen, D. T.; Yeoh, W.; and Lau, H. C. 2013. Distributed
tomated Planning and Scheduling, volume 26, 345–352. Gibbs: A memory-bounded sampling-based DCOP algo-
Boerkoel, J.; Mason, J.; Wang, D.; Chien, S.; and Maillard, rithm. In Intl Conf. on Autonomous Agents and Multi-Agent
A. 2021. An efficient approach for scheduling imaging tasks Systems.
across a fleet of satellites. In Intl Workshop on Planning and Parjan, S.; and Chien, S. A. 2023. Decentralized Observa-
Scheduling for Space. tion Allocation for a Large-Scale Constellation. Journal of
Bonnet, G.; and Tessier, C. 2008. Coordination despite con- Aerospace Information Systems.
strained communications: a satellite constellation case. In Pearce, J. P.; and Tambe, M. 2007. Quality Guarantees on
National Conf. on Control Architectures of Robots, 89–100. k-Optimal Solutions for Distributed Constraint Optimiza-
Eddy, D.; and Kochenderfer, M. J. 2021. A maximum inde- tion Problems. In Intl Joint Conf.s on Artificial Intelligence,
pendent set method for scheduling earth-observing satellite 1446–1451.
constellations. Journal of Spacecraft and Rockets, 58(5): Phillips, S.; and Parra, F. 2021. A case study on auction-
1416–1429. based task allocation algorithms in multi-satellite systems.
Fioretto, F.; Pontelli, E.; and Yeoh, W. 2018. Distributed In AIAA Scitech, 0185.
constraint optimization problems and applications: A sur- Picard, G. 2021. Auction-based and distributed optimization
vey. Journal of Artificial Intelligence Research, 61: 623– approaches for scheduling observations in satellite constel-
698. lations with exclusive orbit portions. arXiv:2106.03548.
Globus, A.; Crawford, J.; Lohn, J.; and Pryor, A. 2004. A Planet. 2023. Our Constellations. [Link]
comparison of techniques for scheduling Earth-observing our-constellations. Accessed: 2023-06-05.
satellites. In Applications of Artificial Intelligence Confer- Schaffer, S.; Chien, S.; Branch, A.; and Hernandez, S.
ence. 2018. Automatic Orbit Selection for a Radio Interferometric
He, L.; Liu, X.; Laporte, G.; Chen, Y.; and Chen, Y. 2018. Spacecraft Constellation. Journal of Aerospace Information
An improved adaptive large neighborhood search algorithm Systems, 15(11): 627–639.
for multiple agile satellites scheduling. Computers & Oper- Shah, V.; Vittaldev, V.; Stepan, L.; and Foster, C. 2019.
ations Research, 100: 12–25. Scheduling the world’s largest earth-observing fleet of
Hirayama, K.; and Yokoo, M. 1997. Distributed partial con- medium-resolution imaging satellites. In Intl Workshop on
straint satisfaction problem. In Principles and Practice of Planning and Scheduling for Space, 156–161.
Constraint Programming, 222–236. Springer. SpaceX. 2023. How Starlink Works. [Link]
Hoang, K. D.; Fioretto, F.; Yeoh, W.; Pontelli, E.; and Zivan, com/technology. Accessed: 2023-10-03.
R. 2018. A large neighboring search schema for multi-agent Squillaci, S.; Pralet, C.; and Roussel, S. 2023. Scheduling
optimization. In Principles and Practice of Constraint Pro- Complex Observation Requests for a Constellation of Satel-
gramming, 688–706. Springer. lites: Large Neighborhood Search Approaches. In Intl Conf.
Joslin, D. E.; and Clements, D. P. 1999. Squeaky wheel on Integration of Constraint Programming, Artificial Intelli-
optimization. Journal of Artificial Intelligence Research, 10: gence, and Operations Research, 443–459. Springer.
353–373. Squillaci, S.; Roussel, S.; and Pralet, C. 2021. Manag-
Lo, M. W. 1999. Satellite-constellation design. Computing ing complex requests for a constellation of Earth observing
in Science Engineering, 1(1): 58–67. satellites. In Intl Workshop on Planning & Scheduling for
Maheswaran, R. T.; Pearce, J. P.; Tambe, M.; et al. 2004. Spaces.
Distributed Algorithms for DCOP: A Graphical-Game- Stranders, R.; Farinelli, A.; Rogers, A.; and Jennings, N.
Based Approach. In PDCS, 432–439. Citeseer. 2009. Decentralised coordination of mobile sensors using
Mahmud, S.; Choudhury, M.; Khan, M. M.; Tran-Thanh, L.; the max-sum algorithm. In Intl Joint Confs. on Artificial In-
and Jennings, N. R. 2019. AED: An anytime evolutionary telligence, 299––304.
dcop algorithm. arXiv:1909.06254. Zhang, W.; Wang, G.; Xing, Z.; and Wittenburg, L. 2005.
Mailler, R.; and Lesser, V. 2004. Solving distributed con- Distributed stochastic search and distributed breakout: prop-
straint optimization problems using cooperative mediation. erties, comparison and applications to constraint optimiza-
In Joint Conf. on Autonomous Agents and Multiagent Sys- tion problems in sensor networks. Artificial Intelligence,
tems, 438–445. 161(1-2): 55–87.