File preview
Resource-aware control for cyber-physical systems
Sandra Hirche Adam Molin Institute of Automatic Control Engineering Technische Universit¨ t M¨ nchen a u D-80290 M¨ nchen, Germany u
hirche@tum.de adam.molin@tum.de
Abstract— An efficient usage of available resources is a substantial requirement for the successful control design in cyber-physical systems. Recent results indicate major benefits of event-based control compared to conventional designs, when resources such as communication, energy, and/or computation, are scarce. In this work we consider multiple control loops which share the communication resource. We propose a novel approach for a distributed solution for the resource sharing. In particular, the adaptation ability of event-triggered control in terms of communication traffic elasticity is exploited. This property is used to implement a distributed price exchange mechanism, where event-triggers adapt their thresholds according to the resource constraints.
I. MOTIVATION The recent increased interest in systems has led to various paradigm shifts in the digital control design. The systems under consideration usually consist of a multitude of smallscale integrated entities coupled through common computational and communication resources. The efficient usage of available resources is a prerequisite for the successful operation of such control systems. This fact has stimulated researchers to look for advanced sampling schemes beyond the conventional periodic sampling scheme to reduce resource consumption. It is well known that event-triggered control schemes achieve the same control performance as time-triggered control schemes, while reducing the number of samples significantly. Besides the necessity for an efficient use of resources, other non-functional requirements like self-configurability and adaptability need to be addressed within the design of cyber-physical systems. In the envisioned system, local entities, such as sensor nodes, are aware that a common resource is shared among them. Such awareness is reflected in the capability of adjusting the sampling rate adaptively to reduce resource needs, while maintaining a certain amount of performance. To be more specific, multiple independent control systems are considered here whose control loops are sharing a common resource. Because of the property of adaptation, a distributed algorithm for an event-triggered control system can be developed, where each subsystem adjusts its event-triggering mechanism to optimally meet a global resource constraint. The problem is formulated in the framework of Markov decision processes (MDPs) with an average cost criterion. Each subsystem is modelled as a discrete-time stochastic linear system with a quadratic control cost. The constraint is given by limiting the
total average number of requests of all subsystems. Despite of the relaxation to an average resource constraint which ignores that more requests may occur than available, it turns out that the approximative approach serves as a good approximation for the problem with hard resource constraints. Inspired by distributed optimization and adaptive MDPs, a distributed sample-path based algorithm is proposed. In order to tackle the underlying optimization problem, a dual pricing mechanism forces each subsystem to adjust their eventtriggering thresholds accordingly. Therefore, the subsystems are able to set the optimal rate at which the resource is acquired by only having local information. Apart from the fact that the adaptation mechanism enables the distributed architecture, the local event-triggers are capable to adjust their thresholds according to runtime changes that are often found in real applications. These are for example given by adding or removing control loops during runtime, changes in the resource constraint, or changes in the local system parameters. II. PROBLEM STATEMENT Figure 1 depicts the cyber-physical system under consideration. It shows N independent control subsystems whose feedback loops are connected through a shared communication network. A control subsystem i consists of a process P i , a controller C i that is implemented at the actuator and a sensor S i . The process P i is given by a controlled timehomogeneous Markov chain with state xk taking values in Rni and evolving by the following difference equation
i xi = Ai xi + B i ui + wk , k+1 k k
(1)
where system parameters Ai ∈ Rni ×ni , B i ∈ Rni ×mi ,control i input ui and system noise wk . At each time step k, the k scheduler situated at the sensor station S i decides, whether the controller C i shall update its state. The ith scheduler is i described by the variable δk ∈ {0, 1}, where
i δk =
1 0
update xi is sent k otherwise
i The received signal at the ith controller, zk , is given by i zk =
xi k ∅
i δk = 1 otherwise
(2)
ui k
xi k
C
shared resource
optimization problem (6). By introducing the price variable λ, we have the dual formulation
ˆ λk
i zk
max min (J 1 + λr1 ) + · · · + min (J N + λrN ) − λc. 1 1
λ≥0 γ ,π γ N ,π N
resource manager
For this problem structural properties can be exploited that lead to the adaptive event-triggered control system illustrated in Fig. 2. The controller is a certainty equivalence controller with linear gain Li , and the event-trigger is a threshold policy of the one-step ahead estimation error ei at the controller. k ˆ The estimated price λk is updated by a gradient method, where the gradient is estimated by the recursive formulae yk+1 = yk + ˆ ˆ 1 TW
N i i y (δk+1 − δk−TW +1 ) = hTW (ˆk , ·). i=1
i zk−1
Fig. 1. System model of the cyber-physical system with N control systems closed over a common resource. The resource manager broadcasts the same variable λk to all subsystems.
i E[xk|Zk−1]
T
event-trigger
In order to quantify the resource constraint, the individual average request rate of the ith subsystem is defined as ri = lim sup
T →∞
ei k π i,λk ,∗
ˆ i δk
1 E[ T
T −1 i δk ]. k=0
(3)
i E[xk |Zk ]
Li
ui k
Pi
xi k
By denoting the total average request rate by y, the resource constraint is given by
N
i zk
ˆ broadcast λk
y=
i=1
ri ≤ c,
c > 0.
(4)
i
resource manager ˆ ˆ λk+1 = [λk + βk (ˆk − c)]+ y y yk+1 = hTW (ˆk , ·) ˆ
Each subsystem i ∈ {1, . . . , N } has a cost function J given by the linear quadratic average-cost criterion J i = lim sup
T →∞
1 E T
T −1
xi,T Qi xi + ui,T Qi ui . u k x k k k
k=0
(5)
where Qi > 0, Qi ≥ 0 and (Ai , B i ) is stabilizable and x u i, 1 i, 1 i, 1 the pair (Ai , Qx 2 ) is detectable with Qi = (Qx 2 )T Qx 2 . x It is assumed that the sensor and the controller of the ith subsystem merely have knowledge of the local system parameters. Given the admissible control and event-triggering policies γ i and π i which are causal mappings of the available observation history, the design objective is to minimize the social cost
N
Fig. 2. Complete structure of the cyber-physical system for subsysˆ tem i with optimal event-triggered scheduler π i,λk ,∗ that adapts its law ˆ k . The price λk is broadcasted to each subsystem ˆ according to the price λ from the central resource manager. System block T denotes a 1-step i delay element, E[xk |Zk ] denotes the state estimate based on observai i i tion Zk = [z0 , . . . , zk ].
min γ1, . . . , γN π1 , . . . , πN
Ji
i=1
s.t.
y≤c
(6)
in a distributed fashion by using the resource manager that measures the requests for the resource in order to implement an adaptation mechanism. III. OPTIMAL DISTRIBUTED RESOURCE SHARING By taking ideas from dual decomposition and adaptive MDPs, a distributed algorithm can be developed that solves
IV. OUTLOOK Based on a dual price exchange mechanism, a framework for the design of distributed event-triggered control systems that share a common resource is developed. The distributed approach is realized by an adaptive event-trigger that adjusts its threshold according to the estimated price for the resource. This promising design approach opens up a diversity of problems in the field of control design for cyber-physical systems with resource constraints that need to be investigated in the future. The consideration of multiple resource constraints shared among different subsystems as well as physical coupling between subsystems is part of prospective research. R EFERENCES
[1] A. Molin and S. Hirche, “Adaptive event-triggered control over a shared network,” to be presented at the CDC’12, 2012. [2] A. Molin and S. Hirche, “On the Optimality of Certainty Equivalence for Event-triggered Control Systems,” to appear in IEEE TAC.
Sandra Hirche Adam Molin Institute of Automatic Control Engineering Technische Universit¨ t M¨ nchen a u D-80290 M¨ nchen, Germany u
hirche@tum.de adam.molin@tum.de
Abstract— An efficient usage of available resources is a substantial requirement for the successful control design in cyber-physical systems. Recent results indicate major benefits of event-based control compared to conventional designs, when resources such as communication, energy, and/or computation, are scarce. In this work we consider multiple control loops which share the communication resource. We propose a novel approach for a distributed solution for the resource sharing. In particular, the adaptation ability of event-triggered control in terms of communication traffic elasticity is exploited. This property is used to implement a distributed price exchange mechanism, where event-triggers adapt their thresholds according to the resource constraints.
I. MOTIVATION The recent increased interest in systems has led to various paradigm shifts in the digital control design. The systems under consideration usually consist of a multitude of smallscale integrated entities coupled through common computational and communication resources. The efficient usage of available resources is a prerequisite for the successful operation of such control systems. This fact has stimulated researchers to look for advanced sampling schemes beyond the conventional periodic sampling scheme to reduce resource consumption. It is well known that event-triggered control schemes achieve the same control performance as time-triggered control schemes, while reducing the number of samples significantly. Besides the necessity for an efficient use of resources, other non-functional requirements like self-configurability and adaptability need to be addressed within the design of cyber-physical systems. In the envisioned system, local entities, such as sensor nodes, are aware that a common resource is shared among them. Such awareness is reflected in the capability of adjusting the sampling rate adaptively to reduce resource needs, while maintaining a certain amount of performance. To be more specific, multiple independent control systems are considered here whose control loops are sharing a common resource. Because of the property of adaptation, a distributed algorithm for an event-triggered control system can be developed, where each subsystem adjusts its event-triggering mechanism to optimally meet a global resource constraint. The problem is formulated in the framework of Markov decision processes (MDPs) with an average cost criterion. Each subsystem is modelled as a discrete-time stochastic linear system with a quadratic control cost. The constraint is given by limiting the
total average number of requests of all subsystems. Despite of the relaxation to an average resource constraint which ignores that more requests may occur than available, it turns out that the approximative approach serves as a good approximation for the problem with hard resource constraints. Inspired by distributed optimization and adaptive MDPs, a distributed sample-path based algorithm is proposed. In order to tackle the underlying optimization problem, a dual pricing mechanism forces each subsystem to adjust their eventtriggering thresholds accordingly. Therefore, the subsystems are able to set the optimal rate at which the resource is acquired by only having local information. Apart from the fact that the adaptation mechanism enables the distributed architecture, the local event-triggers are capable to adjust their thresholds according to runtime changes that are often found in real applications. These are for example given by adding or removing control loops during runtime, changes in the resource constraint, or changes in the local system parameters. II. PROBLEM STATEMENT Figure 1 depicts the cyber-physical system under consideration. It shows N independent control subsystems whose feedback loops are connected through a shared communication network. A control subsystem i consists of a process P i , a controller C i that is implemented at the actuator and a sensor S i . The process P i is given by a controlled timehomogeneous Markov chain with state xk taking values in Rni and evolving by the following difference equation
i xi = Ai xi + B i ui + wk , k+1 k k
(1)
where system parameters Ai ∈ Rni ×ni , B i ∈ Rni ×mi ,control i input ui and system noise wk . At each time step k, the k scheduler situated at the sensor station S i decides, whether the controller C i shall update its state. The ith scheduler is i described by the variable δk ∈ {0, 1}, where
i δk =
1 0
update xi is sent k otherwise
i The received signal at the ith controller, zk , is given by i zk =
xi k ∅
i δk = 1 otherwise
(2)
ui k
xi k
C
shared resource
optimization problem (6). By introducing the price variable λ, we have the dual formulation
ˆ λk
i zk
max min (J 1 + λr1 ) + · · · + min (J N + λrN ) − λc. 1 1
λ≥0 γ ,π γ N ,π N
resource manager
For this problem structural properties can be exploited that lead to the adaptive event-triggered control system illustrated in Fig. 2. The controller is a certainty equivalence controller with linear gain Li , and the event-trigger is a threshold policy of the one-step ahead estimation error ei at the controller. k ˆ The estimated price λk is updated by a gradient method, where the gradient is estimated by the recursive formulae yk+1 = yk + ˆ ˆ 1 TW
N i i y (δk+1 − δk−TW +1 ) = hTW (ˆk , ·). i=1
i zk−1
Fig. 1. System model of the cyber-physical system with N control systems closed over a common resource. The resource manager broadcasts the same variable λk to all subsystems.
i E[xk|Zk−1]
T
event-trigger
In order to quantify the resource constraint, the individual average request rate of the ith subsystem is defined as ri = lim sup
T →∞
ei k π i,λk ,∗
ˆ i δk
1 E[ T
T −1 i δk ]. k=0
(3)
i E[xk |Zk ]
Li
ui k
Pi
xi k
By denoting the total average request rate by y, the resource constraint is given by
N
i zk
ˆ broadcast λk
y=
i=1
ri ≤ c,
c > 0.
(4)
i
resource manager ˆ ˆ λk+1 = [λk + βk (ˆk − c)]+ y y yk+1 = hTW (ˆk , ·) ˆ
Each subsystem i ∈ {1, . . . , N } has a cost function J given by the linear quadratic average-cost criterion J i = lim sup
T →∞
1 E T
T −1
xi,T Qi xi + ui,T Qi ui . u k x k k k
k=0
(5)
where Qi > 0, Qi ≥ 0 and (Ai , B i ) is stabilizable and x u i, 1 i, 1 i, 1 the pair (Ai , Qx 2 ) is detectable with Qi = (Qx 2 )T Qx 2 . x It is assumed that the sensor and the controller of the ith subsystem merely have knowledge of the local system parameters. Given the admissible control and event-triggering policies γ i and π i which are causal mappings of the available observation history, the design objective is to minimize the social cost
N
Fig. 2. Complete structure of the cyber-physical system for subsysˆ tem i with optimal event-triggered scheduler π i,λk ,∗ that adapts its law ˆ k . The price λk is broadcasted to each subsystem ˆ according to the price λ from the central resource manager. System block T denotes a 1-step i delay element, E[xk |Zk ] denotes the state estimate based on observai i i tion Zk = [z0 , . . . , zk ].
min γ1, . . . , γN π1 , . . . , πN
Ji
i=1
s.t.
y≤c
(6)
in a distributed fashion by using the resource manager that measures the requests for the resource in order to implement an adaptation mechanism. III. OPTIMAL DISTRIBUTED RESOURCE SHARING By taking ideas from dual decomposition and adaptive MDPs, a distributed algorithm can be developed that solves
IV. OUTLOOK Based on a dual price exchange mechanism, a framework for the design of distributed event-triggered control systems that share a common resource is developed. The distributed approach is realized by an adaptive event-trigger that adjusts its threshold according to the estimated price for the resource. This promising design approach opens up a diversity of problems in the field of control design for cyber-physical systems with resource constraints that need to be investigated in the future. The consideration of multiple resource constraints shared among different subsystems as well as physical coupling between subsystems is part of prospective research. R EFERENCES
[1] A. Molin and S. Hirche, “Adaptive event-triggered control over a shared network,” to be presented at the CDC’12, 2012. [2] A. Molin and S. Hirche, “On the Optimality of Certainty Equivalence for Event-triggered Control Systems,” to appear in IEEE TAC.