Keywords

1 Introduction

A system is defined as “a combination of components that act together to perform a function which cannot be achieved by any of the individual parts” [1]. A system is also defined as a subset of the universe chosen for our discourse [2]. Different definitions prevail in literature for different perspectives. However, the objective study of a system reflects that it consists mainly of two components, viz. interacting components and a function that the system is supposed to perform [3]. In automata, these components are represented by respective symbols. An automatic system is shown below in Fig. 1, where arrows denote the events/transitions and the circles indicate the states (Fig. 1).

Fig. 1
figure 1

Simple automaton for ON/OFF switching system

Full size image

A system can be classified as time-driven or event-driven [3]. The time-driven systems change states with the variation of time. The continuous state systems, such as an analogue clock, change states with time and hence fall under former category (Fig. 2a). The event-driven systems change states with the occurrence of specific transitions at particular instances of time. The discrete event system changes the states due to the occurrence of events, for example, ON/OFF switch, so it is of the later type (Fig. 2b). There are two broad categories of event-driven systems, one that produces the output on behalf of the present state and another one that provides the output based on both current state and input values [4].

Fig. 2
figure 2

a A time-driven system showing continuity. b An event-driven system showing discreteness

Full size image

In a system, there are different kinds of events. Some are related to each other while some are merely independent of each other. For example, in a simple system of e-commerce, the placement of order and payment are two dependent events. In contrast, cancellation of order and generation of salary may be two independent events. An event may be any stimuli that generate a response in the system. Each event in a system leads to some state. The state is capable of projecting the behaviour of a system at the particular time interval associated with it [3]. A discrete event system (DES) is a “discrete-state event-driven system” [3]. Its states change with respect to the discrete events that occur at different instances of time. Since the states in a DES are crisp, it is used to model a variety of complex systems, for example, CPU task scheduling, traffic systems, database system,s etc. [5].

The main limitation of DES is that it cannot address the problem where the system possesses vague states. For example, a patient’s health state cannot be crisp in nature, because after some prescribed medication from a doctor he/she cannot abruptly turn to well from an unwell state just as a switch does from on to off state. Instead, the patient takes time to transit from poor to stable and thereafter to well state. At some instant, we can only say that the patient is doing well to some degree and cannot claim with certainty that the patient is in a good state [6]. There exists a certain level of fuzziness in this scenario. Instead of DES, we use the same approach with an introduced degree of fuzziness, i.e., fuzzy discrete event system (FDES) to model such situations/ systems. FDES is a DES which deals with the fuzzy data (vague states). In contrast to DES, which follows the classical crisp set approach, FDES supports the fuzzy set theory, proposed by Zadeh [7]. The clinical treatment planning is one of the main applications of FDES, identified so far [8]. The theory of state determination and predictability in FDES also helps us in diagnosing a disease [9, 10].

Although fuzzy states and events were known to the research community since the 1960s, no exertive research was performed since 1979 [11]. The concept was reintroduced in 2001 by Lin and Ying [12] with a certain level of clearness. The authors have been continuously exploring the margins of this field as of now [13]. Presently, the formal theory of FDES is in its development phase [14,15,16,17]. This approach has also been adopted to model the hybrid systems containing both discrete and continuous components [3, 18].

In order to brush off the vagueness about the topic under discussion, this paper attempts to do a brief and useful survey on FDES. The basic concepts regarding FDES are organised. We discuss the development of an FDES from DES and the techniques associated with it in Sect. 2. Section 3 introduces the decision-making in FDES along with an example to illustrate the concept. Section 4 reveals applications of FDES, described with comprehensive descriptions from the air-conditioning system and disease (such as AIDS) medication selection. Finally, Sect. 5 concludes the paper.

2 Fuzzy Discrete Event System (FDES) Modelling

To analyse a system, we need procedures to design, control and quantify system performance, and that is just what modelling does. A model replicates the behaviour of a system [3]. The behaviour of the system is described by some mathematical equation, as shown in Fig. 3. Crisp DES is modelled using the finite automata. A formal automaton is denoted by \(G = (Q, \Sigma ,\delta ,q^{o}\)) [19]. The components of finite automata are a crisp set of states (\(Q\)), an event set (\({\Sigma }\)) that trigger the transition from one state to other and a conversion function (\(\delta )\) describing the occurrence of the event on some state and the resultant output state. \(q\)o and \(q_{{\text{f}}}\) denote the initial and final states, respectively.

Fig. 3
figure 3

Modelling process [3]

Full size image

For example, an automaton for a simple on/off switching system, as shown in Fig. 1, may be expressed as:

$$\begin{aligned} Q & = \left\{ {{\text{on}},{\text{off}}} \right\} \\ \Sigma & = \left\{ {{\text{turn on}},{\text{turn off}}} \right\} \\ \delta & = \left\{ {\begin{array}{*{20}c} {{\text{on}}, \forall \Sigma = {\text{turn on}}} \\ {{\text{off}},\forall \Sigma = {\text{turn off}}} \\ \end{array} } \right. \\ q_{o} & = {\text{off }}\;{\text{or}}\;{\text{on}} \\ q_{f} & = {\text{on}}\;{\text{or}}\;{\text{off}} \\ \end{aligned}$$

As stated earlier, vague states cannot be modelled using DES. Rather, we use FDES for the representation of such systems. Since the states in FDES are not discrete in nature, the above notation proves to be insufficient to represent FDES, and the number of states in FDES is not finite; hence, we use various means to deal with this issue [15, 20]. For FDES modelling, we use a separate notion, as shown in [12, 14 16]. Consider an FDES \(G^{\prime } = (Q^{\prime } ,{\Sigma }^{\prime } ,\delta^{\prime } ,q^{o\prime }\)), where \(Q^{\prime }\) is the set of FDES states, \({\Sigma }^{\prime }\) is the set of FDES events, \(\delta^{\prime }\) is the FDES transition function, and \(q^{o\prime }\) is the start state [21]. Since the notation with symbols like arrows and circles is not relevant in FDES, the notation as per [12, 14, 16] used is as follows:

The current state, \(q^{\prime }\) is denoted by a vector of 0’s, and 1. 0 denotes that the current state value is false for this state indicating the system is not in this state, and ‘1’ denotes that the system is presently in this state. In terminology, this vector is known as a state vector. For example, if we have a system of seven states named as 1, 2, 3, 4, 5, 6, 7 and the current state vector is \(q^{\prime} = \left[ {{ }0{ }0{ }0{ }1{ }0{ }0{ }0{ }} \right]\), it symbolises that the system is in state 4. The current state from \(q^{\prime}\) is the Jth state where value is 1. The length of this vector is obviously equal to the number of states that our system has. In order to incorporate the fuzzy logic and fuzzy sets [22], we can use the fuzzy state vector as follows:

\(q^{\prime} = \left[ {{ }0{ }0{ }0{ }0.3{ }0.7{ }0{ }0{ }} \right]\) means that the system is simultaneously in two states 4 and 5 with membership of 0.3 for state 4 and 0.7 for state 5, respectively. Intuitively, we can say our system is currently in 30% of state 4 and 70% of state 7. For a patient in the above-mentioned example, we may say that currently, he/she is 30% unwell and 70% well.

The FDES transitions \(\delta^{\prime }\) are represented by matrices of events (no of matrices = no of events). For example, if β is any event, then the transition is expressed as:

$$\beta = [\beta_{ij} ] _{n \times n} = \left[ { \begin{array}{*{20}c} {\beta_{11} } & \ldots & {\beta_{1n} } \\ \vdots & & \\ {\beta_{n1} } & { \ldots } & {\beta_{nn} } \\ \end{array} } \right]$$

where \(\beta_{ij}\) = 1 if the state changes from \({\varvec{i}}\) to \({\varvec{j}}\) with the event \(\beta\) and \(\beta_{ij}\) = 0 if no transition happens with the event \(\beta\). For example

\(\beta = \left[ {\begin{array}{*{20}l} {\beta_{11} } \hfill & {\beta_{12} } \hfill \\ {\beta_{21} } \hfill & {\beta_{22} } \hfill \\ \end{array} } \right]_{2 \times 2} = \left[ {\begin{array}{*{20}l} 0 \hfill & 0 \hfill \\ 1 \hfill & 0 \hfill \\ \end{array} } \right]\) means that the event \(\beta\) transits the system from state 2 to state 1 \(({\text{as}}\,\beta_{21} = 1)\).

In the same manner, as fuzziness is applied in subsection (a), it can be used here as well. It can also be exemplified as follows:

\(\beta = \left[ {\begin{array}{*{20}l} {\beta_{11} } \hfill & {\beta_{12} } \hfill \\ {\beta_{21} } \hfill & {\beta_{22} } \hfill \\ \end{array} } \right] _{2 \times 2} = \left[ {\begin{array}{*{20}l} 0 \hfill & {0.1} \hfill \\ 0 \hfill & {0.4} \hfill \\ \end{array} } \right]\) means that it is likely that the system may change its state from state 1 to state 2 with membership (possibility) of 0.1 \(({\text{as}}\,\beta_{12} = 0.1)\) and may remain unchanged in state 2 with a membership of 0.4 \(({\text{as}}\,\beta_{22} = 0.4)\).

The next state is given by the product of \(q^{\prime}\) and \(\beta\) (i.e., \(q^{\prime}\).\(\beta\)). For example, let us assume the current state number to be 2 (out of three states named as state one, state two and state three), then

\(q^{\prime} = \left[ {{ }0{ }1{ }0{ }} \right]\) and let the event \(\beta\) \(= { }\left[ {{ }\begin{array}{*{20}c} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} } \right]\), then the next state will be given by their product as

$$q^{\prime } \cdot \beta = \left[ { 0 1 0 } \right]\left[ { \begin{array}{*{20}c} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} } \right] = \left[ { 1 0 0 } \right]$$

which means from state two, our system will next transit to state one with the effect of event \(\beta\).

When fuzziness is introduced, the next state is given by the max-product operation [7, 12, 23] or composition of fuzzy relations, i.e.,

$${ }q^{\prime } o\,\beta = \max \left[ {\mu_{{q^{\prime}\left( {i,j} \right)}} ,\mu_{{\beta \left( {i,j} \right)}} } \right]$$
(1)

where \({ }\mu { }\) denotes the product between the subscripts.

Example: if \(q^{\prime} = \left[ {{ }0.6{ }0.3{ }} \right]\) and \(\beta\) \(= \left[ {\begin{array}{*{20}l} 1 \hfill & {0.5} \hfill \\ {0.8} \hfill & {0.4} \hfill \\ \end{array} } \right]{ }\), then according to (1)

$$\begin{aligned} q^{\prime }_o\beta & = \left[ {{\text{MAX}}\left\{ {\left( {0.6} \right)\left( 1 \right),\left( {0.3} \right)\left( {0.8} \right)} \right\},{\text{MAX}}\left\{ { \left( {0.6)(0.5} \right),\left( {0.3)(0.4} \right)} \right\}} \right] \\ & = [{\text{MAX}}(0.6,0.24),{\text{MAX }}\left( {0.3, 0.12} \right)] = [ 0.6 0.3] \\ \end{aligned}$$

means that our system will remain in the same state after the \(\beta\) event as the resultant state is same as our \(q^{\prime}\).

In order to diversify the views obtained from the specialists of a particular domain, a separate notion was proposed as an extended FDES theory [16]. It offers to use pure fuzzy numbers instead of the discrete numbers. In this notion, the state is represented by:

$${ }_{k} q^{\prime}_{i} = \left[ {{ }_{k} q^{\prime}_{1} { }_{k} q^{\prime}_{2} { }_{k} q^{\prime} \ldots_{k} q^{\prime}_{n1} } \right]$$
(2)

where \(k\) represents the \(k\) th state, \(i\) denotes the fuzzy state and \(n_{1}\) represents the entire number of fuzzy states of state \(k\). The members are represented by fuzzy representations, for example, if the system is currently in the first state and possesses three fuzzy states, i.e., \(k\) = 1 and \(n_{1}\) = 3, then according to the extended notion

$${ }_{1} q^{\prime}_{i} = \left[ {{ }\frac{1}{1}{ }\frac{1}{0}{ }\frac{1}{0}} \right],{\text{where}}\,{ }_{1} q^{\prime}_{1} = \frac{1}{1},{ }_{1} q^{\prime}_{2} = \frac{1}{0} \;{\text{and}}\;{ }_{1} q^{\prime}_{3} = \frac{1}{0}.$$

This representation can handle the aforementioned notation as a special case [16]. It may be noted that in this kind of representation, the numerators stand for the degree of membership while denominators denote the item under discussion. A fuzzy transition matrix represents the event transition accordingly. Online learning algorithms have been developed to make the system learn the event transition matrices [13].

3 Decision-Making in FDES

Mostly fuzzification is used in decision-making where information is imprecise [24]. We try to make the system decide based on vagueness, just like humans do. Given the statement ‘it is hot outside’, based on the discrete 0 or 1 logic, machines cannot decide how much hot actually the weather is. They cannot determine which clothes to wear and which not because the term ‘hot’ is a vague term. Once FDES is modelled, the system should be able to make such decisions. A detailed architecture for decision-making in FDES, along with an illustration, exists in [25], Fig. 4. Here, we will only discuss the core procedures briefly.

Fig. 4
figure 4

FDES decision-making and control architecture [25]

Full size image

First of all, we need to identify the necessary factors that affect the process of decision-making. For example, if we are planning a prescription schedule for a patient, then the factors that are crucial for the decision-making of regimen selection may include potency, adverse events, adherence and future drug possibilities as revealed in [8].

Once the essential states are known, the next step is to determine the FDES decision model. This decision model comprises of the following four components: fuzzy automata, corresponding states, events in each automaton and the transition matrices of events [25]. The representation of each component is the same as discussed earlier.

Afterwards, a forward-looking tree, as shown in Fig. 5, is constructed. Each node of this tree represents a fuzzy state (denoted by \(q^{\prime }\)). The root node is the initial state. Next state is calculated as \(q^{\prime}\)o\(\beta\). The process goes on until the full tree is ready. L is the number of steps in the tree. The number of nodes depends upon the steps [26].

Fig. 5
figure 5

An L-step forward-looking tree [27]

Full size image

Since the forward-looking tree contains a number of combinations, we need the configuration (path) with optimal cost. In order to achieve this, performance index \(J\left( {q^{\prime } } \right)\) is calculated against all nodes with the help of any effective function (chosen as per suitability). Effective function outputs the weight-based performance value for each node. The weights denote the grade of impact on the corresponding state. Since weights depend on a number of factors, they can be determined by using the facts from the knowledge base [28]. The path (set of nodes) with maximum \(J\left( {q^{\prime } } \right)\) is selected as an optimal path, and the final decision is made. Performance index \(J\left( {q^{\prime } } \right)\) is given by:

$$J\left( {q^{\prime } } \right) = { }w_{1}^{T} { }q^{\prime }_{1} + w_{2}^{T} { }q^{\prime }_{2} + \cdots + w_{n}^{T} { }q^{\prime }_{n}$$
(3)

which may be rewritten as:

$$J\left( {q^{\prime } } \right) = { }\mathop \sum \limits_{i = 1}^{n} w_{i}^{T} { }q^{\prime }_{i} { }$$
(4)

where \(w_{1} ,w_{2} ,w_{3} , \ldots ,w_{n}\) are the weight vectors and \(q_{1}^{\prime } ,q_{2}^{\prime } ,q_{3}^{\prime } , \ldots ,q_{n}^{\prime }\) are the corresponding state vectors.

For instance, let our calculated \(J\) values for forward-looking tree nodes be \(x_{1} ,x_{2} ,x_{3} , \ldots x_{n}\) where \(n = \left| {Q^{\prime } } \right|\), i.e., number of states. We compare these values or simply arrange them in decreasing order, for instance: \(x_{3} > x_{1} > x_{2} > x_{4} > \cdots > x_{{\left( {n - 6} \right)}}\).

The above statement means that \(J\) value for node 3 is the largest, and hence, we choose this node and then check the nodes under node 3 with the highest \(J\) value and select it. Going this way, we get a configuration of nodes and translating the events in the sequence of this configuration is our optimal decision. We take a real example from [25] with calculated \(J\) values and highlight the optimal decision path (with events \(\propto_{1} { }\) and \(\beta_{1}\)) based on greater \(J\) value as shown in Fig. 6.

Fig. 6
figure 6

Optimal decision path based on \({\varvec{J}}{ }\) value [25]

Full size image

4 FDES Applications

FDES is applicable in imprecise situations. It finds its application in treatment modelling, economic modelling, control system modelling, etc. [25]. In this section, we discuss two examples of air-conditioning system and HIV/AIDS treatment regimen selection.

4.1 Air Conditioning System

A study of air-conditioning system prevails in [28]. A.C system is a typical example of FDES as it automatically adjusts the temperature of a space according to the requirement and hence possesses fuzzy states instead of discrete ones.

Modelling of Air-Conditioning FDES

D. Li et al. identified the five factors affecting the decision-making in an A.C. system as end supplied air volume, chilling water volume, cooling water volume, the temperature setting of cooling tower fan and water chiller [28]. The respective events corresponding to these factors may be denoted by \(\propto_{1} , \propto_{2} , \propto_{3} , \propto_{4} \;{\text{and}}\; \propto_{5}\).

The three states identified are: raise (R), maintain (M) and lower (L). So, our automaton for such system may look like \(G^{\prime } = (Q^{\prime } , \Sigma^{\prime } ,\delta^{\prime } ,q\)o\(\prime\)), where symbols have their usual meanings. The five factors mentioned may form the five automata for A.C FDES system, i.e., \(G_{1} ,G_{2} ,G_{3} ,G_{4} \;{\text{and}}\;G_{5}\), respectively.

\(G_{1}\): consists of four states, viz. initial (I1), lower state (L1), maintain state (M1) and raise state (R1).

\({\text{Similarly}},G_{2}\) includes I2, L2, M2 and R2.

\(G_{3}\) includes I3, L3, M3 and R3.

\(G_{4}\) includes I4, L4, M4 and R4.

\(G_{5}\) includes I5, L5, M5 and R5.

As an illustration, \(q_{1} = \left[ {0{ }0{ }0.5{ }0} \right]\) means that automaton \(G_{1}\) is currently in the maintain state (M1) with a membership of 0.5.

Decision-making in A.C FDES

The factors responsible for decision-making are already identified. A.C FDES is also modelled in (a). Now in order to make any decision, we need to construct a forward-looking tree. Every branch of the forward-looking tree is a decision in itself. From so many choices, we need the optimal decision, as stated earlier.

As illustrated in Fig. 7, the states will go on decreasing, e.g., when \(\propto_{3}\) occurred, only four events remained (\(\propto_{1} , \propto_{2} , \propto_{4} \;{\text{and}}\; \propto_{5}\)) to happen. Similarly, at the second stage, only three events are left to happen. In this way, only one event remains at last that can occur.

Fig. 7
figure 7

State reduction [27]

Full size image

After generating the state combinations, an optimal configuration is needed from all possible amalgamations. This is attained by the effectiveness function \(J\left( {q^{\prime } } \right),\) stated in Sect. 3.

The A.C system will choose the decision path with maximum \(J\) value [27]. This configuration will change with the change in inputs, and hence, the temperature will be regulated automatically.

4.2 Treatment Planning

Another important example of the application of FDES is of treatment planning as the treatment process also consists of fuzzy states. Diabetes treatment is illustrated in [29]. Another such example of HIV/AIDS treatment regimen selection process is studied in [26, 30]. This application is vital as HIV/AIDS treatment selection is regarded as a complex medical process [31, 32]. Hao Ying et al. identified the four factors affecting this selection process as potency, adherence, adverse events and future drug possibilities [26, 33,34,35,36]. Four famous and significant first-round HIV/AIDS regimens are studied, and after consultation with the field experts, characteristics of regimens (Table 1) are calculated against each factor [30].

Table 1 Data of clinical factors against four popular first-round HIV/AIDS regimens [30]
Full size table

Modelling of HIV/AIDS treatment regimen selection FDES

The four medical factors mentioned are taken as four state vectors of the fuzzy system denoted by \(q_{1} ,q_{2} ,q_{3} \;{\text{and}}\;q_{4}\), respectively. The \(q_{1}\) comprises of two states, i.e., high and medium, \(q_{2}\) consists of three states, i.e., easy, moderate and challenging, \(q_{3}\) has three states, i.e., medium, low and very low, and \(q_{4}\) has two states, i.e., high and medium. Employing the regimens is identified as a crisp event.

Decisioning in Regimen Selection

The state transition matrices are calculated from the data given in Table 1. The four medical factors are fuzzified in the same way as done in fuzzy controller input variables [37]. The state transition interpretation is the same as shown already. Since \(q_{1}\) has 2 states, \(q_{2}\) has 3 states, \(q_{3}\) has 3 states and \(q_{4}\) has 2 states, the system has to decide from as many as 36 (\(2 \cdot 3 \cdot 3 \cdot 2\)) regimen amalgamations (decisions) and pick the best-suited decision. Out of 36, 4 combinations (viz. medium \(q_{1}\) and moderate \(q_{4}\) when \(q_{2}\) is moderate or challenging and \(q_{3}\) is moderate or small), are considered to be medically pointless. Out of remaining 32 combinations, effective decision is picked using an effective function. We get four values from the function for each combination corresponding to the four treatment regimens. The value having maximum value is taken as the first regimen, and the one with minimum value is the fourth regimen. Moreover, in order to select the optimal weights, genetic algorithm [38] is employed, and the overall effectiveness measure is increased. The model is validated by comparing the system results with the independent physician results. The valid agreement between the two is evident [30].

5 Conclusion and Future Scope

Fuzzy discrete event system is an extension of discrete event system (DES), that is used to study and model the vague systems. In this paper, we present a brief survey on FDES. The techniques to model the FDES are highlighted. We showed the decision-making process of FDES, along with the real-world application in A.C system and HIV/AIDS treatment regimen selection.

The limited availability of literature in this field was realised. The FDES theory is currently in its development phase, but several efforts and increasing research interest in this field are providing opportunities for the same. The identification of relevant fuzzy areas for implementation of FDES needs to be done effectively. Moreover, the states of FDES being indefinite, effective online optimization is the primary concern.