Bottom-up symbolic control and adaptive systems: Abstraction, planning and learning

This thesis develops an optimal planning method for a class of hybrid systems, and introduces machine learning with reactive synthesis to construct adaptive controllers for finite-state transition systems with respect to high-level formal specifications in the presence of an unknown, dynamic environment. For a class of hybrid systems that switches between different pre-defined low-level controllers, this thesis develops an automated method that builds time-optimal control mode sequences that satisfy given system specifications. The planning algorithm proceeds in a bottom-up fashion. First, it abstracts a hybrid system of this class into a special finite-state automaton that can manipulate continuous data expressing attributes of the concrete dynamics. The abstraction is predicate-based, enabled by the convergence properties of low-level continuous dynamics, and emph{encompasses} existing low-level controllers rather than emph{replacing} them during synthesis. The abstraction is weakly simulated by its concrete system, and thus behaviors planned using the abstraction are always implementable on the concrete system. The procedure of abstraction bridges the hybrid dynamical systems with formal language and automata theory and enables us to borrow concepts and methodologies from those fields into control synthesis. In the presence of unknown, dynamic and potentially adversarial environment, this thesis develops an adaptive synthesis method, and advocates the integration of ideas from grammatical inference and reactive synthesis toward the development of an any-time control design, which is guaranteed to be effective in the limit. The insight is that at the abstraction level, the behavior of the unknown environment exhibited during its interaction with the system can be treated as an unknown language, which can be identified by a learning algorithm from finite amount of observed behaviors provided some prior knowledge is given. As the fidelity of the environment model improves, the control design becomes more effective. The thesis then considers reactive synthesis in the case of partial observation (not all environment actions can be completely observed by the system) and multi-agents. Reactive control synthesis methods are developed for systems with incomplete information, that ensure the specifications are satisfied surely, or almost surely (with probability 1). For the synthesis of controllers for multiple concurrent systems with individual specifications, an approach in which each treats the others as adversarial can be too restrictive and unnecessary. This thesis presents a decision procedure for agent behaviors that is based on the solution of a concurrent, multi-agent infinite game. Depending on the context in which interaction takes place, solutions can come in the form of pure (deterministic) Nash equilibria, security strategies, or cooperative pure Nash equilibria. The analysis and methods presented can be extended to the case of decentralized control design for multiple reactive systems. The thesis concludes with a brief overview and possible future research directions.