Researchers in the areas of dynamical systems and control have approached hybrid systems from a ``continuous state space and continuous/discrete time'' point of view. In recent years we have developed a methodology for designing controllers for large scale systems, making use of techniques from game theory and optimal control ([4], [9]. [37], [8]). In this approach, we note that two factors affect the system evolution at this level. The first is the control, and the second is the disturbances that enter the system, over which we assume no control. We distinguish three classes of disturbances: exogenous signals, such as unmodeled forces, sensor noise, etc.; unmodeled dynamics, and actions of other agents, in a multi-agent setting. Disturbances of the first two classes are standard in a single agent setting, but the third class is the most interesting one from the point of view of hybrid control. Acceptable performance can be encoded by means of thresholds on certain cost functions. Our objective is to derive a continuous design for the control inputs that guarantees performance despite the disturbances. If it turns out that the disturbance is such that the specifications cannot be met for any controller, the design fails. The only way to salvage the situation is to somehow limit the disturbance, and for disturbances involving actions of other agents, this may be possible by means of communication and coordination between the agents. Thus, our approach to hybrid controller design consists of determining continuous control laws and conditions under which they satisfy the closed loop requirements. Then, a discrete design is constructed to ensure that these conditions are satisfied.
We have successfully applied these techniques to a number of problems [4] discusses the application of these ideas to the automated highway example, and [7], [37] discusses the application to the air traffic management system application. [5] discusses the application of the game theoretic methodology to flight management systems for UAVs and other single-agent systems. We are primarily interested in control problems where multiple requirements are imposed on the design. This is usually the case for most realistic systems. For example, when dealing with completely discrete systems the requirements usually considered are those of safety (typically encoded by requirements over the finite runs of the system) and liveness or fairness (typically encoded by requirements over the infinite runs). For conventional control problems, on the other hand, the requirements considered are usually safety (encoded by stability or constraints on the system trajectories) and efficiency (the requirement for small inputs or bounds on the speed of convergence). In such a multi-objective setting some of the requirements are usually assumed to be more important than others, either explicitly or implicitly. The priority is important from the point of view of controller synthesis however, as one would like to ensure that the higher priority specifications are not violated in favor of the low priority ones. This observation implicitly restricts the possible choices of the controllers that can be used to satisfy the lower priority specifications. Ideally one would like to be able to classify the controllers that guarantee the high priority specifications and attempt to optimize the system performance with respect to the lower priority ones within this class.
Our research on the application of games and optimal-control ideas to hybrid design and verification will focus on efficient numerical algorithms, for the computation of safe sets, and synthesis procedures. In addition, currently extensive designer input is needed during the controller design, verification, or abstraction process. Thus, we will work on techniques for partially automating the process. Our approach is best suited to address questions of ``reachability'' (safety). Reachability problems can usually be cast as pursuit evasion problems in the gaming framework. Extensions to other important questions such as liveness and performance will also be addressed on this project. In addition, the ``deterministic'' synthesis tools discussed here sometimes give conservative results, because of their worst-case or minmax nature. In the research proposed in this project, we will discuss softening of these methods to ``probabilistic'' synthesis techniques.