Certified global optimality for multi-flyby asteroid trajectory optimization under practical acceleration: guarantee-preserving refinement, calibrated surrogate feasibility, and tight error bounds

Dynamic programming over a multi-stage reformulation of the multi-flyby asteroid trajectory problem was recently proven to deliver approximate global optima with a computable suboptimality bound of order $N\varepsilon_{\max}$ , where $N$ is the number of legs and $\varepsilon_{\max}$ the worst per-stage surrogate error. The certificate, however, is degraded by every ingredient that makes the method practical: the adaptive step refinement that accelerates computation abandons the global-optimality proof, learned per-leg cost and reachability predictors introduce mission-level infeasibility risk with only a heuristic probability threshold, the worst-case bound is loose (about 4000 m/s on the low-thrust GTOC4 instance), and the exact dynamic program remains exponential in the discretized state dimensions. The open problem is to restore and tighten the certificate end to end: refinement schedules that provably preserve or quantify the loss of the global-optimality guarantee, formal links from per-leg predictor error statistics to mission-level feasibility and suboptimality, and distribution-aware bounds tighter than $N\varepsilon_{\max}$ , at cost that scales to long flyby sequences.

Background

A multi-flyby asteroid mission visits a prescribed sequence of asteroids, measuring each one during a brief encounter; a rendezvous additionally matches position and velocity with the target. The trajectory is steered either by impulsive maneuvers (instantaneous velocity changes, quantified by the total velocity increment $\Delta v$ , the standard proxy for fuel cost) or by low-thrust propulsion (weak continuous thrust over weeks or months, which couples fuel consumption to the spacecraft mass state and to whether later targets can be reached at all — the reachability question). Benchmark instances come from the Global Trajectory Optimization Competitions (GTOC), community contests for multi-asteroid mission design. The design pipeline conventionally splits into a combinatorial search over asteroid sequences and, for a fixed sequence, trajectory refinement — historically via direct or indirect optimal-control methods that converge to local optima, of which the problem has many.

Zhang, Guo, Wu, Baoyin, Li, and Topputo (arXiv 2025; Journal of Guidance, Control, and Dynamics 2026) addressed the fixed-sequence step with a guarantee. They reformulate the optimal control problem with interior-point equality constraints (conditions imposed at the intermediate flyby events, not just at the endpoints) as a multi-stage decision problem over discretized flyby epochs, velocities, and mass, to which Bellman's principle of optimality — the dynamic-programming (DP) property that an optimal path is composed of optimal subpaths — applies. The paper names this chain of formulations explicitly: $P_0$ is the original optimal control problem, $P_1$ the multi-stage decision problem (proven to share the global optimum of $P_0$ ), $P_2$ the discretized version of $P_1$ in which each leg cost is replaced by an approximation and which the dynamic program actually solves, and $P_3$ a stochastic perturbation of $P_1$ under which global optimality of the DP recursion is proven. For each leg, the minimal $\Delta v$ , denoted $g_k$ between flybys $k$ and $k+1$ , is supplied by an approximator: closed-form bi-impulse solutions (two-impulse transfers with an analytically known optimal maneuver split) where available, and neural-network estimators of fuel cost and reachability in the low-thrust case. The framework rigorously proves global optimality of the DP solution over the discretized problem and bounds the gap between the $P_2$ solution and the true continuous ( $P_0$ ) optimum by $N\varepsilon_{\max}$ , with $\varepsilon_{\max}$ the worst error of the per-leg approximation $\tilde g_k$ across all $N$ stages. Applied to GTOC4 (impulsive and low-thrust variants) and GTOC11, it improved on the best known solutions.

The guarantee is, however, exactly what the practical machinery erodes. First, DP over time, three velocity components, and mass is exponential — roughly $N_t^2 N_v^6 N_m^2 N$ operations, where $N_t$ , $N_v$ , and $N_m$ are the numbers of discrete epochs, velocity-grid values per component, and mass values, and $N$ the number of legs — so the paper prunes states near ballistic arcs (unpowered coasting arcs fixed by the classical Lambert two-point boundary-value problem for Keplerian motion) and uses an adaptive step refinement that concentrates discretization where it matters; this acceleration explicitly sacrifices the theoretical global-optimality proof, and nothing is known about when or how badly the adaptive search can miss the global optimum. Second, in the low-thrust case the DP selects paths using predicted leg feasibility; prediction errors can make the selected path infeasible when the true optimal-control problems are solved. The paper mitigates this by demanding a high predicted reachability probability per leg, but provides no formal link between the predictor's error statistics and the mission-level feasibility rate (a remark notes that stochastic DP would give expected-value optimality if errors were unbiased and the error space measurable — a pointer, not a construction). Third, the bound $N\varepsilon_{\max}$ is worst-case and conservative: on the low-thrust GTOC4 instance it evaluates to roughly 4000 m/s, too loose to certify the solution at mission-design tolerances, even though the achieved solution beat the previous best by a wide margin. A 2026 follow-up by largely the same group supplies pretrained neural surrogates for low-thrust cost and reachability with far better accuracy and generality (per-leg mean absolute error near 10 m/s on GTOC4 legs), which shrinks $\varepsilon_{\max}$ empirically but leaves the certificate structure untouched: no per-query error bars, no feasibility guarantee, no tighter bound, and no restoration of the adaptive-refinement guarantee.

Problem Statement

Within the multi-stage dynamic-programming framework of Zhang et al. (JGCD 2026) for fuel-optimal multi-flyby asteroid trajectories under a given flyby sequence, establish an end-to-end certified global optimizer: a method that returns, at tractable computational cost for realistic flyby counts, both a provable suboptimality bound relative to the true continuous optimum and a provable mission-level feasibility guarantee. Concretely, the open components, which jointly serve this objective, are: (i) refinement or pruning schedules for the discretized state space that provably preserve the global-optimality guarantee, or a characterization of when and by how much the adaptive search can miss the global optimum, replacing the current heuristic sacrifice of the certificate for speed; (ii) a formal probabilistic treatment of per-leg surrogate error — cost and reachability predictions — that converts predictor error statistics into guaranteed or calibrated mission-level feasibility and suboptimality statements for the DP-selected path (going beyond the current heuristic high reachability-probability threshold and the undeveloped remark that stochastic dynamic programming gives expected-value optimality under unbiased measurable errors); and (iii) error bounds tighter and more distribution-aware than the worst-case product $N\varepsilon_{\max}$ , whose reported looseness (≈ 4000 m/s on the low-thrust GTOC4 instance) currently prevents the certificate from being decision-relevant at mission-design tolerances. Progress on the exponential scaling of exact DP (the ≈ $N_t^2 N_v^6 N_m^2 N$ cost) is the standing constraint these components must respect: the certificate must not be silently dropped to regain tractability.

References

Zhong Zhang, Xiang Guo, Di Wu, Hexi Baoyin, Junfeng Li, Francesco Topputo, 'Global Optimality in Multi-Flyby Asteroid Trajectory Optimization: Theory and Application Techniques', Journal of Guidance, Control, and Dynamics 49 (2026) 1429-1444, DOI: 10.2514/1.G009335, https://doi.org/10.2514/1.G009335 (preprint arXiv:2508.02904, https://arxiv.org/abs/2508.02904)
Zhong Zhang, Giacomo Acciarini, Dario Izzo, Hexi Baoyin, Francesco Topputo, 'Pretrained Approximators for Low-Thrust Trajectory Cost and Reachability', arXiv:2605.26790 (2026), https://arxiv.org/abs/2605.26790
Zhong Zhang, Niccolò Michelotti, Gonçalo Oliveira Pinho, Yilin Zou, Francesco Topputo, 'Optimal Control and Neural Porkchop Analysis for Low-Thrust Asteroid Rendezvous Mission', Astronautics 1 (1) (2026) 6, DOI: 10.3390/astronautics1010006, https://doi.org/10.3390/astronautics1010006 (preprint arXiv:2508.02920, 2025, https://arxiv.org/abs/2508.02920)
An-Yi Huang, Hong-Xin Shen, Zhao Li, Cong Sun, Chao Sheng, Zheng-Zhong Kuai, 'Global Optimization of Multi-Flyby Trajectories for Multi-Orbital-Plane Constellations Inspection', arXiv:2507.02943 (2025), https://arxiv.org/abs/2507.02943
Zhong Zhang, Nan Zhang, Xiang Guo, Di Wu, Xuan Xie, Jia Yang, Fanghua Jiang, Hexi Baoyin, 'Sustainable Asteroid Mining: On the design of GTOC12 problem and summary of results', Astrodynamics 9 (1) (2025) 3-17, DOI: 10.1007/s42064-024-0199-3, https://doi.org/10.1007/s42064-024-0199-3