CS Paper Radar

Stochastic Multistage Constellation Reconfiguration Problem: Stochastic Dual Dynamic Integer Programming Approach

Brycen D. Pearl, Hang Woon Lee

eess.SY math.OC ·submitted 2026-08-10 15:37 UTC · v1

Abstract

Observation tasking is critical to satellite operations, enabling observation of planetary phenomena, orbital debris monitoring, and space domain awareness. To improve the effectiveness of satellite operations, orbital maneuverability is introduced as a leading-edge concept of operations within constellation reconfigurability for response to dynamic events. Previous investigations regarding constellation reconfigurability consist of deterministic mission environments, in which the formulations consider a priori knowledge of the environment; however, observation objectives inherently involve uncertainty at any given time. As such, scheduling satellite operations must account for uncertainties to ensure adequate observation tasking. In response, we present a stochastic variant of the Multistage Constellation Reconfiguration Problem (MCRP) which is solved using Stochastic Dual Dynamic Integer Programming (SDDiP). We additionally explore other stochastic problem-solving techniques for solution quality comparison. To demonstrate each solution method, two computational experiments with stochastic target properties are conducted. The first concerns random orbital targets, and the second concerns simulated hurricanes. The results of the experiments demonstrate the effectiveness of the SDDiP solution approach over other stochastic problem-solving methods. Overall, the stochastic MCRP accounts for target stochasticity while obeying visible time windows and maneuver feasibility.

Comment
34 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Concurrent Space-Based Observer Placement and Scheduling for Cislunar Space Domain Awareness

eess.SY math.OC ·2026-10-23 ·Dominic K. Amato, Hang Woon Lee
similarity 0.65
Abstract · 41 pages

As interest in cislunar space grows, so does the need for space domain awareness (SDA) capabilities to safely support missions. To enhance cislunar SDA capabilities, the use of space-based observers has been proposed. Prior research has explored optimizing observer placement but has not considered scheduling limitations. We propose a mixed-integer linear programming formulation that concurrently optimizes the placement and scheduling of space-based observers for cislunar SDA. Our work considers three aspects of observer scheduling: sensor tasking, communication, and charging. We utilize a scenario-based approach that generalizes observer placement for unknown targets while applying scheduling constraints to each scenario. However, this problem quickly becomes difficult for commercial solvers to handle as the number of scenarios grows. As an alternative, a column generation approach is employed to introduce well-performing schedules into the problem for each orbital slot. A comparative analysis is performed across multiple instances to evaluate the performance of column generation against that of a commercial solver. A case study is then conducted in which the performance of the observers' placement from the concurrent formulation is tested against a set of validation target sets and compared with the performance of two baselines in which placement and scheduling are performed sequentially.

0.22

Offline Approximate Value Iteration: A Reinforcement Learning Approach for Satellite Constellation Deployment

cs.AI math.OC ·2026-11-02 ·Tristan Leuridan, Yiping Fang, Adam Abdin
top venuehot direction similarity 0.64
Abstract

This paper introduces a reinforcement learning-based approximate dynamic programming approach to optimize the deployment of Walker-type satellite constellations under uncertainties, including launch failures and satellite malfunctions. We formulate the problem as a Markov Decision Process that incorporates low-injection orbit launches, continuous low-thrust orbit raising, and variable satellite loads. We adopt the offline approximate value iteration solution method, using linear function approximation with basis functions and action pruning strategies to substantially reduce the computational and memory requirements for finding optimal decision policies. Preliminary results demonstrate convergence to policies with low expected costs and deployment times, both of which are lower than those of a rolling-horizon baseline, showcasing a novel application of approximate dynamic programming in space logistics.

0.48

A two-stage approach to satellite constellation optimization: classical and QUBO formulations

eess.SY math.OC ·2026-10-01 ·Carlo Novara
similarity 0.61
Abstract · 17 pages, 1 figure, 1 table

The design of satellite constellations for Earth observation requires balancing spatial coverage, revisit time, cost, and operational complexity. This paper considers the problem of designing the orbits of a given number of Low Earth Orbit (LEO) or Very Low Earth Orbit (VLEO) satellites to maximize the spatial and temporal resolution achieved over a prescribed set of ground targets. This kind of problem is inherently nonconvex and possibly combinatorial, making its solution computationally demanding for large constellations and target sets. To address this challenge, we propose a two-stage optimization strategy that separates spatial-coverage design from temporal-resolution optimization, thereby reducing the complexity of the overall problem. Two variants of the method are developed. The first employs continuous decision variables during the spatial-optimization stage, whereas the second discretizes these variables and reformulates the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The latter formulation enables the use of efficient classical QUBO solvers and is directly compatible with quantum-annealing hardware. The proposed framework provides a scalable approach to the design of heterogeneous LEO and VLEO Earth-observation constellations and establishes a pathway for exploiting emerging quantum-optimization technologies in satellite mission design. Preliminary simulation results are presented to demonstrate the effectiveness of the strategy.

0.26

Venusian Radio Occultation Constellation Design and Reconfiguration Problems: A Benders Decomposition Approach

eess.SY math.OC ·2026-10-12 ·David O. Williams Rogers, Trupti P. Gosavi, Hang Woon Lee
similarity 0.60
Abstract · 36 pages

Driven by the scientific value of Venusian atmospheric studies, numerous missions, such as Magellan and Venus Express, have relied on single-spacecraft radio occultation (RO) experiments. Despite their proven success, data throughput is inherently limited by the use of a single transmitter and its relative geometry with respect to Earth-based receivers. Therefore, the literature proposes leveraging a constellation of spacecraft to increase RO measurement opportunities and improve spatial and temporal coverage; however, current efforts impose strict simplifying assumptions that limit their applicability and responsiveness to complex mission narratives. Beyond initial constellation design, evolving mission objectives may require event-based constellation reconfiguration during operations. To address both design and operational needs, we propose two problems formulated as integer linear programs: the RO Constellation Configuration Design Problem and the RO Constellation Reconfiguration Problem. Further, we address the programs' solution-space explosion with a Benders decomposition approach. Numerical experiments show the applicability of our problems for constellation configuration design, tackle the full mission pipeline, transitioning from global atmospheric profiling to on-demand regional profiling above areas of volcanic interest, and show that the Benders decomposition approach efficiently obtains high-quality solutions to large-scale instances.

0.23

Large Language Model-Assisted Adaptive Heuristic Search for Agile Earth Observation Satellite Scheduling

cs.AI cs.CL ·2026-11-03 ·He Wang, Yeye Liu, Ruijie Li, Xuemei Jiang, Junyu Wu +3 more
similarity 0.59
Abstract · 5 pages,4 figures

Agile Earth observation satellites must coordinate imaging tasks within limited observation windows, while accounting for attitude maneuvering and onboard energy constraints. Competition among observation opportunities makes scheduling performance sensitive to the heuristic rules used for task selection. This letter proposes a large language model (LLM)-assisted adaptive heuristic search method for agile Earth observation satellite scheduling. The LLM generates an initial heuristic rule according to the characteristics of the scheduling instance. During the subsequent ant colony search, search performance and scheduling information are fed back to the LLM to refine the heuristic rule. The proposed modifications are evaluated through paired solution constructions before being incorporated into the search process. A unified scheduling procedure determines task selection, satellite assignment, and observation timing under the operational constraints. Experiments on six scheduling scenarios involving 50--200 imaging tasks demonstrate that the proposed method achieves 4.3\%--9.6\% higher mean observation benefit than the strongest baseline.

0.21

Chance-Constrained Belief-Space Maneuver Planning for Autonomous Collision Avoidance Under Uncertainty

cs.RO cs.AI ·2026-09-11 ·Grace Ra Kim, Duncan Eddy, Mykel J. Kochenderfer
published similarity 0.59
Abstract · 19 pages, 5 figures, 3 tables, Advanced Maui Optical and Space Surveillance Technologies (AMOS) Conference 2026

Increasing conjunction frequency in low Earth orbit places growing pressure on spacecraft operators to determine not only whether an encounter requires mitigation, but whether sufficient information is available to commit to a maneuver. This work formulates this information-action tradeoff as a belief-space planning problem for conjunctions between a maneuverable spacecraft and an unmaneuverable secondary object. The planner represents the uncertain orbital states as Gaussian beliefs and uses a chance-constrained belief-space Monte Carlo tree search framework to reason over possible future tracking updates before time of closest approach (TCA). A terminal chance constraint limits the probability of reaching TCA above a prescribed collision-risk threshold, allowing the planner to wait for informative tracking while intervening when deferral becomes too risky. We evaluate the approach on eight historical conjunctions from NASA's Conjunction Assessment Risk Analysis dataset. By varying the secondary-object measurement quality and tracking cadence, we generate a total of 96 distinct evaluation scenarios. Across the evaluated conditions, the planner reaches TCA without maneuvering in approximately 40% of episodes while maintaining no terminal collision-risk violations. In contrast, fixed-time rule-based maneuver policies resolve more encounters without maneuvering when intervention is deferred closer to TCA, but at the expense of increasing terminal risk violations. The fraction of episodes reaching TCA without maneuvering depends strongly on tracking quality and measurement cadence, ranging from 76% under accurate, frequent measurements to approximately 18%-20% under the poorest tracking conditions. These results show that tracking quality and frequency are not only inputs to collision-risk estimation: they can determine when intervention becomes necessary.

0.39

Spacecraft Rendezvous Trajectory Generation with Modular Constraints via Diffusion Model Composition

cs.RO cs.LG ·2026-10-05 ·Mariko A. Storey-Matsutani, Richard Linares
similarity 0.57
Abstract

Emerging mission classes such as on-orbit servicing, satellite inspection, and active debris removal require trajectory design methods that are adaptable to a variety of mission scenarios. We present a diffusion-based trajectory generation approach for rendezvous and proximity operations (RPO) that enables flexible configuration of mission constraints. First, individual energy-based diffusion models are trained to satisfy distinct constraints such as approach cone and sensor line-of-sight from a set of optimized trajectories. Then, at inference time, the learned energy models can be composed with one another, or with an analytically defined energy field, to enforce specific constraint combinations. We validate this framework with the composition of a learned approach cone model and a learned sensor line-of-sight model, as well as a learned approach cone model and synthetic obstacle avoidance model, both of which yield constraint satisfaction rates that are within 1 percentage point of the single-constraint models or higher. These results indicate that our compositional diffusion framework can provide a modular approach to RPO trajectory design and enable reconfiguration for new constraint combinations without requiring model retraining.

0.30

Maximizing Detection Probability in UAV Search Missions using Random-Key Optimizers

cs.NE cs.RO ·2026-11-09 ·Antonio Dantas, Elcio Shiguemori, Antonio Chaves
similarity 0.57
Abstract · 21 pages, 3 figures

This paper focuses on the stochastic and real-time constraints of Unmanned Aerial Vehicle (UAV) path planning in Search and Rescue (SAR) missions. We introduce a configurable data-driven and intelligent routing architecture that combines a closed-loop probability update with the Random-Key Optimizers (RKO). Our problem is mathematically modeled as a dynamic probabilistic variant of the Open Vehicle Routing Problem (OVRP), enabling the solver to switch adaptively between two objectives, thereby balancing probability maximization and resource minimization. The framework degrades elegantly under noisy priors but not under biased ones: a systematically biased map performs about half as well as flying with no prior at all. Computational tests show that the proposed scheme is scalable and competitive with single-path scenarios in terms of solution performance and serves as a strong decision guide for intelligent planning in SAR operations in unstable environments

0.25