In this chapter we address the issue of control and estimation when the decision variables must satisfy a finite set constraint. We will distinguish between finite alphabet control and estimation problems. As in the case of convex constraints, the essential difference is whether or not the initial state is given or can be considered a decision variable. Finite alphabet control occurs in many practical situations including: on-off control, relay control, control where quantisation effects are important (in principle this covers all digital control systems and control systems over digital communication networks), and switching control of the type found in power electronics. Exactly the same design methodologies can be applied in other areas; for example, the following problems can be directly formulated as finite alphabet control problems: quantisation of audio signals for compact disc production; design of filters where the coefficients are restricted to belong to a finite set (it is common in digital signal processing to use coefficients that are powers of two to facilitate implementation issues); design of digital-to-analog [D/A] and analog-to-digital [A/D] converters. Finite alphabet estimation problems are also frequently encountered in practice. Common examples are: estimation of transmitted signals in digital communication systems where the signals are known to belong to a finite alphabet (say ±1); state estimation problems where a disturbance is known to take only a finite set of values (for example, either "on" or "off"). In this chapter we show how these problems can be formulated in the same general framework as described in earlier chapters. However, special care is needed to address the finite set nature of the constraints. In particular, this restriction gives rise to a hard combinatorial optimisation problem, which is exponential in the dimension of the problem. Thus, various approximation techniques are necessary to deal with optimisation problems in which the horizon is large. Commonly used strategies are variants of well-known branch and bound algorithms. We will show how the receding horizon principle can be used in these problems. A key observation in this context is the fact that often the "first" decision variable is insensitive to increasing the optimisation horizon beyond some modest value (typically 3 to 10 in many real world problems). Also, a closed form expression for the control law is derived by exploiting the geometry of the underlying optimisation problem. The solution can also be characterised by means of a partition of the state space, which is closely related to the partition induced by the interval-constrained solution, as developed in Chapter 6. As a consequence, the controller can be implemented without relying upon on-line numerical optimisation. Furthermore, the insight obtained from this viewpoint into the nature of the control law can be used to study the dynamic behaviour of the closed loop system.
Constrained Control and Estimation: an Optimisation Approach p. 295-400