QUARTERLY PROGRESS REPORT CONTRACTOR: University of California at Berkeley AGREEMENT NUMBER: F33615-98-C-3614 CONTRACT PERIOD: 9/1/99 - 12/31/03 TITLE: Integrated Design and Analysis Tools for Software Based Control Systems REPORT PERIOD: 7/1/02 - 9/31/02 SPONSOR: Air Force Research Laboratory (AFRL) TECHNICAL POC: Ray Bortner REPORT PREPARED BY: Tom Henzinger (tah@eecs.berkeley.edu) 0. Executive Summary Our effort integrates three tasks: formal modeling and verification; embedded software design; and controller design and analysis. We made substantial progress in all three directions. Some of the highlights include: creation of a C/Posix runtime environment for timed multitasking, platform-based design of time-based control software for a rotorcraft UAV, and implementation of the embedded virtual machine for hard real-time software execution. 1. Research Status Formal Modeling and Analysis ============================ Design, Analysis, and Implementation of the Embedded Virtual Machine The Embedded Machine is a virtual machine that mediates in real time the interaction between software processes and physical processes. It separates the compilation of embedded programs into two phases. The first, platform-independent compiler phase generates E code (code executed by the Embedded Machine), which supervises the timing --not the scheduling-- of application tasks relative to external events, such as clock ticks and sensor interrupts. E code is portable and exhibits, given an input behavior, predictable (i.e., deterministic) timing and output behavior. The second, platform-dependent compiler phase checks the time safety of the E code, that is, whether platform performance (determined by the hardware) and platform utilization (determined by the scheduler of the operating system) enable its timely execution. We have used the Embedded Machine to compile and execute high-performance control applications written in Giotto, such as the flight control system of an autonomous model helicopter. We developed a Giotto compiler that targets the Embedded Machine. E code supervises the timing of functionality code, which can be written in any conventional programming language such as C. An Embedded Machine based Giotto run-time system consists of an implementation of the Embedded Machine together with the scheduler of a real-time operating system. While E code is interpreted by the Embedded Machine, functionality code is native code that is scheduled for execution by the system scheduler. For E code that is generated from a Giotto source program, the scheduling problem is independent of any particular system scheduler; it is only required that the scheduler be compatible with the schedulability test of the Giotto compiler. E code produced by the compiler can be executed on any platform for which an Embedded Machine implementation is available. For the rotorcraft UAV project, we implemented the Embedded Machine on top of HelyOS. We also implemented a Giotto-based electronic throttle controller on a single Motorola MPC 555 processor running the real-time operating system OSEKWorks. For this purpose, we ported the Embedded Machine to OSEKWorks, which is widely used in the automotive industry. In addition to these real-time versions of the Embedded Machine, non-real-time implementations of the Embedded Machine are available for Linux and Windows. We have developed algorithms for ensuring the time safety (i.e., the real-time guarantees) of E code and implemented them in the Giotto compiler. We have also built a software tool for converting Simulink models into Giotto which is compiled into E code that maintains the timing of the Simulink models. Embedded Software Design ======================== Runtime Platform for Timed Multitasking --------------------------------------- Jie Liu (now at Xerox Parc) checked in a preliminary runtime system for the time multitasking (TM) models in Ptolemy II. The runtime system is mainly a scheduler and some time management; it is written in C and uses POSIX threads. Jie has tested it under both Cygwin and Redhat Linux. The runtime system is intended to use together with generated C code from TM models. Jie's current tests and examples use hand-generated C code, since code generation from TM is not yet implement. The system assumes each task to consist of the following functions: typedef struct TASK { char (*isReady)(); void (*exec)(); void (*stopExec)(); void (*produceOutput)(); void (*getDeadline)(struct timeval *tv); char hasDeadline; } TASK_t; Each actor also has a init() and start() function, which are not in the struct of TASK. They are called to initialize a task, once per life time. Tasks are triggered by new events in their input ports. Ports are (to be ) generated from Ptolemy actor's ports. A port is a struct containing new data (in terms of primary data types, and a mutex protecting reading and writing); for example, typedef struct PORT_ACTOR1_INPUT { double v1; int v2; pthread_mutex_t PORT_ACTOR1_INPUT_mutex; char isNew; } PORT_ACTOR1_INPUT_t Each port also associates with a setYYY() method, e.g. setPORT_ACTOR1_INPUT(PORT_ACTOR1_INPUT_t* PORT_ACTOR1_INPUT_val); This method will insert corresponding task (e.g. ACTOR1 here ) to the task queue of the runtime (scheduler). The scheduler does not yet have a notion of priority. It takes the first task in the task queue and executes it if isReady() returns 1. If the task specifies a deadline, a corresponding monitoring thread is created, which will call stopExec() on the task when its deadline is reached. When the task (gracefully) terminates and the deadline has been reached, the produceOutput() function will be called to make the result of one task available to other tasks. This deferred production of outputs is a key part of the TM semantics. Jie implemented a helicopter control example using this runtime system and hand generated actor code. The example uses the hardware-in-the-loop simulator that Judy Liebman, Cedric Ma, and Ben Horowitz used to demonstrate Giotto. Jie took the same helicopter, sensor, and actuator code from them, and replaced the Giotto controller with TM controller. The TM model effectively reduced the one-sample delay per actor introduced by Giotto. There are still a number of limitations, including: * code generation from Ptolemy models. The plan is to generate full code for ports and event handling, but only generate frames for actor code so that users can insert the body of each actor. * handling priorities in the runtime. * adding analysis capabilities, such as schedulability and priority assignment. Caltech Platform ---------------- We continue to work with Caltech on their rolling platform driven by two ducted fans. In particular, Steve Neuendorfer continues to develop code generation with the objective of providing a prototyping software environment for the platform. Controller Design and Analysis ============================== Platform-Based Embedded Software Design and System Integration for Autonomous Vehicles In this work, we presented a methodology for the design of embedded controllers. Our methodology is predicated upon the principles of platform-based design, which uses layers of abstraction to isolate applications from low-level system details and yet provides enough information about the important parameters of the lower layers of abstraction to prevent costly redesigns. The platform-based design approach also provides a framework to pass constraints from higher levels of abstraction to lower ones. Thus, platform-based design provides a basis for successive refinement and correct-by-construction design. In addition, by providing the appropriate layers of abstraction, the methodology allows for the integration of legacy code and ``foreign'' subsystems. An essential layer of abstraction in our methodology is the software platform provided by the programming language Giotto, which allows a clean implementation of a time-based controller application. To present how our design methodology can be applied, we have discussed two redesigns of the control system of a helicopter-based UAV. These designs go a long way toward meeting the goals for our second generation helicopter control system: 1. The use of platform-based design allows us to build a bridge between the time-based controller application and the non-time-based sensors and actuators. 2. A time-based controller eliminates the timing irregularities present in first generation system. Further, the Giotto compiler ensures that the controller application meets its timing requirements. 3. Our platform-based design achieves a high degree of modularity. For example, to substitute a different sensor suite in our first redesign requires only changes to the data processor and the data formatting library. The data processor would require a different sensor initialization routine and a new circular buffer; the formatting library would need a new format conversion routine. However, no part of the controller application would need to be changed. Though our case study contains many details that are specific to our helicopter system, our methodology is widely applicable. We believe that the combination of time-based control and platform-based design can be generally applied to automatic control systems, for which legacy software, independently engineered subsystems, and strict reliability and timing requirements all play a crucial role. 2. Interactions and Technology Transfer Presentations ------------- * T. John Koo, "Platform-Based Embedded Software Design for Multi-Vehicle Multi-Modal Embedded Software," Embedded Software Conference (EMSOFT'02), Grenoble, France, October 7-9, 2002 * Jorn Janneck, "Ptolemy II," Workshop on Semantics Foundation of Engineering Design Languages, Grenoble, France, 14 April, 2002. * Thomas Henzinger, "The symbolic approach to hybrid systems." Invited tutorial, 14th International Conference on Computer-Aided Verification (CAV), July 2002 (Copenhagen, Denmark). Interactions ------------ * T. John Koo visited Northrop Grumman Air Combat Systems, El Segundo, California on July 15 and Oct 21, 2002, for the NGC subcontract on High Confidence Control Design for UAVs. * It has been announced that the National Science Foundation has selected Berkeley to lead a major new initiative in hybrid and embedded software systems. This is part of the NSF information technology research (ITR) initiative, and it will bring $13 million in the next five years to Berkeley and its partner institutions (Vanderbilt University and Memphis). The SEC team is a major part of this effort. For more information, see the website: http://chess.eecs.berkeley.edu. * Tom Henzinger gave a presentation on Giotto to DaimlerChrysler in Stuttgat, Germany, in July 2002. * Tom Henzinger gave a presentation on SEC hybrid systems technology developed at Berkeley to the National Technology Agency of Finland, in September 2002. Technology Transfer ------------------- * A Simulink model of a helicopter control system, which include vehicle dynamics, controllers, sensor models, and a kalman filter, is distributed to Northrop Grumman for the development of High Confidence Control Design for UAVs. * We released Ptolemy II 2.0.1 and Ptplot 5.2. For details, see: http://ptolemy.eecs.berkeley.edu Personnel --------- No personnel changes. 4. Publications [1] Shuvra S. Bhattacharyya, Elaine Cheong, John Davis II, Mudit Goel, Christopher Hylands, Bart Kienhuis, Edward A. Lee, Jie Liu, Xiaojun Liu, Lukito Muliadi, Steve Neuendorffer, John Reekie, Neil Smyth, Jeff Tsay, Brian Vogel, Winthrop Williams, Yuhong Xiong, Haiyang Zheng, "Heterogeneous Concurrent Modeling and Design in Java," Memorandum UCB/ERL M02/23, University of California, Berkeley, CA USA 94720, August 5, 2002. [2] Jie Liu and Edward A. Lee, "A Component-Based Approach to Modeling and Simulating Mixed-Signal and Hybrid Systems," to appear in ACM Trans. on Modeling and Computer Simulation special issue on computer automated multi-paradigm modeling, 2003. (submitted on 7/12/2002). [3] Jie Liu, Johan Eker, Jorn W. Janneck and Edward A. Lee, "Realistic Simulations of Embedded Control Systems," International Federation of Automatic Control, 15th IFAC World Congress, Barcelona, Spain, July 21-26, 2002. [4] Jie Liu and Edward A. Lee, "Timed Multitasking for Real-Time Embedded Software," invited paper in IEEE Control System Magazine, special issue on "Advances in Software Enabled Control", to appear in December, 2002. (submitted on 7/20/2002). [5] B. Horowitz, J. Liebman, C. Ma, T. J. Koo, A. Sangiovanni-Vincentelli, S. Sastry. "Platform-Based Embedded Software Design and System Integration for Autonomous Vehicles," The Proceedings of the IEEE, October 2002. [6] T. J. Koo, J. Liebman, C. Ma, B. Horowitz, A. Sangiovanni-Vincentelli, and S. Sastry. "Platform-Based Embedded Software Design for Multi-Vehicle Multi-Modal Embedded Software," Embedded Software, Alberto Sangiovanni-Vincentelli and Joseph Sifakis (Eds.), Lecture Notes in Computer Science, Springer-Verlag, 2002. [7] S. Zelinski, T. J. Koo, and S. Sastry. "Optimization-based Formation Reconfiguration Planning For Autonomous Vehicles," submitted to International Conference on Robotics and Automation, Taipei, Taiwan, May 2003. [8] Benjamin Horowitz, Judith Liebman, Cedric Ma, T. John Koo, Thomas A. Henzinger, Alberto L. Sangiovanni-Vincentelli, and Shankar Sastry, "Embedded software design and system integration for rotorcraft UAV using platforms," Proceedings of the 15th IFAC World Congress on Automatic Control, Elsevier Science, 2002. [9] Jean-Francois Raskin, Pierre-Yves Schobbens, and Thomas A. Henzinger, Axioms for real-time logics, Theoretical Computer Science 274, 2002, pp. 151-182. [10] Thomas A. Henzinger, The symbolic approach to hybrid systems, Proceedings of the 14th International Conference on Computer-Aided Verification (CAV), Lecture Notes in Computer Science 2404, Springer-Verlag, 2002, page 57. [11] Thomas A. Henzinger and Christoph M. Kirsch, "The Embedded Machine: Predictable, portable real-time code," Proceedings of the International Conference on Programming Language Design and Implementation (PLDI), ACM Press, 2002, pp. 315-326. 5. Financial Data Provided separately on a quarterly basis by the university.