Lazy Abstraction-Based Controller Synthesis

Kyle Hsu, Rupak Majumdar, Kaushik Mallik, Anne-Kathrin Schmuck

Abstract

Abstraction-Based Controller Synthesis (ABCS) is a powerful framework for designing controllers for nonlinear systems, but it is often hampered by the "curse of dimensionality." Traditional methods compute a complete symbolic model of the state space before synthesis, leading to significant computational waste. This paper presents a "lazy" multi-layered ABCS approach that interleaves model construction with the controller search. By only refining the state space where necessary, the proposed method achieves up to a 4.5x speedup over existing multi-layered techniques while maintaining mathematical soundness and completeness.

Introduction

In control theory, designing controllers for complex nonlinear systems—such as autonomous vehicles or power converters—requires navigating an infinite, continuous state space. ABCS addresses this by discretizing the state space into a finite grid of cells, creating a symbolic model. Game-theoretic algorithms then search this grid for a strategy that satisfies safety or reachability requirements.

However, high-precision control requires extremely fine grids, leading to an exponential explosion in the number of cells and transitions. Even state-of-the-art multi-layered approaches typically follow an "eager" paradigm, pre-computing the entire model across all layers. This is inefficient, as large portions of the state space (e.g., regions far from the target or deep within unsafe zones) may never be visited by the final controller.

The Lazy ABCS Framework

The core innovation of this work is the transition from eager to lazy abstraction. Instead of a sequential "model then synthesize" pipeline, the algorithm dynamically explores and refines the state space during the search process.

Visualization of the lazy abstraction process for safety (top) and reach-avoid (bottom) specifications.

Key Technical Innovations

  • Frontier-Based Exploration: The algorithm maintains a frontier of active cells, computing transitions only for the regions currently being explored by the synthesis engine.
  • Layer Switching and Cross-Layer Memory: The system utilizes multiple abstraction layers. Coarse layers allow for rapid progress through simple regions, while fine layers provide precision near obstacles. To ensure consistency, the finest layer (Layer 1) acts as a common repository for intermediate results, allowing the algorithm to switch layers without losing progress.
  • Cooperative Predecessors: For reach-avoid problems, an optimistic search identifies coarse cells that potentially lead to the target. Only these promising cells are subsequently refined, avoiding unnecessary computation in dead ends.

Experimental Evaluation

The proposed algorithms were implemented in the MASCOT tool and evaluated against two standard benchmarks:

  1. Unicycle Model: A nonlinear kinematic vehicle navigating obstacles. The Lazy ABCS approach completed the reach-avoid task in 609 seconds, a ~78% reduction in runtime compared to the eager multi-layered version (2,701 seconds) and significantly faster than the single-layer approach (3,408 seconds).
  2. DC-DC Boost Converter: A second-order power electronics model. The "LazySafe" variant demonstrated exceptional scalability; as more layers were added, runtime decreased because the safe set was largely covered by coarse cells, requiring minimal fine-grained computation.

Conclusion and Future Work

Lazy ABCS demonstrates that interleaving abstraction and synthesis can overcome the traditional bottlenecks of formal controller design. While the approach is highly effective in sparse environments, its performance gains are more modest in highly cluttered spaces where extensive refinement is unavoidable. Future research will focus on integrating these lazy techniques with data-driven exploration and improving heuristic tuning for broader industrial applicability.

Summary updated

Abstract

ion-based controller synthesis (ABCS) is a general procedure for automatic synthesis of controllers for continuous-time nonlinear dynamical systems against temporal specifications. ABCS works by first abstracting a time-sampled version of the continuous dynamics of the open-loop system by a symbolic finite state model.
BibTeX
@inproceedings{hsu2019lazy,
  author = {Kyle Hsu and Rupak Majumdar and Kaushik Mallik and Anne-Kathrin Schmuck},
  title = {{Lazy Abstraction-Based Controller Synthesis}},
  booktitle = {ATVA},
  year = {2019},
  doi = {10.1007/978-3-030-31784-3\_2},
}
Figure