============================= Automotive Challenge Problems ============================= This document lists a set of challenge problems from the automotive domain. The challenge context is model-based design and implementation of embedded systems, therefore, the problems have been divided into categories, each associated with a phase in the design and development process. The challenge problems are generic, in the sense that they apply to most automotive applications, however in the following descriptions we focus on the two particular automotive applications used in the context of the MoBIES project, namely, Powertrain Control (PC) and Cooperative Adaptive Cruise Control with Collision Warning (CACC+CW). For each challenge problem we provide a short description, give pointers to documents which describe the problem in sufficient detail to understand what is the problem and what would be considered a contribution to its solution, and a contact person who can respond to questions related to it. For each contact person not with UC Berkeley, an additional UCB contact who should also be included in correspondence is listed. Table of Challenge Problems 1. Modeling 1.1 Multiple-view modeling 1.2 Automated composition of sub-components 1.3 (Wireless) communication models 2. Model Analysis 2.1 Automatic test generation 2.2 Verification 2.3 Synthesis of switching 2.4 Performance 3. Implementation 3.1 Test vector generation 3.2 Schedulability analysis 3.3 Code generation 3.4 Code debugging and testing 3.5 RTOS generation 3.6 Allocation to distributed platforms 4. Integration 4.1 Model translation 4.2 Integration of different models of computation 4.3 Tool Integration 4.4 Software/hardware Integration 1. Modeling 1.1 Multiple-view modeling Primary point of contact: Ken Butts (kbutts1@ford.com), Mark Wilcutts (wilcutts@me.berkeley.edu) This problem consists of generating and/or maintaining a consistent set of models for the same system, but at different levels of abstraction. We may call these different "views" of the same model. In [Butts] three levels of abstraction are defined: - level 1: hybrid automata with continuous dynamics - level 2: discrete-time controllers and some scheduling information - level 3: platform (e.g., OS, hardware) specific information (e.g., variable sizes). Other refinements might include removing the abstraction of "perfect" inter-module communication which is typical, and replacing it by a more realistic communication model (see problem 1.3). The questions are: - how to "move" from one level to the next, e.g., perhaps automatically refine a level-1 model to a level-2 model - how to preserve consistency when moving automatically, or check consistency of two models developed manually, where consistency means, e.g., some type-compatibility between inputs and outputs in terms of data size, sampling rate etc. Links to detailed documents: In http://vehicle.me.berkeley.edu/mobies/papers/challenges_berkeley.doc reference is made to a paper by Magner, Butts, and Toeppe with respect to this challenge problem. The modeling style guide at http://vehicle.me.berkeley.edu/mobies/papers/stylev242.pdf provides documentation of the Level 2 model structure currently used at Ford. 1.2 Automated composition of sub-components Primary point of contact: Bill Milam (wmilam@ford.com), Stavros Tripakis (stavros@EECS.Berkeley.EDU) The problem here is to come up with an efficient method for automatically composing a set of sub-components (e.g. block diagrams in Simulink) in order to build another component. Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/papers/model_composition_challenge.pdf 1.3 Design and use of good (wireless) communication models Primary point of contact: Pravin Varaiya (varaiya@EECS.Berkeley.EDU) Inter-module communication is already part of automotive systems, e.g., micro-controllers communicating over a CAN bus. With the introduction of applications requiring more complex networking infrastructure (both in terms of media, e.g., wireless, and in terms of protocols, e.g., TCP/IP), communications are an important part of the design. However, they are usually abstracted at the first level of the control design phase, where it is assumed that the modules communicate instantaneously and perfectly (no message loss). The goal is to develop simple enough communication models, which are nevertheless relevant for control design. These models can be used either for analysis or simulation. Simple means not involving, for instance, a complete simulation of the protocol stack and channel models, as is typically done by a network simulator. Links to detailed documents: [PV wil give reference] 2. Model Analysis 2.1 Automatic test generation Primary point of contact: Stavros Tripakis (stavros@EECS.Berkeley.EDU) The problem of automatic test generation is, given the model of a system (in some formalism, e.g., hybrid automata, Simulink blocks), and a specification of the test goal, to generate a set of test cases that check whether the system meets the test goal. The test cases are essentially automata that act as observers/controllers to the system: they generate inputs to the system, and observe the outputs of the system, for some finite time. At the end or before this time interval, they make a verdict, whether the system has passed or failed the test. Automatic test generation can be viewed as "intelligent" simulation. The objective is to generate enough test cases (but also a reasonable number of them) that covers a representative enough class of behaviors, among all possible environment behaviors. Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/papers/embedded_challenge.pdf 2.2 Verification Primary point of contact: Pravin Varaiya (varaiya@EECS.Berkeley.EDU), Ken Butts (kbutts1@ford.com) The problem is to verify that a given model in a formalism such as as the above satisfies a given specification, for example, "an unsafe state is never reached", "the controller is never deadlocked", a variable used by the controller has been defined, and so on. In the CACC+CW application, the main property to be verified is that collision between vehicles is avoided, that is, the distance between the subject vehicle and the vehicle in front is never zero. In the PC application the unsafe or undesirable states might be specified by bounds on engine speed, fuel-air ratio, stability of idle speed, etc. Links to detailed documents: For a general introduction to the hierarchical control architecture see: Varaiya, "Smart cars on smart roads," IEEE Trans Control, 38(2): 195-207, Feb. 1993. For a survey of control designs see: Horowitz and Varaiya, "Control design of an automated highway system," Proc. IEEE, 88(7): 913-25, July 2000. For verification see: Puri and Varaiya, "Driving safely in smart cars," Proc. 1995 American Control Conference. 2.3 Synthesis of switching (hybrid) controllers Primary point of contact: Pravin Varaiya (varaiya@EECS.Berkeley.EDU) The problem here is, given a set of macro-states (system modes), for each of which a control law is defined, and a set of switching conditions between these states, to synthesize a global controller which operates in any of these states and switches between them according to the conditions. The objectives are that the controller is stable, transitions are "smooth", and so on. The synthesis might involve restricting the conditions, adding resets (re-initialize some variables), or synthesizing a transient set of states through which the controller passes during the switch. Links to detailed documents: There isn't much work in this area. For some ideas, see: Asarin et al, "Effective sysnthesis of switching controllers for linear systems," Proc. IEEE, 88(7): 1011-25, July 2000. 2.4 Performance Primary point of contact: Karl Hedrick (khedrick@me.berkeley.edu) The problem is to study robustness to parameter changes (sensitivity), fault tolerance, etc. Controller designs typically incorporate strategies for detection and reaction to faults. Links to detailed documents: For a study of how faults are included in controller design, see Godbole et al, "Design and Verification of Communication Protocols for Degraded Modes of Operation of AHS," Proc. IEEE CDC, 427-32, 1995. 3. Implementation 3.1 Test vector generation Primary point of contact: Ken Butts (kbutts1@ford.com), Stavros Tripakis (stavros@EECS.Berkeley.EDU) This problem is related to problem 2.1, with the difference that it is not the behavior of the model alone which is studied, but rather verification of the behavior of implementation (code and perhaps also hardware) by comparison with the model behavior. Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/papers/embedded_challenge.pdf 3.2 Schedulability analysis Primary point of contact: Stavros Tripakis (stavros@EECS.Berkeley.EDU) Most systems consist of a number of logical tasks, where each task is characterized by a set of activation conditions, execution time, resources that it has to access, and completion deadline. Upon implementation, these logical tasks are mapped onto one or more processes running on a single host machine, therefore sharing the CPU and other resources. The problem of schedulability analysis consists in determining which policy to use for scheduling the physical tasks so that the deadlines of the logical tasks are met (plus other properties such as absence of deadlocks, process starvation, and so on). Alternatively, given a scheduling policy, to determine whether these conditions are met. Notice that we distinguish between logical and physical tasks (processes), since in general, more than one logical tasks can be implemented in the same process, where they are scheduled internally (e.g., Teja generates code like that). Even in this case, it is the requirements of the logical tasks that have to be met. A particular challenge problem is to carry out in an automated way a schedulability analysis similar to the one described in the document below, for the publish/subscribe database architecture used at PATH. Part of the challenge problem is to come up with automated ways to estimate the various execution times necessary in the analysis. Even better would be a synthesis procedure that proposes how priorities are to be assigned to the different processes. Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/vehicle/pub-sub.pdf http://vehicle.me.berkeley.edu/mobies/papers/embedded_challenge.pdf Link to the Publish/Subscribe code distribution (when it becomes available, waiting for the copyright header) 3.3 Code generation Primary point of contact: Dave Bostic, Paul Griffiths (pggriffi@vehicle.me.berkeley.edu) The problem here is to automatically generate code for a given platform, starting from a model (e.g., hybrid automata, dataflow blocks), such that the generated code preserves the properties of the model, potentially under a number of assumptions on the underlying platform. Code generation can occur at various granularities: generating code for pieces of the entire model (e.g., Simulink blocks) up to generating code for the entire model (e.g., Teja). In the first case, support is necessary for "gluing" the pieces together (e.g., scheduling). In the latter case, support is necessary for performing schedulability analysis (c.f. problem 3.2). In case this analysis shows that some deadlines are missed, it is likely that this is due to the granularity of some atomic actions, which is too coarse (i.e., preemption of these actions is necessary). The tool should be able to figure this out and guide the user into splitting the actions in question into more fine-grain pieces. Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/papers/embedded_challenge.pdf 3.4 Code debugging and testing Primary point of contact: Baris Dundar (dundar@eecs.berkeley.edu) Code debugging and testing refers to: first, being able to run and debug the code with or without hardware in the loop; second, being able to map the results to the model from which the code has been generated (if this is the case). For example, if an error occurs during the execution of the code, say a variable X grows above an acceptable limit, one should be able to check whether the same behavior can be reproduced in the model. If this is so, then the model is incorrect. Otherwise, either some of the assumptions of the underlying platform has been violated (e.g., not enough CPU), or the code generator is incorrect. A useful method for code debugging and is the annotation of the code with "self-examining" parts, for example, assertions about the timing, values of variables, and so on. This is often done manually, and a challenge is to generate such annotations automatically and provide support for the interpretation of the results. Links to detailed documents: [Baris will provide reference] 3.5 RTOS generation Primary point of contact: Bill Milam (wmilam@ford.com), Baris Dundar (dundar@eecs.berkeley.edu) Ford's definition of the challenge problem is as follows: given a target software and hardware architecture, the worst-case execution time for the embedded system code, and additional timing constraints, generate a custom RTOS that enables the target code to meet all the timing requirements and is the most efficient in ROM, RAM, and CPU usage. We think that automatic generation of OSEK OIL files for Matlab/Simulink generated code can also be considered under this topic, as the latest version of Matlab can not generate OIL files for OSEK applications. OSEK Implementation Language (OIL) aims to create an OSEK compliant RTOS scaled to a specific application. For all OSEK applications OIL must be used to statically configure the application at compile time. OIL is used to select the scheduling policy, define the objects (like tasks, alarms, events, resources, counters, ISRs...etc) in an application and their attributes. Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/papers/embedded_challenge.pdf 3.6 Allocation of system function and performance to distributed platforms Primary point of contact: Mike Bauer (Mike.Bauer@motorola.com), Mark Wilcutts (wilcutts@me.berkeley.edu) Implementation is relative to a given platform, which includes hardware components such as computers/micro-controllers, sensors, actuators, communication devices and links, and software such as operating systems, device drivers, libraries, or middleware (e.g., Corba, Jini, Publish/Subscribe). Often the choice of the underlying platform has been fixed by other factors, but it may be the case that a number or alternatives are possible. One challenge problem is therefore to provide methods for choosing a platform, given a description of the particular application or class of applications that the platform has to support. The description might be the detailed model of the application, or some general characteristics such as sampling frequencies, desired throughput, and so on. Assuming the platform and application are fixed, and the platform is distributed, a challenge is to support the user in deciding how to partition the different functions or tasks of the application to the different computers, micro-controllers, etc. Such feedback may be input to the code-generation tools, which will generate code for the different parts, as well as for interfacing these parts (e.g., through a network). Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/papers/partitioned_control.pdf 4. Integration This is one challenge problem that has multiple aspects. It has to do with merging of different control applications (e.g the PC and CACC+CW applications): - at the modeling, simulation and analysis level, - at the implementation level. The controllers for PC and CACC+CW are complementary in the sense that CACC+CW produces a desired acceleration/deceleration output, while PC receives acceleration as input and produces torque as output. During the first stages of the project, models and implementations of these two applications will be developed using different formalisms and tools, and on different platforms. The integration challenge is to develop methods and tools in order to be able to perform one or more of the following functions: 4.1 translate models from one formalism to another They can be simulated and analyzed using a given tool: one challenge here is to compare the semantics and expressiveness of the different formalisms, and indicate which is more suitable for which typical control applications. Primary point of contact: Anouck Girard (anouck@path.berkeley.edu) 4.2 integrate formalisms with different semantics into a single formalism Primary point of contact: Stavros Tripakis (stavros@EECS.Berkeley.EDU) 4.3 integrate tools (e.g., Simulink and Teja) so that they can simulate in conjunction two sets of interacting models The challenge here is to preserve real-time properties during the execution of the two tools in parallel. Primary point of contact: Anouck Girard (anouck@path.berkeley.edu) Link to detailed document: http://robotics.eecs.berkeley.edu/~anouck/mobies.htm 4.4 Integrate the software and hardware architectures One challenge here is to build interfaces through which the two implementations will communicate, or alternatively, re-generate the implementations, given that they will run in parallel. Primary point of contact: Anouck Girard (anouck@path.berkeley.edu), Mark Wilcutts (wilcutts@me.berkeley.edu) Links to detailed documents: http://vehicle.me.berkeley.edu/mobies/papers/MoBIES_v2v.pdf ============================= Concerning the model development, the primary points of contact are: Vehicle control: - Plant: Adam Howell (ahowell@vehicle.me.berkeley.edu) - Controllers: Mike Drew (mdrew@vehicle.me.berkeley.edu) Powertrain control: - Plant: Jason Souder (jsouder@me.berkeley.edu), Mark Wilcutts - Controllers: Mark Wilcutts (wilcutts@me.berkeley.edu), Jason Souder (Ken Butts regarding controller representation in Simulink/Stateflow)