Matthew R. Kirchner

Matthew R. Kirchner, Robert Mar, Gary Hewer et al.

Presented is a new method for calculating the time-optimal guidance control for a multiple vehicle pursuit-evasion system. A joint differential game of k pursuing vehicles relative to the evader is constructed, and a Hamilton-Jacobi-Isaacs (HJI) equation that describes the evolution of the value function is formulated. The value function is built such that the terminal cost is the squared distance from the boundary of the terminal surface. Additionally, all vehicles are assumed to have bounded controls. Typically, a joint state space constructed in this way would have too large a dimension to be solved with existing grid-based approaches. The value function is computed efficiently in high-dimensional space, without a discrete grid, using the generalized Hopf formula. The optimal time-to-reach is iteratively solved, and the optimal control is inferred from the gradient of the value function.

Matthew R. Kirchner, Gary Hewer, Jerome Darbon et al.

Presented is a method for efficient computation of the Hamilton-Jacobi (HJ) equation for time-optimal control problems using the generalized Hopf formula. Typically, numerical methods to solve the HJ equation rely on a discrete grid of the solution space and exhibit exponential scaling with dimension. The generalized Hopf formula avoids the use of grids and numerical gradients by formulating an unconstrained convex optimization problem. The solution at each point is completely independent, and allows a massively parallel implementation if solutions at multiple points are desired. This work presents a primal-dual method for efficient numeric solution and presents how the resulting optimal trajectory can be generated directly from the solution of the Hopf formula, without further optimization. Examples presented have execution times on the order of milliseconds and experiments show computation scales approximately polynomial in dimension with very small high-order coefficients.

Matthew R. Kirchner, Eddie Ball, Jacques Hoffler et al.

We present a numeric method to compute the safe operating flight conditions for a helicopter such that we can ensure a safe landing in the event of a partial or total engine failure. The unsafe operating region is the complement of the backwards reachable tube, which can be found as the sub-zero level set of the viscosity solution of a Hamilton-Jacobi (HJ) equation. Traditionally, numerical methods used to solve the HJ equation rely on a discrete grid of the solution space and exhibit exponential scaling with dimension, which is problematic for the high-fidelity dynamics models required for accurate helicopter modeling. We avoid the use of spatial grids by formulating a trajectory optimization problem, where the solution at each initial condition can be computed in a computationally efficient manner. The proposed method is shown to compute an autonomous landing trajectory from any operating condition, even in non-cruise flight conditions.

Matthew R. Kirchner, Mark J. Debord, João P. Hespanha

We present a method for optimal coordination of multiple vehicle teams when multiple endpoint configurations are equally desirable, such as seen in the autonomous assembly of formation flight. The individual vehicles' positions in the formation are not assigned a priori and a key challenge is to find the optimal configuration assignment along with the optimal control and trajectory. Commonly, assignment and trajectory planning problems are solved separately. We introduce a new multi-vehicle coordination paradigm, where the optimal goal assignment and optimal vehicle trajectories are found simultaneously from a viscosity solution of a single Hamilton-Jacobi (HJ) partial differential equation (PDE), which provides a necessary and sufficient condition for global optimality. Intrinsic in this approach is that individual vehicle dynamic models need not be the same, and therefore can be applied to heterogeneous systems. Numerical methods to solve the HJ equation have historically relied on a discrete grid of the solution space and exhibits exponential scaling with system dimension, preventing their applicability to multiple vehicle systems. By utilizing a generalization of the Hopf formula, we avoid the use of grids and present a method that exhibits polynomial scaling in the number of vehicles.

Matthew R. Kirchner

We introduce a method to perform automatic thresholding of SIFT descriptors that improves matching performance by at least 15.9% on the Oxford image matching benchmark. The method uses a contrario methodology to determine a unique bin magnitude threshold. This is done by building a generative uniform background model for descriptors and determining when bin magnitudes have reached a sufficient level. The presented method, called meaningful clamping, contrasts from the current SIFT implementation by efficiently computing a clamping threshold that is unique for every descriptor.