Stability of multiplexed NCS based on an epsilon-greedy algorithm for communication selection

Consider a closed-loop discrete-time linear system

for all $k\in\mathbb{Z}_{\geq 0}$, where ${x}_{k}\in\mathbb{R}^{n_{{x}}}$ is the state, $u_{k}\in\mathbb{R}^{n_{u}}$ is the control input and $y_{k}\in\mathbb{R}^{n_{y}}$ is the output at $k^{\text{th}}$ instant. We make the following assumptions regarding the original closed-loop system.

In this letter, we are interested in an application where the plant and the controller are remotely located. The communication between the plant and the controller occurs over a wireless communication network. The networked system is illustrated in Fig. 1. The networked system dynamics can be written as

where $\hat{u}_{k}$ denotes the networked version of the control signal. We proceed by emulation of the controller (2) and use the controller as

where $\hat{{x}}_{k}$ denotes the estimates of the state at the controller end. A more detailed explanation of these quantities is presented later in this section.

Motivated by real-world communication constraints in the form of bandwidth limitations, we consider a communication constraint as described below. At any time instant, the network scheduler has three choices:

1. i)

   transmit the control input from the controller to the plant or,

2. ii)

   transmit the measured signal from the plant to the predictor or,

3. iii)

   not communicate at all.

These three choices are encapsulated in the form of a switch variable $a_{k}$ that takes values in a discrete set $\mathcal{A}\coloneqq\{-1,0,1\}$ where,

We also consider lossy communication in the sense of a packet drop scenario. Consider $\gamma_{k}$ to denote the packet drop event, modeled as independent Bernoulli random variables with probabilities:

where $\gamma_{k}=1$ indicates a successful packet transmission and $\gamma_{k}=0$ indicates failure.

Based on the switching and the packet drop assumptions, the transmitted control information through the network is written as

The coarse estimate of the state at the controlled end is

Define the concatenated state as

with $\hat{{x}}_{-1}={x}_{0}$ and $\hat{u}_{k-1}=\bf{0}_{n_{u}}$ respectively. The overall model of the system is written as

with

and

We employ the $\varepsilon$-greedy switching strategy for the decision-making process [19]. The algorithm consists of two parts: exploration and exploitation. Exploration addresses finding new possible solutions, whereas exploitation addresses utilizing the already known optimal solution. The variable $\varepsilon$ acts as a parameter that weighs the two. Let the per-stage cost be defined by

The switching strategy is defined mathematically as follows:

where $r_{k}\sim\text{unif}[0,1]$ and $\beta\in]0,1[$ is a discount factor that discounts the cost at future time stages.

When $r_{k}$ is less than $\varepsilon$ the switching variable $a_{k}$ is chosen uniformly randomly from $\{-1,1\}$. This random selection represents exploration by allowing the system to consider other strategies that might not be optimal for that instance but could provide a better solution over a longer horizon. When $r_{k}\geq\varepsilon$, the switch variable $a_{k}$ is determined by the exploitation part, i.e., minimizing the expected cost function. Where the cost function has the following terms:

1. i)

   ${{x}_{k}^{\intercal}Q{x}_{k}}$, represents a penalty on the state, where ${x}_{k}$ is the state at time instant $k$, and $Q\succeq 0$.

2. ii)

   ${\hat{u}_{k}^{\intercal}R\hat{u}_{k}}$ represents the penalty on the control effort, where $u_{k}$ is the control at time instant $k$, and $R\succ 0$.

3. iii)

   ${\lambda a_{k}^{\intercal}a_{k}}$ introduces a penalty for transmission of a packet, with $\lambda$ being a weighing parameter that controls the trade-off between state and control cost versus the transmission cost.

Thus the $\varepsilon$-greedy strategy creates a balance between exploration and exploitation, ensuring that new strategies are explored while utilizing the accumulated information.

In this subsection, we discuss in detail the generalized switching probability under the $\varepsilon$- greedy algorithm and analyze the effect of the $\varepsilon$-greedy switching strategy on the MSS of the system. The switching probability distribution function $\mathcal{P}_{g}\in[0,1]^{3}$ is given by

with some switching algorithm $g$. Given the switching strategy defined in (15), the probabilities of switching states are influenced by the choice of $\varepsilon$. The choice of $\varepsilon$, in turn, decides the balance between exploration and exploitation. With the switching strategy (15) the switching probability distribution (denoted as $\mathcal{P}_{\varepsilon}$) can be written as

Here,

1. i)

   the first term, $\varepsilon\left(\frac{1}{2},0,\frac{1}{2}\right)$, represents the probability distribution in the exploration phase because of the uniform switching between $1$ and $-1$. With probability $\varepsilon$, the switch positions are chosen randomly, with an equal probability ($\frac{1}{2}$) of switching to $1$ or $-1$ and zero probability of remaining in position $0$, and

2. ii)

   the second term, $(1-\varepsilon)\left(p,1-p-q,q\right)$, represents the probability distribution in exploitation phase. With probability $1-\varepsilon$, the switching follows a policy based on the probabilities $p$ and $q$, where:

   • •

     $p$ is the probability of switching to position 1,

   • •

     $q$ is the probability of switching to position $-1$,

   • •

     $(1-p-q)$ is the probability of remaining in position $0$.

Here, $p,q\in[0,1]$ and $p+q\leq 1$ to ensure that all probabilities sum to 1.

In this section, we elaborate on the framework of the Markovian Jump Linear System (MJLS) that relates to the system described in (10). An MJLS is a linear system that goes through random transitions between a finite number of modes, each governed by linear dynamics. The random transitions are governed by Markovian probabilities associated with switching from one mode to another mode. In the problem, the randomness takes place at two levels: the first is at the switching under $\varepsilon$- greedy policy and the second is the random packet drop. With this backdrop, we introduce modes of operation under varying circumstances.

System Modes: The system can operate in one of several modes at any instance, which is determined by the switch position and the status of packet transmission. These modes represent different scenarios of switching and packet drop. We define the modes of the Markovian switching system as follows:

where,

• •

  the first entry in each tuple indicates the position of the switch, which can be 1,-1, or 0;

• •

  the second entry denotes whether the packet transmission was successful ($\mathcal{S}$) or failed ($\mathcal{F}$), and

• •

  the third entry corresponds to the system matrix $\mathsf{A}$ that governs the dynamics in that particular mode.

For example, $\mathcal{M}1$ represents the case where the switch is in position 1, the packet transmission is successful, and the system dynamics are described by the matrix $\mathsf{A}_{1}$. On the other hand, $\mathcal{M}2$ represents the case where the switch is in position 1 but the packet transmission has failed, thus the system dynamics revert to $\mathsf{A}_{0}$.

The mode transition probability, $p_{ij}$, represents the likelihood of the system switching from mode $i$ to mode $j$ in the next time step.

Objective: Our goal is to determine the value for $\varepsilon$, given a $\delta\in]0,1]$, that ensures the origin of the system (10) remains Mean Square Stable under the switching algorithm (15).

We study this through specific corner cases:

1. C1.

   $p=0$ and $q=1$: This case represents the switch being in position $-1$ throughout the entire exploitation phase, indicating that only observations are transmitted.

2. C2.

   $p=1$ and $q=0$: This case represents the switch being in position $1$ throughout the entire exploitation phase, indicating that only control signals are transmitted.

3. C3.

   $p=0$ and $q=0$: This case depicts the switch remaining in position $0$ for the duration of the exploitation phase, signifying that no transmissions occur.

The probability of switching in each of the corner cases is tabulated in TABLE 1.

Let $\mathsf{P}^{(c)}\in[0,1]^{M\times M}$ denote the mode transition probability matrix associated with the corner case $c$, where $c\in\{1,2,3\}$. Here, the superscript $c$ is the variable representing each corner case. Each $\mathsf{P}^{(c)}_{j}\in[0,1]$ denotes the probability of transitioning from each node to the mode $\mathcal{M}j$ in the corner case $c$, i.e., $\mathsf{P}^{(c)}_{ij}=\mathsf{P}^{(c)}_{j}$ for all $i,j\in\{1,2,\ldots,5\}$. The mode transition probabilities, for each case, are described in Table 2 and depicted in Fig. 2. With the given packet transmission success probability $\delta\in]0,1]$, we provide the necessary conditions for the MSS of the system using the LMIs given in [20].

To determine the value of $\varepsilon$ that satisfies the LMIs required for MSS, we utilize a method involving Semi-Definite Programming (SDP) solvers and the bisection method. Based on Theorem 1, we set up the necessary LMIs involving symmetric positive definite matrix $V$. These LMIs establish the conditions for MSS that the system must satisfy. We employ an SDP solver to numerically solve the formulated LMIs. Given the dependence of $V$ matrix on $\varepsilon$, we apply the bisection method to determine the value of $\varepsilon\,(\bar{\varepsilon})$ that satisfies all LMIs. Starting with an initial range for $\varepsilon\in[0,1]$, the bisection method iteratively narrows down to $\bar{\varepsilon}$ by checking the existence of solutions of LMIs at midpoints within the range.

The sequential decision-making problem is treated as a Markov Decision Process (MDP). The MDP has three components: i) state, ii) action, and iii) reward. The state space consists of $\{{x}_{k}\}\in\mathbb{R}^{n_{{x}}}$ and the action space is $a_{k}\in\{-1,0,1\}$. Define per-stage reward as

The system transitions from state ${x}_{k}$ to ${x}_{k+1}$ based on action $a_{k}$ and receives reward $r_{k+1}$. To evaluate the performance of a given policy, we use the action value function, denoted as $\mathsf{Q}_{\pi}({x},a)$. For a policy $\pi$, which maps states to probabilities of selecting actions, the action value function is defined as:

The optimal $\mathsf{Q}$ value (denoted as $\mathsf{Q}_{*}({x}_{k},a_{k})$) satisfies Bellman’s principle of optimality:

The optimal policy can be found iteratively in the case of discrete sets of states and actions by the value iteration method [19]. In this problem, the state space is continuous, and this method cannot be directly applied. Hence, we use an advanced deep reinforcement learning technique using a neural network.

We approach the solution of the problem (23) using deep reinforcement learning [22]. A Deep Q Network (DQN) estimates the $\mathsf{Q}$-values for each state and action. Thereby approximates the function $\mathsf{Q}({x},a;\theta)$, where the function is parameterized by $\theta$. The state acts as the input to the DQN, and the output corresponding to each action is the approximated $\mathsf{Q}$-value. The loss is derived using Bellman’s principle as

Here, two forward passes are made through the network to get the $\mathsf{Q}$-values for the current and next states. To avoid this, Mnih et al. introduced the replay memory framework and another target network replicating the actual network but updated only after a few iterations [22]. Algorithm 1 presents the deep reinforcement learning technique used.