Abstract constituent system (CS) model

Description

Detailed system models – be it for CS or SoS – easily become very large, which makes it difficult or even impossible to analyse these models using conventional methods and tools. Abstraction techniques aim at reducing the size of system models, either by creating a simpler/more abstract version of an existing model, or by creating an simple/abstract system model right from the start. Thereby, the model must preserve relevant (with respect to the property under consideration) system properties. In the context of DANSE, three categories of abstraction techniques have been identified (cf. deliverable D7.3.2):

1.     Abstractions to analyse complex models

These techniques start from an existing complex system model, apply an abstraction function to it (the exact nature of this function depends on the chosen technique), and in this way generate a simpler yet more abstract system model. The abstraction can be done by for example generalising (releasing constraint), merging, or removing parts of the original system specification.

Advantages of these techniques (amongst others):

o    Most abstraction functions can be applied automatically and do not require additional effort from the system developer

o    System developers do not need to determine the essential system parts (i.e., those that should not be abstracted) in the beginning

2.     Abstract specifications

These techniques are used to directly model the system on an abstract level. It is thus up to the developer to leave out those system parts that are irrelevant for the current property under consideration.

Advantages of these techniques (amongst others):

o    The system specification used in subsequent analysis/verification steps does not change (from "original" to "abstract") but remains the same, which increases readability and recognisability

o    The abstract system specification is usually more comprehensible, and thus more usable, since the abstract specification contains less details compared to the whole "original" system.

3.     Abstractions generated from observations

These techniques are used to generate formal system models from behaviour observations only, i.e., when the system is available as a "black box" only.

Advantages of these techniques (amongst others):

o    The techniques can generate a formal system model even in cases where the only information about the system are its input and output behaviour.

o    Even if a formal system model exists, the resulting model obtained from applying these techniques can be more simple than the actual system model.

DANSE research centres on one technique per category:

1.     Abstractions to analyse complex models:

There exist already a number of (by now) state-of-the-art techniques in this category. DANSE research focuses on a technique called "Timing Abstraction. Timing abstractions are used, when verification of timing requirements like end-to-end deadlines are necessary. In DANSE, a state-based timing analysis approach has been worked out, which relies on abstraction functions defined in the context of time. Two kinds of abstraction functions are considered: The first kind of abstraction functions shall only minimize the state-spaces of the interfaces of constituent systems or resources, whereby the result of the analysis is not affected. These abstraction functions are automatically performed by the analysis tool. The second class of abstractions strive to further reduce the state space at the cost of accuracy. Hereby, the results get more pessimistic, but the time needed to verify a property is reduced. These abstraction functions have to be selected by the developer.

2.     Abstraction specifications:

DANSE research in this category focuses on a specification technique called "Visual Logic", which has been further developed in the context of the project. It provides a modelling formalism to model SoS where the aspect of geographical distribution (cf. section 3.9) is most important. In addition, it provides means to specify communications between arbitrary subsystems (CSs) or even subsystem parts.

3.     Abstractions generated from observations:

DANSE research in this category focuses on a technique called "Statistical Learning", which has also been further developed in the context of the project. It is based on Langevin equations, and was adapted for use in the context of SoS. It allows the automatic creation of a statistical model based on its inputs, which allows for a Monte-Carlo simulation of the original input.

The remaining subsections will each be tripartite (at least to some extend) to take the above three categories into account, and will detail the three representative techniques described above.

Initial Situation

1.     Timing Abstraction

So far, the analysis tool automatically performs the minimization of interfaces of a set of considered constituent systems. In the future, a set of abstraction functions shall be provided for the developer, who is then able to compromise between accuracy and execution time of the verification tool.

2.     Visual Logic

At the moment, the Visual Logic can merely be used to model a rather restricted class of SoS, namely  (sequences of) traffic situations on the highway (with the traffic situation being the SoS, the individual vehicles being the CSs). However, it will be extended into a more powerful Graphical Calculus.

The Graphical Calculus will allow to model arbitrary agents (instead of vehicles) on a generalised (yet bounded) 2D "canvas" (instead of the highway) moving along straight or arched trajectories (instead of only straight trajectories).

The Visual Logic is used to model (sequences of) traffic situations on the highway, together with communications between system parts like for example driver, steering wheel or (parts of) the driver assistance system. In this way, it is used to specify typical driving manoeuvres on the highway, like for example entering the highway, overtaking or car following.

A typical example to be modelled with the Graphical Calculus extension would be a production hall, where autonomous robots transport (intermediate) goods to and from different work stations.

3.     Statistical Learning

The statistical learning could be used in several ways:

o    The most common way is to apply it on incoming data, for example from an external very complex source. If this source is indeed too complex for a detailed simulation the statistical learning method could be used to create rather easily an executable abstraction from this data files.

o    Another application scenario is the replacement or analysis of legacy components. The statistical learning method learns the behaviour of the legacy system and could be used to analyse and observe this behaviour or ultimately replace the legacy component completely.

o    The Monte-Carlo Simulation of a learned system is also much faster to execute than most detailed models and therefore could be used whenever time is critical.

Expected Result

1.     Timing Abstraction

Choosing an appropriate abstraction function shall lead to a reduction of the verification time of timing analysis tasks. This is necessary for two kinds of applications: When optimal architectures are searched, analysing a single architecture shall not take much time, such that as many architectures can be analysed as possible. On the other hand, when dynamicity is considered, re-validation efforts shall be minimized. The reduction of the verification time with the aid of reducing the state-space is a prerequisite for this.

2.     Visual Logic

Though the Visual Logic was developed to be simple and intuitive, thus easy to use, it has a formal, automaton-based semantics, which (with some modifications/extension) will be featured by the Graphical Calculus as well. This allows to use well-established tools and formalisms for further analysis of the modelled SoS. For example, it is possible to check whether certain system states can be reached (safety), or whether certain properties hold for all system states (liveness).

3.     Statistical Learning

For the method itself, it works successful, if the learned model would create a good enough abstraction for the original data or system. The method tries to gather statistical quantities and correlations to allow a good statistically sufficient reconstruction of the original signal. It has to be defined which level of accuracy is needed. For example the probability density functions and structure functions of the reconstructed signals have to match the original ones.

Required Tools

1.     Timing Abstraction

o    RTANA (timing analysis tool)

2.     Visual Logic

o    Graphical editor for Visual Logic/Graphical Calculus (still to be developed)

o    Off-the-shelf tools for further analysis of the resulting automaton, for example Uppaal[1]

3.     Statistical Learning

o    MATLAB/SIMULINK for FMI creation

o    FMU/FMI for model exchange

o    DESYRE for the learning and simulation process

The tool flow for Timing Abstraction and Statistical Learning within the DANSE ToolNet environment is shown in Figure 39.

Figure 39: Tool Flow: Abstract Constituent System Models

Activities

In general, performing an abstraction is divided into the activities shown in Figure 40. After identifying the existing CS to be handled, the choice of abstraction methods depends on whether an internal model of the CS is known, and – if so – whether this internal model is actually needed in further development steps.


Figure 40: General Abstraction Methodology

Figure 40 shows the general abstraction methodology for the three categories of abstraction techniques. We detail the three abstraction activities into further subactivities as follows:

1.     Timing Abstraction

o    Choose an appropriate abstraction from a set of offered abstraction functions

o    Run RTANA

o    If result is too pessimistic, choose another abstraction function, or run RTANA without any abstraction functions. RTANA will then use only its minimization techniques

2.     Visual Logic

The application of the Visual Logic method is divided into the subactivities shown in Figure 41.

Figure 41: Visual Logic

Identify necessary snapshots:

The snapshots necessary for the driving manoeuvre to be modelled are identified. Snapshots are distinguished based on the position of vehicles. Positions are considered separately for the two dimensions: a vehicle can (laterally) be on a lane or in between two lanes, and two vehicles can (longitudinally) be in one of seven (if only one vehicle size is allows) respectively one of thirteen (if vehicles can have different sizes) relations (cf. James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11), 832-843 (1983)).

Model CSs (cars) for each snapshot:

Once the necessary snapshots have been identified, vehicles are positioned in each snapshot, such that the spatial relations between the vehicles and/or lane separators model the desired traffic situation.

Model communications for each snapshot:

Next, the communications between vehicles and vehicles parts are modelled for each snapshot.

Translate specification into automaton model:

Finally, the resulting visual logic specification is translated into a formal automaton model, which can be used for further analysis.

3.     Statistical Learning

The application of the Statistical Learning method is divided into the subactivities shown in Figure 42:

Prepare Task:

o    Identify values to be learned

o    How many variables are necessary?

o    Identify further values only to be condition on (not learned)

o    Identify/modify the range and distribution of input values for optimal results

Input values  to learning method (done by FMI or DESYRE):

o    The FMI master has to transfer the necessary input values into the learning FMU in every step

Check if learning is finished:

o    EOF – End of (Data) File

o    Necessary statistical accuracy is reached

Start reconstruction:

o    Define valid initial values (only first step)

o    Input conditional (not learned) and previous values per FMI/master each step

o    Retrieve reconstructed values and transfer them to other CS components

Figure 42: Statistical Learning

Limitations

1.     Timing Abstraction

The limitations of the timing abstraction techniques directly depend on the limitations of the timing analysis tool (see section 5.10 for details).

2.     Visual Logic

As mentioned above, the Visual Logic can currently model only a rather restricted class of SoSs: traffic situations on the highway, with vehicles being the individual CSs. Once the extension into the Graphical Calculus is finished, it will be possible to handle more general SoSs, where the (directed) highway is replaced by an (almost) arbitrary 2D plane, and vehicles are replaced by agents that cannot only move on straight trajectories but in addition on arched trajectories.

3.     Statistical Learning

In general this method is limited to markovian systems, but many applications show also good results for more general systems. However, the biggest disadvantage of the method is that it needs always a certain time/amount of data for the learning process, although it is possible to create a system by using assumptions only and entering them into the model directly.

Follow-up Solution Methods

1.     Timing Abstraction

o    Generate optimized architectures: determine the performance of the current architecture and find "better" ones (with respect to the used metrics)

o    Generate architecture alternatives: if some timing properties are violated, adapt the architecture in an appropriate way

2.     Visual Logic

The automaton model resulting from a Visual Logic specification (and later from a Graphical Calculus specification) can be used in many off-the-shelf tools. If timing constraints are used in the Visual Logic specification, the resulting automaton is a timed automaton, such that for example Uppaal could be used for further analysis. 

3.     Statistical Learning

A possible follow-up method could evaluate the difference in the SoS between using the original (legacy) components and when using the learned components. Since the statistical learning method will only create (and check for) a statistical representation it will always deviate from the absolute values of the original signals.


[1] www.uppaal.org