Automatic Reconfiguration of Untimed Discrete-Event Systems

M. Macktoobian and W. M. Wonham

(Department of Electrical and Computer Engineering
University of Toronto
Toronto, ON, Canada M5S 3G4
Email: {matin.macktoobian,wonham}@scg.utoronto.ca)

Abstract

This work introduces a general formulation of the reconfiguration problem for untimed discrete-event systems (DES), which can be treated directly by supervisory control theory (SCT). To model the reconfiguration requirements we introduce the concept of reconfiguration specification (RS); here reconfiguration events (RE) are introduced to force a transition from one system configuration to another. Standard SCT synthesis is employed to obtain a reconfiguration supervisor (RSUP) in which designated states serve as the source states for RE. The reconfiguration problem itself is formulated as that of establishing guaranteed finite reachability of a desired RE source state in RSUP from the current state in RSUP at which a change in configuration is commanded by an external user. The solvability (or otherwise) of this reachability problem is established by backtracking as in standard dynamic programming.

{textblock}

14(1.5,1) Published in “2017 14th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE)”
DOI: 10.1109/ICEEE.2017.8108839

1 Introduction

Highly complex systems are typically composed of many components. A system configuration (mode) is implemented by a particular subset of the system’s components exhibiting a specific functionality. Dynamic reconfiguration is the automatic switching of the current configuration of the system to a new one commanded by the system’s external user (e.g., manager of a factory workcell). The importance of reconfiguration, in the case of complex systems, is two-fold. First, the model now embraces multimodal systems, thereby achieving multifunctionality through multimodality. Second, since reconfiguration enables switching from a faulty configuration to a sound one, the overall system’s reliability, and its robust response to faults, are each enhanced.

There have been extensive investigations into the notion of reconfiguration in the context of different complex systems such as power systems ([1, 2, 3]), embedded systems ([4, 5]), hybrid systems ([6, 7]), and manufacturing systems ([8]). Petri-net-based modeling of DES has also been employed to realize dynamic reconfiguration tasks. For example, [9] proposed a communication protocol to coordinate reconfiguration of software agents by coordination matrices. Many other applications of Petri nets could be cited of dynamic reconfiguration of complex systems (e.g., see [10]).

Moreover, some efforts have been applied to engineer reconfigurable DES. For instance, [11] recommended a coordinated approach to solve the problem; the technique stressed communication among the subsystems of the DES. It was further assumed that all subsystems are equipped with coordinators to manage the system reconfigurations. The virtual coordinator exchanges messages with subsystems separately, rather than subsystems intercommunicating directly. Whenever a subsystem desires to execute a global reconfiguration, it first requests permission of the coordinator. However, the approach seems not to be efficiently scalable.

Recently, the notion of state attraction [12] has been used to reconfigure DES by regular specifications. In particular, a coordination automaton (CA) is generated to weakly attract a required reconfiguration. The path from each initial state of CA to its marked state guides a particular supervisor to realize the required reconfiguration [13]. However, this approach is unable to reconfigure DES at any arbitrary state, and the synthesized CA is nondeterminstic including more than one initial state.

For the reconfiguration control of DES, SCT [14] has already shown promise. Recall that in SCT a supervisor is synthesized for given formal specifications in such a way as to be correct by design. In this spirit [15] addressed the dynamic rescheduling of a timed DES (or TDES) by use of a timed supervisor. In addition [16] proposed a method based on Petri nets and integer programming to optimize the cost of reconfiguration. The method uses linear constraints to synthesize deadlock-free supervisors by SCT.

This paper presents an automatic procedure to reconfigure DES by SCT dynamically. To this end, we introduce the notion of reconfiguration specification (RS) to model reconfiguration requirements; this specification is incorporated into the SCT supervisor synthesis in the usual way. The resulting supervisor not only realizes the behavioral specifications of the DES, but also switches between configurations when reconfiguration is commanded by an external system manager. Finally, it is necessary to know whether a desired reconfiguration is achievable from a particular state of the supervisor or not. At that point we apply a backtracking path-finding algorithm based on dynamic programming to collect all forcible paths (if any) that solve the intended reconfiguration problem.

The paper is organized as follows: Section 2 is devoted to preliminaries. Section 3 elaborates on the realization of the automatic dynamic reconfiguration by SCT. The new definition of RS is stated in Section 3.1. Section 3.2 provides the RSUP synthesis process. The reconfiguration problem is formally defined in Section 4.1. In Section 4.2 we describe the collection of forcible backtracking paths; the formal algorithm is presented Section 4.3. Section 5 illustrates the proposed method with an example, and conclusions are drawn in Section 6.

2 Preliminaries

SCT controls DES modeled by the Ramadge-Wonham framework [17, 18]. A DES is formally represented by a generator, say

\textbf{G}=(Q,\Sigma,\delta,q_{0},Q_{m}),

where $\Sigma=\Sigma_{c}\dot{\cup}\Sigma_{u}$ is a finite alphabet of event labels, partitioned into the controllable event labels and the uncontrollable ones; $Q$ is the state set, assumed finite; $\delta:Q\times\Sigma^{*}\rightarrow Q$ is the extended partial transition function; $q_{0}$ is the initial state; and $Q_{m}\subseteq Q$ is the subset of marked states. The closed behavior and the marked behavior of G are the languages

L(\textbf{G}):=\{s\in\Sigma^{*}|\delta(q_{0},s)!\}

and

L_{m}(\textbf{G}):=\{s\in L(\textbf{G})|\delta(q_{0},s)\in Q_{m}\}

Here $\delta(q_{0},s)!$ means that $\delta(q_{0},s)$ is defined. A supervisory control function for G is a map $\textbf{V}:L(\textbf{G})\rightarrow\Gamma$ , in which $\Gamma=\{\gamma\in Pwr(\Sigma)|\gamma\supseteq\Sigma_{u}\}$ is the set of control patterns. ‘G under supervision of V’ is written as $\textbf{V}/\textbf{G}$ .

Given a sublanguage $M\subseteq L_{m}(\textbf{G})$ we define the marked behavior of $\textbf{V}/\textbf{G}$ as $L_{m}(\textbf{V}/\textbf{G}):=L(\textbf{V}/\textbf{G})\cap M$ . V is a marking nonblocking supervisory control (MNSC) for the pair $(M,\textbf{G})$ if $\overline{L_{m}(\textbf{V}/\textbf{G})}=L(\textbf{V}/\textbf{G})$ . In practice, V is implemented by a supervisor, which can be taken as a generator SUP that represents the maximally permissive controlled behavior $L_{m}(\textbf{V}/\textbf{G})$ subject to a generator specification, say SPEC; we denote this computation by SUP = supcon (G,SPEC). For details see, e.g., [14].

Figure 1: Generator of a binary RS

3 DES Reconfiguration

Refer to caption — Figure 2: DES reconfiguration process

3.1 Reconfiguration Specification

A reconfiguration requirement is a transition request to transfer the system from one configuration to another. The set of reconfiguration requirements associated with a DES is represented by the RS. As the first step, the following definition clarifies the notion of configuration (mode).

Definition \@upn1 [Configuration (Mode)].

Let G be a DES constructed by (synchronous product of) the collection of component sets $C_{\textbf{G}}=\{C_{\textbf{G}}^{\alpha}|\alpha\in\mathcal{I}\}$ , where $\mathcal{I}$ is an index set. A configuration (mode) of G is a component set $C^{0}_{\textbf{G}}\subseteq C_{\textbf{G}}$ such that G operates as the corresponding synchronous subproduct, when the elements of $C^{0}_{\textbf{G}}$ and $C_{\textbf{G}}\setminus C^{0}_{\textbf{G}}$ are respectively active and inactive.

The source and destination configurations, corresponding to a reconfiguration task, are connected through a reconfiguration event (RE) which specifies a transition from the former to the latter.

Definition \@upn2 [RE].

Given DES G with component set $C_{\textbf{G}}$ , let $C^{\mathcal{A}}_{\textbf{G}},C^{\mathcal{B}}_{\textbf{G}}\subset C_{\textbf{G}}$ be two configurations of G, where $\mathcal{A}$ and $\mathcal{B}$ are the component sets which must be deactivated and activated respectively in the course of reconfiguration; then, RE $\sigma_{\mathcal{A},\mathcal{B}}$ must occur to trigger the reconfiguration task. We formalize this task as follows.

Definition \@upn3 [RS].

For a configuration $C_{\textbf{G}}^{\mathcal{I}}$ of G, with components $\{\textbf{G}_{a}|a\in\mathcal{I}\}$ , let $\Sigma_{\mathcal{I}}$ denote the set of exactly the event (labels) appearing in the corresponding components, i.e.

\Sigma_{\mathcal{I}}:=\bigcup\{\Sigma_{a}|a\in\mathcal{I}\}

For clarity we first consider the case of just two configurations, indexed by $\mathcal{A}$ and $\mathcal{B}$ , and assume that reconfiguration requires switching either from $C_{\textbf{G}}^{\mathcal{A}}$ to $C_{\textbf{G}}^{\mathcal{B}}$ , with the system G initially in mode $C_{\textbf{G}}^{\mathcal{A}}$ . As in Definition 2, bring in the corresponding switching events $\sigma_{\mathcal{A},\mathcal{B}}$ and $\sigma_{\mathcal{B},\mathcal{A}}$ . We define the RS as the DES

E_{\mathcal{R}}:=(Q_{\mathcal{R}},\Sigma_{\mathcal{R}},\delta_{\mathcal{R}},{q_{0}}_{\mathcal{R}},{Q_{m}}_{\mathcal{R}})

where

•

$Q_{\mathcal{R}}:=\{q_{\mathcal{A}},q_{\mathcal{B}}\}$
•

$\Sigma_{\mathcal{R}}:=\Sigma_{\mathcal{A}}\cup\Sigma_{\mathcal{B}}\dot{\cup}\{\sigma_{\mathcal{A},\mathcal{B}},\sigma_{\mathcal{B},\mathcal{A}}\}$
Note that $\Sigma_{\mathcal{A}}\cup\Sigma_{\mathcal{B}}$ is disjoint from $\{\sigma_{\mathcal{A},\mathcal{B}},\sigma_{\mathcal{B},\mathcal{A}}\}$ .

•

\delta_{\mathcal{R}}(q_{\mathcal{A}},\sigma):=\begin{cases}q_{\mathcal{A}}~{}~{}~{}\text{if}~{}~{}~{}\sigma\in\Sigma_{\mathcal{A}},\\ q_{\mathcal{B}}~{}~{}~{}\text{if}~{}~{}~{}\sigma=\sigma_{\mathcal{A},\mathcal{B}},\end{cases}

\delta_{\mathcal{R}}(q_{\mathcal{B}},\sigma):=\begin{cases}q_{\mathcal{B}}~{}~{}~{}\text{if}~{}~{}~{}\sigma\in\Sigma_{\mathcal{B}},\\ q_{\mathcal{A}}~{}~{}~{}\text{if}~{}~{}~{}\sigma=\sigma_{\mathcal{B},\mathcal{A}},\end{cases}

•

${q_{0}}_{\mathcal{R}}:=q_{\mathcal{A}}$
•

${Q_{m}}_{\mathcal{R}}:=\{q_{\mathcal{A}},q_{\mathcal{B}}\}$

$E_{\mathcal{R}}$ is depicted in Fig. 1.

It is obvious that, with some notational elaboration, this definition of $E_{\mathcal{R}}$ could be extended to an arbitrary number of distinct configurations and pairwise switchings among them, but we refrain from doing so here.

3.2 Reconfiguring Supervisor Synthesis

In general SCT synchronizes the plant DES G with its associated behavioral specification prior to synthesizing the supervisor which controls it. To synthesize RSUP we provide in this section an extended supervisor synthesis procedure in which the RS is taken into account.

The main idea is to treat the RS on the same footing as any other behavioral specification. The process is illustrated in Fig. 2.

We start by synchronizing all the components associated with G; here the operator ‘ $\parallel$ ’ denotes synchronous product [19]. Then, G is synchronized with the RS $E_{\mathcal{R}}$ leading to the multimodal version of G, say GMode as follows.

\textbf{GMode}:=(||_{i=1}^{n}\textbf{G}_{i})||E_{\mathcal{R}}

Next, the global system specification is defined by the synchronization of the behavioral specification $E$ with all events of GMode. Finally, the reconfiguration supervisor is computed as:

\textbf{RSUP}:=\textbf{supcon}(\textbf{GMode},[\textbf{allevents}(\textbf{GMode})||E])

where the operator allevents returns a marked one-state DES selflooped with all the events of the argument. For details see, e.g., [14].

We emphasize that RSUP enforces both the behavioral and reconfiguration requirements of G.

In the next section we complete the design process by presenting an algorithm to solve the final reconfiguration problem.

4 Reconfiguration Solvability

We construct a backtracking algorithm that collects all forcible paths reaching a suitable target state of RSUP from an arbitrary current state. To this end, we first present the formal definition of the reconfiguration problem, then obtain the conditions for backtracking forcibility, and finally propose an algorithm to solve the problem.

4.1 Problem Statement

Especially when it is the intended response to some unexpected failure or emergency, reconfiguration could possibly be commanded from an arbitrary state in RSUP of the current (running) configuration. Thus the system must be forced onto a path or set of paths in the RSUP state space leading from the current state to one at which the desired reconfiguration event is defined. The question is then whether or not such a path (set) always exists and can be executed in timely fashion. We thus consider

Problem \@upn1 [Reconfiguration Feasibility].

Denote by $q_{c}$ the state where RSUP currently resides, and let $q_{r}$ be a state at which a desired reconfiguration event, say $\sigma_{r}$ , is defined; namely $\delta_{\mathcal{R}}(q_{r},\sigma_{r})!$ Subject to an appropriate specification of forcibility, determine the forcible path (set) from $q_{c}$ to $q_{r}$ .

We shall declare a path (set) forcible if it can be enforced using the standard SCT “technology” of controllable event disablement, with or without the possible additional use of preemption by a forcible event ([14], Sect. 3.8).

The following section describes how to obtain a forcible path (set).

4.2 Backtracking Forcibility

The algorithm is critically governed by the conditions which define forcibility of each backtracking step; if a backtracking step is forcible, then its event is appended to the current path.

We explain the backtracking forcibility conditions (BFCs) by a hypothetical search space as depicted in Fig. 3. We assess the forcibility of the backtracking from $q_{r}$ to $q_{i}$ . In other words, we plan to find whether $\sigma$ contributes to an forcible path (from $q_{i}$ to $q_{r}$ ) or not.

Let $\Sigma^{i}=\{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4},\sigma^{\prime}\}$ be the set of defined events at $q_{i}$ , competing with $\sigma$ to occur. Let also $\Sigma_{i}=\{\sigma\}$ be the defined events transitioning from $q_{i}$ to $q_{r}$ . If any of the following four conditions hold, then backtracking to $q_{i}$ is permissible, and $\sigma$ is a solution to this problem:

BFC-1: $\Sigma^{i}=\varnothing$
There is no event competing with $\sigma$ to occur at $q_{i}$ . In other words, $\sigma$ is the exclusive event which can occur at $q_{i}$ .

BFC-2: $(\forall\sigma^{\prime}\in\Sigma^{i})~{}\sigma^{\prime}\in\Sigma_{c}$
If all of the $\Sigma^{i}$ events are controllable, then they can be disabled; therefore, $\sigma$ can occur at $q_{i}$ .

BFC-3: $[(\nexists\sigma^{\prime}\in\Sigma_{i})~{}\text{pr}(\sigma^{\prime},\sigma)]~{}~{}\wedge~{}~{}[(\forall\sigma^{\prime}\in\Sigma^{i}_{u})(\exists\sigma^{\prime\prime}\in\Sigma^{i})]~{}\text{pr}(\sigma^{\prime\prime},\sigma^{\prime})$
$\Sigma^{i}$ is composed of both controllable and uncontrollable events. The first subformula says no competing event should be able to preempt $\sigma$ . The second subformula asserts that each uncontrollable event must be preemptable by at least another event. Note that the binary relation $\text{pr}(\sigma^{\prime},\sigma^{\prime\prime})$ holds if the forcible event $\sigma^{\prime}$ can preempt $\sigma^{\prime\prime}$ (see, section 3.9 of [14]). Furthermore, $\Sigma_{u}^{i}$ and $\Sigma_{c}^{i}$ represent the largest uncontrollable and controllable subsets of $\Sigma^{i}$ , respectively, where $\Sigma^{i}=\Sigma_{c}^{i}\dot{\cup}\Sigma_{u}^{i}$ .

BFC-4: $(\exists\sigma^{\prime}\in\Sigma_{u}^{i})(\forall\sigma^{\prime\prime}\in\Sigma_{j}\cup\Sigma^{j})~{}~{}[\delta(q_{i},\sigma^{\prime})=q_{j}\wedge\sigma^{\prime\prime}\in\Sigma_{c}$ ], where $\Sigma_{j}$ contains the event(s) transitioning from $q_{j}$ and to $q_{r}$ , and $\Sigma^{j}$ contains the event(s) transitioning from $q_{j}$ to the other states.

This condition determines the succession of the uncontrollable events leading to a state containing only controllable events; since the controllable events can be disabled, both $\sigma$ and $\sigma^{\prime}\sigma^{\prime\prime}$ are forcible paths.

We employ the foregoing conditions, as decision-making criteria, to solve the reconfiguration problem by a backtracking algorithm in the next section.

4.3 Reconfiguration Solvability Algorithm

Admissible paths can be collected by the Algorithm 1. The inputs are the target state, from which the backtracking starts; the source state, which is the algorithm’s goal to be visited; the state list of the supervisor, which is the search space of the problem including the target and source state; and a temporary list of incomplete paths initialized to empty, in which the potential solutions are stored, corresponding to each instantiation of the algorithm. The output is the collection of the found paths.

The algorithm keeps the track of the visited states and events. If it visits a state that is the destination of more than one event, the algorithm checks inductively the solvability of those branches.

Algorithm 1 Path Collector Algorithm (

\mathcal{PCA}

)

q_{r}

\triangleright

Target state

q_{s}

\triangleright

Source state

Q_{T}

\triangleright

State list

\mathcal{P}_{\text{temp}}

\triangleright

Temporary list of an incomplete path

\mathcal{P}

\triangleright

Path collection

8:if

Q_{T}=\varnothing

then

9: return

\mathcal{P}

\triangleright

All instances of

\mathcal{PCA}

are terminated.

10:else

11:

\mathcal{Q}\leftarrow\{q|\delta(q,\sigma)=q_{r}\}

12: for each

q_{i}\in\mathcal{Q}

13:

\Sigma_{i}\leftarrow\{\sigma|\delta(q_{i},\sigma)=q_{r}

}

14:

\Sigma^{i}\leftarrow\{\sigma|\delta(q_{i},\sigma)!\}-\Sigma_{i}

15: if

q_{i}=q_{s}

then

16:

\mathcal{P}\leftarrow\text{append }\Sigma_{i}\text{ to }\mathcal{P}_{\text{temp}}

17:

Q_{T}\leftarrow Q_{T}-\{q_{i}\}

18: else

19: for each

\sigma\in\Sigma_{i}

20: if (BFC-1

\parallel

BFC-2

\parallel

BFC-3

\parallel

BFC-4) then

21:

\mathcal{P}_{\text{temp}}\leftarrow\text{append }\sigma\text{ to }\mathcal{P}_{\text{temp}}

22:

Q_{T}\leftarrow Q_{T}-\{q_{i}\}

23: return

\mathcal{PCA}(q_{i},q_{s},Q_{T},\mathcal{P}_{\text{temp}})

24: end if

25: end for

26: end if

27: end for

28:end if

Line 1 defines the terminal case; if all states are checked, then the path collection will be delivered.

Line 4 gathers the states that have transitions to the current target state. The defined events at each found state are stored in two variables: variable $\Sigma_{i}$ which contains the event(s) transitioning from the found state $q_{i}$ to the current state (Line 6); and variable $\Sigma^{i}$ which stores the event(s) transitioning from $q_{i}$ to the other states (Line 7).

If $q_{i}$ is the source state (Line 8), then a path is found. Hence, the recent found event is attached to the temporary solution, and the result is stored in the path collection (Line 9). Moreover, $q_{i}$ is removed from the global list of unvisited states (Line 10). Otherwise, BFCs are checked with respect to the elements of $\Sigma_{i}$ and $\Sigma^{i}$ (Line 13). If any of these conditions holds, then the backtracking from the current state to $q_{i}$ is authorized, thereby appending $\sigma$ to the temporary solution variable (Line 14). Then, the global variable list is updated by removing $q_{i}$ (Line 15), and a new instantiation of the algorithm is called according to the updated current state (Line 16). Note that both $Q_{T}$ and $\mathcal{P}$ are global variables that can be read and modified by any instantiation of $\mathcal{PCA}$ .

Finally, Algorithm 1 can be incorporated appropriately into the final solvability checker function, i.e., Algorithm 2. First, the state list is initialized to the unvisited states; thus, the target state is initially excluded (Line 1). Then, all of the found paths by instantiations of $\mathcal{PCA}$ are gathered (Line 2). The fourth argument of $\mathcal{PCA}$ represents the found path that is initially empty. As already asserted, each successful backtracking step appends the found event to its incomplete path. At the end, the decision is made based on the path collection (Lines 3-7).

Algorithm 2 Reconfiguration Solvability Algorithm (

\mathcal{RSA}

)

q_{r}

\triangleright

Target state

q_{s}

\triangleright

Source state

4:RSUP

\triangleright

Supervisor

6:solvability

Q_{T}\leftarrow Q_{\textbf{RSUP}}-\{q_{r}\}

\mathcal{P}\leftarrow\mathcal{PCA}(q_{r},q_{s},Q_{T},\varnothing)

9:if

\mathcal{P}\neq\varnothing

then

10: return The reconfiguration problem IS solvable by any path of

\mathcal{P}

11:else

12: return The reconfiguration problem IS NOT solvable.

13:end if

5 Example

We provide an example to illustrate a configuration problem associated with a DES.

Figure 4 depicts SMALL FACTORY (SF) with two 3-state machines M1 and M2, and buffers BUF1 and BUF2 with three slots and one slot, respectively. Assume that the machines can work with either of the buffers. In other words, SF has two modes: $C^{1}_{\textbf{SF}}=\{\textbf{M1},\textbf{M2},\textbf{BUF1}\}$ , and $C^{2}_{\textbf{SF}}=\{\textbf{M1},\textbf{M2},\textbf{BUF2}\}$ . Moreover, the events are described in Table 5. Given the required RS as Fig. 5, the synthesized RSUP is controllable including 78 states and 270 events.

Assume that SF resides currently at [41] ¹¹1In this section, symbols $[q]$ and $\Braket{\sigma}$ represent state $q$ and event $\sigma$ , respectively. and a reconfiguration is requested to switch from $C^{1}_{\textbf{SF}}$ to $C^{2}_{\textbf{SF}}$ . Let [9] be the destination state, including $\braket{91}$ where the reconfiguration event $\braket{91}$ is defined.

Consequently, $\mathcal{RSA}$ backtracks from the [9] to [41] to find all forcible paths. The shortest path is $\braket{23,31,20,31,20,31}$ , as depicted in Fig. 6. The path computation is analyzed as follows.

•

Backtracking [9] to [5]: according to BFC-2, backtracking is authorized; because $\braket{11}$ can be disabled.
•

Backtracking [5] to [19]: $\braket{11}$ can be safely disabled, but $\braket{22}$ may occur sooner than $\braket{20}$ , thereby preempting it according to BFC-3. According to the BFC-4, $\braket{23}$ can be disabled, so the occurrence of $\braket{22}$ is handled and blocked by the aforesaid disablement. Therefore, both paths $\braket{20}$ and $\braket{22,23}$ are qualified paths.
•

Backtracking [19] to [12]: the same as backtracking [9] to [5].
•

Backtracking [12] to [32]: the same as backtracking [5] to [19].
•

Backtracking [32] to [26]: according to BFC-1, backtracking is authorized; because there is no event competing with $\braket{31}$ to occur.
•

Backtracking [26] to [41]: the same as backtracking [32] to [26], considering $\braket{23}$ instead of $\braket{31}$ .

The results demonstrate that the reconfiguration problem is solvable, and the supervisor can randomly select any path from the forcible path collection to realize the reconfiguration.

It is important to note, finally, that at state [9], which serves as source state for the RE $\braket{91}$ the controllable event $\braket{11}$ must be disabled, and $\braket{91}$ must be forced to preempt the uncontrollable events $\braket{20,22}$ . This is acceptable on physical grounds, inasmuch as $\braket{11}$ (M1 takes a new workpiece) is controllable, and $\braket{20,22}$ can only occur while M2 is working, so that preemption can be plausibly assumed to take place in the working time delay interval.

Note that the 2-way RS may result in blocking in case of retaining the possibility of a reconfiguration from $C^{2}_{\textbf{SF}}$ back to $C^{1}_{\textbf{SF}}$ , since disabling $\braket{91}$ ends up with the disablement of another reconfiguration. We may address two approaches to solving this issue: first, $C^{1}_{\textbf{SF}}$ can be considered as the initial state of RS, thereby solving the second reconfiguration problem independently of the first one; alternatively, a 1-way RS can be used for each reconfiguration.

Event	Description
11	M1 takes a workpiece.
20	M2 successfully completes processing a workpiece.
12 / 22	Breakdown occurs in M1 / M2.
13 / 23	M1 / M2 is repaired.
30 / 32	M1 increments BUF1 / BUF2.
31 / 33	M2 decrements BUF1 / BUF2.
91	The reconfiguration $C^{1}_{\textbf{G}}\rightarrow C^{2}_{\textbf{G}}$ is requested.
93	The reconfiguration $C^{2}_{\textbf{G}}\rightarrow C^{1}_{\textbf{G}}$ is requested.

6 Conclusion

This paper proposes a solution to the reconfiguration problem for DES. To this purpose, we first model reconfiguration requirements of the DES by RS. Then, SCT synthesizes RSUP, considering the RS. Finally, forcible paths are computed by a dynamic-programming-based algorithm, so it can check the solvability of a user-initiated reconfiguration request. The algorithm in fact backtracks from a desired reconfiguration event source state to the current state in RSUP. Guaranteed finite reachability of the source state is confirmed (or otherwise) by the construction of the forcible path set.

Acknowledgment

This work is supported by the Natural Sciences and Engineering Research Council (NSERC), Grant Number DG-480599.

References

[1] A. Y. Abdelaziz, F. Mohamed, S. Mekhamer, and M. Badr, “Distribution system reconfiguration using a modified tabu search algorithm,” Electric Power Systems Research, vol. 80, no. 8, pp. 943–953, 2010.
[2] F. V. Gomes, S. Carneiro, J. L. R. Pereira, M. P. Vinagre, P. A. N. Garcia, and L. R. De Araujo, “A new distribution system reconfiguration approach using optimum power flow and sensitivity analysis for loss reduction,” IEEE Transactions on Power Systems, vol. 21, no. 4, pp. 1616–1623, 2006.
[3] T. E. McDermott, I. Drezga, and R. P. Broadwater, “A heuristic nonlinear constructive method for distribution system reconfiguration,” IEEE Transactions on Power Systems, vol. 14, no. 2, pp. 478–483, 1999.
[4] N. Voros, A. Rosti, and M. Hübner, Dynamic System Reconfiguration in Heterogeneous Platforms: The MORPHEUS Approach. Springer Science & Business Media, 2009, vol. 40.
[5] C. van Leeuwen, Y. Rieter-Barrell, Z. Papp, A. Pruteanu, and T. Vogel, “Model-based engineering of runtime reconfigurable networked embedded systems,” in Runtime Reconfiguration in Networked Embedded Systems. Springer, 2016, pp. 1–28.
[6] M. Momayyezan, D. B. W. Abeywardana, B. Hredzak, and V. G. Agelidis, “Integrated reconfigurable configuration for battery/ultracapacitor hybrid energy storage systems,” IEEE Transactions on Energy Conversion, vol. 31, no. 4, pp. 1583–1590, 2016.
[7] C. Wang, X. Yang, Z. Wu, Y. Che, L. Guo, S. Zhang, and Y. Liu, “A highly integrated and reconfigurable microgrid testbed with hybrid distributed energy sources,” IEEE Transactions on Smart Grid, vol. 7, no. 1, pp. 451–459, 2016.
[8] D. Sanderson, J. C. Chaplin, L. De Silva, P. Holmes, and S. Ratchev, “Smart manufacturing and reconfigurable technologies: Towards an integrated environment for evolvable assembly systems,” in Foundations and Applications of Self* Systems, IEEE International Workshops on. IEEE, 2016, pp. 263–264.
[9] M. Khalgui, O. Mosbahi, Z. Li, and H.-M. Hanisch, “Reconfiguration of distributed embedded-control systems,” IEEE/ASME Transactions on Mechatronics, vol. 16, no. 4, pp. 684–694, 2011.
[10] L. O. Matos and J. W. G. Sanchez, “Reconfiguration strategy for fault tolerance of power distribution systems using Petri net,” in Ecuador Technical Chapters Meeting (ETCM), IEEE, vol. 1. IEEE, 2016, pp. 1–6.
[11] J. Zhang, M. Khalgui, Z. Li, G. Frey, O. Mosbahi, and H. B. Salah, “Reconfigurable coordination of distributed discrete event control systems,” IEEE Transactions on Control Systems Technology, vol. 23, no. 1, pp. 323–330, 2015.
[12] Y. Brave and M. Heymann, “Stabilization of discrete-event processes,” International Journal of Control, vol. 51, no. 5, pp. 1101–1117, 1990.
[13] A. Nooruldeen and K. W. Schmidt, “State attraction under language specification for the reconfiguration of discrete event systems,” IEEE Transactions on Automatic Control, vol. 60, no. 6, pp. 1630–1634, 2015.
[14] W. M. Wonham, “Supervisory Control of Discrete-Event Systems,” Sys. Control Group, ECE Dept., Univ. of Toronto, Toronto, ON, Canada, 2017 [Online] Available: http://www.control.toronto.edu/DES/.
[15] X. Wang, Z. Li, and W. Wonham, “Dynamic multiple-period reconfiguration of real-time scheduling based on timed DES supervisory control,” IEEE Transactions on Industrial Informatics, vol. 12, no. 1, pp. 101–111, 2016.
[16] R. Sampath, H. Darabi, U. Buy, and J. Liu, “Control reconfiguration of discrete event systems with dynamic control specifications,” IEEE Transactions on Automation Science and Engineering, vol. 5, no. 1, pp. 84–100, 2008.
[17] P. J. Ramadge and W. M. Wonham, “Supervisory control of a class of discrete event processes,” SIAM journal on control and optimization, vol. 25, no. 1, pp. 206–230, 1987.
[18] W. M. Wonham, “Supervisory control of discrete-event systems,” Encyclopedia of Systems and Control, pp. 1396–1404, 2015.
[19] ——, “Design Software: TCT,” Sys. Control Group, ECE Dept., Univ. of Toronto, Toronto, ON, Canada, 2017 [Online] Available: http://www.control.toronto.edu/DES/.