Feedback Designs for Controlling Device Arrays with Communication Channel Bandwidth Constraints

Feedback Designs for Controlling Device Arrays with Communication Channel Bandwidth Constraints Abstract This paper reports a tight bound on the data capacity a feedback channel must provide in order to stabilize a right half-plane pole. 1 Introduction Device arrays of MEMS actuators such as micro-pistons and micro-valves comprise a “smart structures” technology which is both interesting and challenging. Current designs are quickly moving beyond the “proofof- concept” stage in which relatively small arrays, with between four and twenty actuators on a single chip, have been tested with each device in the array having direct communication by means of “wires” for both control and sensing. We have recently fabricated arrays with between 50 and 100 devices on a single chip, and these designs seem to have achieved more or less the maximum possible device density in which direct addressing of each actuator is feasible. In the next generation of device arrays, which will feature as many as 10,000 actuators on a single chip, it will be necessary to close feedback control loops using communication channels shared by multiple device elements. Work is only just now beginning on the switching and encoding strategies that will be needed to produce stable closed-loop dynamics across a broad spectrum of applications. We are finding that many of the bandwidth assignment issues that are predominant in managing the traffic in modern communications networks are also present in some form in networked actuator arrays. This note presents recent results on the effects of communications bandwidth constraints in feedback control designs. The main results involve a novel interplay between control and information theory. From one viewpoint, the theory of control using bandwidth-constrained feedback channels may be thought of as an enriched version of classical digital control theory. Indeed, bandwidth constraints in feedback control raise interesting quantization issues in which there is a trade-off between the coarseness of control and observation data and the time required to send data over the link. High performance in many applications calls for finely quantized data and a correspondingly large set of codewords used to describe the system’s inputs and outputs. It has been shown that fine data quantization requires either a larger channel capacity or longer periods allocated to data transmission. The relationship between the control system structure and 1 Controlling device arrays with communications bandwidth constraints Baillieul 2 the channel capacity is central to understanding the design of feedback control laws which are capable of providing high-quality regulation of the system’s performance. An interesting concept which has emerged in this research is that of “required attention”—a term which is intended to serve as both a descriptive characteristic of dynamical systems in general and a figure of merit for closed-loop feedback designs. In Brockett ([1]), this latter notion of “required attention” is developed, and in the case of linear systems having no right half-plane poles, the term is given a precise quantitative meaning in terms of something called an “attention functional”. For linear systems having no right half-plane poles, Brockett has solved the “minimum attention” problem using a variational argument. In the present note, we shall present a slightly different perspective in which the notion of “required attention” is captured by the amount of channel capacity (in bits per second) which is required to implement a stable feedback law. One intuitively appealing result is that by our measure, the required attention for a stable feedback law increases as a function of how far open-loop poles extend into the right half-plane. This definition of “required attention” provides the first instance of which we are aware of a characterization of a system’s complexity in terms of how much information must be transmitted in order to control it. It is expected that this measure will play a role in developing channel allocation strategies for controlling large scale device arrays. Classical feedback control theory is aimed at understanding design principles for integrating sensors and actuators for controlling a physical system in a way that it will perform its prescribed tasks efficiently and reliably. The basic principles are very simple as illustrated in Figure 1. Information about the state of the system of interest (called the plant G) is provided by output sensor data. The control system (represented by the box labeled H together with the dotted interconnection) processes signals from sensor outputs, compares the state of the system with specified operating goals, and “closes the loop” by sending appropriate actuator signals to keep the system operating as near as possible to it operating goals. There is today a vast array of mathematically sophisticated tools for design and analysis of the controller H. The tools apply to both continuous and discrete-time systems, and for many applications, they have become an essential aid for implementations of feedback control mediated by digital microprocessors. As we shall indicate below, however, many feedback control laws cannot be implemented in a satisfactory way if the links between the plant (G) and the controller (H) do not have adequate information carrying capacity. The paper is organized as follows. In the next section, a bound is established on the capacity required on the channel between G and H in order to stabilize a right half-plane pole in G. The bound is tight and the result has been proved for the case of first order systems. Section 3 discusses extensions to higher order systems. 2 Digital control of first order systems with uniform sampling rate We consider controlling a first-order plant, as depicted in Figure 1, G(s) = b/(s − a). The cases of greatest interest are those in which a > 0, since the controller H must be designed to stabilize the plant. Classical control theory (e.g. [2]) provides many approaches to designing H, and implementations mediated by digital microprocessors can be carried out by selecting the appropriate discrete-time tools. We wish to understand how these results are affected if there are bandwidth constraints or limitations on the feedback links connecting G and H. The case we shall treat here involves digital control with a uniform sampling interval h. We assume control actuation is of the sample-and-hold type, so that control inputs to the system are constant over each sampling interval. The state of the plant evolves in discrete time according to x(k + 1) = α x(k) + β u(k), (1) Controlling device arrays with communications bandwidth constraints - G Baillieul 3 - H Figure 1: where b ah (e − 1). a If a digital computer is used to implement feedback control, a sensor reading of the (typically analog) value x(k) is digitized and stored in a computer register. Using whatever control algorithm has been implemented, the computer determines a value of the control input u(k) (from a finite set U of admissible control values), and this in turn is converted to an analog value (e.g. a voltage or a current) which is then fed back to the plant. For many applications, eight or fewer bits suffice to specify the values of the control function u(·), and hence the cardinality of the set U of admissible control values is typically ≤ 256. Whatever the cardinality, |U |, of the set of admissible controls, the number N of bits needed to uniquely encode each control value is such that |U | ≤ 2N . The inequality may be strict since some encoding schemes will use a certain number of bits for purposes other than identifying control values. Our interest in the present note is in the case in which the communication channels between the control computer and the plant have a low data rate—say R bits per second. This situation would arise, for instance, if a single computer were controlling many plants connected serially by a single communication link. In this setting, a number of interesting nonclassical issues arise. α = eah , and β = • There is a trade-off between the cardinality of the set of admissible control values (or levels) u(k) and amount of time required on average to transmit digitally encoded data from the control computer to the plant. This problem is discussed in Wong and Brockett, [3], where both controller and sensor data are assumed to be encoded using prefix codes. Using known bounds on the average length of codewords in prefix codes, bounds are given on the minimum sampling interval, h, required to permit the transmission of control data between the sensors and actuators and the control computer. • Some systems are intrinsically more complex than others in the sense that a finer quantization of control levels is required to guarantee stable performance. The main results of the present note are that (i) the number K of distinct possible control values or levels must be greater than or equal to eah in order to implement stable feedback control, and (ii) the channel capacity R must exceed a log2 e. Stated in less precise but more suggestive language, the greater the degree of instability of the openloop system, the finer the quantization of control values and the more information there is which must be communicated between the controller and plant in each time interval. Classical notions of asymptotic stability must be modified in order to discuss control designs with quantized control values. Definition 1 (Wong & Brockett, [3]) A linear control system is said to be containable if for any open set S containing the origin, there is a corresponding open set M containing the origin and an encoding of a feedback control law such that any trajectory started in M remains in S for all time. Controlling device arrays with communications bandwidth constraints Baillieul 4 Definition 2 A linear control system (1) with admissible control set U is boundable if there exists a compact set S such that for each x0 ∈ S there is a control sequence U = {u(k) ∈ U : k = 1, 2, . . .} such that the trajectory defined by (1) with x(0) = x0 and control input sequence U remains in S for all time. Containability is a property the discrete-time control system (1) must possess in order for there to exist a finite set U of control values which can be used to implement an (approximately) asymptotically stabilizing control law. Boundability assumes that a finite set U of control values has been chosen together with a systematic way of encoding and transmitting these values from the controller to the plant. Containability is stronger than boundability, and any system which is not boundable cannot be containable. Example 1 The case of binary control. Suppose the set U of admissible control values has two elements. These correspond to what we assume are precisely two different possible actuator commands. While these values might be different voltages or currents or other physical quantities of constant magnitudes, there is no loss of generality in the model in assuming that U = {−1, 1}, since this may always be brought about for a system of the form (1) by an affine change of coordinates. To make the discussion of boundability interesting, we assume that (1) is open-loop unstable: i.e. α > 1. In this case, it is not difficult to see that implementing any stabilizing feedback law results in closed loop dynamics given explicitly by ½ α x(k) + β x(k) ≤ 0 x(k + 1) = . (2) α x(k) − β x(k) > 0 Fact The closed loop system (2) admits an invariant interval if and only if α < 2. Proof There are two fixed points of the mapping (2): −β/(α − 1), β/(α − 1). In studying the closed loop mapping (2), it is important to note that α < 2 if and only if β < β/(α − 1). If α < 2, an easy calculation shows that the interval [−β/(α − 1), β/(α − 1)] is invariant. (There are other invariant intervals too in this case.) Suppose on the other hand that there is an invariant interval. This can only happen if β ≤ β/(α − 1), because otherwise there is a subinterval of points containing the origin (specifically ¶ µ 2 β 2 −β (1 − ), (1 − ) α−1 α α−1 α such that no bounded trajectory of (2) can enter the interval. But the set of points in (−β/(α−1), β/(α−1)) which are initial points of trajectories entering this neighborhood can be shown to be dense. On the other hand, any trajectory started outside [−β/(α−1), β/(α−1)] is clearly unbounded. This proves our statement.2 This result that (1) is boundable using a two-element control set U = {−1, 1} if and only if α < 2 is a special case of our more general result. Specifically the inequalities α < 2 and ah log2 e < 1 are equivalent. The second more clearly expresses the bound which the product of the (right half-plane) pole magnitude and the sampling interval must satisfy in order for the system to be boundable using binary control. The main result of the section is the following: b whose sampled realization is given by (1). If the Theorem 1 Consider a first order system G(s) = s−a channel capacity R is greater than a log2 e, then we may chose a sampling interval h and a set U of admissible control values such that |U | > eah and such that the resulting feedback control implementation is boundable. Remark 1 Control information versus control authority. An interesting aspect of the example and the main theorem is that the conditions for boundability and the existence of invariant intervals do not depend on β. They depend only on the amount of information that can be communicated between the controller and plant in one unit of time. Controlling device arrays with communications bandwidth constraints Baillieul 5 Remark 2 Remarks on the channel capacity conditions. (i) The proof of this theorem involves the explicit construction of the set U of control values together with a feedback law which renders a compact interval invariant under motions of the system (1). As indicated in the above example, the condition a log2 e < R is also essentially necessary because the cardinality of the set U must be larger than eah in order to guarantee bounded motions of (1). The channel capacity R must in turn be large enough to transmit enough bits of data to uniquely identify control values in each time interval h. (ii) The theorem actually represents a crude lower bound on the amount of channel capacity one would like to have to implement feedback control of a physical system. It provides only a condition for the existence of a bounded response. To address the myriad standard control design issues such as rise time, gain and phase margins, etc., we shall need to have the capacity to transmit a great deal more data through the channel. Remark 3 Design of the control value set. 1. Magnitude and spacing of the control values. In our general formulation of the problem of quantized feedback control, we have assumed the set of admissible control values is symmetric about the origin: U = {−dn , −dn−1 , . . . , −d1 , d1 , . . . , dn } (where the elements are listed in order of increasing magnitude). In real-time digital control implementations, an interesting design question is whether the control levels di should be evenly spaced. (This question comes up, for instance, in choosing whether to use integer [evenly spaced] or floating point arithmetic [logarithms of floating point numbers are evenly spaced].) Suppose we focus the discussion on the case in which a standard constant gain feedback design, u = u(x) = −kx is being implemented in terms of our quantized finite set of control values. If we choose a control set U corresponding to the bounding case in which |U | ∼ eah in Theorem 1, one is then forced to take the control values to be more or less evenly spaced. Stable control with logarithmic spacing of the control values will thus require higher channel capacity in the feedback loops. The magnitude of the control values in the finite set U is a design parameter whose value may be chosen without regard to the channel capacity (assuming it takes no more bits to transmit a large value than to transmit a small value provided the cardinality of the set U itself is fixed). There is, however, the following consideration. 2. Switching thresholds. Suppose we again choose to implement a constant gain feedback control law u = −kx. The following are important considerations: (a) For each sampled value of the state x(j), one should choose a control value di ∈ U such that |di + kx(j)| = min{|d + kx(j)|}, d∈U and the algorithm should switch control levels at each sampling time as needed so as to ensure this choice of control level is applied. (b) While the question of whether it is ever useful to consider sets U of unevenly spaced control values remains open, it appears that unevenly spaced switching thresholds tend to make the dynamics of (1) relatively erratic. (c) For sets of evenly spaced control values U = {−dn , −dn−1 , . . . , −d1 , d1 , . . . , dn }, where dj = jd for a fundamental control value d, it is important to choose d ∼ k. Not doing so can also result in relatively erratic dynamic behavior of (1) These observations will be amplified and illustrated by simulation experiments to be reported elsewhere. Controlling device arrays with communications bandwidth constraints 3 Baillieul 6 The case of higher order and multivariable systems We have remarked that the channel capacity bound of Theorem 1 provides a crude lower bound guaranteeing the existence of bounded motions in the idealized case of first order systems. For higher order systems, the requirements on channel capacity are more severe if there is more than one right half-plane pole in the open loop (uncontrolled) system. The following result presents conditions under which bounded motions are assured for a system evolving in IRn . Theorem 2 Consider the constant coefficient linear control system ẋ(t) = Ax(t) + bu(t) (3) where A is an n × n matrix and b is n × 1. (Thus u is a scalar input.) Assume A has distinct real eigenvalues and (A, b) is a controllable pair. Let τ = eλ(A)max h , where λ(A)max is the largest eigenvalue of A. Then if log2 τ < 1/n, there is a finite set U of control values such that the sampled version of (3) is boundable. Proof The sampled system corresponding to (3) is x(k + 1) = F x(k) + Γu(k), −1 where F = e and Γ = A (e − I)b. Let U be a (finite) set of control values. A set K is invariant if for any x ∈ K, there is a control sequence u1 , . . . , um ∈ U such that Ah Ah F m x + F m−1 Γu1 + · · · + Γum ∈ K. This is equivalent to ¡ ¢ x ∈ F −m K − F m−1 Γu1 − · · · − Γum , for some m; u1 , . . . , um ∈ U , or [ K⊆ [ [F −m K − F −1 Γu1 − · · · − F −(m−1) Γum ]. (4) m≥1 u1 ,...,um ∈U Under the hypothesis of the theorem, it is not difficult to show that the unit hypercube, K = [0, 1]n , can be made to be invariant by proper choice of control set U . Since λmax (F ) < 21/n , λmin (F −1 ) > 2−1/n . From this it follows that 1 vol(F −n (K) > n vol(K). 2 (Since both K and F −n (K) are rectangular, and the length of a side of F −n (K) > 1/2 the length of a side of K, the result is straightforward.) From this, it follows that we may chose 2n control values such that equation (4) is satisfied. This proves the theorem.2 Remark 4 Remarks on quantized control of higher order systems. The first order quantized control systems considered in the previous section are of some importance for device arrays of MEMS actuators, since individual device elements are frequently modeled by such low order systems. Nevertheless, the theory of higher order systems is also important, although at present it is somewhat less developed. If a system has two or more unstable open loop poles, for instance, we do not have a tight bound on the smallest possible channel capacity needed to implement a stable (or at least bounded) feedback law. Theorem 2 provides sufficient conditions for implementing a control law with a bounded response, but the minimum possible size of the control set U (together with corresponding channel capacity requirements) is not specified. Controlling device arrays with communications bandwidth constraints Baillieul 7 Example 2 The inverted micropendulum. For control systems with only a single unstable pole, the results of the previous section apply. An interesting example is provided by a slight modification of the classical inverted pendulum example. Recently, using fundamentally nonlinear methods, we have stably balanced some very small ( 18 -inch) pendulums. It is interesting to think about trying to balance pendulums of this size using digital implementations of classical feedback methods. p Recall that for the inverted pendulum there is one right half-plane pole whose magnitude is roughly g/`. Taking g = 10 (meters/sec.2 ) and ` = 0.001 (meters), we can use the bound of pTheorem 1 to estimate the minimum channel capacity needed to implement this control. In this case a = g/` = 100, and thus the minimum channel capacity required is 100 log2 e = 144.2695041... bits per second. As remarked in the previous section, this is a tight bound, but it is one which gives only a conservative estimate of the data capacity that is needed to support a moderately sophisticated control law (as prescribed by standard LQR or H ∞ techniques). Moreover, if sophisticated data encoding is used in the communications link between the pland and controller, the required channel capacity will be even higher. While a data rate of even 1000 bits/second is well within the bounds of even the slowest telephone modems, it suggests that there could be limits in trying to multiplex a large number of devices using a noisy channel such as might be encountered in a MEMS array. 4 Conclusion This short note has raised the question of what is the minimum data capacity needed in the communication link between a controller and plant in order to stabilize a system with right half-plane poles. For systems with a single real right half-plane pole a, the requirement on the channel capacity R is that R > a log2 e.