project image or logo
Image courtesy European Space Agency source

Background

Worldwide, there is an explosion of information sources relevant to environmental monitoring. Ground based sensors are being deployed at an incredible rate, and their data is more easily accessible via the Internet of Things (IoT). This explosion of networked sensors even extends to space, where traditional and New Space actors have deployed worldwide monitoring assets such as Terra and Aqua, Suomi-NPP, Sentinel, and Planet’s Dove, Skysat, and other constellations (with over 100 spacecraft).

With many potential information sources and space assets come two distinct challenges: combining the many information sources to track complex spatiotemporal science phenomena and tasking the large set of space assets with varying orbits, costs, and capabilities.

Technology

Diagram on information scope
Graphic of information shared among agents in the various algorithm types

In large-scale constellations, distributed coordination methods allow users to moderate the amount of information shared among agents when coordinating on request allocation. Compared to centralized approaches, they do so without requiring a single agent to manage state for all others, allowing computation to be parallelized.

We describe novel distributed Artificial Intelligence/Multi Agent algorithms to allocate observations in a constellation and compare their performance to centralized and highly distributed algorithms using realistic problem and orbit distributions. Our methods are based on algorithms for Distributed Constraint Optimization like Maximum Gain Messaging (MGM) and Distributed Stochastic Algorithm (DSA) [Fioretto et al. 2018].

agent communication
Graphic visualizing inter-agent communication during scheduling in a single iteration of the Broadcast Decentralized algorithms

In particular, we developed two types of Broadcast Decentralized (BD) algorithms, BD Request Satisfaction and BD Contention that offer a less computationally intensive, heuristic search-based approach to the problem of observation request allocation for large-scale satellite constellations. We aim to maximize the number of requests satisfied by agent observations and minimize the number of future requests agents cannot observe due to data volume or slew constraints.

Ferdinando Fioretto, Enrico Pontelli, and William Yeoh. 2018. Distributed Constraint Optimization Problems and Applications: A Survey. Journal of Artificial Intelligence Research 61, (March 2018), 623–698. DOI:https://doi.org/10.1613/jair.5565

Impact

Preliminary analysis on a request allocation problem involving thousands of observation requests distributed among hundreds of satellites shows the promise of our Distributed Constraint Optimization-based algorithms to search for quick, approximate solutions to the large-scale constellation request allocation problem with low data volume for agent coordination.

Status

Early prototyping of algorithms began in 2021. Efforts to evaluate and generalize application of Broadcast Decentralized algorithms have followed.

Publications

Team

Steve Chien
Shreya Parjan
Ryan Harrod

Sponsors

Earth Science Technology Office