Reachability Tools for Guaranteeing Performance and Safety of Multibody Control Systems
Abstract
The proposed work builds on the concept and tools of reachable set computation for both the design of multibody control systems, as well as the formal verification of the safety and performance of the resulting systems. By multibody control systems, we mean a group of vehicles, each modeled as a dynamic system, and each with its own actuation capabilities, interacting with each other to achieve a goal. The goal is typically physical, such as target reaching, threat elimination, or collision avoidance. The vehicles can sense and communicate, though avoiding detection and dealing with corrupted information is also part of the challenge. We propose to use the framework of multiple-player differential game theory, in which each player is a dynamical system modeled with differential equations, and competes or cooperates with other players to achieve a goal. The game may have multiple goals, which may be modeled using a single joint objective function or a set of single objective functions, and each player takes actions which optimize the objective function according to its goal. Hamilton-Jacobi (HJ) reachability theory is a method for solving such differential game problems, and it is applicable to nonlinear, time-varying dynamics. However, HJ reachability scales exponentially in the dimension of the continuous state, and thus is unsuitable in its current form for problems of morethan two vehicles. Newly developed methods by the PI and her research group can allow HJ reachability to be extended to larger numbers of vehicles, though the methods that have been developed to date require that the level of interaction between vehicles decreases as the number of vehicles increases. This proposal presents systematic methods for treating challenge problems of 2 to 20 vehicles, with ranges of interaction dynamics and goals. These methods create an infrastructure in which the mathematical guarantees of safety and performance provided by reachability are maintained in these larger dimensional problems. The proposed work is organized in 5 research thrusts: (1) Automatic system decomposition where computation is performed in the lower dimensional subspaces: here, we will build on new techniques for constructing self-contained subsystems, in which coupling between subsystems is allowed. We will construct conditions on system dynamics so that exact decomposition can be performed, and we will explore how to constrain multibody control systems so that both exact and approximate decomposition methods provide effective solutions; (2) Combining low dimensional reachabilityfor two vehicles with discrete logic for treating multiple vehicle problems: here, we will explore the use of matching and inductive algorithms to extend exact solutions for two vehicles to the many vehicle case; (3) Exploiting cooperation when possible to reduce dimensionality: in this thrust we will explore both efficient computational methods for optimal control, as well as sequential organization to provide solutions for large numbers of vehicles; and (4) investigating geometric partitioning: here, we will design practical methods for partitioning the state space, building on Voronoi partitioning and path defense methods. A final cross-cutting research task proposes to: (5) Consider the different information exchange possibilities in these problems and to understand how the mathematical guarantees vary as information becomes more or less available under different information structures, and what this means for the level of interaction between vehicles. The proposed work will result in design algorithms and tools, working papers, experiments on local unmanned aerial vehicles platforms that we already have at Berkeley, aswell as on simulations of Naval systems, and technology transfer to Naval scenarios.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 10, 2018
- Source ID
- N000141812214
Entities
People
- Claire J. Tomlin
Organizations
- Office of Naval Research
- United States Navy
- University of California Regents