Incremental Simplicial Trajectory Replanning (ISTR): Kinodynamic Search for Collision-Free Spacecraft Relative Motion*

Collision-free relative motion planning for spacecraft in uncertain local orbital environments is critical for on-orbit servicing, inspection, and collision risk mitigation. Yet, existing graph- and tree-based planners typically restrict trajectory propagation to discrete connections, with guarantees tied to the maintained graph or sample set. This study proposes incremental simplicial trajectory replanning (ISTR*) with Directional Action-front Recursion (DAR) as its search core. DAR propagates arrival costs over directed state–time action domains and retains the realizing controls to construct dynamically feasible trajectories through continuous joining states. Based on the target- and time-indexed corrected-dynamics inferred-control (CDIC) posterior regions, the probabilistic occupancy of non-cooperative objects is modeled. Each posterior update modifies action admissibility and reopens the dependent search records. The theoretical analysis establishes finite-model feasibility and optimality, fixed-instance asymptotic optimality under feasible recovery and vanishing-error refinement, and probabilistic completeness for stochastic refinement. Numerical experiments demonstrate feasible trajectory recovery under updated collision constraints. The primary orbital experiments achieve mission-completion rates of at least 85%; active reoptimization reduces the median final executed cost by 55.9% on tasks completed by both policy configurations.