Practical controller synthesis for MTL0, ∞

Guangyuan Li, Peter Gjøl Jensen, Kim Guldstrand Larsen, Axel Legay, Danny Bøgsted PoulsenSPIN 2017 · DOI

This paper tackles the challenge of automatically generating control software that guarantees complex real-time behavior. The authors introduce a novel approach to synthesize controllers for specifications written in Metric Temporal Logic (MTL0,∞), a powerful language for describing real-time properties. Their work bridges the gap between theoretical undecidability and practical applicability by developing an approximate synthesis method and a robust toolchain.

TL;DR

This paper presents a practical method for synthesizing controllers for real-time systems specified in MTL0,∞, a logic for which controller synthesis is generally undecidable. By translating MTL0,∞ formulas into Timed Büchi Automata and employing over- and under-approximations, the authors provide a toolchain that enables the automatic generation of control software for complex real-time specifications, demonstrating its effectiveness on several case studies.

What Problem Does This Paper Address?

Automatic controller synthesis aims to algorithmically construct control software that ensures a system's behavior meets a given specification, regardless of external inputs. While this concept has been explored for decades, real-time systems introduce significant complexity. Metric Temporal Logic (MTL) and its variants, like MTL0,∞, are expressive formalisms for specifying such real-time properties, allowing for precise temporal constraints (e.g., "event A must happen within 5 time units of event B").

However, synthesizing controllers for general MTL0,∞ specifications is known to be undecidable. This undecidability arises from the inherent difficulty in determinizing timed automata, a key component in many synthesis approaches. Existing methods either struggle with the complexity of determinization or are limited to simpler subclasses of temporal logics. The authors address this by proposing an approximate synthesis technique that, while not always exact, provides sufficient guarantees for practical applications and is computationally tractable.

Methods

The core of the paper lies in a multi-step process for translating MTL0,∞ specifications into a form suitable for controller synthesis:

  1. MTL0,∞ to Timed Büchi Automata (TBA): The authors first develop an exact translation from MTL0,∞ formulas to non-deterministic Timed Büchi Automata (TTBA). This involves constructing a "closure" of the formula and then generating an extended formula that incorporates monitoring clocks to track time progression for temporal operators. This TTBA captures the semantics of the original MTL0,∞ specification.
  2. Deterministic Over- and Under-Approximations: To overcome the challenges of determinization, the authors employ a technique to construct deterministic over- and under-approximations of the TTBA. This is achieved by adapting the standard subset construction from non-deterministic finite automata to the timed domain.
  3. Under-approximation: This automaton is guaranteed to accept a subset of the original specification's language. A controller synthesized from this automaton will be "safe" – it will always satisfy the original property, though it might not be "complete" (i.e., it might miss some valid behaviors).
  4. Over-approximation: This automaton accepts a superset of the original specification's language. If a controller cannot be synthesized for the over-approximation, then no controller exists for the original specification. If a controller can be synthesized for the over-approximation, it implies the existence of a controller for the original specification, and the under-approximation can be used to find it.
  5. Toolchain Integration: The authors have implemented these methods in a toolchain that seamlessly integrates their TTBA construction component (CASAAL) with UPPAAL-TIGA, a tool for synthesizing controllers for Timed Games with Büchi objectives. This integration allows users to specify properties in MTL0,∞, have them translated into TBAs, and then use UPPAAL-TIGA to synthesize a controller.

Datasets

The paper does not introduce new datasets. Instead, it uses established benchmarks for evaluating controller synthesis techniques:

  • Cat and Mouse Game: A classic example from UPPAAL literature used to model multi-agent interactions and complex temporal properties.
  • Train-Gate Example: Another well-known benchmark for testing real-time system verification and synthesis, involving multiple trains and a gate.
  • Chinese Juggler: A scalable example used to assess the performance of synthesis algorithms with an increasing number of components (plates).

Key Insights and Ideas

  • Bridging Undecidability with Approximation: The most significant insight is the successful application of over- and under-approximations to make an undecidable problem practically solvable. This approach provides a robust framework for synthesizing controllers even when exact methods fail.
  • Exactness in Practice: The authors demonstrate that their approximations are often "exact and tight" in practice, meaning the under- and over-approximated automata are frequently equivalent to the original specification's automaton. This suggests that for many realistic scenarios, the theoretical undecidability doesn't manifest as a practical limitation.
  • Seamless Tool Integration: The creation of a unified toolchain (CASAAL + UPPAAL-TIGA) is a crucial practical contribution. It lowers the barrier to entry for using advanced controller synthesis techniques by abstracting away the complex intermediate steps.
  • MTL0,∞ as a Practical Specification Language: The work validates MTL0,∞ as a powerful and expressive language for specifying real-time control objectives, capable of capturing a wide range of safety, liveness, and bounded liveness properties.

Key Results

  • Exact Translation to TTBA: The paper presents the first exact translation from MTL0,∞ to (non-deterministic) Timed Büchi Automata.
  • Practical Synthesis Toolchain: A functional toolchain (CASAAL + UPPAAL-TIGA) is developed and demonstrated for synthesizing controllers.
  • Scalability and Performance: Experiments on the Cat and Mouse, Train-Gate, and Chinese Juggler examples show that the synthesis process is feasible within reasonable computation times and memory limits for non-trivial formulas and model sizes.
  • High Approximation Quality: In most experimental cases, the over- and under-approximations were found to be exact, validating the effectiveness of the proposed method. For instance, in the Cat and Mouse example, all but one property yielded exact approximations.

Limitations and Future Work

  • Approximation Necessity: While often exact, the method inherently relies on approximations. In cases where the approximations are not exact, the synthesized controller might be overly conservative (from the under-approximation) or might not exist (if the over-approximation fails).
  • Determinization Complexity: Although the authors mitigate the direct determinization of TBAs, the underlying process of constructing and manipulating these automata can still be computationally intensive for very complex specifications or large systems.
  • Future Work: The authors suggest refining their deterministic over- and under-approximation construction by using the breakpoint technique for Büchi determinization. Further exploration of the "exact and tight" property and its theoretical underpinnings is also a promising direction. Extending the approach to other temporal logics or more complex system models could also be valuable.

Summary updated

BibTeX
@inproceedings{li2017practical,
  author = {Guangyuan Li and Peter Gjøl Jensen and Kim Guldstrand Larsen and Axel Legay and Danny Bøgsted Poulsen},
  title = {{Practical controller synthesis for MTL0, ∞}},
  booktitle = {SPIN},
  year = {2017},
  doi = {10.1145/3092282.3092303},
}
Figure