Necessity

The following theorem shows the necessity of the anytime capacity for the purpose of stabilizing the linear physical dynamics in a CPS.

The rigorous proof of the theorem is given in Ref. [13]. Here, we provide a sketch of the proof. The key point is the simulated plant as shown in Fig. 5.22. Due to the perfect feedback channel, the sensor can simulate the plant observer and controller. The idea is to link communication reliability with control stability.

Below is the basic setup of the proof:

• We can consider the system illustrated in Fig. 5.22 as a special communication system. The information source is a sequence of i.i.d. bits {s_i(t)}_i, t at the sensor. The bit sequence will be regenerated at the controller.

• The bit sequence {s_i(t)}_i, t is encoded as follows. The sensor uses the bit sequence to generate time-independent random perturbations {w(t)}, which correspond to the random perturbations in real physical dynamics. Hence the sensor can generate a simulated plant with simulated random perturbation and simulate control actions. The system state in a simulated plant x consists of two parts $\stackrel{-}{x}$, which is driven by the generated random perturbation w, and $\tilde{x}$, which is driven by the control action.

• We assume that the simulated physical dynamics can be stabilized by the control action. As we will see, the simulated dynamics x(t), as the sum of the simulated sources $\stackrel{-}{x}(t)$ and $\tilde{x}(t)$, can be reconstructed at the controller with an error of a particular magnitude. The simulated dynamics $\tilde{x}(t)$ in Fig. 5.22 can also be simulated at the controller due to the shared initial state and the control actions at both the sensor and the controller. Then we can use the bit sequence s(t) to convey information about $\stackrel{-}{x}$. Since x is small due to the stabilization, $\stackrel{-}{x}$ can be approximated by $\tilde{x}$. Thus $\stackrel{-}{x}$ can be reconstructed by the controller with small error (since $\tilde{x}$ can be generated by the controller), and the bit sequence s(t) can be decoded with a particular error rate, which can be controlled by the system stability characterized by η.

• Essentially, this communication system conveys information via the simulated physical dynamics, thus linking the communication capacity and system stability.

The details are given below. The simulated system state $\tilde{x}(t)$ has the following dynamics:

$\begin{array}{l}\tilde{x}(t+1)=A\tilde{x}(t)+u(t),\hfill \end{array}$

where u(t) can be perfectly simulated by the sensor since it knows the output of the communication channel. In the other simulated dynamics, the system state is driven by the simulated noise, namely

$\begin{array}{l}\stackrel{-}{x}(t+1)=A\stackrel{-}{x}(t)+w(t).\hfill \end{array}$

Then the sum of $\stackrel{-}{x}$ and $\tilde{x}$ is a simulated version of the true dynamics, since

$\begin{array}{ll}x(t+1)\hfill & =\stackrel{-}{x}(t+1)+\tilde{x}(t+1)\hfill \\ \hfill & =A\stackrel{-}{x}(t)+A\tilde{x}(t)+u(t)+w(t)\hfill \\ \hfill & =Ax(t)+u(t)+w(t).\hfill \end{array}$

Since the original physical dynamics can be stabilized and |x(t)| will be sufficiently small, then $\tilde{x}(t)$ will be sufficiently close to $-\stackrel{-}{x}(t)$.

In Fig. 5.22, we assume that the observer transmits bit i at time $\frac{i}{R}$ where R is the data rate. It is easy to verify that

$\begin{array}{ll}\stackrel{-}{x}(t+1)\hfill & =\sum _{i=0}^t{A}^{i}w(t-1-i)\hfill \\ \hfill & =A^t\sum _{j=0}^t{A}^{-j}w(j).\hfill \end{array}$

The sum ${\sum }_{j=0}^t{A}^{-j}w(j)$ is similar to the representation of a factional number with base A. Then, using induction, we can prove that $\stackrel{-}{x}$ can be written as

$\begin{array}{l}\stackrel{-}{x}(t)=\gamma A^t\sum _{k=0}^{\lfloor Rt\rfloor }{(2+{ϵ}_1)}^{-k}{S}_k,\hfill \end{array}$

where S_k is the kth bit, and γ and ϵ₁ are constants whose expressions can be found in Ref. [13]. This can be achieved by representing the tth random perturbation w(t) as

$\begin{array}{l}w(t)=\gamma A^{t+1}\sum _{k=\lfloor Rt\rfloor +1}^{\lfloor R(t+1)\rfloor }{(2+{ϵ}_1)}^{-k}{S}_k.\hfill \end{array}$

Assuming that the rate R is smaller than ${log}_{2}A$, it was shown in Ref. [13] that bits can be encoded into the simulated plant. At the output of the communication channel, estimates ${\stackrel{-}{s}}_i(t)$ can be extracted from the ith bit such that

$\begin{array}{l}P({ŝ}_{1:j}(t)\ne s_{1:j}(t))\le P\left(|x(t)|\ge A^{t-\frac{j}{R}}\left(\frac{\gamma {ϵ}_1}{1+{ϵ}_1}\right)\right).\hfill \end{array}$

Here the key idea is that, since we have assumed that the physical dynamics are stabilized and thus x(t) is very small, $\stackrel{-}{x}(t)$ is very close to $\tilde{x}(t)$ and thus can be estimated from $\tilde{x}(t)$ known at the controller (since the initial state and control actions are shared by both the controller and sensor).

Due to the assumption that the system is η-stable, we have

$\begin{array}{ll}P(|x(t)|>m)\hfill & \le \frac{E[|x(t)|\eta ]}{m^{\eta }}\hfill \\ \hfill & \le K{m}^{-\eta },\hfill \end{array}$

where the first inequality is due to the Markov inequality, which measures the probability of deviation from the expectation, and the second one is due to the assumption of η-stability.

Substituting Eq. (5.123) into Eq. (5.122), we have

$\begin{array}{l}P({ŝ}_{1:j}(t)\ne s_{1:j}(t))\le \left(K\left(\frac{1}{\gamma }+\frac{1}{\gamma {ϵ}_1}\right)\right)2^{-\eta {log}_{2}A\left(t-\frac{i}{R}\right)}.\hfill \end{array}$

Notice that $\frac{i}{R}$ is the time that the ith bit is sent and thus $t-\frac{i}{R}$ is the (continuous-time) delay of decoding. This concludes the proof by checking the definition of anytime capacity.

Sufficiency

We first extend the anytime capacity to a broader meaning:

Similarly to C_any in the previous discussion, we can define C_g-any. Note that the definition of anytime capacity in Definition 14 is simply a special case of the g-anytime capacity, if the function g is exponential; i.e.,

$\begin{array}{l}g(d)=K{2}^{-\alpha d}.\hfill \end{array}$

Now we discuss the following sufficient condition for the stability of physical dynamics:

Encoding procedure

Due to the assumption of perfect feedback of communication channels, the sensor can perfectly know the control action taken by the controller, namely u(t). On the other hand, the sensor also perfectly knows the system state x(t). Hence it also has perfect estimation of the random perturbation by using

$\begin{array}{l}w(t)=x(t+1)-Ax(t)-u(t).\hfill \end{array}$

Hence one natural idea is to encode w(t) and send it to the controller, since w is the only randomness in the system. However, Ref. [13] proposed a more effective approach in which “the observer will act as though it is working with a virtual controller through a noiseless channel of finite rate R…” The detailed encoding procedure is given as follows.

The sensor simulates a virtual process $\stackrel{-}{x}(t)$ whose dynamics are given by

$\begin{array}{l}\stackrel{-}{x}(t+1)=A\stackrel{-}{x}(t)+w(t)+ū(t),\hfill \end{array}$

where $ū(t)$ is the computed action of a virtual controller simulated at the sensor. It also keeps updating the following two virtual dynamics:

$\begin{array}{l}{x}_u(t+1)=A{x}_u(t)+ū(t)\hfill \end{array}$

and

$\begin{array}{l}\tilde{x}(t)=A\tilde{x}(t)+w(t),\hfill \end{array}$

which results in $\stackrel{-}{x}(t)=x_u(t)+\tilde{x}(t)$. Since the sensor can stabilize the simulated dynamics $\stackrel{-}{x}(t)$ within an interval, − x_u(t) should be very close to $\tilde{x}(t)$. Hence the actual controller will try to take actions close to x_u(t). This can be accomplished by the sensor sending an approximation of the computed control action $ū$ to the actual controller, which is illustrated in Fig. 5.23.

In summary, the whole system works as follows. Since the sensor knows all the information of the physical dynamics, it simulates the stabilization of the dynamics by using computed control actions; the sensor sends its computed control actions to the controller after quantization; the controller estimates all the previous control actions with an exponentially decreasing error rate (guaranteed by the anytime capacity); then the controller estimates the current system state of the simulated dynamics at the sensor and takes control actions to force the true system state to be close to the simulated one. Note that, although the sensors sends its computed control actions to the controller, it does not directly inform the controller about the control action that the controller should take; it simply informs the controller where the simulated system state is and thus the controller can try to catch up with the simulated system state, which is destined to be stable (Fig. 5.24).

Due to the communication constraint R, the sensor can take one of 2^R values (where we assume that 2^R is an integer). If $\stackrel{-}{x}(t)$ is within the interval $\left[-\frac{\Delta }{2},\frac{\Delta }{2}\right]$, $A\stackrel{-}{x}(t)$ lies in $\left[-\frac{A\Delta }{2},\frac{A\Delta }{2}\right]$. The sensor can choose one of the possible control actions uniformly aligned in the interval $\left[-\frac{A\Delta }{2},\frac{A\Delta }{2}\right]$, which is within the distance $\frac{A\Delta }{2^{R+1}}$ of $A\stackrel{-}{x}(t)$, such that

$\begin{array}{l}A\stackrel{-}{x}(t)+ū(t)\in \left[-\frac{A\Delta }{2^{R+1}},\frac{A\Delta }{2^{R+1}}\right].\hfill \end{array}$

After the perturbation by the random noise, we have

$\begin{array}{l}\stackrel{-}{x}(t+1)\in \left[-\frac{A\Delta }{2^{R+1}}-\frac{\Omega }{2},\frac{A\Delta }{2^{R+1}}+\frac{\Omega }{2}\right].\hfill \end{array}$

To make $\stackrel{-}{x}(t)$ always within $\left[-\frac{\Delta }{2},\frac{\Delta }{2}\right]$, we require

$\begin{array}{l}\frac{A\Delta }{2^{R+1}}\le \frac{\Delta }{2},\hfill \end{array}$

which can be achieved if

$\begin{array}{l}\Delta =\frac{\Omega }{1-A{2}^{-R}},\hfill \end{array}$

when $R>{log}_{2}A$.

Then the sensor can simply send out R bits to indicate the virtual control it takes to limit the virtual state $\stackrel{-}{x}(t)$ within $\left[-\frac{\Delta }{2},\frac{\Delta }{2}\right]$. Upon receiving the bits from the sensor, the controller chooses a control to make the true system state x(t) as close to the virtually simulated state $\stackrel{-}{x}$ as possible.

The strategy of the control action computed at the controller is illustrated in Fig. 5.25. The controller obtains the estimate of the system state using

$\begin{array}{l}{\widehat{\mathbf{x}}}_{t+1}(t)=\sum _{i=0}^t{A}^i{û}_{t-i}(t),\hfill \end{array}$

where $û+t-i(t)$ is the estimation of the computed control action at time t − i (i.e., $ū(t-i)$) given all the received channel outputs before time t + 1.

Then the controller chooses the control action u(t) such that $\tilde{x}(t+1)$ equals $\widehat{x}(t)$; i.e.,

$\begin{array}{l}u(t)={\widehat{x}}_{t+1}(t)-A\tilde{x}(t).\hfill \end{array}$

Given the above strategies of coding, decoding, and control action, the stability of the dynamics is rigorously proved in Ref. [13].

Law of requisite variety

The relationship between communications and control was originally considered by Wiener [78]. Then Ashby [77] proposed the Law of Requisite Variety in his celebrated book. Here the term “variety” means the number of states of the corresponding system, which is actually closely related to the concept of entropy (if the system state is uniformly distributed, then entropy is equal to log(variety)). Based on the concept of variety, Ashby proposed the follow law of requisite variety:

Without a rigorous mathematical formulation and proof, Ashby claimed “only variety in the regulator can force down the variety due to the disturbances; only variety can destroy variety.” This is illustrated by the example in Fig. 5.27. We consider two players, R (regulator) and D (disturbance). The varieties of their actions are denoted by V_R and V_D, respectively. We assume that player D takes action first and then R follows. This is similar to practical control systems: the system state is first randomly perturbed and then controlled by the controller. In Fig. 5.27A, each player has three possible actions (α, β and γ for R, and 1, 2, 3 for D). The outcomes of different action pairs are given in the table. The goal of the game is: if the outcome is a, R wins; otherwise, R loses. It is obvious that, regardless of the action taken by player D, player R can always choose its action adaptively and achieve the goal a. In this case, we claim that player R can control the game. However, in Fig. 5.27B, player D has more options than player R, thus making R unable to control the game.

We now consider a more generic case. If two elements in the same row are identical, then player R need not distinguish the corresponding actions of player D, which is too favorable to R. Hence we assume that no two elements in the same row are identical. Then it is easy to prove that the variety of the outcome (denoted by V_O), given the strategy of R, cannot be less than V_D/V_R.

Then if we use a logarithmic scale to measure the variety, the above conclusion can be translated into the following inequality:

$\begin{array}{l}log(V_O)\ge log(V_D)-log(V_R).\hfill \\ \hfill \end{array}$

If the distributions of O, R, and D are all uniform, then we have

$\begin{array}{l}H(O)\ge H(D)-H(R).\hfill \\ \hfill \end{array}$

This inequality implies that a larger H(R) (i.e., having more states of the controller) helps to better reduce the entropy of the output; otherwise, if H(R) is small, the output may have a larger uncertainty than the disturbance. Although communication is not explicitly mentioned in the argument, we can consider the communication network as part of the controller. If the communication capacity is too small, then the controller cannot have much variety (since it does not have many options due to the limited number of reliable messages sent from the sensor), thus causing large entropy (or uncertainty) at the system output. Note that these arguments are merely qualitative. More rigorous analysis will be provided subsequently.

Shannon entropy in discrete-value dynamics

Based on the qualitative argument in the law of requisite variety, we provide a detailed analysis of the entropy change in discrete physical dynamics by following the argument of Conant [79]. Consider a controller R (called a regulator in Ref. [79]) regulating a variable Z (which can be considered as the system state) subject to random perturbation S. R and S jointly determine the output Z. It is assumed that R, S, and Z have finite alphabets and the system evolves in discrete time, given by

$\begin{array}{l}Z(t)=\varphi (S(t),R(t)),\hfill \\ \hfill \end{array}$

where ϕ is the evolution law.

We further assume that S is independent of R. Notice that the system dynamics is memoryless. Two types of control strategies are considered, as illustrated in Fig. 5.28:

• Point regulation: The goal is to minimize the changes of output Z (i.e., to make the regulated variable Z as constant as possible).

• Path regulation: The goal is to minimize the unpredictability of the outcomes. Hence the outcome Z could change; however, the change should be as predictable as possible.

We analyze the point regulation first. Since the regulator wants to minimize the change (or the uncertainty) of Z, it targets minimizing the entropy of Z. When R is active, the action selected by R is a function of Z (i.e., closed-loop control). The corresponding entropy of Z is denoted by H_c(Z), where the subscript c means closed loop. When R is idle and uses a fixed action i (i.e., open-loop control), the corresponding entropy of Z is denoted by $H_o^i(Z)$, where the subscript o means open loop. The minimum entropy subject to the open-loop control is given by

$\begin{array}{l}{H}_o^{*}(Z)=\underset{i}{min}{H}_o^i(Z).\hfill \end{array}$

Then we obtain the following theorem on the difference between $H_o^{*}(Z)$ and H_c(Z), i.e., the entropy reduced by the controller R when compared with the optimal open-loop control.

From the definition of K, we have the following corollary:

We then consider path regulation, in which we have a series of perturbations S(1 : T), control actions R(1 : T), and outputs Z(1 : T). The argument is similar. Again, we consider the open-loop and closed-loop cases. When the controller R is active (i.e., closed-loop control), we add a subscript c to the quantities; when open-loop control is used, we use the subscript o.

Using the same argument as in the point regulation, we can prove a similar conclusion:

$\begin{array}{l}{H}_o(Z(1:T))-H_c(Z(1:T))\le I(R(1:T);S(1:T))+KT,\hfill \end{array}$

which also implies

$\begin{array}{l}{h}_o(Z)-h_c(Z)\le i(R;S)+K,\hfill \end{array}$

where h is the entropy rate, defined as $h(X)={lim}_{T\to \infty }\frac{1}{T}H(X(1:T))$, and the average mutual information i is similarly defined.

Shannon entropy in continuous-value dynamics

In the previous discussion, we considered discrete systems with very simple architectures (in particular, they are memoryless). We now provide a detailed analysis of the entropy change in continuous physical dynamics having more detailed and practical structures by following the argument in Ref. [80].

First we consider the entropy in the procedure of system state estimation, since in many situations (such as the optimal control of linear systems), the controller estimates the system state first and then computes the corresponding control action. The estimation procedure is illustrated in Fig. 5.29, where n is the random perturbation, x is the system state, and e is the estimation error. The sensor observes the random perturbation directly and the filter provides an estimation about x. We assume

$\begin{array}{l}\left\{\begin{array}{c}\mathbf{x}=\mathbf{D}\mathbf{n},\\ \mathbf{v}=\mathbf{F}(\mathbf{z}),\\ \mathbf{e}=\mathbf{x}-\mathbf{v}.\end{array}\right.\hfill \end{array}$

The entropy relationships in the estimation problem are disclosed in the following theorem:

We then consider the entropy change in the disturbance rejection feedback control, whose architecture is illustrated in Fig. 5.30. Here, n(t) is the random perturbation and x(t) is the system state. The feedback consists of a linear prefilter B, a measurement error w, and a post filter C. The output of the sensor is given by

$\begin{array}{l}\mathbf{z}=\mathbf{C}(\mathbf{B}\mathbf{x}+\mathbf{w}).\hfill \end{array}$

Then the feedback signal is given by

$\begin{array}{l}\mathbf{v}(t)=F(\mathbf{z}(t),t),\hfill \end{array}$

where F is a generic function which can be nonlinear and time varying.

The input of the plant is the error between the perturbation n and the estimation v; i.e.,

$\begin{array}{l}\mathbf{e}(t)=\mathbf{n}(t)-\mathbf{v}(t).\hfill \end{array}$

The linear output of the plant x is then given by

$\begin{array}{l}\mathbf{x}(t)=\mathbf{D}\mathbf{e}(t),\hfill \end{array}$

where D is a fixed matrix.

Our goal is to compare the entropy of the system state in closed-loop and open-loop control systems. In open-loop control, where we set F = 0, we denote the output by x_o(t), given by x_o(t) = Dn(t). The following theorem shows the relationship between h(x) and h(x_o):

Immediate conclusions can be drawn in the following corollary:

Controller design based on entropy

Since entropy measures the uncertainty of system dynamics, it can be used as the criterion of controller synthesis. Here, we briefly introduce the formulation of the entropy-based control system [82]. We assume that y(t) ∈ [a, b] is the output of a stochastic system at time slot t. The control action is denoted by u(t). The distribution of y and u is denoted by γ. The B-spline expansion of the distribution is given in [83]

$\begin{array}{l}\gamma (\mathbf{y},\mathbf{u})=\sum _{i=1}^n{w}_i(\mathbf{u})B_i(\mathbf{y}),\hfill \end{array}$

where B_i is the ith basis function and w_i is the expansion coefficient. The cost function is defined as

$\begin{array}{l}J(\mathbf{u})=-{\int }_a^b\gamma (\mathbf{y},\mathbf{u})log\gamma (\mathbf{y},\mathbf{u})d\mathbf{y}+R\parallel \mathbf{u}{\parallel }^2,\hfill \end{array}$

which is a combination of the output entropy and the cost of action. The optimal control action can then be obtained by taking the derivative of J with respect to u. The details can be found in Ref. [82].

Criticisms on entropy-based control

Although entropy provides a good measure of the uncertainty of dynamics and low entropy is a necessary condition for a good operation status of a system, there have been criticisms of entropy-based control [84]:

• Entropy-based control approaches do not solve the problems that traditional control theory cannot solve. Moreover, entropy is only valid for stochastic systems and cannot handle deterministic systems.

• The criterion of entropy minimization is questionable. Entropy is dependent on the relative shape of the distribution and is independent of the relative locations. For example, the two distributions illustrated in Fig. 5.31 have the same distribution since they have the same shape. However, the one on the left is centered around the desired operation status while the other is not. Hence it should be desirable to achieve the distribution on the left; however, entropy-based control cannot distinguish between the two distributions and may provide the undesired one. A remedy is to add a constraint on the expectation of the distribution when minimizing the entropy.

• The entropy of the output in the sense of an alphabet without the definition of distances may not represent the variance of the output in its numerical meaning. This can be well illustrated in the following example [84]. Suppose that the controller and perturbation each have three possible actions (denoted by (q, r, p) and (a, b, c), respectively). The outcomes of the system are given in the following matrix, where the columns and rows represent the actions of controller and perturbation:

$\begin{array}{l}\left(\begin{array}{ccc}1& 9& 4\\ 5& 2& 8\\ 7& 6& 3\end{array}\right)\hfill \end{array}$

Consider two strategies of the controller: (A) fix the action p; (B) adaptive control action: $a\to q$, $b\to r$, and $c\to p$. It is easy to check that the first strategy gives the outputs {1, 4, 9} while the second strategy results in {4, 5, 6}. If we interpret the outputs as abstract alphabets, the outputs of the two strategies have the same entropy. However, if the outputs are explained as numbers, obviously the second strategy results in much less numerical variance.

Analytical results of entropy reduction

To further validate the entropy approach, we provide analytic results on the entropy reduction in control systems. We consider the following standard linear dynamics:

$\begin{array}{l}\left\{\begin{array}{c}\mathbf{x}(t+1)=\mathbf{A}\mathbf{x}(t)+\mathbf{B}\mathbf{u}(t)+\mathbf{w}(t),\hfill \\ \mathbf{y}(t)=\mathbf{C}\mathbf{x}(t)+\mathbf{n}(t),\hfill \end{array}\right.\hfill \end{array}$

where x is the system state with dimension N, u is the control action, y is the observation, and w and n are the noise in the dynamics and observation, respectively. We assume that the noises w(t) and n(t) are both Gaussian with covariance matrices Σ_w and Σ_n.

For the LQG control, the following theorem shows the exact evolution of the covariance matrix:

Based on the evolution law of the covariance matrix in LQG control, we obtain the following sufficient condition of the temporal reduction of entropy:

System model

We consider finite state physical dynamics with discrete timing structure. The N states of the physical dynamics are denoted by x₁, …, x_N. In each time slot, the CPS proceeds in the following three stages, as illustrated in Fig. 5.36:

• Entropy increase stage: At the beginning of the time slot (e.g., the tth time slot), the state of the CPS is denoted by X(t − 1) with distribution p_t−1, and the corresponding entropy is denoted by H(t − 1). The state is perturbed by random perturbations and is changed to X₀(t) with conditional probability Q_mn = P(X₀ = n|X = m) and entropy H₀(t)(> H(t − 1)). Here the impact of random perturbation is represented by the transition probability Q.

• Observation stage: An external sensor makes an observation on the system state and sends a message M(t) to the controller. We assume that the observation is noiseless. The coding scheme and the communication channel are not specified. For notational simplicity, we define P(x_i|m_j) = P(X(t) = x_i|M(t) = m_j) and P₀(x_i|m_j) = P(X₀(t) = x_i|M(t) = m_j). We denote by R the number of possible messages.

• Entropy decrease stage: A control action A(t) is computed by the controller and then actuated. The system state is then changed to X(t) with distribution p_t and entropy H(t). Then the physical dynamics proceeds to the next time slot.

For simplicity, we assume that the sensor is an external device and thus do not consider the entropy at the sensor itself. We do not consider the cost of computing.

We assume that there are D possible control actions that can be taken by the controller, denoted by a₁, …, a_D. Each control action maps X₀(t) to X(t). W assume that the controlled dynamics is deterministic; i.e., given the action A and the state X₀ after the entropy increase stage, the system state X is uniquely determined. We denote the mapping, indexed by the control action, by f_i if A = a_i; i.e., X(t) = f_i(X₀(t)). The mapping from the received messages at the controller to the action is called the control strategy.

To simplify the analysis, for the physical dynamics and control action, we have the following assumptions:

• Each control action provides an injective mapping for the system states.

• For any state pairs i and j, there exists a unique control action that maps i to j.

Note that, for the first assumption, it is easy to prove that a many-to-one mapping can help to decrease the entropy. Hence the assumption implies that we are dealing with the most difficult situation; i.e., open-loop control cannot decrease the entropy. The second assumption also simplifies the analysis, although it is still not clear whether it is easy to extend to a more generic case.

Note that all these assumptions are reasonable in practical cases. Take linear dynamics with continuous-valued state x(t) and dynamics x(t + 1) = Ax(t) + Bu(t), for instance. If B is a square matrix and invertible (hence dim(u) = dim(x)), then the mapping between x(t + 1) and u(t) is one-to-one, given the current system state x(t). Meanwhile, if A is invertible, the mapping between x(t + 1) and x(t) is also one-to-one, given u(t). Note that here the system state is continuously valued, which is different from the assumption in this subsection that the system state is discrete; however, if we partition the state space with sufficient precision, the two assumptions hold approximately.

For the communication and control strategies, we have the following assumptions for the control strategy:

• The message M is determined by the current observation; i.e., M(t) = h(X₀(t)), where h is the mapping mechanism.

• The action is dependent on the current received message, thus making the control Markovian. A non-Markovian strategy, which may improve the performance, will be studied in the future.

• The strategy is deterministic and one-to-one. This is reasonable since a randomized strategy may increase the output entropy. We denote by g the mapping from M to A; i.e., A = g(M).

Entropy reduction in one time slot

We first analyze the entropy reduction within a single time slot. For notational simplicity, we omit the time indices in the notation, since the time slot is fixed. The following lemma is key to bridging the communication requirement and entropy reduction.

Remark 5

The conclusion in Lemma 4 is equivalent to

$\begin{array}{l}H(X_0)-H(X)=I(X_0;M)-I(X;M),\hfill \end{array}$

  (5.179)

where the left-hand side is the reduction of entropy of the system dynamics in this time slot, while the right-hand side is the difference between two mutual pieces of information. As illustrated in Fig. 5.37, the mutual information I(X₀;M), namely the information on the system dynamics after the entropy increase stage, obtained by the controller, cannot be fully used to reduce the entropy; some residual, I(X;M), will be unused, intuitively speaking. Interestingly, this is similar to the Carnot heat engine [86, 87], in which the energy from a high-temperature source cannot be fully used to generate work, unless the absolute temperature of the colder source is zero.

Based on the conclusion in Lemma 4, the following corollary can be obtained, which states that the information sent out by the sensor may not be fully used to reduce the entropy.

Based on Lemma 4, we obtain one of the main conclusions of this section in the following theorem, which provides upper and lower bounds for the entropy reduction in one cycle of the CPS. These bounds are independent of the controller design (or equivalently, valid for all possible controllers).

Both bounds in Theorem 18 are tight under certain conditions, which is stated in the following corollary:

Entropy change in the long term

Since we assume that the number of states is finite and the system evolution (including the control policy, communication mechanism, and entropy increase mechanism) is time invariant, the system will converge to a stationary distribution of system states. This implies that the entropy will converge to a deterministic value H*. It is an open problem to obtain an exact explicit expression for H*, although we can compute the stationary distribution numerically. A lower bound of H* is provided for a two-state system, when the communication channel is sufficiently good and the perturbation in the entropy increase stage is symmetric.