Eric Kim

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2019-118

August 16, 2019

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-118.pdf

Control synthesis is the problem of automatically constructing a control strategy that induces a system to exhibit a declared behavior. Synthesis algorithms vary widely across different classes of system dynamics and specifications. While continuous optimization has traditionally been used to construct stabilizing controllers for physical systems modeled with differential equations, temporal logic synthesis for finite state machines heavily leverages discrete algorithms and data structures. Hybrid systems are a class of systems that exhibit both continuous and discrete behaviors, which are necessary to capture phenomena such as impacts for legged robots and congestion shockwaves in freeways. Tractable control synthesis remains elusive because hybrid systems violate many of the fundamental topological assumptions made by prior algorithms for purely continuous or discrete systems. This thesis exploits compositionality and system structure to provide a suite of algorithmic and theoretical techniques to tackle acute computational bottlenecks in hybrid control synthesis.

The first half of this thesis provides a framework for engineers to model control systems and construct algorithmic pipelines for control synthesis. By explicitly capturing system structure, this framework gives users the flexibility to rapidly iterate over and leverage a library of optimizations for control synthesis. We demonstrate this framework in the context of abstraction-based control, a synthesis workflow that translates continuous systems into finite state machines by throwing away high precision information. Different optimization techniques such as multi-scale grids, lazy abstraction, and decomposed synthesis, can all be expressed as modifications to a computational pipeline. We demonstrate computational gains while synthesizing safe motion primitives for numerous robotic examples.

The second half addresses distributed control synthesis where multiple controllers act as agents that seek to jointly satisfy a specification and are restricted by some communication topology. We introduce parametric assume-guarantee contracts as a formalism to derive guarantees about the closed loop behavior of a collection of interacting components. Dynamic contracts allow contract parameters to change at runtime and enable coordination of multiple interacting sub-systems. These results are demonstrated in the context of a freeway ramp meter and an adjacent arterial network.

Advisors: Sanjit A. Seshia and Murat Arcak

---

BibTeX citation:

@phdthesis{Kim:EECS-2019-118,
    Author= {Kim, Eric},
    Title= {Constructive Formal Control Synthesis through Abstraction and Decomposition},
    School= {EECS Department, University of California, Berkeley},
    Year= {2019},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-118.html},
    Number= {UCB/EECS-2019-118},
    Abstract= {Control synthesis is the problem of automatically constructing a control strategy that induces a system to exhibit a declared behavior. Synthesis algorithms vary widely across different classes of system dynamics and specifications.
While continuous optimization has traditionally been used to construct stabilizing controllers for physical systems modeled with differential equations, temporal logic synthesis for finite state machines heavily leverages discrete algorithms and data structures.
Hybrid systems are a class of systems that exhibit both continuous and discrete behaviors, which are necessary to capture phenomena such as impacts for legged robots and congestion shockwaves in freeways. Tractable control synthesis remains elusive because hybrid systems violate many of the fundamental topological assumptions made by prior algorithms for purely continuous or discrete systems.
This thesis exploits compositionality and system structure to provide a suite of algorithmic and theoretical techniques to tackle acute computational bottlenecks in hybrid control synthesis.

The first half of this thesis provides a framework for engineers to model control systems and construct algorithmic pipelines for control synthesis.
By explicitly capturing system structure, this framework gives users the flexibility to rapidly iterate over and leverage a library of optimizations for control synthesis.
We demonstrate this framework in the context of abstraction-based control, a synthesis workflow that translates continuous systems into finite state machines by throwing away high precision information. Different optimization techniques such as multi-scale grids, lazy abstraction, and decomposed synthesis, can all be expressed as modifications to a computational pipeline. We demonstrate computational gains while synthesizing safe motion primitives for numerous robotic examples.

The second half addresses distributed control synthesis where multiple controllers act as agents that seek to jointly satisfy a specification and are restricted by some communication topology. We introduce parametric assume-guarantee contracts as a formalism to derive guarantees about the closed loop behavior of a collection of interacting components. Dynamic contracts allow contract parameters to change at runtime and enable coordination of multiple interacting sub-systems.
These results are demonstrated in the context of a freeway ramp meter and an adjacent arterial network.},
}

EndNote citation:

%0 Thesis
%A Kim, Eric 
%T Constructive Formal Control Synthesis through Abstraction and Decomposition
%I EECS Department, University of California, Berkeley
%D 2019
%8 August 16
%@ UCB/EECS-2019-118
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-118.html
%F Kim:EECS-2019-118