Learning Optimal Signal Temporal Logic Decision Trees for Classification: A Max-Flow MILP Formulation

2024-07-30 · Kaier Liang, Gustavo A. Cardona, Disha Kamale, Cristian-Ioan Vasile

This paper presents a novel framework for inferring timed temporal logic properties from data. The dataset comprises pairs of finite-time system traces and corresponding labels, denoting whether the traces demonstrate specific desired behaviors, e.g. whether the ship follows a safe route or not. Our proposed approach leverages decision-tree-based methods to infer Signal Temporal Logic classifiers using primitive formulae. We formulate the inference process as a mixed integer linear programming optimization problem, recursively generating constraints to determine both data classification and tree structure. Applying a max-flow algorithm on the resultant tree transforms the problem into a global optimization challenge, leading to improved classification rates compared to prior methodologies. Moreover, we introduce a technique to reduce the number of constraints by exploiting the symmetry inherent in STL primitives, which enhances the algorithm's time performance and interpretability. To assess our algorithm's effectiveness and classification performance, we conduct three case studies involving two-class, multi-class, and complex formula classification scenarios.

📄 PDF Abstract BibTeX arXiv:2407.21090

Code (0)

등록된 구현이 없습니다.

Tasks

Classificationglobal-optimization

Classification of Time-Series Data Using Boosted Decision Trees

2021-10-01 · Erfan Aasi, Cristian Ioan Vasile, Mahroo Bahreinian, Calin Belta

Time-series data classification is central to the analysis and control of autonomous systems, such as robots and self-driving cars. Temporal logic-based learning algorithms have been proposed recently as classifiers of s…

Autonomous Driving Classification Self-Driving Cars Time Series+1

Inferring Temporal Logic Properties from Data using Boosted Decision Trees

2021-05-24 · Erfan Aasi, Cristian Ioan Vasile, Mahroo Bahreinian, Calin Belta

Many autonomous systems, such as robots and self-driving cars, involve real-time decision making in complex environments, and require prediction of future outcomes from limited data. Moreover, their decisions are increas…

Autonomous Driving Decision Making Prediction Self-Driving Cars+2

Ternary Logic Encodings of Temporal Behavior Trees with Application to Control Synthesis

2026-04-13 · Ryan Matheu, John S. Baras, Calin Belta arxiv

Behavior Trees (BTs) provide designers an intuitive graphical interface to construct long-horizon plans for autonomous systems. To ensure their correctness and safety, rigorous formal models and verification techniques a…

Knowledge Extraction with Interval Temporal Logic Decision Trees

2023-05-26 · Guido Sciavicco, Stan Ionel Eduard

Multivariate temporal, or time, series classification is, in a way, the temporal generalization of (numeric) classification, as every instance is described by multiple time series instead of multiple values. Symbolic cla…

Classification Time Series Time Series Classification

Deep reinforcement learning under signal temporal logic constraints using Lagrangian relaxation

2022-01-21 · Junya Ikemoto, Toshimitsu Ushio

Deep reinforcement learning (DRL) has attracted much attention as an approach to solve optimal control problems without mathematical models of systems. On the other hand, in general, constraints may be imposed on optimal…

Decision Making Deep Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)