Symbolic control translates the control synthesis problem from the continuous- to the discrete-state domain, allowing the designer to address complex control specifications expressed as automata or temporal logic formulas. Existing tools for symbolic control are hampered by severe computational bottlenecks as the system dimension grows, particularly in the “abstraction” stage when the state space is partitioned into discrete states (“symbols") and transitions among the discrete states are determined with reachability analysis. This talk will present our results to overcome these bottlenecks by exploiting system structure. We will discuss: (1) taking advantage of monotonicity properties of the dynamical model for efficient reachability computations, (2) using sparsity structures in the dependency graph of state variables for parsimonious abstraction algorithms that dramatically reduce runtime, and (3) dividing the control synthesis task into sub-problems of manageable size with compositional procedures. We will demonstrate the scalability enabled by these ideas on several practically motivated examples.
Murat Arcak is a professor at U.C. Berkeley with appointments in the Department of Electrical Engineering and Computer Sciences, and the Department of Mechanical Engineering. He received the B.S. degree in Electrical Engineering from the Bogazici University, Istanbul, Turkey (1996) and the M.S. and Ph.D. degrees from the University of California, Santa Barbara (1997 and 2000). His research is in dynamical systems and control theory with applications to synthetic biology, multi-agent systems, and transportation.