Steve Chien

AAMAS Conference 2026 Conference Paper

Large-Scale Continual Scheduling and Execution for Dynamic Distributed Satellite Constellation Observation Allocation

• Itai Zilberstein
• Steve Chien

The size and capabilities of Earth-observing satellite constellations are rapidly increasing. Leveraging distributed onboard control, we can enable novel time-sensitive measurements and responses. However, deploying autonomy to large multiagent satellite systems necessitates algorithms with efficient computation and communication. We tackle this challenge and propose new, online algorithms for large-scale dynamic distributed constraint optimization problems (DDCOP). We present the Dynamic Multi-Satellite Constellation Observation Scheduling Problem (DCOSP), a new formulation of DDCOPs that models integrated scheduling and execution. We construct an omniscient offline algorithm to compute the novel optimality condition of DCOSP and present the Dynamic Incremental Neighborhood Stochastic Search (D-NSS) algorithm, an incomplete online decomposition-based DDCOP approach. We show through simulation that D-NSS converges to near-optimal solutions and outperforms DDCOP baselines in terms of solution quality, computation time, and message volume. Our work forms the foundation of the largest in-space demonstration of distributed multiagent AI to date: the NASA FAME mission.

JAIR Journal 2025 Journal Article

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

• Itai Zilberstein
• Ananya Rao
• Matthew Salis
• Steve Chien

Deploying multi-satellite constellations for Earth observation requires coordinating potentially hundreds of spacecraft. With increasing onboard capability for autonomy, we can view the constellation as a multi-agent system (MAS) and employ decentralized scheduling solutions. We analyze the multi-satellite constellation observation scheduling problem (COSP) and formulate it as a distributed constraint optimization problem (DCOP). COSP requires scalable inter-agent communication and computation and consists of millions of variables which, coupled with the assumptions and structure, make existing DCOP algorithms inadequate for this application. We develop a scheduling approach that employs a carefully constructed heuristic, referred to as the Geometric Neighborhood Decomposition (GND) heuristic, to decompose the global DCOP into sub-problems to enable the application of DCOP techniques. We present the Neighborhood Stochastic Search (NSS) algorithm, a decentralized algorithm to effectively solve COSP and other large-scale distributed problems, using decomposition. The experiments confirm the efficacy of the approach against baseline algorithms, and we discuss the generality of NSS, GND, and properties of COSP to other domains.

AAMAS Conference 2025 Conference Paper

Planning, Scheduling, and Execution on the Moon: The CADRE Technology Demonstration Mission

• Gregg Rabideau
• Joseph Russino
• Andrew Branch
• Nihal Dhamani
• Tiago Stegun Vaquero
• Steve Chien
• Jean-Pierre de la Croix
• Federico Rossi

NASA’s Cooperative Autonomous Distributed Robotic Exploration (CADRE) mission, slated for flight to the Moon’s Reiner Gamma region in 2025/2026, is designed to demonstrate multi-agent autonomous exploration of the Lunar surface and sub-surface. A team of three robots and a base station will autonomously explore a region near the lander, collecting the data required for 3D reconstruction of the surface with no human input; and then autonomously perform distributed sensing with multi-static ground penetrating radars (GPR), driving in formation while performing coordinated radar soundings to create a map of the subsurface. At the core of CADRE’s software architecture is a novel autonomous, distributed planning, scheduling, and execution (PS&E) system. The system coordinates the robots’ activities, planning and executing tasks that require multiple robots’ participation while ensuring that each individual robot’s thermal and power resources stay within prescribed bounds, and respecting ground-prescribed sleep-wake cycles. The system uses a centralized-planning, distributed-execution paradigm, and a leader election mechanism ensures robustness to failures of individual agents. In this paper, we describe the architecture of CADRE’s PS&E system; discuss its design rationale; and report on verification and validation (V&V) testing of the system on CADRE’s hardware in preparation for deployment on the Moon.

JAIR Journal 2023 Journal Article

How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy

• Natalia Ponomareva
• Hussein Hazimeh
• Alex Kurakin
• Zheng Xu
• Carson Denison
• H. Brendan McMahan
• Sergei Vassilvitskii
• Steve Chien

Machine Learning (ML) models are ubiquitous in real-world applications and are a constant focus of research. Modern ML models have become more complex, deeper, and harder to reason about. At the same time, the community has started to realize the importance of protecting the privacy of the training data that goes into these models. Differential Privacy (DP) has become a gold standard for making formal statements about data anonymization. However, while some adoption of DP has happened in industry, attempts to apply DP to real world complex ML models are still few and far between. The adoption of DP is hindered by limited practical guidance of what DP protection entails, what privacy guarantees to aim for, and the difficulty of achieving good privacy-utility-computation trade-offs for ML models. Tricks for tuning and maximizing performance are scattered among papers or stored in the heads of practitioners, particularly with respect to the challenging task of hyperparameter tuning. Furthermore, the literature seems to present conflicting evidence on how and whether to apply architectural adjustments and which components are “safe” to use with DP. In this survey paper, we attempt to create a self-contained guide that gives an in-depth overview of the field of DP ML. We aim to assemble information about achieving the best possible DP ML model with rigorous privacy guarantees. Our target audience is both researchers and practitioners. Researchers interested in DP for ML will benefit from a clear overview of current advances and areas for improvement. We also include theory-focused sections that highlight important topics such as privacy accounting and convergence. For a practitioner, this survey provides a background in DP theory and a clear step-by-step guide for choosing an appropriate privacy definition and approach, implementing DP training, potentially updating the model architecture, and tuning hyperparameters. For both researchers and practitioners, consistently and fully reporting privacy guarantees is critical, so we propose a set of specific best practices for stating guarantees. With sufficient computation and a sufficiently large training set or supplemental nonprivate data, both good accuracy (that is, almost as good as a non-private model) and good privacy can often be achievable. And even when computation and dataset size are limited, there are advantages to training with even a weak (but still finite) formal DP guarantee. Hence, we hope this work will facilitate more widespread deployments of DP ML models.

IJCAI Conference 2022 Conference Paper

An Efficient Approach to Data Transfer Scheduling for Long Range Space Exploration

• Emmanuel Hebrard
• Christian Artigues
• Pierre Lopez
• Arnaud Lusson
• Steve Chien
• Adrien Maillard
• Gregg Rabideau

Long range space missions, such as Rosetta, require robust plans of data-acquisition activities and of the resulting data transfers. In this paper we revisit the problem of assigning priorities to data transfers in order to maximize safety margin of onboard memory. We propose a fast sweep algorithm to verify the feasibility of a given priority assignment and we introduce an efficient exact algorithm to assign priorities on a single downlink window. We prove that the problem is NP-hard for several windows, and we propose several randomized heuristics to tackle the general case. Our experimental results show that the proposed approaches are able to improve the plans computed for the real mission by the previously existing method, while the sweep algorithm yields drastic accelerations.

EAAI Journal 2022 Journal Article

Romie: A domain-independent tool for computer-aided robust operations management

• Michael Saint-Guillain
• Jonas Gibaszek
• Tiago Vaquero
• Steve Chien

Romie is a decision support tool based on AI’s latest advances in the domain of robust scheduling. Unlike all existing systems, the tool allows to (i) visually model the operational problem and context entirely (ii) optimize to find near-optimal schedules while taking uncertainty into account and (iii) deal with a combination of various key performance indicators (KPIs). It comes with a web user interface. Part or all of the modelled activities may be associated to random variables describing their stochastic durations, in order to produce schedules that are robust w. r. t. temporal uncertainty. Hence, depending on the pursued KPIs, the schedules maximize a combination of the following terms: the probability of satisfying the problem constraints, the expected return/efficiency, the expected outcome quality, and even the operators’ wellness by minimizing its expected extra-hours. Initially developed for spatial exploration and demonstration in the context of Mars analogue missions (i. e. missions on Earth that simulate condition and aspects of Mars missions), this versatile tool is here applied to operations management in both biotechnology manufacturing and robots parametrization in a cave exploration context.

ICML Conference 2021 Conference Paper

Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates

• Steve Chien
• Prateek Jain 0002
• Walid Krichene
• Steffen Rendle
• Shuang Song 0001
• Abhradeep Thakurta
• Li Zhang 0001

We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method that achieves: i) (nearly) optimal sample complexity for matrix completion (in terms of number of items, users), and ii) the best known privacy/utility trade-off both theoretically, as well as on benchmark data sets. In particular, we provide the first global convergence analysis of ALS with noise introduced to ensure DP, and show that, in comparison to the best known alternative (the Private Frank-Wolfe algorithm by Jain et al. (2018)), our error bounds scale significantly better with respect to the number of items and users, which is critical in practical problems. Extensive validation on standard benchmarks demonstrate that the algorithm, in combination with carefully designed sampling procedures, is significantly more accurate than existing techniques, thus promising to be the first practical DP embedding model.

AAAI Conference 2021 Conference Paper

Tempered Sigmoid Activations for Deep Learning with Differential Privacy

• Nicolas Papernot
• Abhradeep Thakurta
• Shuang Song
• Steve Chien
• Úlfar Erlingsson

Because learning sometimes involves sensitive data, machine learning algorithms have been extended to offer differential privacy for training data. In practice, this has been mostly an afterthought, with privacy-preserving models obtained by re-running training with a different optimizer, but using the model architectures that already performed well in a nonprivacy-preserving setting. This approach leads to less than ideal privacy/utility tradeoffs, as we show here. To improve these tradeoffs, prior work introduces variants of differential privacy that weaken the privacy guarantee proved to increase model utility. We show this is not necessary and instead propose that utility be improved by choosing activation functions designed explicitly for privacy-preserving training. A crucial operation in differentially private SGD is gradient clipping, which along with modifying the optimization path (at times resulting in not-optimizing a single objective function), may also introduce both significant bias and variance to the learning process. We empirically identify exploding gradients arising from ReLU may be one of the main sources of this. We demonstrate analytically and experimentally how a general family of bounded activation functions, the tempered sigmoids, consistently outperform the currently established choice: unbounded activation functions like ReLU. Using this paradigm, we achieve new state-of-the-art accuracy on MNIST, FashionMNIST, and CIFAR10 without any modification of the learning procedure fundamentals or differential privacy analysis. While the changes we make are simple in retrospect, the simplicity of our approach facilitates its implementation and adoption to meaningfully improve state-of-the-art machine learning while still providing strong guarantees in the original framework of differential privacy.

IJCAI Conference 2020 Conference Paper

Robustness Computation of Dynamic Controllability in Probabilistic Temporal Networks with Ordinary Distributions

• Michael Saint-Guillain
• Tiago Stegun Vaquero
• Jagriti Agrawal
• Steve Chien

Most existing works in Probabilistic Simple Temporal Networks (PSTNs) base their frameworks on well-defined probability distributions. This paper addresses on PSTN Dynamic Controllability (DC) robustness measure, i. e. the execution success probability of a network under dynamic control. We consider PSTNs where the probability distributions of the contingent edges are ordinary distributed (e. g. non-parametric, non-symmetric). We introduce the concepts of dispatching protocol (DP) as well as DP-robustness, the probability of success under a predefined dynamic policy. We propose a fixed-parameter pseudo-polynomial time algorithm to compute the exact DP-robustness of any PSTN under NextFirst protocol, and apply to various PSTN datasets, including the real case of planetary exploration in the context of the Mars 2020 rover, and propose an original structural analysis.

IJCAI Conference 2015 Conference Paper

Activity-Based Scheduling of Science Campaigns for the Rosetta Orbiter

• Steve Chien
• Gregg Rabideau
• Daniel Tran
• Martina Troesch
• Joshua Doubleday
• Federico Nespoli
• Miguel Perez Ayucar
• Marc Costa Sitja

Rosetta is a European Space Agency (ESA) cornerstone mission that entered orbit around the comet 67P/Churyumov-Gerasimenko in August 2014 and will escort the comet for a 1. 5 year nominal mission offering the most detailed study of a comet ever undertaken by humankind. The Rosetta orbiter has 11 scientific instruments (4 remote sensing) and the Philae lander to make complementary measurements of the comet nucleus, coma (gas and dust), and surrounding environment. The ESA Rosetta Science Ground Segment has developed a science scheduling system that includes an automated scheduling capability to assist in developing science plans for the Rosetta Orbiter. While automated scheduling is a small portion of the overall Science Ground Segment (SGS) as well as the overall scheduling system, this paper focuses on the automated and semiautomated scheduling software (called ASPEN- RSSC) and how this software is used.

AAMAS Conference 2012 Conference Paper

Decentralized Active Robotic Exploration and Mapping for Probabilistic Field Classification in Environmental Sensing

• Kian Hsiang Low
• Jie Chen
• John Dolan
• Steve Chien
• David Thompson

A central problem in environmental sensing and monitoring is to classify/label the hotspots in a large-scale environmental field. This paper presents a novel \emph{decentralized active robotic exploration} (DARE) strategy for probabilistic classification/labeling of hotspots in a \emph{Gaussian process} (GP)-based field. In contrast to existing state-of-the-art exploration strategies for learning environmental field maps, the time needed to solve the DARE strategy is independent of the map resolution and the number of robots, thus making it practical for in situ, real-time active sampling. Its exploration behavior exhibits an interesting formal trade-off between that of boundary tracking until the hotspot region boundary can be accurately predicted and wide-area coverage to find new boundaries in sparsely sampled areas to be tracked. We provide a theoretical guarantee on the active exploration performance of the DARE strategy: under reasonable conditional independence assumption, we prove that it can optimally achieve two formal cost-minimizing exploration objectives based on the misclassification and entropy criteria. Importantly, this result implies that the uncertainty of labeling the hotspots in a GP-based field is greatest at or close to the hotspot region boundaries. Empirical evaluation on real-world plankton density and temperature field data shows that, subject to limited observations, DARE strategy can achieve more superior classification of hotspots and time efficiency than state-of-the-art active exploration strategies.

TIST Journal 2012 Journal Article

Surface Sulfur Detection via Remote Sensing and Onboard Classification

• Lukas Mandrake
• Umaa Rebbapragada
• Kiri L. Wagstaff
• David Thompson
• Steve Chien
• Daniel Tran
• Robert T. Pappalardo
• Damhnait Gleeson

Orbital remote sensing provides a powerful way to efficiently survey targets such as the Earth and other planets and moons for features of interest. One such feature of astrobiological relevance is the presence of surface sulfur deposits. These deposits have been observed to be associated with microbial activity at the Borup Fiord glacial springs in Canada, a location that may provide an analogue to other icy environments such as Europa. This article evaluates automated classifiers for detecting sulfur in remote sensing observations by the hyperion spectrometer on the EO-1 spacecraft. We determined that a data-driven machine learning solution was needed because the sulfur could not be detected by simply matching observations to sulfur lab spectra. We also evaluated several methods (manual and automated) for identifying the most relevant attributes (spectral wavelengths) needed for successful sulfur detection. Our findings include (1) the Borup Fiord sulfur deposits were best modeled as containing two sub-populations: sulfur on ice and sulfur on rock; (2) as expected, classifiers using Gaussian kernels outperformed those based on linear kernels, and should be adopted when onboard computational constraints permit; and (3) Recursive Feature Elimination selected sensible and effective features for use in the computationally constrained environment onboard EO-1. This study helped guide the selection of algorithm parameters and configuration for the classification system currently operational on EO-1. Finally, we discuss implications for a similar onboard classification system for a future Europa orbiter.

TIST Journal 2012 Journal Article

Using Clustering and Metric Learning to Improve Science Return of Remote Sensed Imagery

• David S. Hayden
• Steve Chien
• David R. Thompson
• Rebecca Castaño

Current and proposed remote space missions, such as the proposed aerial exploration of Titan by an aerobot, often can collect more data than can be communicated back to Earth. Autonomous selective downlink algorithms can choose informative subsets of data to improve the science value of these bandwidth-limited transmissions. This requires statistical descriptors of the data that reflect very abstract and subtle distinctions in science content. We propose a metric learning strategy that teaches algorithms how best to cluster new data based on training examples supplied by domain scientists. We demonstrate that clustering informed by metric learning produces results that more closely match multiple scientists’ labelings of aerial data than do clusterings based on random or periodic sampling. A new metric-learning strategy accommodates training sets produced by multiple scientists with different and potentially inconsistent mission objectives. Our methods are fit for current spacecraft processors (e.g., RAD750) and would further benefit from more advanced spacecraft processor architectures, such as OPERA.

STOC Conference 2011 Conference Paper

Almost settling the hardness of noncommutative determinant

• Steve Chien
• Prahladh Harsha
• Alistair Sinclair
• Srikanth Srinivasan 0001

In this paper, we study the complexity of computing the determinant of a matrix over a noncommutative algebra. In particular, we ask the question: "Over which algebras is the determinant easier to compute than the permanent?" Towards resolving this question, we show the following results for noncommutative determinant computation: [Hardness] Computing the determinant of an n x n matrix whose entries are themselves 2 x 2 matrices over any field of zero or odd characteristic is as hard as computing the permanent over the field. This extends the recent result of Arvind and Srinivasan, which required the entries to be matrices of dimension linear in n. [Easiness] The determinant of an n x n matrix whose entries are themselves d x d upper triangular matrices can be computed in poly(n d ) time. Combining the above with the decomposition theorem for finite dimensional algebras (and in particular exploiting the simple structure of 2 x 2 matrix algebras), we can extend the above hardness and easiness statements to more general algebras as follows. Let A be a finite dimensional algebra over a finite field of odd characteristic with radical R(A). [Hardness] If the quotient A/R(A) is noncommutative, then computing the determinant over the algebra A is as hard as computing the permanent. [Easiness] If the quotient A/R(A) is commutative, and furthermore R(A) has nilpotency index d (i.e., d is the smallest integer such that R(A) d =0), then there exists a poly(n d )-time algorithm that computes determinants over the algebra A. In particular, for any constant dimensional algebra A over a finite field of odd characteristic, since the nilpotency index of R(A) is at most a constant, we have the following dichotomy theorem: if A/R(A) is commutative then efficient determinant computation is possible, and otherwise determinant is as hard as permanent.

IS Journal 2010 Journal Article

Using Onboard Clustering to Summarize Remotely Sensed Imagery

• David S Hayden
• Steve Chien
• David R Thompson
• Rebecca Castano

Many current and future NASA missions are capable of collecting enormous amounts of data, of which only a small portion can be transmitted to Earth. Communications are limited due to distance, visibility constraints, and competing mission downlinks. Long missions and high resolution, multispectral imaging devices easily produce data exceeding the available bandwidth. As an example, the HiRISE camera aboard the Mars Reconnaissance Orbiter produces images of up to 16. 4 Gbits in data volume but downlink bandwidth is limited to 6 Mbits per second (Mbps).

IS Journal 2009 Journal Article

Onboard Science Processing Concepts for the HyspIRI Mission

• Steve Chien
• Dorothy Silverman
• Ashley Gerard Davies
• Daniel Mandl

This paper presents the operational concept for onboard processing for the HysIRI mission which is an Earth observing mission that includes both thermal infrared instrument and a hyperspectral visible/shortwave infrared instrument, and that is being considered for launch in the next decade. This article describes the potential application of AI techniques for the HyspIRI mission-for both onboard processing and ground-based, automated mission planning.

SODA Conference 2007 Conference Paper

Convergence to approximate Nash equilibria in congestion games

• Steve Chien
• Alistair Sinclair

AAAI Conference 2006 Conference Paper

Integrated AI in Space: The Autonomous Sciencecraft on Earth Observing One

• Steve Chien

The Earth Observing One spacecraft has been under the control of AI software for several years – experimentally since 2003 and since November 2004 as the primary operations system. This software includes: model-based planning and scheduling, procedural execution, and event detection software learned by support vector machine (SVM) techniques. This software has enabled a 100x increase in the mission science return per data downlinked and a >$1M/year reduction in operations costs. In this paper we discuss the AI software used, the impact of the software, and lessons learned with implications for future AI research.

SODA Conference 2004 Conference Paper

A determinant-based algorithm for counting perfect matchings in a general graph

• Steve Chien

FOCS Conference 2004 Conference Paper

Algebras with Polynomial Identities and Computing the Determinant

• Steve Chien
• Alistair Sinclair

Nisan (1991) proved an exponential lower bound on the size of an algebraic branching program (ABP) that computes the determinant of a matrix in the non-commutative "free algebra" setting, in which there are no non-trivial relationships between the matrix entries. By contrast, when the matrix entries commute there are polynomial size ABPs for the determinant. This paper extends Nisan's result to a much wider class of non-commutative algebras, including all non-trivial matrix algebras over any field of characteristic 0, group algebras of all non-abelian finite groups over algebraically closed fields of characteristic 0, the quaternion algebra and the Clifford algebras. As a result, we obtain more compelling evidence for the essential role played by commutativity in the efficient computation of the determinant. The key to our approach is a characterization of non-commutative algebras by means of the polynomial identities that they satisfy. Extending Nisan's lower bound framework, we find that any reduction in complexity compared to the free algebra must arise from the ability of the identities to reduce the rank of certain naturally associated matrices. Using results from the theory of algebras with polynomial identities, we are able to show that none of the identities of the above classes of algebras is able to achieve such a rank reduction.

AAMAS Conference 2004 Conference Paper

The Earth Observing One Autonomous Science Agent

• Steve Chien

STOC Conference 2002 Conference Paper

Clifford algebras and approximating the permanent

• Steve Chien
• Lars Eilstrup Rasmussen
• Alistair Sinclair

(MATH) We study approximation algorithms for the permanent of an n x n (0,1) matrix A based on the following simple idea: obtain a random matrix B by replacing each 1-entry of A independently by ± e , where e is a random basis element of a suitable algebra; then output |det( B )| 2 . This estimator is always unbiased, but it may have exponentially large variance. In our first main result we show that, if we take the algebra to be a Clifford algebra of dimension polynomial in n , then we get an estimator with small variance. Hence only a constant number of trials suffices to estimate the permanent to good accuracy. The idea of using Clifford algebras is a natural extension of earlier work by Godsil and Gutman, Karmarkar et al. , and Barvinok, who used the real numbers, complex numbers and quaternions respectively.(MATH) The above result implies that, in principle, this approach gives a fully-polynomial randomized approximation scheme for the permanent, provided |det( B )| 2 can be efficiently computed in the Clifford algebras. Since these algebras are non-commutative it is not clear how to do this. However, our second main result shows how to compute in polynomial time an estimator with the same mean and variance over the 4-dimensional algebra (which is the quaternions, and is non-commutative); in addition to providing some hope that the computations can be performed in higher dimensions, this quaternion algorithm provides an exponential improvement in the variance over that of the 2-dimensional complex version studied by Karmarkar et al .

AAMAS Conference 2002 Conference Paper

The Techsat-21 Autonomous Science Agent

• Steve Chien
• Robert Sherwood
• Rebecca Castano
• Brian Williams
• Paul Zetocha
• Pat Capaellare

AAAI Conference 1999 Conference Paper

An Integrated System for Multi-Rover Scientific Exploration

• Tara Estlin
• Alexander Gray
• Tobias Mann
• Gregg Rabideau
• Rebecca Castaño
• Steve Chien
• Eric Mjolsness
• Jet Propulsion Laboratory

This paper describes an integrated system for coordinating multiple rover behavior with the overall goal of collecting planetary surface data. TheMulti- P~overIntegrated Science UnderstandingSystemcombines concepts from machine learning with planning and scheduling to perform autonomous scientific exploration by cooperating rovers. Theintegrated system utilizes a novel machinelearning clustering component to analyze science data and direct newscience activities. Aplanning and scheduling systemis employedto generate rover plans for achievingscience goals andto coordinate activities amongrovers. Wedescribe each of these components and discuss someof the key integration issues that arose during developmentand influenced both systemdesign and performance.

NeurIPS Conference 1997 Conference Paper

On Efficient Heuristic Ranking of Hypotheses

• Steve Chien
• Andre Stechert
• Darren Mutz

This paper considers the problem of learning the ranking of a set of alternatives based upon incomplete information (e. g. , a limited number of observations). We describe two algorithms for hypoth(cid: 173) esis ranking and their application for probably approximately cor(cid: 173) rect (PAC) and expected loss (EL) learning criteria. Empirical results are provided to demonstrate the effectiveness of these rank(cid: 173) ing procedures on both synthetic datasets and real-world data from a spacecraft design optimization problem.