Control of Discrete Event Systems by Using Symbolic Transition Model: An Application to Power Grids

The control theory of discrete event systems (DES) has been proposed by [1] as language theory, typically aimed at synthesizing a controller for a given system and control objectives. Subsequently, many modeling approaches have emerged, including automata [2], finite state machines [1], and Petri nets [3]. Despite the availability and study of several types of modeling formalisms for the control theory of discrete event systems, these models have suffered from the state explosion problem [4].

The computation of data flow models is specified by a directed graph whose nodes represent states and edges represent transitions. The use of data flow models (symbolic approach) addresses scalability issues, specifically the state explosion problem, where models of infinite discrete event systems can be composed of a finite set of symbolic transitions [4]. Similarly, in our case, events are defined as guarded symbolic transitions through our symbolic transition model. Thus, the model of an infinite-state system consists of a set of finite symbolic transitions. The specification of our models (plants) is considered using the concept of synchronous data flow languages, which extends the computation of data flow models with conditional statements. This implies that explicit automata (i.e., state transitions) are symbolically (i.e., implicitly) encoded using synchronous languages. Control theory is then applied to a data flow model to synthesize controllers satisfying safety and optimization control objectives.

The works [5‐9] have applied the input/output symbolic approach for synthesizing a safety controller. All of them utilize the same synthesis algorithm constructed in [10]; however, they have considered handling only boolean variables. [11, 12] represent the most recent works on symbolic discrete controller synthesis algorithms for infinite-state systems; however, they have not considered the specification of outputs. On the other hand, the input/output approach has been considered in some papers; however, systems are defined as finite state machines or automata [13]. For example, an automata-based synchronous language approach has been explored in [14]; however, the state explosion problem prompts the use of symbolic approaches.

Reactive infinite-state systems typically involve both input and output variables. This case has not been taken into account in previous studies on the symbolic approach for the control of such systems, they have considered handling only input variables. Our contribution fills this gap by presenting a symbolic transition model for the control of input/output infinite-state systems, aiming to satisfy safety objectives. Our models better accommodate the modeling of discrete event systems as they consider both input and output variables.

Meanwhile, other studies on discrete controller synthesis (DCS) have considered optimization objectives [6, 7] and cost function [15], where these strategies are based on the dynamic programming algorithm [16]. The target state space should be defined in order to compute an optimal controller in these works mentioned. Our new symbolic limited optimal control algorithm presented in this paper considers cost functions based on state transitions instead of defining the target states in order to deal with the optimization objective. This algorithm offers a new solution in this sense for better handling of discrete event systems modeling.

Several studies have applied discrete controller synthesis techniques to various systems in the literature. For instance, [17] successfully applied discrete controller synthesis techniques to hardware circuits, achieving improved power efficiency. In addition, [18, 19] demonstrated the effectiveness of discrete controller synthesis in hardware circuits. However, limited research has been conducted on the application of discrete controller synthesis techniques to power grids. [20] proposed a methodology for surveillance and performance analysis of a micro-grid during a perturbation based on discrete event systems. The paper presents an energy management system for the effective operation of microgrids, including the use of battery energy storage systems to manage the integration of intermittent energy resources and reduce undesirable effects like power fluctuations. [21] proposed a DES framework based on model-diagnoser for fault section estimation in the power grid, considering the failure and false trips of devices such as protective relays and circuit breakers. [22] demonstrated the application of discrete event systems theory for modeling and analyzing power transmission networks, by using Petri nets and finite state machines. In their study, [23] utilized discrete controller synthesis techniques for safety control to prevent overloading of the power grid caused by additional load from conventional residential and industrial sources as well as electric vehicles. However, it should be noted that all of the aforementioned approaches were based on finite state machines (FSMs) and did not incorporate symbolic techniques. Additionally, none of these approaches considered optimization targets, which limits their effectiveness in real-world power grid applications. To bridge this gap, our study proposes a symbolic approach to apply discrete controller synthesis techniques to power grids.

In our extensive literature review, our motivation is to cultivate more effective management by establishing more reliable modeling environments within a framework utilizing discrete control synthesis methods for input/output reactive infinite-state systems. Thus, we aim to address this gap in the literature. Compared to studies in the literature such as [17‐19], our main contribution is that we offer a new modeling environment for input/output reactive infinite-state systems. While the outputs of the systems cannot be adequately modeled in these studies, we enable realistic modeling of outputs in our approach. Additionally, when comparing it with other existing optimization techniques such as [6, 7, 15], the novelties of this work provide optimization targets within a certain cost function based on state transitions without specifying the target states.

Besides the DCS approach, there are also many intelligent ANN models in the literature. In [24], a novel higher-order recurrent neural network (HORNN) is introduced for indirect adaptive control of complex nonlinear dynamical systems. The HORNN model, based on a higher-order Pi-Sigma neural network, exhibits superior performance in simulation experiments, achieving a significantly lower instantaneous mean square error of 0.058 compared to popular neural networks. In [25], the memory recurrent Elman neural network (MRENN) is introduced as an enhanced version of the classical Elman neural network (ENN), designed for identifying unknown dynamics in time-delayed nonlinear plants. MRENN exhibits stability through Lyapunov-stability criteria-based parameter updates and outperforms other well-known models in terms of identifying plant dynamics, as demonstrated in simulation results. In [26], radial basis function network (RBFN) is utilized for simultaneous online identification and indirect adaptive control of nonlinear dynamical systems, capitalizing on its simplicity and mathematical formulation compared to multilayer feed-forward neural networks. The proposed RBFN-based controller, applied in the absence of plant dynamics information, showcases adaptability to parameter variations and disturbances, surpassing multilayer feed-forward neural network (MLFFNN) in capturing and controlling system dynamics. In [27], a fully connected recurrent neural network (FCRNN) structure is presented for identifying unknown dynamics in nonlinear systems, incorporating internal feedback layers with adjustable weights to enhance memory properties. The FCRNN demonstrates superior performance in identification accuracy and robustness compared to other neural network models, as validated through experimental results and confirmed by comparative evaluations. In [28], the locally recurrent neural network with input feed-through (LRNNIFT) is introduced for controlling nonlinear dynamical systems, chosen for its simplicity and mathematical model compared to Elman neural networks (ENNs) and feed-forward neural networks (FFNNs). Simulation results underscore the LRNNIFT-based controller’s effectiveness in achieving adaptive control and mitigating disturbances, with comparative analyses revealing its superior performance over both FFNN and ENN controllers in adaptive control applications.

Many design criteria must be taken into consideration in the control of dynamic systems. For example, there are many studies in the literature that address stability issues for dynamic systems. [29] presents an adaptive dynamic programming-based control and identification scheme for nonlinear dynamical systems, guiding the plant’s output along a desired reference trajectory. Weight update equations using both gradient descent and Lyapunov stability methods ensure global stability, demonstrating superior accuracy in experimental results on three nonlinear dynamical systems. [30] presents a novel temporally local recurrent radial basis function network for modeling and adaptive control of nonlinear systems, featuring recurrent hidden neurons with weighted self-feedback loops and a weighted linear feed-through. The proposed network demonstrates superior efficacy in testing on five complex nonlinear systems, outperforming other neural network structures, and exhibits robust disturbance rejection capabilities. [31] proposes an adaptive control approach using a diagonal recurrent neural network (DRNN) derived from a fully connected recurrent neural network (FCRNN) for nonlinear dynamical systems. The DRNN, featuring self-recurrent neurons, effectively captures the dynamic behavior of the controlled nonlinear plant, demonstrating superior performance and robustness against parameter variations and disturbance signals compared to a multilayer feed-forward neural network (MLFFNN). [32] introduces a novel higher-order context-layered recurrent pi-sigma neural network (CLRPSNN) for nonlinear dynamical system identification, incorporating an additional context layer. The weight tuning procedure, combining back-propagation (BP) and the Lyapunov-stability method, results in superior performance compared to other models, as evidenced by comparative analysis in simulation studies for nonlinear dynamical system identification. [33] introduces a compound recurrent feed-forward neural network, merging the strengths of a feed-forward neural network (FFNN) and a locally recurrent neural network, for identifying nonlinear dynamic systems. The proposed model, combining FFNN and RNN, demonstrates superior prediction accuracy, robust performance against disturbance signals, and improved response to parameter variations compared to other state-of-the-art neural models, as evident from simulation results.

The optimization algorithm presented can be considered as a deterministic learning algorithm that handles all possible situations in the future. When compared to the methods preferred for dynamic systems in the literature, DCS, which is also a model checking tool, guarantees formal correctness, meeting the safety objectives strictly and allowing the application of various optimization techniques. Thus, its application becomes particularly crucial for systems of critical importance, accentuating its prominence in critical systems.

In summary, while discrete controller synthesis techniques have been widely applied in various domains, their application to power grids is still a relatively emerging research area. Our study contributes to the existing literature by proposing a symbolic approach to apply discrete controller synthesis techniques to power grids. We further detail and illustrate our approach through a realistic case study and experimentally evaluate both our safety and optimal (optimization) control algorithms. The comparison with previous works in the literature underscores the novelty and significance of our research. This section provides an overview of the relevant literature and highlights the contributions of our study in the context of discrete controller synthesis techniques for power grids.

Contributions:The rest of this paper is organized as follows. Section 2 provides the details of the symbolic transition model. Safety control policies for input/output infinite-state systems are presented in Sect. 3, while Sect. 4 exhibits the new symbolic limited optimal control algorithm for such systems. Our approach is illustrated on a realistic case study in Sect. 5, and the experimental evaluation of our modeling framework is presented in Sect. 6. Finally, Sect. 7 concludes this paper.

In this section, our symbolic transition model for the control of discrete event systems is introduced. Our models for infinite discrete event systems consist of finite sets of symbolic transitions (\( \delta \)), states (\( Q \)), inputs (\( I \)), and outputs (\( O \)). Transitions are guarded actions (where guard \(g \in I \) and action \(a \in O \)) on the state variables whose domains are (in)finite and they are synchronously fired to update system variables. First, the symbolic modeling of a given uncontrolled system (i.e., plant) is defined. Subsequently, the supervisory control for these systems is addressed to fulfill specified objectives in the form of a set of logical expressions that will be constrained by the system.

As aforementioned, our models, described as a tuple, are encoded as a synchronous program, and any component of a synchronous program can be expressed in the form of a finite Mealy machine, where a transition is taken at each reaction. In this section, first, a simple case is taken to illustrate the principle of discrete controller synthesis; for this, the result of the basic controller synthesis algorithm directly applied on Mealy machines is described. Then, this principle is adopted to our safety discrete controller synthesis algorithm.

The synthesis algorithm aforementioned is a base strategy. In this section, a novel algorithm is proposed for refining the base strategy \(\sigma \) toward satisfying a given optimization objective. The optimization objective is to minimize a cost function \(\zeta \) summed over \(k \in \mathbb {N}^+\) ticks, in the form of guarded numerical expressions, where each tick is actually associated with the cost function \(\zeta \) for each transition. Our algorithm operates on these guarded numerical expressions that are symbolically represented using cascading conditional constructs where condition predicates are expressed using state, input, and output symbols, and leaves are Rational constants. Especially due to the finiteness of the domains of definitions for all symbols, the set of all guarded numerical expressions as described above is closed under basic arithmetic operations such as addition, composition with conditional constructs, as well as existential symbol elimination and substitution of symbols in the predicate conditions of said constructs.

A preliminary requirement of the symbolic technique presented in this paper is to operate on a set of expressions (\(e\)) that is closed under various operations such as the substitution of symbols by expressions, and parametric optimization. As this is not the case of the guarded linear arithmetic expressions (\(\mathcal {L}_{\mathbb {Q}}\)) involved in our models, our algorithm operates on the (strictly greater) set \(\mathcal {L}_{\mathbb {X}}\) where the domain of coefficients and linear expressions take their values in \(\mathbb {X} = \mathbb {Q} \cup \big \{-\infty ,\infty ,\textsf{NaN}\big \}\). Note that \(\mathcal {L}_{\mathbb {X}} \supset \mathcal {L}_{\mathbb {Q}}\). Therefore, our algorithm operates on linear expressions where coefficients. Note this is a strict super-set of the guarded linear arithmetic expressions of our models. As controllable input symbols may only appear in guards, the symbolic optimization operator \({Min}_V\) (resp. \({Max}_V\)) lifts the elimination of finite symbols (variables \(V\)) as:where \(\exists _V c\) (resp. \(\forall _V c\)) existentially (resp. universally) eliminates all symbols in controllable input variables \(C\) from predicate \(c \in C\).

In the algorithm, the optimization objective enforces the minimization of a cost function \(\zeta \in \mathcal {L}_\mathbb {X}\) using variables in \( Q \cup I \cup O \), summed over \(k \in \mathbb {N}^+\) ticks. The algorithm considers the pessimistic scenario and aims to escape from the highest cost. The best outcome \(\eta _k\) is recursively computed as:where:Finally, our revised strategy \(\sigma {'}\) satisfies the objective by the valuation of variables \(C\) for the given \(\eta _k\). The computation of our strategy is as follows:where \(C'\) is primed version of \(C\); \((\eta _k \big [C \mapsto C'\big ] < \eta _k)\) denotes that the valuation of variables in \(C\) outperforms the valuation of variables in \(C'\); and \(\sigma {'}\) still holds our base strategy.

This section describes how our proposed approach, which comprises \(\textsf{STM}_{}\) and synthesis algorithms, can be applied for modeling, control, and analysis of in/output reactive infinite-state systems. In this direction, the approach is illustrated with a realistic case study, and a systematic modeling framework is proposed to prevent the overloading of a power transmission network.

In the past, every discrete event that occurred in centralized small-scale power systems was manually monitored and operated when necessary changes were required in system operations. However, today, the size and operation of power systems have increased considerably. With the deregulation of these decentralized systems, it has become very difficult to observe and control the process using traditional methods. In addition, the uncontrolled charging of electric vehicles with increasing usage has brought a great burden to the network, and this rate of increase continues. Adding this load to conventional residential and industrial loads causes power grids to become overloaded, which therefore, the negative impact on the grid has become inevitable without an effective energy management system.

The energy management of power grids is considered a feedback discrete controller synthesis problem, which is a proper technique for such safety-critical systems since it always guarantees desired objectives. In this regard, this work elaborates in a detailed and systematic manner on how to model the energy manager using the approach for an energy-efficient and robust power grid management system, taking into account optimization targets by leveraging user statistics.

The implementation aims to model the power grids and synthesize a manager, especially to avoid overloading. Furthermore, our proposed model and new control algorithms are experimentally evaluated. In this regard, simple artificial designs of power transmission networks are created in this implementation, based on the description provided in Fig. 3 (i.e., several power stations, consumers, and power distribution stations).

The safety algorithm aims to maintain a power station in a more secure state by utilizing the data provided in the current state space. Conversely, the optimization algorithm considers future states (i.e., given \(k\) ticks) to prevent worst-case scenarios.

The implementation begins by modeling and encoding the objectives as \(\textsf{STM}_{}\), similar to the previous section. Following this, a controller synthesis is performed using the control algorithms presented. Subsequently, this controller is transformed into a suitable script language or environment, allowing it to be employed as a manager within the power grid system.

In the power grid implementation, various random scenarios have been created using an artificial simulation environment in Python. The results for Designs 1, 2, and 3 have been documented in the table. Controllers derived from the \(\textsf{STM}_{}\) s models and objectives corresponding to each design are then translated back into the Python environment. Subsequently, simulations have been executed, and the outcomes have been reported for both the controlled and randomly executed scenarios, as presented in Table 1.

Table 1 illustrates the extent to which the power at the station with the highest rate of exceeding the given maximum power (\(\mathcal {P}_{\max }\)) in that design surpasses the maximum power. In the \(\textsf{STM}_{}\)-based designs, no station exceeds the power limit, while in the same designs, for the random-based controller, some stations have exceeded the limit by 11%, 13%, and 9%, respectively. \(\mathcal {P}_\mathrm{avg.}\) represents the average power at stations that exceeded the limit. In \(\textsf{STM}_{}\) designs, since no station exceeded the limit, the average values are 0. However, as seen in the random controllers, multiple stations exceeded the limit. \(C_\mathrm{star.}\) indicates the starvation condition, which represents situations where consumers cannot be adequately supplied by the grid. In this case, the \(\textsf{STM}_{}\) technique and control algorithms have prevented such starvation conditions.

Table 2 presents the performance metrics of our \(\textsf{STM}_{}\) control synthesis tool in various designs. The time and memory required to synthesize a controller are provided in the columns, demonstrating its efficiency in terms of cost. Additionally, it’s worth noting that there is a specific condition where a controller cannot be generated. This condition arises when the value that leads to the danger state, modeled as a fixed value, falls below a certain threshold. This is because safety-oriented DCS algorithms always ensure that at least one station’s peak power exceeds a certain threshold to meet the customers’ needs securely.

To provide a clearer explanation of our results and performance criteria, the experimental simulation graphs in Fig. 4 are presented, where (a) displays the peak powers of the power stations, each represented by a different color; (b) illustrates the power demands of consumers, each also depicted in distinct colors; (c) and (d) depict the power consumption by the consumers in (b) from the power stations in (a), using DCS and random manager, respectively. For instance, in the 10th time period, the peak power of the station represented by the green color is 50 units. The power consumption from this station is 22 units for DCS and 53 units for random. Therefore, our performance criterion \(\mathcal {P}_{\max }\) in Table 1 is 0% for DCS and 6% for random. Similarly, \(\mathcal {P}_\mathrm{avg.}\) is calculated by dividing the sum of \(\mathcal {P}_{\max }\)s by the number of stations. The term "starvation" (\(C_\mathrm{star.}\)) indicates cases where the demands of consumers cannot be met by the stations. For example, in time period 20, the powers demanded by consumers are 54, 68, 51, 22, 40, and 64 units, totaling 299 units. In (b), the powers provided by the stations at the same time period are 35, 53, 49, 57, 48, and 57 units, also totaling 299 units. Thus, in this case, starvation does not occur. This situation cannot be prevented by the random manager, but the approach we present always guarantees that this situation does not occur by means of the safety objective. As indicated in Table 2, it is stated whether such a situation is feasible or not.

The hyper-parameter settings used to achieve the desired system behavior are automatically adjusted. These settings correspond to our controllable variables (\(q_{ PS _{}}\) in Eq. 14 and \(q_{ C _{}}\) in Eq. 16). The valuation of these controllable variables (i.e., hyperparameter) is updated in each atomic action based on the desired system behavior (i.e., observers), as outlined in Sect. 5. This valuation is performed in accordance with an invariant (i.e., always true) along with the system behavior, as described in Sect. 3.2.

The use of controllers that provide formal correctness is crucial in safety-critical systems. Therefore, we focus on a deterministic strategy. Foundations of DCS and program synthesis resemble principles of model checking, ensuring system satisfaction with specifications. Common temporal logics for model checking, such as linear-time temporal logic (LTL) [34] and computation tree logic (CTL) [35], exhibit exponential and doubly exponential synthesis time complexity, respectively. The complexity of the control synthesis algorithm used by both Sigali [10] and ReaX [11], DCS tools classifiable under model checking, is exponential; however, the approach we propose is quadratic. Although it seems to have higher complexity compared to heuristic methods, it demonstrates superior performance in a deterministic manner with its formal correctness. It is also noteworthy that computation is only performed once during synthesis; afterward, the obtained controller runs dynamically at runtime. Additionally, as depicted in Table 2, even in artificial scenarios requiring a large number of states, the experimental feasibility assessment for synthesis time is compiled in a relatively short time.

It is possible to model the STM approach for power grids presented in Sect. 5 with some modifications, akin to the approaches in the works by [10, 11]. When comparing performance tests, our approach revealed that in various scenarios, the synthesis time was found to be shorter by 15% to 25% compared to the work by [11], while yielding faster results ranging from 20% to 40% compared to the work by [10]. As a note, since the approaches in these studies are also deterministic, they ensure safety conditions precisely like our approach. However, considering the optimization objectives, our approach has consistently prevailed in maintaining power stations in a more secure state. On the other hand, non-symbolic traditional approaches such as those proposed by [20, 23] suffer from state explosion problems in terms of performance. That is, they cannot consider very distant future situations over a time window as done in our approach, in order to optimize their targets.

As a result, power stations do not enter the danger state in most of the designs, and no power station ever reaches its peak power. In contrast, in the random control group, some power stations disregarded the power peak, as well as the alert systems. Meanwhile, the limited optimal control algorithm ensures that it always avoids the worst power consumption among the possible scenarios, by leveraging the traces of consumer behavior and utilizing controllable inputs.

In this paper, a new modeling framework for controlling input/output reactive infinite-state systems using symbolic discrete controller synthesis techniques is proposed. The presented symbolic transition models enhance the modeling of discrete event systems by considering both input and output aspects. Safety objectives are specified and fulfilled, with the safety control policies ensuring the desired properties of the system modeled by the symbolic transition model. Additionally, a novel optimal control algorithm is introduced, which minimizes a cost function directly defined on transitions, allowing computation without specified target states to address optimization objectives. Experimental application of the framework to power grids demonstrates promising results for such systems. Lastly, the framework holds potential for applications in various systems, including the energy efficiency of hardware circuits.