dtControl: Decision Tree Learning Algorithms for Controller Representation

Pranav Ashok, Mathias Jackermeier, Pushpak Jagtap, Jan Kretínský, Maximilian Weininger, Majid Zamani

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 conceptual relationship between a decision tree representation (a), the resulting state-space partitioning (b), and the original lookup table (c).

The tool introduces two primary technical innovations:

  1. 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.
  2. 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.
A decision tree for a 10-room thermal control system, illustrating how a massive lookup table is reduced to just three decision nodes.

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

Abstract

Decision tree learning is a popular classification technique most commonly used in machine learning applications. Recent work has shown that decision trees can be used to represent provably-correct controllers concisely. Compared to representations using lookup tables or binary decision diagrams, decision trees are smaller and more explainable. We present dtControl, an easily extensible tool for representing memoryless controllers as decision trees. We give a comprehensive evaluation of various decision tree learning algorithms applied to 10 case studies arising out of correct-by-construction controller synthesis. These algorithms include two new techniques, one for using arbitrary linear binary classifiers in the decision tree learning, and one novel approach for determinizing controllers during the decision tree construction. In particular the latter turns out to be extremely efficient, yielding decision trees with a single-digit number of decision nodes on 5 of the case studies.
BibTeX
@inproceedings{ashok2020dtcontrol,
  author = {Pranav Ashok and Mathias Jackermeier and Pushpak Jagtap and Jan Kretínský and Maximilian Weininger and Majid Zamani},
  title = {{dtControl: Decision Tree Learning Algorithms for Controller Representation}},
  booktitle = {HSCC},
  year = {2020},
  url = {https://openreview.net/forum?id=ytp0S3PWMN},
}
Figure