Computationally Tractable Reachability Subspace Surfaces Applied to Space Operations

For a given continuous-time dynamical system with control input constraints and pre- scribed state boundary conditions, one can compute the reachable set for a specified time horizon. Forward reachable sets contain all states that can be reached using a feasible control policy at the specified time horizon. Alternatively, backwards reachable sets contain all initial states that can reach the prescribed state boundary condition using a feasible control policy at the specified time horizon. The computation of reachable sets has been applied to problems such as vehicle collision avoidance, operational safety planning, system capability demonstration, economic modeling, and weather forecasting. While numerous methods have been developed to compute reachable sets, these methods generally make sacrifices in accuracy and computational demand due to considerations such as system dynamics, geometric representation of the sets, and dimensional scalability. The most dimensionally scalable methods use geometric objects such as polytopes, zonotopes, ellipsoids, and support functions with linear assumptions to compute approximations of the reachable set. On the other hand, Hamilton-Jacobi-Bellman reachability formulations are the most general in terms of system dynamics and geometric representation, but suffer from the curse of dimensionality and most are computationally intractable for high-dimensional systems. The first contribution of this work presents a novel method for computing forward/backwards reachable sets/tubes for continuous time nonlinear dynamic systems by efficiently solving for samples of the reachable set boundary using optimal control and continuation methods. This technique is a compromise between the accuracy and system generality of the Hamilton-Jacobi-Bellman methods with the speed and dimensional scalability of the geometric set-based methods. Furthermore, dimensionally-driven costs can be significantly reduced by only computing projections of the reachable set onto user-specified state dimensions. As the reachable set boundaries are described using independent point solutions, the evolution of these reachable sets over time results in sparse and dense collections of point solutions. The second contribution of this work presents analytic results necessary to prove distributed computation convergence, as well as necessary conditions for curvature- or uniform coverage-based sampling methods. For curvature-based sampling, support functions are used to identify regions of the reachable set boundary with high curvature. For distance- based sampling, the proposed approach uses distributed control methods by treating each point solution as a decentralized agent and solving the surface coverage problem. Furthermore, by judiciously spawning additional point solutions, it’s possible to increase the sampling uniformity of the reachable set boundary. The third contribution of this work draws connections between reachability theory and multi-objective optimization. Both reachability and multi-objective optimization problems search for surfaces in objective space satisfying the necessary conditions of optimality. Furthermore, reachability surfaces and pareto-optimal surfaces are both sets of extremal solutions that optimize some objective function. This suggests a connection between the two fields with the potential of cross-fertilization of computational techniques and theory. Finally, a major contribution of this work is in the development and creation of the Sampled Continuation Reachability (SCoRe) software library developed in Python. This tool contains efficient implementations of the theory and algorithms from this work.