Efficient Control Synthesis and Learning in Distributed Cyber-Physical Systems

Abstract:

Scientific challenges: How can multiple cooperative cyber-physical systems communicate and coor- dinate to accomplish complex high-level tasks within unknown, dynamic and adversarial environments?

Overview: This collaborative project between the University of Delaware (UD) and Boston University (BU) aims at developing a framework unifying temporal logic planning and adaptive reactive synthesis for multiple cooperative cyber-physical systems that operate in dynamic and unknown environments. Hybrid dynamical system modeling approaches are developed, in which concrete systems admit discrete abstractions that  can be identified and analyzed  using tools from automata theory, formal  language theory, grammatical inference, and model checking. The PIs envision multiple systems learning the dynamics of an unknown environment collectively, and then refine their plans based on models for the environmental dynamics that are inferred during execution.

Results: We develop a framework that integrates game theory and grammatical inference for adaptive control synthesis of cyber-physical systems operating in unknown, dynamic, and potentially adversarial environments. We show how action model learning and grammatical inference can be jointly utilized for identifying the interactions between a system and its environment, instead of just modeling the environment. Essentially, action model learning is used to identify how the actions of the system and its environment affect the state of the world (system + environment). Grammatical inference then operates in parallel, identifying a formal language which describes the environment. This framework accommodates multiple learning paradigms for constructing provably-correct, adaptive control policies in real-time. For multi-robot systems, we develop a method for the automatic planning of optimal paths for a group of robots that satisfy a common high-level mission specification. The task includes a sub-task in the form of an optimizing proposition that must be repeatedly satisfied. We develop planning algorithms for groups of robots to ensure that the maximum time between successive objective achievements is minimized. Communication protocols are designed to guarantee the correctness of the plan during deployment, and bounds on how much individual subsystem behavior can deviate from the optimal solution, are provided. To alleviate state-space explosion, incremental synthesis algorithms are developed, allowing agents to be incorporated in the synthesis procedure successively in order to maximize the probability of satisfying a given specification. The adaptive control design has the potential to be extended from single agent to collections of multiple cooperative heterogeneous cyber-physical systems, operating in unknown uncertain and adversarial environments, which outlines the direction of ongoing work.

Broader impacts: This research activity is multidisciplinary, combining expertise from robotics, lin- guistics, cognitive science, and computer science, and in this capacity exposes researchers of different fields to entirely new ideas and ways of thinking. Exploiting a common theoretical foundation provided by formal language theory, we establish new and reinforce existing intellectual links between disparate scientific communities, and educate a new generation of scholars versed in topics of both arts and sci- ences, and engineering. Our own graduate students receive significant interdisciplinary training, and have developed a range of analytical techniques that cross traditional academic boundaries.

  • CPS Domains
  • Concurrency and Timing
  • Real-time Systems
  • Control
  • Modeling
  • Real-Time Coordination
  • Robotics
  • Education
  • Foundations
  • National CPS PI Meeting 2013
  • 2013
  • Poster
  • Academia
  • CPS PI Poster Session
Submitted by Herbert Tanner on Thu, 10/24/2013 - 11:03