In the previous section, we studied the communication requirements for controllers with separated state estimation and control. However, there are two limitations to this setup:
• For generic cases, it is not clear whether separated state estimation and control are optimal.
• For the communication channel, we used the channel capacity to measure the capability of conveying information. However, the concept of channel capacity is reasonable for communications with long delays, not for the case of CPSs with very limited delays.
• The possible transmission errors, due to the noisy channel, are not considered.
Hence in this section, we will study a novel metric for the communication channel in the context of stabilizing stochastic linear physical dynamics, namely the anytime capacity, which was proposed by Sahai and Mitter in 2006 [13].
For simplicity, we consider a scalar system state in a discrete time framework, whose evolution law is given by
where x is the system state, u is the control action, and w is time-independent random perturbation with bounded amplitude (i.e., |w(t)| < Ω/2), E[w] = 0, and . We assume that A > 1; otherwise, there is no need for communications since the system is inherently stable.
The overall system under study is illustrated in Fig. 5.18. A sensor observes the system state of the physical dynamics and then sends messages through a noisy communication channel. There could be a feedback channel for the forward communication channel, through which the sensor knows the output of the communication channel. It is also possible for the sensor to know the control action taken by the controller, if the communication channel output is fed back to the sensor and the sensor shares the strategy of the controller.
The following two concepts of system stability will be used in the subsequent analysis:
The η-stability is looser than the f-stability, since the f-stability places a direct constraint on large values of the system state.
For simplicity, we assume that the noisy communication channel is memoryless and discrete-time. It is characterized by the conditional probability P(r|s), where s (send) and r (receive) are the input and output symbols.
For a communication channel, the traditional channel capacity is given by
which is optimized over the possible input symbol probability P(S). As explained in chapter 2, the channel capacity measures the capability of conveying information with asymptotically long codeword lengths and arbitrarily small error rates. However, in the context of controlling physical dynamics, the infinite delay of codewords in the traditional setup of information is intolerable, thus making the traditional concept of channel capacity inadequate.
Below is an example proposed in Ref. [13] showing the inadequacy of the traditional concept of channel capacity. Consider the binary erasure channel illustrated in Fig. 5.19. The probability that the transmitted symbol, 0 or 1, is correctly received is 1 − δ, while the probability of the symbol being erased (thus receiving a common symbol e) is given by δ. Similarly, we can have an L-bit erasure channel, in which the alphabets of inputs and outputs are both {0, 1}L (hence the input and output are L-dimensional binary vectors, or L-bit packets). The correct transmission probability is p(s|s) = δ, while the erasure probability p(e|s) is δ. It has been shown that the channel capacity of an L-bit erasure channel is given by (1 − δ)L. Furthermore, we can have a real erasure channel, in which the input and output alphabets are real numbers R, and the conditional probabilities are p(x|x) = 1 − δ and p(0|x) = δ.
For a counterexample of traditional channel capacity, we consider the system in Eq. (5.107) with A = 1.5 and Ω = 1 (hence the perturbation satisfies |w(t)|≤ 0.5). We assume that the communication channel is the real erasure case with δ = 0.5. Hence with probability 0.5, the system state x(t) can be perfectly transmitted to the controller, while the transmission is blocked with probability 0.5. The optimal control strategy is to transmit the system state measured by the sensor directly, thus s(t) = x(t); the control action is u(t) = −Ar(t). Hence when the transmitted symbol is successfully passed through the communication channel, the previous system state can be completely canceled by the control action and only the random perturbation remains. However, if the transmitted symbol is erased, no control action is carried out (since u(t) = 0).
In the event that all the transmissions after time t − i − 1 are erased while the first t − i transmissions are correct, the system state at time t + 1 is given by
Since the set of events (denoted by ) that all the transmissions after time t − i − 1 (i from 0 to t) are erased while the first t − i transmissions are correct is only a subset of the whole set of events (e.g., there could be alternative erasures and transmission successes), we have
where the first inequality is due to the fact that is only a subset of the events, and the third equation is due to the assumption that the noise is white. It is easy to verify that E[x2(t + 1)] diverges as .
According to the above argument, the communication channel cannot stabilize the physical dynamics. Meanwhile, the real erasure channel has an infinite channel capacity, since one successfully transmitted real-valued symbol can convey infinite information. Hence the channel capacity in the traditional sense does not necessarily characterize the capability of real-time transmission and system stabilization. Ref. [13] realized this deficiency and thus proposed the concept of anytime capacity, which will be explained subsequently.
The focus of anytime capacity is “on the maximum rate achievable for a given sense of reliability rather than the maximum reliability possible at a given rate” [13]. The structure of the anytime capacity setup is illustrated in Fig. 5.20.
We denote by Mτ the R-bit observation received by the sensor’s encoder at time τ. Based on the output of the communication channel, the decoder obtains a reconstructed message (τ ≤ t), namely the estimation of Mτ at time t. The error probability is , namely the probability that not all the messages M1, …, Mt−d are correctly decoded at time t. The procedure is illustrated in Fig. 5.21.
Based on this context, the anytime capacity of a communication channel is defined as follows [13]:
It is easy to verify the following inequality [13]:
where Er(R) is the traditional error exponent for the transmission rate R of the same communication channel [75]. Intuitively, the anytime capacity has a higher requirement than the traditional channel capacity.
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 {si(t)}i, t at the sensor. The bit sequence will be regenerated at the controller.
• The bit sequence {si(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 , which is driven by the generated random perturbation w, and , 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 and , can be reconstructed at the controller with an error of a particular magnitude. The simulated dynamics 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 . Since x is small due to the stabilization, can be approximated by . Thus can be reconstructed by the controller with small error (since 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 has the following dynamics:
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
Then the sum of and is a simulated version of the true dynamics, since
Since the original physical dynamics can be stabilized and |x(t)| will be sufficiently small, then will be sufficiently close to .
In Fig. 5.22, we assume that the observer transmits bit i at time where R is the data rate. It is easy to verify that
The sum is similar to the representation of a factional number with base A. Then, using induction, we can prove that can be written as
where Sk is the kth bit, and γ and ϵ1 are constants whose expressions can be found in Ref. [13]. This can be achieved by representing the tth random perturbation w(t) as
Assuming that the rate R is smaller than , it was shown in Ref. [13] that bits can be encoded into the simulated plant. At the output of the communication channel, estimates can be extracted from the ith bit such that
Here the key idea is that, since we have assumed that the physical dynamics are stabilized and thus x(t) is very small, is very close to and thus can be estimated from 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
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
Notice that is the time that the ith bit is sent and thus is the (continuous-time) delay of decoding. This concludes the proof by checking the definition of anytime capacity.
We first extend the anytime capacity to a broader meaning:
Similarly to Cany in the previous discussion, we can define Cg-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.,
Now we discuss the following sufficient condition for the stability of physical dynamics:
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
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 whose dynamics are given by
where is the computed action of a virtual controller simulated at the sensor. It also keeps updating the following two virtual dynamics:
and
which results in . Since the sensor can stabilize the simulated dynamics within an interval, − xu(t) should be very close to . Hence the actual controller will try to take actions close to xu(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 2R values (where we assume that 2R is an integer). If is within the interval , lies in . The sensor can choose one of the possible control actions uniformly aligned in the interval , which is within the distance of , such that
After the perturbation by the random noise, we have
To make always within , we require
which can be achieved if
when .
Then the sensor can simply send out R bits to indicate the virtual control it takes to limit the virtual state within . 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 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
where is the estimation of the computed control action at time t − i (i.e., ) given all the received channel outputs before time t + 1.
Then the controller chooses the control action u(t) such that equals ; i.e.,
Given the above strategies of coding, decoding, and control action, the stability of the dynamics is rigorously proved in Ref. [13].
In this section, we analyze the reduction of Shannon entropy for the assessment of communication capacity requirements. As has been explained in chapter 2, entropy indicates the uncertainty of a system. Hence it is desirable to decrease the entropy such that the system state is more concentrated around the desired operation state. However, in stochastic systems, there is a high probability that external random perturbations will increase the entropy, unless the system state entropy has already been very large.2 Therefore communication is needed to provide “negative entropy” to compensate for the entropy generated by random perturbations (entropy reduction will eventually be carried out by the controller), thus acting as a bridge linking the analyses of communications and stochastic system dynamics, as illustrated in Fig. 5.26.
Note that the concept of entropy is also used for the analysis in Section 5.2, where the system is deterministic and the only uncertainty stems from the unknown initial state. In this section, the system is stochastic; hence the Shannon entropy, instead of the topological entropy, is used to measure the system uncertainty. The relationship between the topological entropy and the Shannon-type entropy (more precisely, the Shannon-Sinai entropy of dynamical systems [12]) can be described by the Variational Principle (Theorem 6.8.1 in Ref. [12]), which will not be explained in detail in this book.
In this section, we will provide a comprehensive introduction to communication capacity analysis based on the reduction of Shannon entropy in physical dynamics. We will first provide a qualitative explanation of entropy reduction from the viewpoint of cybernetics. Then we begin from discrete state systems and extend to continuous state systems.
We first provide an analysis of Shannon entropy in dynamics, using the arguments of cybernetics [77, 78]. The analysis does not explicitly concern communications; however, it provides insights for future discussions.
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 VR and VD, 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 VO), given the strategy of R, cannot be less than VD/VR.
Then if we use a logarithmic scale to measure the variety, the above conclusion can be translated into the following inequality:
If the distributions of O, R, and D are all uniform, then we have
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.
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
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 Hc(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 , where the subscript o means open loop. The minimum entropy subject to the open-loop control is given by
Then we obtain the following theorem on the difference between and Hc(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:
which also implies
where h is the entropy rate, defined as , and the average mutual information i is similarly defined.
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
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
Then the feedback signal is given by
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.,
The linear output of the plant x is then given by
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 xo(t), given by xo(t) = Dn(t). The following theorem shows the relationship between h(x) and h(xo):
Immediate conclusions can be drawn in the following corollary:
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]
where Bi is the ith basis function and wi is the expansion coefficient. The cost function is defined as
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].
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:
Consider two strategies of the controller: (A) fix the action p; (B) adaptive control action: , , and . 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.
Many existing control strategies are not based on the performance metric of entropy. However, they can also indirectly reduce the entropy, since uncertainty is usually undesirable. In this chapter, we take LQG control [72] as an example. The system dynamics are linear with Gaussian noise (both in the system state evolution and observation). The cost of the control is given by
where Q and R are both nonnegative definite matrices, and T is the final time under consideration. Intuitively, when R = 0 and Q = I, all the efforts are used to reduce the expected square norm of x. When E[∥x∥2] is small, the uncertainty is small, thus making the entropy small. Note that reduction in E[∥x∥2] does not necessarily imply reduction in the entropy; however, if E[∥x∥2] is substantially reduced, there is a high probability that the entropy will also decrease.
Here, we use numerical results to demonstrate the entropy reduction. We consider a power network with Ng generators. For generator n, its dynamics are described by the following swing equation [4]:
where δ is the phase, Pmn is the mechanical power, and Pen is the electric power. Mn is the rotor inertia constant and Dn is the mechanical damping constant. We denote , which is the frequency of rotation.
Similarly to the seminal work by Thorp [56], we ignore the connection of loads. We assume that the system state is close to an equilibrium point. The standard frequency is denoted by f0 (e.g., 60 Hz in the United States) and the frequency deviation of generator i is denoted by Δfi. The angle deviation δi − f0t − θi (where θi is the initial phase of generator i) is denoted by Δδi. Then when Δfi and Δδi, i = 1, …, Ng, are both sufficiently small, the dynamics can be linearized to
where ΔPmi is the difference between mechanical power and stable power, which is assumed to be the control action. The coefficients {cik}ik can be obtained from the analysis of real power. The details are omitted due to limitations of space, and can be found in Ref. [56]. Obviously, the state of each node is two-dimensional (Δδi, Δfi).
We use the IEEE New England 39-bus model, which is illustrated in Fig. 5.32. The parameters of the transmission lines are obtained from the model. We assume that all generators have the same parameters: momentum M = 6 and damping D = 0 (i.e., we ignore damping). The feedback gain matrix K is obtained from the linear quadratic regulation (LQR) controller synthesis. The state of each bus is given by (f, δ), where f is the frequency and phase.
First we assume that there is no observation noise and the system state can be observed directly (i.e., y(t) = x(t)). We use LQG control by assuming Q = rI, R = I. We also add noise to the system state evolution with variance σ.
We consider the dynamics of Bus 1 by severing the connection to all other buses. We choose 10 random starting points. The 10 corresponding traces are illustrated in Fig. 5.33. We observe that the uncertainty is eliminated with time.
We then consider all the 39 buses. The traces of system entropy in four cases, where r is the ratio between Q and R, are shown in Fig. 5.34. We observe that, in all these four cases, the entropy is a monotonically decreasing function of time. Moreover, a larger noise power or a smaller r will decrease the rate of entropy reduction.
We then consider the observation noise and assume σ = 1. Traces of the two-dimensional dynamics are shown in Fig. 5.35. We observe that the entropy still tends to decrease.
In these simulation results, we observe that the entropy is reduced by the LQG controller, although it is not designed to reduce the entropy. Hence the entropy approach for analyzing the communication capacity requirements is valid.
To further validate the entropy approach, we provide analytic results on the entropy reduction in control systems. We consider the following standard linear dynamics:
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:
In the previous subsections, we discussed the entropy change in the control system, which does not explicitly involve communications; hence it is still not applicable to a CPS. In this subsection, we will study a CPS with communications and discrete-state physical dynamics using the arguments in Ref. [15].
We consider finite state physical dynamics with discrete timing structure. The N states of the physical dynamics are denoted by x1, …, xN. 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 pt−1, and the corresponding entropy is denoted by H(t − 1). The state is perturbed by random perturbations and is changed to X0(t) with conditional probability Qmn = P(X0 = n|X = m) and entropy H0(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(xi|mj) = P(X(t) = xi|M(t) = mj) and P0(xi|mj) = P(X0(t) = xi|M(t) = mj). 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 pt 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 a1, …, aD. Each control action maps X0(t) to X(t). W assume that the controlled dynamics is deterministic; i.e., given the action A and the state X0 after the entropy increase stage, the system state X is uniquely determined. We denote the mapping, indexed by the control action, by fi if A = ai; i.e., X(t) = fi(X0(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(X0(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).
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.
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:
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.
In the previous discussion, we assumed that the dynamics is discretely valued. However, in practice, many systems are continuously valued. Here we follow Ref. [89] to study the relationship between entropy and communications in continuously valued dynamics.
We consider the system illustrated in Fig. 5.38. Here d is the random disturbance. x is the state of the plant, while y is the output. y is fed back to a causal controller, which is also subject to noise c. The plant (physical dynamics) is described as follows:
Here the feedback control can be considered as a noisy communication channel, which is continuous in both values and time. This is different from modern digital communication systems. However, the equivalent analog communication system can provide insight into digital ones.
The following assumptions are made:
• The noises in the observation c, the system disturbance d, and the initial state x(0) are mutually independent.
• The control action is given by u(t) = K(t, y(0 : t), c(0 : t)), where K can be a time-varying deterministic function and is dependent on the history of observations and observation noises, and is thus casual.
The fundamental limit of the control system in Fig. 5.38 can be characterized by Bode’s Law, which will be explained subsequently. First we define the sensitivity function S(z) as the transfer function between disturbance d and error e. Since we expect small errors given the disturbance, we desire small S(z). However, Bode’s law states that for a strictly proper loop gain we have
where Ω is the set of unstable poles in open-loop control. Obviously, the right-hand term is independent of the feedback control scheme. Hence the sensitivity function S cannot be arbitrarily reduced over all the frequencies. Note that here we consider the system as deterministic (the perturbation is also deterministic). In the context of stochastic systems, we need to use the power spectrum density, instead of the signal spectrum. The extension to the stochastic system has been carried out in Ref. [89] and will be introduced subsequently.
In Ref. [89], the fundamental limit of the control system is studied from the viewpoint of entropy. The following theorem is of key importance in the analysis:
A rigorous proof of Theorem 19 is given in Ref. [89].
Based on the inequality in Theorem 19, Ref. [89] proved the following extension of the Bode-like performance limitation.
The following lemma was shown in Ref. [89] to illustrate the requirement of information flow in the feedback, or equivalently the required amount of communication in the feedback control: