# Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming
## 2 Related Work  
There exist several approaches devoted to learning temporal logic specifications, particularly for STL. We partition here them into two categories: template-based and template-free. While those in the former category rely on a user-provided template formula and focus on estimating parameters for it, the latter also try to learn the formula structure. We fall in the template-free domain.  
Template-based methods cast the STL specification mining problem as an optimization problem in terms of the satisfaction degree \(\rho\) of an STL formula (see Section 3). Succinctly, we define \(\rho\) as a (real-valued) degree of satisfaction of an STL formula with respect to a trajectory. [PERSON] et al. [7] adopted an active learning approach, dependent on a probability distribution over \(\rho\), to query the next point in the parameters space to be evaluated. [PERSON] and [PERSON] [8] extended the work cited previously with a statistical approach that emulates the expected value of this probability distribution using Gaussian Process Regression [9]; optimization of the emulation was then performed via the GP-UCB algorithm [10]. In general, these approaches are labeled as Parametric Signal Temporal Logic (PSTL) [11; 12].  
Although interesting on its own, the applicability of PSTL is sometimes limited, since specifying templates can be hard to start with. As such, template-free methods also attempt to build an optimal structure for the formula. The vast majority of the works in this regard start from a dataset of labeled trajectories, partitioned into positive and negative examples, and try to learn an STL classifier for the data. As an example, [PERSON] et al. [13] proposed ROGE (RObustness GEnetic algorithm), a bi-level optimization procedure, which optimized the structure by a genetic algorithm and the parameters using Bayesian Optimization. To the best of our knowledge, it is the only attempt at using an evolutionary algorithm for solving the template-free problem. Others mined STL structure by exploring a directed acyclic graph [14], using a decision-tree oriented approach [15], or employing enumerative solvers [16].  
The achievements of the aforementioned approaches have been remarkable, but none of them addressed the problem of mining STL specifications from unlabeled data. Considering real-world scenarios, it is often the case that we labeled data that are not available, because labeling is costly. Still, those data do bring some information that could be, in principle, condensed in the form of an STL specification. Some special cases of the unlabeled data case have been considered: [PERSON] et al. [17] and [PERSON] et al. [16] addressed unsupervised clustering of time-series data using PSTL, i.e., they learned just the parameters of template formulas.  
To the best of our knowledge, the only work learning both structure and parameters of a formula from unlabeled data is [18], where the authors proposed a heuristic for sequentially building more complex formulas. This seems a very interesting approach, but its applicability to large datasets is unclear: the experimental evaluation of the cited paper is based on a single trajectory and the results concerning the learning of the structure of the formula are not clear. Unfortunately, the code is not available and this hampers reproducibility and comparisons.  
A different approach for designing automatic rules for road traffic has been proposed by [PERSON] et al. [19]. Similar to this study, the authors relied on grammar-based genetic programming and did not use labeled data. Differently from here, they did not use STL as the syntax for the rules and they optimized rules with the goal of maximizing the efficiency and safety of (simulated) road traffic rather than for describing real data of road traffic.