Research

Questions of reachability for continuous and hybrid systems can be formulated as optimal control or game theory problems, whose solution can be characterized using variants of the Hamilton-Jacobi-Bellman or Isaacs partial differential equations. The formal link between the solution to the partial differential equation and the reachability problem is usually established in the framework of viscosity solutions. For the case of nonlinear control system we were able to establish a connection in [external page 1]. This and related theorithical works (see for example the work of external page Prof. C. Tomlin, external page Prof. Ian Mitchell, external page Prof. Alex Bayen) have motivated the development of computational tools for solving reachability problems by computing viscosity solutions to appropriate partial differential equations (see for example the Level Set Toolbox ). We have used such tools to adress problems in avionics.  

The problems of reachability, invariance and controlled invariance for discrete time systems have been extensively studied in the literature for over three decades. Most recently these problems have attracted renewed attention, partly because improvements in computational capabilities have made it possible to implement the algorithms for systems of practical interest. Another reason for the renewed interest in these problems is the emergence of new classes of practically important systems, such as hybrid systems. There are differents approaches used to deal with reachability problem for discrete-time system: A geometric approach has been used to address the problem for the special case where the disturbance constraints are independent of the state [external page 2] [external page 3], and generalizations of the existing results have been made for the case of state and input dependent disturbances in [4].  

We have considered hybrid systems that combine discrete event dynamics with nonlinear continuous dynamics. Typically the discrete event dynamics model linguistic and qualitative information and naturally accommodate mode switching logic, and the continuous dynamics model the physical processes themselves. Input variables can also be used to model both continuous and discrete controls and disturbances. We have explored two different methods for addressing reachability of hybrid systems.

• Optimal control approach: To adress the problem of computing reachable sets, analysis based on optimal control and game theory have been used for continuous time hybrid dynamical systems, then a Hamilton-Jacobi equations has been derived, whose solutions describe the boundaries of reachable sets [external page 5], [external page 6],[external page 7], [external page 8]. For discrete time systems, an algorithm for computing maximal controlled invariants sets are derived [external page 9].
  
• Viability theory approach: The problem of computing reachability have been revisited in the context of viability theory. Instead of relying on dynamic programming and viscosity solutions (as showed in the optimal control approach), a non-smooth analysis tools is used to characterize the solution. [10], [external page 11]  

A class of stochastic processes, called piecewise-deterministic Markov processes, is proposed as a model for studying stochastic hybrid systems. The piecewise-deterministic Markov processes (PDMPs) are an important class of non-linear continuous-time stochastic hybrid dynamical systems which admit theoretical analysis. We have developped some approaches for studying the reachability problem for PDMP. For this class of stochastic processes we have formulated a probabilistic reachability problem. Basic properties of PDMPs are reviewed and could be used to show that the reachability question is indeed well defined. Possible methods for computing the reachability probability are then investigated [external page 12]. The reach-avoid problem for continuous-time diffusions without switches has also been studied in [13].  

The study of discrete time SHS is adpoted in order to gain a deeper understanding of the theoretical and computational issues associated with the reachability analysis of stochastic hybrid systems. We developped a methodology to compute the maximum probability of remaining in a safe set for a discrete time stochastic hybrid system (DTSHS) whose dynamics is affected by a control input. The approach is based on formulating the reachability analysis problem as an optimal control problem. The maximum probability of remaining in a safe set for a certain time horizon can then be computed by dynamic programming [14]. In addition, the approach is unified for probabilistic reach-avoid problems [15]. In addition, in presence of adversaries affecting system trajectory, a two-player zero sum game for the reachability problem is formulated and its solution are derived [16]. Motivated by trajectory planning in uncertain and dynamic environments, the safety and reachability problems are extended to account for stochastic safe and target sets [17 (publication not available)].  

Research has addressed the cases in which there are multiple reachability specifications. This setting includes motion planning objetives such as reaching certain subsets of state-space in a fixed order or in an arbitrary order. To solve this problem, a finite state deterministic automaton is used to define the complex specifications. The problem of maximizing probability of specification satisfaction is then formulated as a reachability problem for a properly defined stochastic hybrid system [18]. Motion planning with multiple reachability objectives have also been studied in continuous-time setting for switching diffusions [19].  

This approach aims to beat the curse of dimensionality for reachability problems by approximating the solution using a neural network. We take an optimal control approach to the reachability problem and characterize viable sets as level sets of a value function that satisfies a Hamilton Jacobi PDE. Instead of solving the PDE numerically, however, we try to avoid gridding and train a neural network to approximate the solution. Our choice of neural networks for carrying out this approximation is motivated by the fact that:

• The number of collocation points necessary to train a neural network tends to grow polynomially with the desired accuracy.
  For the same precision neural networks tend to provide analytical approximations that require fewer parameters than finite element type methods (e.g. gridding) or polynomials. Therefore the solution has smaller memory requirements.

The trade off is, of course that convergence results will no longer be deterministic, since training points will in general be drawn randomly. We have considered two approachs:

• Extract random collocation points and train a neural network which satisfies a Hamilton Jacobi PDE by using non-smooth optimization algorithm. [20]
• Extracts random initial conditions and then use randomization to explore the space of bang-bang controls in an attempt to find viable trajectories starting at the given initial condition. The cost for the best among these randomly selected controls is then used to train the neural network. [21]

Methods of approximating reachability probabilities have been studied in the last decade. For the nonlinear discretet-time system, we can approximate stochastic reachability probability in a Bayesian format. Then, a randomized algorithm is used to compute the reachable set [external page 22]. A Monte Carlo approch for reachability computation problem is used in order to take the advantages of the Monte Carlo framework, in terms of the flexibility and complexity of the prediction models that can be used [external page 23], [external page 24].  

An equivalent formulation of the dynamic programming principle is through an infinite dimensional linear program. The optimization variable in this program represents the value function of the optimal control problem. We have been using this approach to compute the value function and the optimal policy of the stochastic reachability problem. Since the linear program capturing the value function is infinite dimensional, we introduce basis functions to approximate the value function. Then, in order to address the infinite dimensional constraints, we have used relaxations through sampling approach [25].  

For more informations please see the page of the Air Traffic Control Group.

Our earlier reachability work consentrated on AHS (Automated Highway System). AHS are considered as alternative to solve the transportation problems of the future. The objective of an AHS is to reduce congestion and increase the throughput and safety of the highway system, without building new roads, by adding automation to the vehicles and the roadside. We have worked on a number of problems on AHS, including the design of safe hybrid controllers [external page 30] ,[external page 31], [external page 32] , and fault tolerant control [external page 33], [external page 34].  

Camera surveillance systems typically consist of a space to be surveilled and a collection of Pan-Tilt-Zoom (PTZ) and static cameras that are tracking objects while obtaining high resolution images. Our goal is to use reachability analysis to design trajectories for the PTZ cameras that successfully achieve surveillance tasks, such as area patrolling, target acquisition and target tracking. We have formulated such surveillance tasks as reach-avoid problems using the techniques in [14] ,[15],[17], and proposed tractable methods to approximate their solution [35], [36]. Our framework is based on modelling camera dynamics as Markov decision processes (MDPs) and using stochastic target and safe sets to capture the evolution of potential evaders. We are also developing task allocation schemes in order to extend the application of reach-avoid surveillance techniques to larger camera networks. Our current approach to controlling camera networks is based on the fact that each camera can achieve sub-optimal surveillance tasks without considering the state of other cameras [37]. For more informations please see the web site of the Networked Control System Group.