Abstract
Formal synthesis of controllers for cyber-physical systems often results in massive lookup tables that exceed the memory capacity of embedded devices. This paper introduces dtControl, an open-source tool that employs decision tree learning to compress these tables into compact, human-readable representations. By utilizing machine-learned predicates and a novel "on-the-fly" determinization algorithm called MaxFreq, dtControl achieves significant reduction in controller size while maintaining safety guarantees, often outperforming traditional Binary Decision Diagrams (BDDs).
Introduction
In the design of cyber-physical systems, such as autonomous vehicles or smart grids, formal synthesis is used to generate controllers with mathematical safety guarantees. However, these tools typically output lookup tables—exhaustive lists of state-action pairs—that are too large for the resource-constrained embedded chips found in hardware. While Binary Decision Diagrams (BDDs) are a common compression alternative, they are difficult for humans to interpret and minimize. dtControl bridges this gap by providing extreme compression alongside explainability through decision trees.
Methodology
dtControl adapts standard decision tree learning algorithms, such as CART, for the specific task of controller representation. Unlike traditional machine learning, which prioritizes generalization, dtControl requires an exact fit to the training data to preserve the safety guarantees of the original synthesized controller.
The tool introduces two primary technical innovations:
- Machine-Learned Predicates: Instead of simple axis-aligned splits (e.g., $x < 5$), dtControl can use linear classifiers like Logistic Regression or SVMs as decision nodes. These "oblique splits" combine multiple variables, resulting in significantly shallower trees.
- MaxFreq Determinization: Many synthesized controllers are "permissive," allowing a set of safe actions for any given state. Rather than picking a single action before building the tree, the MaxFreq algorithm selects the action during construction based on which one appears most frequently in the current data subset. This "on-the-fly" choice guides the algorithm toward a simpler, more uniform tree structure.
Experimental Evaluation
The researchers evaluated dtControl on 10 case studies derived from correct-by-construction controller synthesis, including:
- Single-input systems: Cartpole, 2D Thermal control, Helicopter, Cruise control, and a DC-DC converter.
- Multi-input systems: 10D Thermal control, Truck-Trailer, Traffic control, and various vehicle/aircraft models.
Key Results and Discussion
dtControl demonstrated remarkable performance across all benchmarks, particularly in terms of compression and explainability.
- Extreme Compression: In a 10-room temperature control system, a lookup table containing 52,488 pairs was reduced to a decision tree with only three decision nodes.
- Explainability: The simplified trees allow for manual inspection. In a cruise control case study, the tree revealed a counter-intuitive behavior (decelerating when the lead car was far away) that was a bug in the original logic, which had been hidden within the massive lookup table.
- Performance: For complex systems like Traffic control, dtControl succeeded in seconds, whereas BDD-based tools often timed out or produced larger representations.
Conclusion and Future Work
dtControl provides a practical path for deploying formally verified controllers on embedded hardware by exporting trees directly as C code. While the MaxFreq algorithm is highly effective for permissive controllers, future work will focus on improving results for deterministic inputs and exploring non-linear algebraic predicates to further simplify high-dimensional systems. The tool is open-source and supports various input formats, with plans to expand compatibility to tools like pFaces and QUEST.
Summary updated