Problem 4.4

Decentralized control with

communication between controllers

Jan H. van Schuppen

CWI

P.O. Box 94079, 1090 GB Amsterdam

The Netherlands

[email protected]

1 DESCRIPTION OF THE PROBLEM

Problem 1: Decentralized control with communication between controllers

Consider a control system with inputs from r different controllers. Each controller has partial observations of the system and the partial observations of each pair of controllers is different. The controllers are allowed to exchange online information on their partial observations, state estimates, or input values, but there are constraints on the communication channels between each tuple of controllers. In addition, there is specified a control objective.

The problem is to synthesize r controllers and a communication protocol for each directed tuple of controllers, such that when the controllers all use their received communications the control objective is met as well as possible.

The problem can be considered for a discrete-event system in the form of a generator, for a timed discrete-event system, for a hybrid system, for a finite-dimensional linear system, for a finite-dimensional Gaussian system, etc. In each case, the communication constraint has to be chosen and a formulation has to be proposed on how to integrate the received communications into the controller.

Remarks on problem

(1) The constraints on the communication channels between controllers are essential to the problem. Without it, every controller communicates all his/her partial observations to all other controllers and one obtains a control problem with a centralized controller, albeit one where each controller carries out the same control computations.

(2) The complexity of the problem is large, for control of discrete-event systems it is likely to be undecidable. Therefore, the problem formulation has to be restricted. Note that the problem is analogous to human communication in groups, firms, and organizations and that the communication problems in such organizations are effectively solved on a daily basis. Yet there is scope for a fundamental study of this problem also for engineering control systems.

The approach to the problem is best focused on the formulation and analysis of simple control laws and on the formulation of necessary conditions.

(3) The basic underlying problem seems to be: what information of a controller is so essential in regard to the control purpose that it has to be communicated to other controllers? A system theoretic approach is suitable for this.

(4) The problem will also be useful for the development of hierarchical models. The information to be communicated has to be dealt with at a global level, the information that does not need to be communicated can be treated at the local level.

To assist the reader with the understanding of the problem, the special cases for discrete-event systems and for finite-dimensional linear systems are stated below.

Problem 2: Decentralized control of a discrete-event system with communication between supervisors

Consider a discrete-event system in the form of a generator and supervisors:

The problem or better, a variant of it, is to determine a set of subsets of the event set that represent the events to be communicated by each supervisor to the other supervisors and a set of supervisors,

to the other supervisors and a set of supervisors,

where represents the communication signal from Controller s to Controller j, where is the control input of Controller s for the communication to Controller j, and where the dimensions of the state, the input signals, the output signals, and of the matrices have been omitted. The ith controller observes output yi and provides to the system input ui. Suppose that Controller 2 communicates some components of his observed output signal to Controller 1. Can the system then be stabilized? How much can a quadratic cost be lowered by doing so? The problem becomes different if the communications from Controller 2 to Controller 1 are not continuous but are spaced periodically in time. How should the period be chosen for stability or for a cost minimization? The period will have to take account of the feedback achievable time constants of the system. A further restriction on the communication channel is to impose that messages can carry at most a finite number of bits. Then quantization is required. For a recent work on quantization in the context of control see, [17].

2 MOTIVATION

The problem is motivated by control of networks: for example, of communication networks, of telephone networks, of traffic networks, firms consisting of many divisions, etc. Control of traffic on the internet is a concrete example. In such networks, there are local controllers at the nodes of the network, each having local information about the state of the network but no global information.

Decentralized control is used because it is technologically demanding and economically expensive to convey all observed informations to other controllers. Yet it is often possible to communicate information at a cost. This viewpoint has not been considered much in control theory. In the trade-off, the economic costs of communication have to be compared with the gains for the control objectives. This was already remarked on in the context of team theory a long time ago. But this has not been used in control theory till recently. The current technological developments make the communication relatively cheap and therefore the trade-off has shifted toward the use of more communication.

3 HISTORY OF THE PROBLEM

The decentralized control problem with communication between supervisors was formulated by the author of this paper around 1995. The plan for this problem is older, though, but there are no written records. With Kai C. Wong a necesary and sufficient condition was derived (see [20]) for the case of two controllers with asymmetric communication. The aspect of the problem that asks for the minimal information to be communicated was not solved in that paper. Subsequent research has been carried out by many researchers in control of discrete-event systems, including George Barrett, Rene Boel, Rami Debouk, Stephane Lafortune, Laurie Ricker, Karen Rudie, Demos Teneketzis; see [1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 16, 19]. Besides the control problem, the corresponding problem for failure diagnosis has also been analyzed; see [6, 7, 8, 9]. The problem for failure diagnosis is simpler than that for control due to the fact that there is no relation of the diagnosing via the input to the future observations. The problem for timed discrete-event systems has been formulated also because in communication networks time delays due to communication need to be taken into account.

There are relations of the problem with team theory; see [10]. There are also relations with the asymptotic agreement problem in distributed estimation; see [18]. There are also relations of the problem to graph models and Bayesian belief networks where computations for large scale systems are carried out in a decentralized way.

4 APPROACH

Suggestions follow for the solution of the problem. Approaches are: (1) Exploration of simple algorithms. (2) Development of fundamental properties of control laws.

An example of a simple algorithm is the IEEE 802.11 protocol for wireless communication. The protocol prescribes stations when they can transmit and when not. All stations are in competition with each other for the available broadcasting time on a particular frequency. The protocol does not have a theoretical analysis and was not designed via a control synthesis procedure. Yet it is a beautiful example of a decentralized control law with communication between supervisors. The alternating bit protocol is another example. In a recent paper, S. Morse has analyzed another algorithm for decentralized control with communication based on a model for a school of fishes.

A more fundamental study will have to be directed at structural properties. Decentralized control theory is based on the concept of Nash equilibrium from game theory and on the concept of person-by-person optimality from team theory. The computation of an equilibrium is difficult because it is the solution of a fixpoint equation in function space. However, properties of the control law may be derived from the equilibrium equation, as is routinely done for optimal control problems.

Consider then the problem for a particular controller: it regards as the combined system the plant with the other controllers being fixed. The controller then faces the problem of designing a control law for the combined system. However, due to communication with other supervisors, it can in addition select components of the state vector of the combined system for its own observation process. A question then is which components to select. This approach leads to a set of equations, which, combined with those for other controllers, have to be solved.

Special cases of which the solution may point to generalizations are the case of two controllers with asymmetric communication and the case of three controllers. For larger number of controllers graph theory may be exploited but it is likely that simple algorithms will carry the day.

Constraints can be formulated in terms of information-like quantities as information rate, but this seems most appropriate for decentralized control of stochastic systems. Constraints can also be based on complexity theory as developed in computer science, where computations are counted. This case can be extended to counting bits of information.

BIBLIOGRAPHY

[1] G. Barrett, Modeling, Analysis and Control of Centralized and Decentralized Logical Discrete-Event Systems, Ph.D. thesis, University of Michigan, Ann Arbor, 2000.

[2] G. Barrett and S. Lafortune, “A novel framework for decentralized supervisory control with communication, ” In: Proc. 1998 IEEE Systems, Man, and Cybernetics Conference, New York, IEEE Press, 1998.

[3] G. Barrett and S. Lafortune, “On the synthesis of communicating controllers with decentralized information structures for discrete-event systems, ” In: Proceedings IEEE Conference on Decision and Control, pp. 3281–3286, New York, IEEE Press, 1998.

[4] G. Barrett and S. Lafortune, “Some issues concerning decentralized supervisory control with communicatio, ” In: Proceedings 38th IEEE Conference on Decision and Control, pp. 2230–2236, New York, IEEE Press, 1999.

[5] G. Barrett and S. Lafortune, “Decentralized supervisory control with communicating controllers, ” IEEE Trans. Automatic Control, 45:1620– 1638, 2000.

[6] R. K. Boel and J. H. van Schuppen, “Decentralized failure diagnosis for discrete-event systems with costly communication between diagnosers, ” In: Proceedings of International Workshop on Discrete Event Systems (WODES2002), pp. 175–181, Los Alamitos, IEEE Computer Society, 2002.

[7] R. Debouk, Failure diagnosis of decentralized discrete-event systems, Ph.D. thesis, University of Michigan, Ann Arbor, 2000.

[8] R. Debouk, S. Lafortune, and D. Teneketzis, “Coordinated decentralized protocols for failure diagnosis of discrete-event systems, ” Discrete Event Dynamics Systems, 10:33–86, 2000.

[9] R. Debouk, S. Lafortune, and D. Teneketzis, “Coordinated decentralized protocols for failure diagnosis of discrete event systems, ” Report CGR-97-17, College of Engineering, University of Michcigan, Ann Arbor, 1998.

[10] R. Radner, “Allocation of a scarce resource under uncertainty: An example of a team, ” In: C. B. McGuire and R. Radner, eds, Decision and organization, pp. 217 – 236. North-Holland, Amsterdam, 1972.

[11] S. Ricker and K. Rudie, “Know means no: Incorporating knowledge into decentralized discrete-event control, ” In: Proc. 1997 American Control Conference, 1997.

[12] S. L. Ricker, Knowledge and Communication in Decentralized Discrete Event Control, Ph.D. thesis, Queen’s University, Department of Computing and Information Science, August 1999.

[13] S. L. Ricker and G. Barrett, “Decentralized supervisory control with single-bit communications, ” In: Proceedings of American Control Conference (ACC01), pp. 965–966, 2001.

[14] S. L. Ricker and K. Rudie, “Incorporating communication and knowledge into decentralized discrete-event systems, ” In: Proceedings 38th IEEE Conference on Decision and Control, pp. 1326–1332, New York, IEEE Press, 1999.

[15] S. L. Ricker and J. H. van Schuppen, “Asynchronous communication in timed discrete event systems, ” In: Proceedings of the American Control Conference (ACC2001), pp. 305–306, 2001.

[16] S. L. Ricker and J. H. van Schuppen, “Decentralized failure diagnosis with asynchronuous communication between supervisors, ” In: Proceedings of the European Control Conference (ECC2001), pp. 1002–1006, 2001.

[17] S. C. Tatikonda, Control under communication constraints, Ph.D. thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, 2000.

[18] D. Teneketzis and P. Varaiya, “Consensus in distributed estimation with inconsistent beliefs, ” Systems Control Lett., 4:217–221, 1984.

[19] J. H. van Schuppen, “Decentralized supervisory control with information structures, ” In: Proceedings International Workshop on Discrete Event Systems (WODES98), pp. 36–41, London, IEE, 1998.

[20] K. C.Wong and J. H. van Schuppen, “Decentralized supervisory control of discrete-event systems with communication, ” In: Proceedings International Workshop on Discrete Event Systems 1996 (WODES96), pp. 284–289, London, IEE, 1996.