Lazy Abstraction-Based Control for Reachability

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

TL;DR

This paper introduces "lazy abstraction-based controller synthesis" (Lazy ABCS) for continuous-time nonlinear systems. By only computing necessary parts of system abstractions on-demand, Lazy ABCS significantly speeds up the process of finding controllers that ensure system safety and reachability, outperforming previous multi-layered methods.

What Problem Does This Paper Address?

Synthesizing controllers for complex, continuous-time nonlinear dynamical systems is a challenging problem. Abstraction-based controller synthesis (ABCS) offers a solution by creating simplified, finite-state models of the system and synthesizing controllers for these models. Multi-layered ABCS improves this by using multiple abstractions of varying granularity, leveraging coarser abstractions for efficiency. However, a bottleneck in existing multi-layered ABCS is the need to fully compute all abstract transitions for each layer, even if many of these transitions are not relevant to the specific control problem. This paper addresses this inefficiency by developing a "lazy" approach that computes abstractions only when and where they are needed during the synthesis process.

Methods

The core innovation is the application of "lazy abstraction" to multi-layered ABCS. Instead of pre-computing all abstract transitions for each layer, Lazy ABCS focuses on computing transitions only for a "frontier" of states that are relevant to the current stage of the synthesis algorithm.

Key techniques include:

  • Multi-layered Abstraction: The system is represented by a hierarchy of finite-state models (layers) with varying levels of detail (granularity).
  • Lazy Computation: Abstract transitions are computed "on-demand" for a limited set of "frontier" states. This frontier is dynamically determined based on the progress of the synthesis algorithm.
  • Fixed-Point Algorithms: Standard fixed-point iteration techniques are used for safety and reach-avoid specifications, but adapted to work with the on-demand abstraction.
  • Frontier Construction: For safety, the frontier is defined by states that are potentially unsafe. For reach-avoid, it involves an over-approximation of reachable states using auxiliary systems and a cooperative predecessor operator.
  • Switching Protocols: The algorithms manage switching between abstraction layers during the fixed-point computations, saving and reloading intermediate results to leverage work done in other layers.

Datasets

Not discussed in the paper. The paper uses benchmark examples for evaluation, specifically:

  • A unicycle model for a reach-avoid control problem.
  • A DC-DC boost converter for a safety control problem.

Key Insights and Ideas

  • On-Demand Abstraction is Key: The most significant insight is that a full abstraction is often unnecessary. Computing only the relevant parts of the abstract transition system dramatically reduces computational cost.
  • Frontier as a Guiding Principle: The concept of a "frontier" effectively identifies the critical states for which abstractions need to be computed, guiding the lazy approach.
  • Multi-Layered Lazy Approach: Combining multi-layered abstractions with lazy computation offers a powerful way to balance abstraction granularity and computational effort.
  • Efficiency Gains: The paper demonstrates that this lazy approach leads to substantial performance improvements compared to methods that pre-compute entire abstractions.

Key Results

The paper presents experimental results comparing Lazy ABCS with previous multi-layered ABCS algorithms (EagerReach and EagerSafe) and single-layer approaches.

  • Significant Speedup: For the unicycle reach-avoid problem, LazyReach2 was over 4 times faster than EagerReach2 (total time 609s vs. 2701s).
  • Scalability: The performance gains are particularly noticeable with increasing complexity (e.g., more obstacles). Lazy ABCS explores the state space more efficiently by focusing computation.
  • Safety Control Performance: For the DC-DC boost converter, LazySafe also showed significant speedups, especially as the number of abstraction layers increased.
  • Soundness and Completeness: Theoretical proofs are provided to ensure that the lazy approach maintains the soundness and completeness guarantees of traditional ABCS.

Limitations and Future Work

  • Parameter Tuning: The performance of the algorithms can be sensitive to the choice of parameters, such as the number of layers (L) and the step size for reachability (m).
  • Incomparable Systems: The paper notes that direct FRRs between abstraction layers are not always guaranteed, which complicates the synthesis process and requires careful handling of layer switching.
  • Future Work: The authors suggest designing more scalable and robust tools, and combining algorithmic techniques with structural heuristics or orthogonal methods like data-driven exploration.

Summary updated

Abstract

We present lazy abstraction-based controller synthesis (ABCS) for continuous-time nonlinear dynamical systems against reach-avoid and safety specifications. State-of-the-art multi-layered ABCS pre-computes multiple finite-state abstractions of varying granularity and applies reactive synthesis to the coarsest abstraction whenever feasible, but adaptively considers finer abstractions when necessary. Lazy ABCS improves this technique by constructing abstractions on demand. Our insight is that the abstract transition relation only needs to be locally computed for a small set of frontier states at the precision currently required by the synthesis algorithm. We show that lazy ABCS can significantly outperform previous multi-layered ABCS algorithms: on standard benchmarks, lazy ABCS is more than 4 times faster.
BibTeX
@inproceedings{hsu2019lazy,
  author = {Kyle Hsu and Rupak Majumdar and Kaushik Mallik and Anne-Kathrin Schmuck},
  title = {{Lazy Abstraction-Based Control for Reachability}},
  booktitle = {ATVA},
  year = {2019},
  doi = {10.1007/978-3-030-31784-3\_2},
}

Loading related content...

Figure