Model-Based Development of an Adaptive Vehicle Stability ...€¦ · BASICQ T AVAILABLE Ay measured vYaw_based V_CarRef wheel_based S LI P _P ROB(low, me d, high) ax_based vYaw ay_based

Model-Based Development of an Adaptive

Vehicle Stability Control System

Rasmus Adler, Ina Schaefer, Tobias SchüleFraunhofer IESE and TU Kaiserslautern

Germany

Workshop “Modellbasierte Entwicklung eingebetteter Fahrzeugfunktionen”14. März 2008

Berlin

Self-Adaptive Systems

What are the special features of these systems?

adaption of algorithms according to current state of environment




Faults andEnvironment

Changes





Changes

Runtime adaptation





Changes

Runtime adaptation

Degrade functionality to remain operational byswitching to different predetermined configuration





Changes

Runtime adaptation

SafetySurvivability

Degrade functionality to remain operational byswitching to different predetermined configuration

Adaptive Systems DevelopmentAdaptation increases design complexity, since

decentralized adaptation mechanism

reconfiguration triggers reconfiguration complex interdependencies

Adaptive Systems DevelopmentAdaptation increases design complexity, since

decentralized adaptation mechanism

reconfiguration triggers reconfiguration complex interdependencies

Solution:

Model-Based Design of Adaptive Systems

Integrated with Formal Verification of Adaptation Behaviour

Outline

Case Study: An Adaptive Vehicle Stability Control System

MARS Modelling Concepts

Development Process and Verification

Conclusion and Future Work

Adaptive Vehicle Stability Control

System Architecture

Controller Components

Actuator

ComponentsTraction Control

Yaw Rate Corrector

Steering Angle Delimiter

Sensor

Components

steering_angle_Input

yaw_rate

ayax

brakeGas_Input

steering_angle_cntrl

rear_brake_cntrl

left_brake_cntrlright_brake_cntrl

v_wheelFR v_wheelFL v_wheelRL v_wheelRR

Controller ComponentsController Modules

steering_angle_Input

v_CarRef

wheel slip

v_yaw

brake

delimited_steering_angle

corrected_ rear_brake

corrected_left_brakecorrected_ right_brake

Steering Angle Delimiter

gasdelimited_gas

Yaw Rate Corrector

Traction Control

Main Concepts reducing Design Complexity:

Modular System Structure

Propagation of Adaptation by Quality extended Data Types (Datives)

Separation of Adaptation and Functionality in Components

Adaptive System Modelling (MARS)

Qualities

UNAVAILABLE

BASICQT

AVAILABLE

Ay

measured vYaw_based

V_CarRef

wheel_basedSLIP_PROB(low,med,high)

ax_based

vYaw

ay_based

Adaptive Components

Input and Output Ports for Functional Data

Required and Provided Ports for Qualities

Set of Predetermined Configurations with Pre- and Postconditions on Input and Output Qualities

v_yaw

v_wheelFR

steering_angleInput

yaw_rate

ay

v_CarRef

P1

P9

P8

P7

P6

P5

P4

P3

P2Pre2 Post2 P6:STEERING_ANGLE && P9 -> STEERING_BASED(P8:VWHEEL_BASED && SLIP_PROB == low)

Pre4 Post4P4:VWHEEL && P5:VWHEEL P9 -> RWHEEL_BASED

Pre3 Post3P2:VWHEEL && P3:VWHEEL && P9 -> FWHEEL_BASEDP6:STEERING_ANGLE

Pre1 Post1P1:VYAW_MEASURED P9 -> SENSOR_BASED

Configuration Measured

Pre5P7:MEASURED && (P8:AX_BASED || Post5 P8:WHEEL_BASED && SLIP_PROB == low ) P9 -> AY_BASED

Pre6 Post6TRUE P9 -> UNAVAILABLE

Configuration SteeringBased

Configuration FWheelBased

Configuration RWheelBased

Configuration AyBased

Configuration Off

Component VYawCalc (Adaptation Specification View)

port number port name referenced QT quality flow

P1: yawrate VYAW_MEASURED requiredP2: v_wheelfl VWHEEL requiredP3: v_wheelfr VWHEEL requiredP4: v_wheelrl VWHEEL requiredP5: v_wheelrr VWHEEL requiredP6: steering_angle STEERING_ANGLE requiredP7: ay AY requiredP8: v_carref VCARREF requiredP9: v_yaw VYAW provided

v_wheelFL

v_wheelRR

v_wheelRL

Configuration AyBasedPre5 Post5

P7: measured &&(P8: ax_based || P9 ! ay_based

P8: wheel_based && slip_prob == low)

P7

P8

P9

Component VYawCalc (Adaptation Specification View)

UNAVAILABLE

BASICQT

AVAILABLE

Ay

measured vYaw_based

V_CarRef

wheel_basedSLIP_PROB(low,med,high)

ax_based

vYaw

ay_based

Adaptive Components (3)

Modelling AdaptationComponent VYawCalc (Adaptation Specification View)

Configuration MeasuredPre1 Post1

P1: vYaw_mesured P9 ! sensor_based

P1

P2

P3

P4

P5

P6

P7

Configuration SteeringBasedPre2 Post2

P6: steering_angle && P9 ! steering_based

(P7: vWheel_based && SLIP_PROB == low)

Configuration FWheelBasedPre3 Post3

P2: vWheel && P3: vWheel && P9 ! fWheel_based

P6: steering_angle

Configuration RWheelBasedPre4 Post4

P4: vWheel && P5: vWheel P9 ! rWheel_based


P7: measured && (P8: ax_based || P9 ! ay_based

P8: wheel_based && SLIP_PROB == low)

Configuration OffPre6 Post6

TRUE P9 ! UNAVAILABLE

P8

P9

measured

wheel_basedSLIP_PROB == low

UNAVAILABLE

UNAVAILABLE

UNAVAILABLE

UNAVAILABLE

UNAVAILABLE

UNAVAILABLE




P1

P2

P3

P4

P5

P6

P7






P6: steering_angle








P8

P9

measured





P1

P2

P3

P4

P5

P6

P7






P6: steering_angle








P8

P9

measured





P1

P2

P3

P4

P5

P6

P7






P6: steering_angle








P8

P9

measured





P1

P2

P3

P4

P5

P6

P7






P6: steering_angle








P8

P9

measured


ay_based

Development ProcessMARS Models

(GME)Simulink Models

Code Generation(Real Time Workshop)

Theorem Proving

Simulation Probabilistic Analysis

SAS Models

Model Checking (Averest)

Development ProcessMARS Models

(GME)Simulink Models

Code Generation(Real Time Workshop)

Theorem Proving

Simulation Probabilistic Analysis

SAS Models

Model Checking (Averest)

Verification of Adaptation Behaviour

System Properties

“Is the system stable?”

Classification

adaptation functionality

application–specific

generic

“Is configuration C active at point t?”

“Are theredivisions by zero?”

“Is the value of X always greater

than zero?”

System Properties

“Is the system stable?”

Classification

adaptation functionality

application–specific

generic

“Is configuration C active at point t?”

“Are theredivisions by zero?”

“Is the value of X always greater

than zero?”

No module gets stuck in the default configuration ‘off ’:

Every module can reach all configurations at all times:

No inconsistent states can be reached:

No configuration is always only transient:

Adaptive Generic Properties

AG(c = o! ! EFc "= o!)

AG(n!

i=1

EF c = configi)

AG(n!

i=1

c = configi)

n!

i=1

EFEG c = configi

Properties of VSC System Controller Modules correctly implement Fail-Safe Layer.

Traction Control:AG((gas output.quality = available

! gas input.quality = available)" ctraction control #= O! )

Steering Angle Delimiter:AG((steering angle input.quality = available

! steering angle servo.quality = available)" csteering angle delimiter #= O! )

Yaw Rate Correction:AG((wheel brakeFL.quality = available

! wheel brakeFR.quality = available! wheel rearBrake.quality = available)! brake input.quality = available" cyaw rate corrector #= O! )

Figure 6: Safety Properties of Core Modules

erties for each module and also that the fail-safe modes ofthe core modules satisfy the safety requirements.

In the evaluation of our approach, we have reduced theoriginal vehicle stability control system with respect to thegeneric adaptation properties for each module i by system,module and adaptive slicing as well as by a combinationof adaptive and system slicing. For each module i and therespective reduction algorithm, we obtained a system con-taining the relevant system parts in the selected level of de-tail. Furthermore, we have reduced the original system withrespect to each of the three safety properties of the coremodules by system, module and adaptive slicing as well asby a combination of adaptive and system slicing. Here, weobtained reduced systems for each of the three propertiesin the selected granularities. We have measured the timesnecessary for each reduction and the time for the analysis ofthe respective system by model checking.

#Var.

Slicing

Time

[s]

Analysis

Time

[s]

(generic)

Analysis

Time

[s] (fail-

safe)

Original Model 232 n/a 9.22 263.35Adaptive Sliced 148 0.007 2.78 143.12System Sliced 112 0.140 2.10 9.57Ad.-Sys. Sliced 48 0.043 1.53 12.03Module Sliced 38 0.043 1.49 11.90

Table 1: Slicing for Vehicle Stability Control

Table 1 shows the average sizes of the systems before andafter reduction by slicing in di!erent levels of detail and theaverage times required for the reductions with the di!er-ent slicing techniques. Furthermore, it shows the averageanalysis times over the systems reduced with the same slic-ing technique for the generic adaptation properties for eachmodule and for the fail-safe properties of the core modules.It can be observed that the size of the model expressed bythe average number of variables decreases the more detailedthe reduction is. As expected, module slicing provides thebest possible model reduction minimising the number of sys-tem variables by 85 %. Furthermore, we see that the timefor computing the reduction increases the more detailed theanalysis is. In this direction, adaptive slicing allows large

model reductions without a detailed analysis by design ofSAS models. The reason why system slicing in this exampletakes longer than module slicing is that the number of inter-connections in the considered example system is rather highwhereas the modules themselves do not contain many vari-ables. In a more loosely coupled system slicing can outper-form module slicing. Furthermore, if we perform adaptiveslicing followed by system slicing the time for the reductionis about the same as for module slicing because no functionalconnections have to be considered for system slicing.

With respect to the average analysis times required byAverest, it can be observed that all reductions allow sig-nificant speed up in verification time, e.g. by 95% for thefail-safe properties on the module sliced system. For thegeneric adaptation as well as for the fail-safe properties itholds that the smaller the model is the more e"cient ver-ification is possible. The average verification time for thefail-safe properties on a system that is reduced by systemslicing is unexpectedly small. The reason is that coinci-dentally this specific verification problem allows an e"cientrepresentation of the models in the internal BDD packagesof the model checker which does not apply in general andcannot be e"ciently predicted in advance.

5. RELATED WORKThe verification of adaptive systems has become an ac-

tive area of research [12, 22, 23] in order to find models forsafe adaptation behaviour. However, these approaches donot provide a constructive modelling technique but requireto specify the global adaptation behaviour directly whichis hardly feasible for complex systems as in the automotivedomain. In this direction, the presented approach aims atthe integration of the constructive and explicit modellingtechnique MARS [19] for adaptive embedded systems withformal verification. In [17], verification of MARS models us-ing model checking was first proposed. In this work, MARSmodels are translated directly to input of the model checkersuch that the applicability is limited to smaller models.

Slicing has been introduced in [21] as an e!ective tech-nique used for debugging and program comprehension insequential programs. A survey of techniques can be foundin [18]. Recently, slicing has also been used for concurrentstate-based system models, e.g. extended hierarchical au-tomata [20, 10, 11] or input/output transition systems [13].However, most of these approaches work on relatively low-level model representations in contrast to SAS models cap-turing the high-level intuition of adaptive modelling con-cepts. In [5], slicing is used to reduce software architec-ture models expressed by UML statecharts. However thecomponent-based structure of software architecture modelsis not exploited for determining irrelevant parts with respectto the considered property.

With respect to model reduction for model checking, coneof influence reduction, e.g. for Boolean circuits [4], is ap-plied to the internal model representations similar to staticbackward slicing. In BANDERA [9], a model checking envi-ronment for Java, program slicing techniques for Java pro-grams are applied. Slicing for Promela, the concurrent inputlanguage for the Spin model checker, is proposed in [14].

In SAL [8], slicing on a low-level intermediate transitionsystem representation is used for model reduction. AlthoughSAL specifications have a modular structure, the modular-ity is not exploited for slicing. The IF [3] framework applies

Experimental ResultsTable 2 shows the number of fixpoint iterations performed during model checking and thetime required to check Properties 1–4 on a Pentium 4 processor with 2.8 GHz and 512MB RAM. As these properties actually represent sets of formulae (one formula for eachcomponent/configuration), we have determined minimal, average, and maximal values inaddition to the total ones. The total time required to check all properties was less than threeminutes. Stability could not be checked in less than one hour by means of standard modelchecking procedures for LTL. However, using the approach presented in [ASSV07], itcould be checked in less than half an hour (1723 seconds). Nevertheless, there is still alarge gap compared to the runtimes for Properties 1–4. The main reason for this is that thelatter can benefit from abstractions such as cone of influence reduction [CGP99], whereaschecking stability requires considering the complete system.

Property Time [seconds]Min. Avg. Max. Total

P1 (liveness) < 0.1 3.1 71.5 84.0P2 (reachability) < 0.1 2.4 52.1 63.8P3 (safety) < 0.1 0.1 0.2 0.7P4 (persistence) < 0.1 0.3 4.5 19.6

Table 2: Experimental results of model checking

It should be mentioned that not all of these properties were satisfied in the initial designof the vehicle stability control system. For example, it turned out that the configurationFWheelBased of the component VYawCalc was never active for more than a single cy-cle (violation of Property 4). This behavior was due to interdependencies between thecomponent VYawCalc and other components that caused it to switch to the configurationSteeringBased in the next cycle. Although this particular case might not be safety-critical,the results of verification are often useful for gaining a better understanding of the wholesystem.

Besides the properties described above, which are concerned with generic features of theadaptation behavior, we also checked a number properties ensuring that the system al-ways provides its basic functionality given that the minimal required sensors and actua-tors are operational. In particular, if the sensors and actuators concerning steering angle,brake force, and gas are operational, neither of the corresponding controller componentsis in the shutdown configuration Off. In this way, it is guaranteed that the adaptationbehavior implemented in the system does not corrupt any essential functionality. For ex-ample, if the intended steering angle is available and the steering servo works, i.e., delim-ited steering angle quality is available, then the component SteeringAngleDelimiter is notin the configuration Off :

AG((steering angle driverInput quality = available!delimited steering angle quality = available)" c(SteeringAngleDelimiter) #= Off)

As another example, the following property ensures that the braking system does not fail

12

As a model checking back-end, we use Averest,2 a framework for the specification, imple-mentation, and verification of reactive systems [SS05]. In Averest, a system is given in asynchronous programming language, which is well-suited for describing adaptive systemsobtained from SAS models, as both are based on a synchronous semantics. Furthermore,a causality analysis of synchronous programs can be used to detect cyclic dependenciesthat may occur if the quality flow generated by an output is used as input in the samecomponent. Specifications can be given in temporal logics such as CTL and LTL (seeSection 5).

Once the adaptation behavior of a MARS model has been successfully validated and veri-fied, it can be implemented by means of a given adaptation framework. Such a frameworkmight either be a central component in the system coordinating all adaptation processesor be distributed over several components. We have developed a distributed frameworkin MATLAB-Simulink,3 which provides an interface for the integration of the function-ality and supports code generation using Simulink’s Real-Time Workshop. Additionally,the framework offers a generic configuration transition management, which can be usedto specify the interaction between functionality and adaptation behavior in more detail.The resulting design can then be evaluated by co-simulations of functional and adaptationbehavior. In order to avoid undesirable interference between functional and adaptation be-havior, additional techniques may be employed that guarantee smooth blending betweenfunctional outputs during reconfigurations [Bei07].

5 Experimental Results

In this section, we present experimental results on the verification of the vehicle stabilitycontrol system using model checking. Table 1 shows some characteristics of the system.

Number of components 28Number of configurations 70Lines of code ! 2500Number of reachable states ! 5 · 1018

Number of properties 151

Table 1: Characteristics of the vehicle stability control system

As specification languages for reasoning about adaptation behavior, we employ the tem-poral logics CTL (computation tree logic) and LTL (linear time temporal logic) [CGP99,Sch03]. In both CTL and LTL, temporal operators are used to specify properties along acomputation path that corresponds to an execution of the system. For example, the for-mula F! states that ! eventually holds and G" states that " invariantly holds on a givenpath. In CTL, every temporal operator must be immediately preceded by one of the pathquantifiers A (for all paths) and E (at least one path). Thus, AG! and EF" are CTL formu-

2http://www.averest.org3http://www.mathworks.com

10

Characteristics of Vehicle Stability Control System

Analysis Times for Generic Adaptive Properties

Related WorkModelling and Verification of Adaptive Systems

[Zhang, Cheng; 2005/06]:Modelling and Verification of Adaptation Behaviour based on Petri Nets

[Schneider, Schüle, Trapp; 2006]:Direct Translation of Modelling Concepts to Verification Tools

[Bradbury et al.; 2004]:Survey on Self-Managed Software Architectures

Conclusion

Modelling Concepts for Adaptive Systems

Integration of Model-based Development and Formal Verification

Future Work

Extension of Modelling Concepts with Intuitive Property Specification at Modelling Level

Further Development of Verification Techniques

Propagation of Verification Results back to Modelling Level

Documents

Model-Based Development of an Adaptive Vehicle Stability ...€¦ · BASICQ T AVAILABLE Ay measured vYaw_based V_CarRef wheel_based S LI P _P ROB(low, me d, high) ax_based vYaw ay_based