Sparse Single-Use Thruster Selection for Control Moment Tracking Using a Depth-First Branch-and-Bound Algorithm

In high-altitude interception, low atmospheric density limits the effectiveness of aerodynamic control, making thruster-based attitude control essential. In systems using single-use impulse-type lateral thrusters, each actuator can be fired only once, generates a fixed thrust magnitude, and is subject to a limit on the number of simultaneously active thrusters. Therefore, selecting an appropriate set of thrusters to track a desired control moment can be formulated as a cardinality-constrained combinatorial optimization problem. This paper proposes a depth-first search (DFS)-based branch-and-bound algorithm for sparse thruster selection. The objective is to minimize the tracking error between the generated and desired control moments while penalizing the number of active thrusters. To improve computational efficiency, thrusters are ordered by moment magnitude, and a problem-specific lower bound is derived from the residual moment and an upper bound on the achievable contribution of the remaining thrusters. This bound enables effective pruning of unpromising branches. The search space is further reduced by reformulating the problem using symmetric thruster pairs that generate opposing moments. Numerical results show that the proposed method achieves accurate moment tracking while significantly reducing computation time compared with the exact mixed-integer quadratic programming (MIQP) benchmark. Mixed-integer linear programming (MILP) is also included as an additional mixed-integer linear surrogate comparison.