# Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming
## 6 Experimental Evaluation
### Data Processing  
The aim of the data processing step is to extract useful attributes. Chiefly, we want attributes that (1) are more meaningful to the other road settings than the one considered in this study and (2) effectively describe the phenomenon at hand, i.e., capture measurements that are relevant for monitoring road traffic. The first point discards attributes such lane identifier and position with respect to the reference point since they would be of no interest for roads with a different topology and number of lanes. At the same time, we want attributes that are relative to the vehicle and not to the setting. For example, positions and coordinates should be relative, not absolute. As a result, formulas are more readable as they employ attributes that are immediately comprehensible. In the following, we detail how we extracted additional attributes from the ones reported in the original dataset. A set of very relevant attributes is the set of distances from the nearest neighbors of each vehicle. Intuitively, such a set of attributes is relevant for drivers and allows formulas to clearly and synthetically be expressed such as \" keep a safety distance of at least 10 m from the closest front vehicle\". To formalize this, we partition the space surrounding each vehicle as shown in Figure 4, and we find the closest vehicle in each of the eight regions. We thus consider eight new attributes, namely E, SE, S, SW, W, NW, N, and NE. To efficiently compute them, we used a kd-tree [30], a spatial data structure. Given a query point and a set of \(k\)-dimensional points, it allows for logarithmic-time (in the number of points) look-up of nearest neighbors, improving over the quadratic time (in the number of points) of a brute-force search. For us, points are cars and are bi-dimensional (lateral and longitudinal offsets with respect to the reference position). Given that construction and update take both linear time (in the number of points) for a kd tree, we built a separate tree for every frame instead of updating all cars' positions. Finally, after having found the nearest neighbors for every car and for every frame, we trimmed neighbors that might not be sensed in a real-world setting. In particular, we set to \(-\infty\) the distances above 485 ft. Moreover, we limit the neighbor search to the current and adjacent lanes of a vehicle, as we assume that drivers do not care about vehicles in far lanes. To summarize, we built a dataset with velocity (vel) and eight distances (E, SE, S, SW, W, NW, N, NE) as attributes, which together form the set of attributes \(A\) mentioned in Section 4. On the other hand, width and height were discarded. Figure 4: A car and its eight neighboring regions. Regions are labeled using cardinal directions. Boundaries can be swiftly computed starting from the \(x,y\) positions of the front-left corner of the car, using car width and car height (provided in the dataset). We do not consider trajectories being longer than \(t_{f}=20\,\mathrm{s}\), since that could result in specifications requiring agents (both human and automated) to consider an unpractically long behavior history. To accomplish this, we partitioned the trajectories as follows. Let \(|\mathbf{x}|\) be the number of samples for trajectory \(\mathbf{x}\). For each trajectory \(\mathbf{x}\in\mathcal{X}\), we split it into a new set of trajectories by sliding a window of size \(n\) over it, with \(\frac{n}{2}\) overlapping, obtaining approximately \(\frac{2|\mathbf{x}|}{n}\) new trajectories. The resulting pool of trajectories shares the same length \(n\), which must be chosen to reflect a sensible interval of monitoring for an autonomous agent. Thus, we set \(n=200\), corresponding to \(20\,\mathrm{s}\) for this dataset. We remark that, by fixing \(n=200\), all the new trajectories will have a maximum size (number of samples) of \(200\); given that, with our grammar, the maximum necessary length of the formula is \(198\) (see Section 5.3), no issue regarding the necessary length of formulas arises.