Coordination Control of Distributed Systems

The chapter provides a brief overview of the five case studies of the C4C Project. A section on the role of case studies in EU-sponsored research is presented first. Of each case study is described the aim of the case, the setting of the problem, the research issues, and the C4C Teams involved. The communalities and differences of the case studies are discussed.

The problem of coordinating the motion of autonomous underwater vehicles under constrained acoustic communications is formulated and investigated in the context of the model predictive control (MPC) framework. The impact of acoustic communications and perturbations on the motion performance and robustness is discussed. A reach set formulation of the MPC scheme is outlined.

Problems of motion coordination for autonomous vehicles are discussed in the framework of dynamic programming (DP). The challenges of the practical deployment of DP-based controllers are illustrated with a formation control problem.

The computation and control challenges arising in the coordination of multi-vehicle systems are discussed in the framework of (coupled) physical and computational dynamics. The challenges are formulated as classical control problems of optimization, invariance, and attainability for systems governed by the laws of physics and computation. Directions for future research are discussed with special emphasis on the aspects of coupled dynamics and dynamic structure that seem to be missing in the literature.

The purpose of this chapter is to describe the leader–follower approach for coordinating many interacting components of a large network. This leader–follower approach is suitable for systems with intermediate load, where only a few critically loaded components are having difficulties to achieve their local specifications. We assume that a supervisor, acting at a hierarchically higher level of the control protocol, has selected assigned to these critical components the role of leader agents. Leader agents send additional specifications to their neighboring follower components so as to ensure that the output of these follower components makes it easier for the leader component to achieve its own specifications. The local control agents generate control inputs so that all specifications are met, including at the followers those specifications imposed by their neighboring leader. Local controllers thus help each other in such a way that the overall system achieves good performance. In this essay, we illustrate this approach by applying it to controlling the switchingtimes of traffic lights in an urban area. Traffic is described in this case study by specifying the arrival times and the size of platoons of vehicles at sensor locations in the network. Control actuation should try to minimize the average vehicle delay by switching traffic lights, as often as possible, from red to green whenever a platoon arrives. The leader–follower approach combines the idea of green waves with local feedback control at each intersection. Each local controller finds an online solution to a local optimization problem, subject to specifications. Coordination is achieved by letting leader intersections specify bounds on the earliest and latest time that platoons are allowed to leave their neighboring follower intersection, in such a way as to minimize the waste of capacity at a leader intersection. The proposed leader/follower approach may be useful for coordination control in directed networks under intermediate load conditions, where heavily loaded leader components can request help from less loaded upstream followers.

At traffic control centers there is a need to predict the traffic flow in road networks for a horizon of about 30 min or longer. At traffic control centers, there is a need to predict the traffic flow in road networks for a horizon of about 30 min or longer. The predictions are needed to detect troublesome traffic situations before they occur, primarily congestion, and to evaluate one or more control scenarios. The chapter summarizes the following: (1) an adaptive prediction algorithm for prediction of traffic flow at the boundary of the road network and (2) a method to compute coordinated–distributed prediction of traffic flow in a road network.

This chapter is on the design of automated guided vehicle (AGV) systems within the framework of the traditional zone-control strategy. Our focus will be on the descriptions of two things: (1) a novel event-based zone-control model which includes formal definitions of the road network used by the vehicles and the event-based behavior the vehicles must follow while in operation and (2) a set of traffic control rules that excludes inter-vehicle collisions and system deadlocks but imposes no restrictions on route selections of vehicles. We also briefly mention an application of the proposed strategy to the container transshipment at a container terminal, where the interested reader will be led to a reference. At the end, we point out several possible directions for further work.

Control and coordination are important aspects of the development of complex machines due to an ever-increasing demand for better functionality, quality, and performance. In WP6 of the C4C project, we developed a synthesis-centric systems engineering framework suitable for supervisory coordination of complex systems. The framework was employed to synthesize and validate a supervisory coordinator for maintenance procedures for a prototype of a high-tech Océ printer, showing proof of concept and viability of the proposed framework. The supervisor eliminates undesired behavior that could occur as a result of undesired interaction of the distributed printer components. In this chapter, we discuss the model-based systems engineering framework that was employed for synthesis of the supervisor, and we illustrate the modeling process.

This essay deals with the coordination of the control actions in a network of interacting components, where actuator values for each component are calculated by its local control agent (CA). If the local CAs act independently, then the interaction between different control loops often leads to instability of the network as a whole. Using hierarchical control, including centralized solutions, requires very detailed global model knowledge and may not be robust against communications failures. In this essay, we introduce a coordination paradigm that considers only the hierarchical layer of the CAs. Each local CA implements a model-predictive control (MPC), but neighboring CAs, moreover, exchange their planned control actions in the near future. This information allows each local CA to improve its local anticipation, provided it knows an approximate model of its neighbor. This achieves coordination between the different CAs. We call this approach the coordinating MPC (CMPC) . In order to easily illustrate the advantages of CMPC, we use secondary voltage control in a large-scale multi-area electric power system as a case study. It is known that the electric power system may be destabilized when different neighboring CAs react in an uncoordinated way to incidents that cause the local voltages to temporarily leave their safe sets. In the CMPC approach, each CA sends information on its planned control actions to its neighbors. Simulations for a well-known test system have shown that CMPC significantly increases the size of the set of perturbations that can be tolerated without leading to global instability, as opposed to using anticipation only. In this case study, we use a very simple hybrid model of each area of the electrical power system and consider discrete control actions only. The case study, therefore, provides a good way of introducing CMPC for cyber-physical systems.

System architectures of networked control systems are described and classified. The overall classification starts with distinguishing multilevel systems and distributed systems. At any particular level of a multilevel system, even of a one-level distributed system, one can distinguish the graph of the system network: A ring network, a line network, a grid network, etc. Systems can further be distinguished in their interaction relations. Control theory can benefit from this classification by focusing for control synthesis on each class separately.

Defined are the following control architectures for control of distributed and of multilevel systems: Distributed control, distributed control with direct communication between controllers, coordination control, and multilevel control. Principles and guidelines for the choice of these control architectures are provided.

A coordinated system is a multilevel system in which one distinguishes a coordinator subsystem at the highest level and the remaining subsystems at the lowest level. The control task of the coordinator is to coordinate the interaction of the subsystems at the lower level. The problems are then to formulate the concept of coordination, to construct for a distributed system and control objectives a coordinator subsystem of minimal complexity, and to develop control synthesis for coordinated systems.

This chapter serves as an introduction to the concepts of coordinated linear systems, in formal as well as intuitive terms. The concept of a coordinated linear system is introduced and formulated, and some basic properties are derived, providing both a motivaton and a formal basis for the following chapters of this part.

The concept of a coordinated linear system which contains a coordinator and two or more linear subsystems is defined. Both the case without inputs and the case with inputs are discussed in geometric terms. The class of control laws that conform with the structure of coordinated linear systems is considered: control synthesis then separates into control synthesis for the coordinator and for each of the local subsystems.

Some results on LQ optimal control for coordinated linear systems are summarized and discussed. The standard LQ problem is restricted to structure-preserving feedback laws. Given a fixed coordinator control law, the control problems for the subsystems decouple; the optimal control problem for the coordinator, however, depends on the subsystem dynamics and is analytically unfeasible (in its general formulation).

The aim of this essay is to provide a brief introduction to supervisory control theory of discrete-event systems.

The aim of this essay is to provide a brief introduction to the coordination control approach for distributed discrete-event systems with synchronous communication, where

synchronous communication

means synchronization of subsystems by the simultaneous occurrence of shared events.

A team problem is a stochastic decision problem with two or more decision makers. The decision is only taken once, there is no time axis as in control theory. The teams strive to optimize a common objective function but have different information to reach their decisions. The team wants to determine an optimum, the global optimum if it exists. To achieve at an optimum, they use the concept of a person-by-person or person-by-person equilibrium. The main problem of team theory is then to determined conditions under which a person-by-person equilibrium is also an optimum or the global optimum, and to compute a person-by-person equilibrium. This chapter restricts attention to what is called static team theory and does not discuss at length dynamic team theory.

In this chapter, we discuss the application of Girsanov’s measure transformation in generalizing static team theory to dynamic team theory of stochastic dynamic decision systems with nonclassical information structures. We apply Girsanov’s measure transformation to obtain an equivalent decision system under a reference probability measure, in which the corresponding observations and information structures available for decisions are not affected by any of the team decisions, so that static team theory is directly applicable. We also present necessary and sufficient team and person-by-person (PbP) optimality conditions, which are described in terms of backwards stochastic differential equations (BSDEs) and conditional Hamiltonian functionals.

Decentralized control problems with non-classical information structure relate, by definition, issues of information and control. If different controllers have different observations, a consensus estimate of the system state cannot be generated. To compensate for this information deficiency, any controller can generate an input signal that encodes part of its private information and which is subsequently observed by other controllers. The use of control actions to convey information through the system is known as

signaling

. Analysis and synthesis of signaling laws is an open and urgent problem of control theory.

The aim of this chapter is to introduce the reader to one of the important applications of distributed control that is manufacturing networks. In this chapter, we present selected results of our study focused on performance analysis of manufacturing machines and tandem lines operated under distributed surplus-based control. The distributed nature of the controller ensures that the control action for each machine in the network depends merely on the state of its neighboring machines. This fact significantly simplifies implementation of the control algorithm. By rigorous mathematical analysis in combination with classical control theory, we are able to show the optimality of surplus-based control for a single manufacturing machine and evaluate the demand tracking accuracy of a manufacturing line with bounded intermediate buffers. Particular attention is given to the flow models that describe the dynamical behavior of a manufacturing machine and a line. The analytical results of this chapter are supported by a simulation example.

Control of distributed systems with the control architecture of distributed control with direct communication between controllers is used in engineering and new applications are in development. Examples are control of road vehicles with communication between these and control of message routing in communication networks where the communication is between adjacent nodes of the network. The control synthesis for this control architecture is considerably difficult. Major research issues include the following: What should be communicated between controllers? When should such information be communicated? How is the communication to be carried out using encoders and decoders? How to integrate the received information from two or more sources into a coherent view of the system and how to carry out control synthesis?

By the data rate theorem, the smallest capacity of the communication channel for which the observation problem is solvable is equal to the topological entropy of the open-loop system. A similar result holds true for control problems under communication constraints. Therefore, in real applications, it is important to estimate the topological entropy to find limitations caused by limited data rate of the communication channels. We show that such an estimate can be found by the direct Lyapunov method.

An information structure specifies the observationsd available to the controllers of a decentralized or a distributed control system. The observations include those received directly from the control system and those received directly from other controllers. A classification of information structures is stated including classical, overlapping, and private information structures. Control synthesis is best distinguished per information structure.

Control theory is explored for several classes of information structures formulated in a previous chapter. Control theory with classical information structures is well investigated. Control theory with private information is described at length; it has many open-research problems. The well-known Witsenhausen counterexample is of this class. Finally, control theory with overlapping information structures is briefly explored. Research issues for control with information structures are discussed.

Control and filtering of decentralized systems can benefit from a decomposition of the available observations into components. The concepts of common, private, correlated, and sufficient information have been proposed and are defined in this chapter. A decentralized control system in which the outputs and the states have been decomposed with respect to these concepts will facilitate the synthesis of communication laws and control laws for decentralized control.

Which reduced linear combination of its observations should Observer 2 send to Observer 1 so as to allow Controller 1 to make a better state estimate of the decentralized system? As a performance criterion, the variance of the state estimate is used. Algorithms and optimality are discussed for the case when the rank of the combination is free to be chosen and when it is fixed.

When it comes to controlling large systems, such as networked infrastructure systems (roads, the electricity network, data communications networks, etc.), hierarchical control (HC) is among the most often used options. Yet, HC is still not very well understood and its applications are primarily human oriented, not automated. Several knowledge gaps limit its automated application, even in cases where this would offer considerable societal benefits, for instance, for the congestion problem in road traffic. HC is first of all a way to reduce complexity in the control of large systems. If this works well, the control becomes scalable and the controlled systems can have virtually any size. This chapter proposes a way to do this complexity reduction with HC in cases that involve a high level of automation. It introduces a number of key notions for HC and lists requirements for its applicability. A subsequent chapter will show how these requirements can be fulfilled for the application of HC to the management of road traffic.

This chapter presents a solution to the problem of network management of road traffic along the based on the concepts described in Chap.

28

. Hierarchical control turns out to fit very well with this problem and offers a scalable and implementable solution to this long standing problem with high societal value. The two main components of the approach are a recursive, geographic split-up of a given network, and a multilevel control synthesis.

Using dynamic multi-path routing in ad hoc networks, backpressure [

8

] joint scheduling and routing offers considerable gains in throughput over conventional single-path routing algorithms. Indeed, it guarantees to achieve the network capacity and so its throughput performance cannot be bettered by any algorithm. While maximizing network throughput, backpressure routing comes with no guarantee on network delay. This shortcoming of the backpressure network controller motivated the development of the

Layered Backpressure

packet scheduling algorithm for wireless ad hoc networks which is presented here.

Caching of data at various places in a network can improve its performance in terms of access latency. Analysis of the network topology with concepts originating from the field of social network analysis can be adopted to improve caching. Here, we present how new centrality measures can be used for the selection of the so-called mediator nodes to control the caching decisions.

Dynamic complex networks illustrate how ‘agents’ interact by exchanging information, in a network that is constantly changing; an example of such networks is a vehicular ad hoc network. This article investigates the issue of influence propagation in dynamic, complex networks, and in particular, it proposes a method for identifying influential nodes in a network with probabilistic links. Based on control-theoretic concepts, we develop the

range probabilistic control centrality

(RPCC). For evaluation purposes, we used the susceptible, infected, recovered (SIR) model, which is simple model for epidemic spreading assuming no births or deaths, accepting that the incubation period of the infectious agent is instantaneous, and that the duration of infectivity is same as length of the disease; it also assumes a completely homogeneous population with no age, spatial, or social structure. Our experimentation shows that the proposed identification method is able to recognize very effective spreaders. The key feature of these nodes is that they are positioned at the beginning of ‘strong’ paths, upon which paths a large number of other nodes lies.

One of the main issues in assuring plant stability in networked control systems (NCS) is related to the presence of a packet-based network which may introduce communication delay and packet dropouts. We improve the standard network model by considering a more complex communication architecture where different transmission options with different reliability (i.e., packet loss probabilities or amount of delays) are available. This behavior is obtained by introducing quality-of-service (QoS) guarantees in packet-based networks through the differentiated services (DiffServ) approach according to which packets are marked and sent by using either a high- or a low-priority service class. In this work, we investigate the extension of the model predictive control (MPC) to choose both the command value and its assignment to one of the two classes according to the predicted state of the plant and the knowledge of network condition.

A co-simulation framework for networked control systems is presented. The use of different simulation tools for system and communication components allow to build more realistic verification scenarios.

This chapter provides a brief introduction to the Fundamental Problem of Communication, as formulated by Shannon, and evolved over the years into various generalities, including the authors’ views on

Duality of a Source to a Channel.

Suggestions for further research are described, with emphasis on the importance of this duality in nonanticipative or real-time information transmission in both communication and communication for control, of delay-sensitive applications.

Directed information is an information theoretic measure which accounts for the direction of information flow over causal systems with feedback, such as network communication and communication for control problems. In this chapter, we discuss several functional and topological properties of directed information for general Polish spaces (complete separable metric spaces) using the topology of weak convergence of probability measures. These include, convexity/concavity of directed information, weak compactness of families of causally conditioned convolutional distributions, lower semicontinuity of directed information, continuity of directed information, and extremum problems of directed information, including variational equalities [utilized in Blahut–Arimoto algorithm (BAA)], which are important in nonanticipative or real-time joint source-channel coding (JSCC). These basic functional and topological properties of directed information are analogous to those of mutual information. Throughout the chapter, the importance of the properties of directed information is discussed in the context of extremum problems of directed information, such as point to point and network applications.

In this chapter, we introduce the information nonanticipative rate distortion function (RDF), and we compare it with the classical information RDF, identifying certain limitations of the later, with respect to nonanticipative or real-time transmission for delay-sensitive applications. Then, we proceed further to describe applications of nonanticipative RDF in (1) joint source-channel coding (JSCC) using nonanticipative (delayless) transmission, and in (2) bounding the optimal performance theoretically attainable (OPTA) by noncausal and causal codes for general sources. Finally, to facilitate the application of the information nonanticipative RDF in computing the aforementioned bounds and in applying it to JSCC based on nonanticipative transmission, we proceed further to present the expression of the optimal reproduction distribution for nonstationary sources.

Building on the material of previous chapters, a duality of sources and channels, both with memory and feedback is investigated, based on nonanticipative transmission, with respect to excess distortion probability. The methodology is based on (i) identifying the information structures of capacity achieving channel distributions, and encoder functions and (ii) identifying the information structures of optimal reproduction distributions of the nonanticipative rate–distortion function (RDF). An example is presented of a source with memory and a channel with memory, operating optimally, in real-time.

We introduce the verification of hybrid systems as offered by the open-source framework called

ARIADNE

. The

ARIADNE

C++ library exploits approximation techniques based on the theory of computable analysis for implementing formal verification algorithms based on reachability analysis. We demonstrate the tool using a classical example of a controlled water tank system.

In this essay, we discuss the application of formal methods for the verification of properties of control systems designed for autonomous robotic systems. We illustrate our proposal in the context of surgery by considering the automatic execution of a simple action such as puncturing. To prove that a sequence of subtasks planned on preoperative data can successfully accomplish the surgical operation despite model uncertainties, we specify the problem by using hybrid automata. We express the requirements of interest as questions about reachability properties of the hybrid automaton model. Then, we compare the different performance of current state-of-the-art tools for reachability analysis of hybrid automata.

Differential inclusions are mathematical models of nondeterministic continuous-time systems for which no stochastic information on the behavior is known. They arise naturally as reduced models of deterministic systems or as models of components of a distributed system with partial knowledge of the inputs. In order to verify that such systems satisfy safety specifications, we need to compute rigorous over-approximations to the set of reachable states. In this essay, we outline such a method, which gives high-order error for a single time step and a uniform bound on the error over the finite time interval. The approach is based on the approximations of inputs by finitely parametrized functions at each time step.

We propose an extension of the Hybrid I/O Automaton (HIOA) model, where each automaton lives in a generic environment (called world), and interacts with it. We call this object as World Automaton (WA). Each WA occupies a specific position in the world and each position has properties that influence the automaton behavior. Furthermore, the automaton is able to affect the properties of the underlying world. We build our extension in such a way that a WA itself can be an environment for other WAs, thus allowing for nested worlds.

In this chapter, we address the average-consensus problem for a distributed system whose components (nodes) can exchange information via interconnections (links) that form an arbitrary, possibly directed, communication topology (digraph). Specifically, we discuss how the nodes can asymptotically obtain the average of their initial values by describing two different types of algorithms: one based on weight adaptation and one based on ratio consensus.

A research program is formulated for control of distributed and of multilevel systems (including hierarchical systems). Successively, the research topics of integration, modeling, multilevel control, coordination control, distributed control with direct communication between controllers, distributed control without communication, communication and control, informatics, and economics are discussed. In addition, the usefulness of the research areas of system theory, complexity, cognition, and algebra is also mentioned.