On Modeling of Discrete Event Dynamic Systems : Using Symbolic Algebraic Methods

Sammanfattning: The interest in discrete event systems (DEDS) has increased during the last years, due to the lack of methods and tools that are capable to handle the complexity of problems and tasks present in industry to day. In this thesis we will consider a symbolic and algebraic framework which will be used for modeling, analysis, and synthesis of DEDS.We will use polynomials belonging to a polynomial ring over finite fields to represent finite quantities, functions, and relations of a DEDS system. The polynomials make it possible to improve efficiency and scalability of DEDS computations, as shown in this thesis by the modeling and analysis of the landing gear controller of the Swedish fighter aircraft JAS 39 Gripen. A polynomial model, represented by binary decision diagram (BDD), is automatically generated from a 1200 lines Pascal implementation, which contains 105 binary variables of which 26 are state variables. Function specifications expressed with temporal algebra, are verified using tools for dynamic analysis, which we also use to compute a polynomial representing the set of all reachable states in the model.To explore the ability and applicability of the polynomial approach when doing synthesis, we use a tank system containing actuators (pump and valves) and sensors (the tank level and measurable disturbances). We propose a synthesis method that uses actuator priority, weighting of states, and Gröbner bases to compute explicit control laws for the actuators, fulfilling the control objectives even if one of the actuators (the pump) is defective.Modeling aspects are emphasized further by comparing the polynomial approach which we have used, with Boolean expressions and established DEDS approaches in the community of automatic control like Ramadge-Wonham, Petri nets, and COCOLOG. We discuss how to handle transformation between signals and events for DEDS and how to modularize DEDS to gain complexity advantages. Model description languages are discussed and desirable features are stated, using the experiences achieved from the modeling of the tank system and the landing gear controller.