Efficient Control Synthesis and Learning in Distributed Cyber-Physical Systems
Abstract
Scientific challenges. How can multiple cyber-physical systems be enabled and coordinated to accomplish complex tasks in unknown and adversarial environments?
This collaborative project between the University of Delaware (UD) and Boston University (BU) explores the hypothesis that hybrid cyber-physical agents that interact with each other in a dynamic environment can be modeled in a way that their abstract behavior can be captured and analyzed using the tools of formal language theory—tools which can be transferred and adapted from the scientific study of natural language. This process creates a new paradigm for symbolic control design for hybrid systems that exploits the computational benefits of tight formal characterizations of the models considered, while additionally enabling the cyber-physical systems to learn the dynamics of their environment.
Results. We have created a hybrid systems model that captures dynamical systems that switch between different stable closed-loop dynamics using an assume-guarantee predicate logic, and have shown how to use this logic to construct discrete abstract models, which are small in size and are weakly similar to the concrete hybrid dynamical systems. The weak simulation allows for (sub)optimal planning using the small, discrete system which has guaranteed behavior on the con- crete system. This bottom-up approach to planning does not dictate to practitioners non-intuitive, untested control strategies, but instead shows how to combine existing validated algorithms to give rise to more complex behaviors in a provably correct and predictable way.
Then we brought together concepts from algebraic automata theory, hybrid systems, game theory, and grammatical inference into a framework that facilitates symbolic control design for hybrid systems operating in unknown and/or adversarial environments. This is a step toward realizing our goal of developing a theory in support of emergency response resource allocation, real- time planning, and coordination problems. The framework uses discrete abstractions to transfer the problem from the hybrid domain to the realm of discrete models of computation, utilizes grammatical inference to enable the system to identify the dynamics of its environment, and employs game theoretic methods to design control policies that guarantee mission success irrespectively of environmental effects, when possible.
This paradigm is illustrated with two different learning formulations embedded in hybrid sys- tems that interact with unknown and dynamic environments. These different formulations are complimentary: The BU team uses a Markov process model for the environment dynamics and captures the case of a dynamic, stochastic, but autonomous environment. The UD team use a de- terministic model for the environment, and account for cases where the ’environment’ is controlled by an intelligent adversary responding to the agent’s actions.
Broader impacts. Apart from advancing state-of-the-art in cyberphysical systems research, this research activity has impacts along several dimensions. It is a multidisciplinary effort involving robotics, linguistics, cognitive science, and computer science, and provides interdisciplinary training to graduate students in these areas. Consequently, the results obtained contribute to each of these fields individually. We envision this research having successful applications in emergency response scenarious which involve multiple, coordinated efforts in uncertain environments.
Award ID: 1035577
Submitted by Herbert Tanner
on
Abstract
Scientific challenges. How can multiple cyber-physical systems be enabled and coordinated to accomplish complex tasks in unknown and adversarial environments?
This collaborative project between the University of Delaware (UD) and Boston University (BU) explores the hypothesis that hybrid cyber-physical agents that interact with each other in a dynamic environment can be modeled in a way that their abstract behavior can be captured and analyzed using the tools of formal language theory—tools which can be transferred and adapted from the scientific study of natural language. This process creates a new paradigm for symbolic control design for hybrid systems that exploits the computational benefits of tight formal characterizations of the models considered, while additionally enabling the cyber-physical systems to learn the dynamics of their environment.
Results. We have created a hybrid systems model that captures dynamical systems that switch between different stable closed-loop dynamics using an assume-guarantee predicate logic, and have shown how to use this logic to construct discrete abstract models, which are small in size and are weakly similar to the concrete hybrid dynamical systems. The weak simulation allows for (sub)optimal planning using the small, discrete system which has guaranteed behavior on the con- crete system. This bottom-up approach to planning does not dictate to practitioners non-intuitive, untested control strategies, but instead shows how to combine existing validated algorithms to give rise to more complex behaviors in a provably correct and predictable way.
Then we brought together concepts from algebraic automata theory, hybrid systems, game theory, and grammatical inference into a framework that facilitates symbolic control design for hybrid systems operating in unknown and/or adversarial environments. This is a step toward realizing our goal of developing a theory in support of emergency response resource allocation, real- time planning, and coordination problems. The framework uses discrete abstractions to transfer the problem from the hybrid domain to the realm of discrete models of computation, utilizes grammatical inference to enable the system to identify the dynamics of its environment, and employs game theoretic methods to design control policies that guarantee mission success irrespectively of environmental effects, when possible.
This paradigm is illustrated with two different learning formulations embedded in hybrid sys- tems that interact with unknown and dynamic environments. These different formulations are complimentary: The BU team uses a Markov process model for the environment dynamics and captures the case of a dynamic, stochastic, but autonomous environment. The UD team use a de- terministic model for the environment, and account for cases where the ’environment’ is controlled by an intelligent adversary responding to the agent’s actions.
Broader impacts. Apart from advancing state-of-the-art in cyberphysical systems research, this research activity has impacts along several dimensions. It is a multidisciplinary effort involving robotics, linguistics, cognitive science, and computer science, and provides interdisciplinary training to graduate students in these areas. Consequently, the results obtained contribute to each of these fields individually. We envision this research having successful applications in emergency response scenarious which involve multiple, coordinated efforts in uncertain environments.
Award ID: 1035577