Using Sample-Based Continuation Techniques to Efficiently Compute Subspace Reachable Sets and Pareto Surfaces

Abstract

For a given continuous-time dynamical system with control input constraints and prescribed state boundary conditions, one can compute the reachable set at 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 many problems such as vehicle collision avoidance, operational safety planning, system capability demonstration, and even economic modeling and weather forecasting.

However, computing reachable volumes for general nonlinear systems is very difficult to do both accurately and efficiently. The first contribution of this thesis investigates computational techniques for alleviating the curse of dimensionality by computing reachable sets on subspaces of the full state dimension and computing point solutions for the reachable set boundary. To compute these point solutions, optimal control problems are reduced to initial value problems using continuation methods and then solved.

The sample-based continuation techniques are computationally efficient in that they are easily parallelizable. However, the distribution of samples on the reachable set boundary is not directly controlled. The second contribution presents necessary conditions for distributed computation convergence, as well as necessary conditions for curvature- or uniform coverage-based sampling methods.

Solutions to multi-objective optimization problems are generally defined using a set of feasible solutions such that for any one objective to improve it is necessary for other objectives to degrade. This suggests there is a connection between the two fields with the potential of cross-fertilization of computational techniques and theory. The third contribution explores analytical connections between reachability theory and multi-objective optimization with investigation into properties, constraints, and special cases.