Semantics-based Abstraction

• In this section, we describe the steps to build the specification-oriented semantics abstraction model, and the refinement process. Also, we introduce the steps that how to use the abstract model to predict the semantics of the incoming states.

A Running Example

Let us consider an autonomous vehicle with the adaptive cruise control (ACC) system, shown in the figure above. ACC receives the information from cameras, lidar, and radar sensors and outputs an acceleration or deceleration command to manipulate the vehicle’s speed. There are two requirements for the system: 

1. Distance requirement φdist, which means the vehicle must maintain a safe distance from the leading car; 

2. Velocity requirement φvelo, which says velocity should be close to the user-set cruising speed when the distance requirement is satisfied. Suppose, in state s, the degree of satisfaction of distance requirement is 15, and the degree of satisfaction for velocity is −7 (a negative number represents the violation of the requirement). The semantics of ACC is (15,-7).

Experience Collection

To construct the model, we first conduct a large number of simulations of the CPS with respective sub-controllers, which aim to collect enough characteristics of the system. Taking the simulation data and the AI-CPS as input, we then profile the system to extract information, i.e., semantics, actions, and transitions, which can represent the system behavior. The input to the abstraction is a set of traces that records the semantics information, actions, and transitions taken during the simulation. Then, we abstract the semantics, action, and transitions to construct our semantics-based abstract model. 

After the semantics is obtained, each concrete state si in the semantics space is a vector. Such a granular representation is still impractical for further analysis since each dimension of the state is continuous, which means the state space could be prohibitively large. Thus, we perform state abstraction to group the states that are close. We perform two steps to construct the abstract states. First, since the scale of different requirements might be different, we perform normalization to normalize the data into a unifying scale. Specifically, the degree of satisfaction is normalized to [−1, 1]. A positive (negative) number indicates the case of satisfaction (violation), and a higher/lower number represents the requirement that is more satisfied (violated) by the system. 

A good abstract model should be a succinct and precise model at the same time. Succinctness means the number of states should be small, while preciseness implies that the semantics error between the abstract states and concrete states is small. Note that there is a trade-off between these two requirements: smaller abstract space, i.e., less abstract states, may lead to greater error in terms of semantics values, and vice versa.

The minimum distance ensures two segments should reflect different semantics levels, and the minimum number of enclosed concrete states prevents the occurrence of redundant segments which only contain a few concrete states. In addition, we notice that some special concrete states indicate critical circumstances, namely, extreme violation or satisfaction with specifications. Merging these concrete states into the neighbour abstract states may cause a significant error in semantics values; thus, we use the third parameter, maximum distance, to split these particular states as individual abstract states. The values of the semantics of an abstract state are computed as the a

We propose an algorithm for refining the state abstraction, which targets at reducing the semantics error between the abstract states and the corresponding enclosed concrete states. Our semantics-based abstraction method not only narrows the huge state space of CPSs but also provides a human-interpretable way to describe the status of a system in terms of the degree of satisfaction with different specifications. Namely, despite the numerous system information collected by sensors, designers can understand the system characteristics and controller behaviors intuitively and transparently. More attention can be called regarding the safety and functional requirements during the construction of control systems in AI-CPSs

Abstract Model Selection

There are five parameters in equation (1): e_MAX, e_MEAN, d_MIN, d_MAX, n_MIN, where e_MEAN and e_MAX are the predefined average and maximum tolerances of the abstraction errors on j-th dimension, d_MIN and d_MAX are the minimum and maximum lengths of segments on j-th semantics dimension, and n_MIN is the minimum number of concrete states in the segments on j-th dimension. For e_MAX and e_MEAN, we set them as 0.05 and 0.2, respectively (shown in the manuscript Section 4.2.3). The intuition is that we would like to get a small mean and maximum tolerances for the abstraction error.

For d_MIN, d_MAX, and n_MIN, in order to acquire a succinct and precise model, we select the parameters by Algorithm 1 in the manuscript, which we describe as follows: As introduced in Section 3.2.3, it is a challenging task to search the suitable state abstraction parameters while satisfying the semantics error constraint. To construct a succinct and precise model, we thus design an abstraction refinement process (Algorithm 1 in the manuscript) which automatically updates the parameters, i.e., d_MIN, d_MAX, and n_MIN, based on a pre-generated list of 3-tuple. Each tuple is a sequence of the three parameters, and each element is generated as follows: d_MIN is a set of values from 0.01 to 0.1 with the step size of 0.001, d_MAX is a set of value from 0.005 to 0.1 with the step size of 0.005, and n_MIN is a set of value from 0.1% to 10% with the step size of 0.1%. The list is a permutation of the values of three parameters. The automatic update procedure picks an element in the list, and the Algorithm checks whether it satisfies the requirement (Line 8 of Algorithm 1) of preciseness, i.e., the semantics error is less than the threshold, and succinctness, i.e., the reduction level is lower than the threshold. Let us take the parameters selection experiments on AFC and BBC as an example. Table I is the parameters for AFC and Table II is for BBC. The figure below shows the results of the preciseness, measured in semantics error, and succinctness, measured in model size, for two systems. The x-axis is the parameter set, and the y-axis is the relative value (The reference for semantics error is Set 1, and the one for model size is Set 10). Assume the algorithm iterates over 10 sets of parameters. First, the algorithm finds that some sets of parameters do not satisfy the two requirements, e.g., Set 1, 2, 3, 9, 10, and finally finds that Set 6 satisfies the two requirements. If we continue the iteration, we may find some other parameters that might also work (e.g., Set 7 in AFC). However, Set 6 is the first set that satisfies the requirement; thus, we take Set 6.

The abstraction maps the large, concrete state space of CPSs onto a more compact space and preserves the degree of satisfaction w.r.t different system specifications. So, our abstract model can provide an intuitive description and understanding of the system operation status. Moreover, the specifications we used for abstractions and evaluations are directly extracted from the documents of the collection systems. 

For the degree of satisfaction, we manually and carefully design the formula that can reflect the extent of the satisfaction/violation for the specification of the system. The formulae are in the form of Simulink blocks, which is hard to display on paper. Thus, we put the detailed formulas and computation of the degree of satisfaction for each specification on our supplement website.

High-dimensional continuous state space is one of the major challenges in reinforcement learning, as it makes the search for optimal policy computationally intractable. In addition, unlike the commonly used reinforcement learning benchmarks with discrete state space, CPSs usually come with complicated dynamics and multiple operation requirements which require more efforts to construct reliable control systems. 

Our abstraction can decompose the concrete state space and transfer to a more compact abstract state space. Each abstract state should represent a group of concrete states that share similar physical information regarding the degree of satisfaction with different specifications. Therefore, by observing the abstract states enclosed by each simulation trail, we can intuitively understand the satisfaction/violation w.r.t specifications. A brief overview of the behavior characteristics of the controller can be derived so that we can interpret the strengths and weaknesses of the current controller regarding different system requirements. Classic ensemble methods such as majority-vote cannot be directly applied to the CPS scenario due to the continuous action space. Certain abstraction techniques are required to narrow the action space to limited options; therefore, further various ensemble strategies become adaptable. Moreover, it is also challenging to conduct semantics prediction on concrete state space. Since when encountering unseen concrete states or actions during simulations, concrete state-based semantics predictions are unavailable as no reference exists in collected experience. 

Our semantics abstraction maps the concrete states from different regions onto specific abstract states accordingly. Namely, we are able to transfer unseen concrete states to proper abstract states and predict the incoming semantics, which can guide our newly proposed ensemble strategies. Overall, semantics abstraction is necessary as it not only reduces the large state space with better transparency but initiates the predictability of the semantics of the incoming states, which is vital to our ensemble strategies.

In order to deliver a more concrete understanding of the negative impact of semantics errors on ensemble strategies, we conduct additional experiments to show the performance of semantics-guided ensemble strategies with abstract models with different semantics errors. As three of our newly proposed ensemble control strategies leverage the semantics prediction to guide the control output aggregation, namely, Top-1 Semantics Prediction (Top-1 Pred), Top-k Semantics Prediction (Top-k Pred), and Coordinator with prediction (Coordinator Pred). We aim to demonstrate the performance of these semantics-guided strategies with increasing semantics errors. We choose Satisfaction Rate (SATE) as the performance indicator as it provides an overview satisfaction ratio regarding the specifications. We perform the experiment on AFC and BBC. 

Table III shows the result of AFC, Table IV is for BBC, and Figure 2 pictorially illustrates the result for two systems. We carefully select hyperparameters during the semantics abstraction to For each system, we construct 9 new abstract models with different errors, from the order of 10E-05 to the order of 10E-02, on each semantics dimension. 

From Figure 2, we can see that the performance of three ensemble strategies drops (lower SATE) as the semantics errors keep increasing. This finding is in accord with our discussion in Section 4.4.4 that a well-refined abstract model is required to provide precise predictions of incoming semantics; otherwise, the semantics-based controllers can be misguided to unexpected states. Namely, a competent abstract model should provide semantics predictions within a limited error tolerance. However, this error limit highly depends on semantics with typical specifications. Considering the plate semantics error in BBC, the SATE of three strategies drops to about 75% when the plate semantics errors are around 0.0034. However, these strategies still have a relatively good performance on the ball specification with a similar level of errors on ball semantics. We consider this semantics error interpretation regarding different specifications as one of our future works.