Innovations-based Priority Assignment for Control over CAN-like Networks

stability analysis of stochastic prioritized dynamic scheduling for resource-aware heterogeneous multi-loop control systems
Dr.SagaLindberg Profile Pic
Dr.SagaLindberg,Philippines,Researcher
Published Date:18-12-2017
Your Website URL(Optional)
Comment
Innovations-based Priority Assignment for Control over CAN-like Networks Adam Molin, Chithrupa Ramesh, Hasan Esen and Karl Henrik Johansson Abstract—We present an innovations-based prioritization An autonomous vehicle must be capable of sensing its mechanism to efficiently use network resources for data gath- environment and navigating without human input. In ad- ering, without compromising the real-time decision making dition to onboard sensing solutions using Radar, Lidar, capability of the control systems. In the envisioned protocol, GPS, and computer vision, autonomous vehicles must be each sensor assigns the Value of Information (VoI) contained able to receive information from infrastructure nodes and in its current observations for the network as the priority. Tour- naments are used to compare priorities and assign transmission other vehicles in the vicinity. An important challenge is to slots, like in the CAN bus protocol. By using a rollout strategy, incorporate the profusion of data sources in to the CAN we derive feasible algorithms for computing the VoI-based bus. Dynamic or state-based priorities are likely to play an priorities for the case of coupled and decoupled systems. In the important role in ensuring efficient use of the CAN bus. case of decoupled systems, performance guarantees with regard The idea of using the state or measurement of a physical to the control cost of the VoI-based strategy are identified. We illustrate the efficiency of the proposed approach on a system to determine channel access has been prevalent for platooning example in which the vehicles receive measurements some time now 2–4. The deviation in the state from from multiple sensors. the nominal value was used to determine a priority in Try-Once-Discard (TOD) 2. Maximum error first is the I. INTRODUCTION prioritization principle used in TOD, to guarantee input-to- state stability for deterministic systems with disturbances. We consider a scenario where multiple sensors commu- The implementation of the original idea was centralized, nicate over a shared network to perform estimation and and required a network coordinator to collect and compare control tasks. The shared network prevents simultaneous errors from the various physical processes in the network. transmissions from sensors. Prioritising data packets based Distributed implementations of this algorithm and the effect on their content can help to ensure delivery of important of packet losses have been studied in 5 and 6. A similar packets and provide performance guarantees for control and approach has been used in 7 to identify a dynamic utiliza- estimation. We identify a prioritisation scheme that offers a tion policy for the Time Division Multiple Access (TDMA) significant improvement in performance over other typically slots of the IEEE 802.15.4 protocol. An alternate approach used solutions. for stochastic systems over a network was presented and The networked control scenario described above is quite analyzed in 8 for decoupled systems. Other works study typical in automotive systems. An automobile contains many the stochastic stability of controlling decoupled systems with different electronic control units (ECU) for various subsys- error-dependent randomized priorities 9, 10. While the tems, such as antilock braking, cruise control, etc. Each prioritymechanismhasbeenheuristicallychosenin8–10, subsystem communicates with other subsystems, receives our formulation of the priority assignment is based on the measurements from sensors and transmits control signals frameworkofVoI,whichallowsforasystematicandanalytic to actuators. The CAN bus standard specifies the protocol approach to compare with centralized decision policies. for communication between various components within a Our main contribution is the systematic development of vehicle 1. Data transmission on the CAN uses a lossless an innovations-based priority scheme for scheduling multiple bit-wise arbitration method to compare the device IDs, sensor data over a CAN-like networked control system. We which serve as static priorities, and resolve contention be- introduce a specific variant of VoI for calculating prior- tween components that attempt simultaneous transmissions. ities. The concept of VoI is well-known in information Autonomous vehicles and automated driving solutions are analysis and optimal decision making, and is defined as the the next technological leap for automotive systems. These price a decision maker is willing to pay to utilize certain solutions offer higher reliability and faster reaction time, information 11. It is extensively applied in the area of while simplifying the task of driving. information economics 12, 13 and in the field of health care for determining diagnostic value 14. Closer to our A. Molin and K. H. Johansson are with the ACCESS Linnaeus Centre, work, VoI is also used in the problem of sensor selection Electrical Engineering, KTH Royal Institute of Technology, Stockholm, for data fusion 15–17. While the typical VoI formulation Sweden, adammol, kallejkth.se. C. Ramesh is with the Automatic Control Laboratory, ETH Zurich, presumes knowledge of only the statistics of the information, Switzerland, rameshccontrol.ee.ethz.ch. the novelty of our approach is that each sensor takes the H. Esen is with the Technical Research Department, DENSO AUTO- current measurement into account when computing the VoI. MOTIVE Deutschland GmbH, Freisinger Str. 21, 85386 Eching, Germany, h.esendenso-auto.de. Inspired by 18, we use a rollout strategy, which assumesu k per the law Process x =Ax +Bu +w k+1 k k k n p where the statex ∈R and the controlu ∈R . The initial k k y y 1,k M,k value of the state x is assumed to be zero mean Gaussian 0 with covariance R . The process noise w is assumed to be 0 k an independent and identically distributed (i.i.d.) zero-mean ··· Controller S S 1 M Gaussian with covariance R . The measurements y are w j,k δ δ 1,k M,k given by xˆ xˆ xˆ c,k c,k c,k y =C x +v j,k j k j,k y y 1,k M,k m m ×n j j with y ∈R and C ∈R . The measurement noise j,k j CAN-like Bus v is also assumed to be an i.i.d. zero-mean Gaussian j,k xˆ z k c,k sequence with covariance R . We assume that all the v,j primitiverandomvariables,i.e.,x ,w andv ,aremutually 0 k j,k independent. Observer We aim to minimize the finite horizon cost " N−1 X C T T T J =E x Q x + x Q x +u Q u (1) N N 1 k 2 k N k k Fig. 1. Multi-sensor networked control system over CAN-like bus. Sensor k=0 S ,1≤j ≤M transmit data according to the triggering variableδ . The j j,k augmented measurement vector z is used for updating the state estimate k n×n p×p n×n with Q ∈ R , Q ∈ R , and Q ∈ R being 1 2 N xˆ at the observer. c,k positive definite matrices. that the future transmission schedule is predetermined by a B. Priority-based transmission baseline heuristic 19, in order to keep the determination Each sensor assigns a priority to its available data. Tourna- of the VoI feasible. For decoupled systems, we show that ments are then performed to determine which sensors get to the VoI-based priority takes the form of a weighted squared transmit in the N available tournament slots, and in which T innovation at each sensor, where the weighting matrix can be order, based on the assigned priorities. determinedrecursively.Moreover,weshowthattheproposed Let δ ∈ 0,1 denote the channel access outcome of j,k scheme is identical to the optimal centralized scheduling rule the jth sensor. It is defined as based on the rollout strategy. Thus, we have a performance ( guarantee for the prioritization scheme: the control cost is 1 node j wins any of the N tournaments T δ = j,k upper bounded by the cost obtained by the baseline schedule 0 otherwise. used in the rollout strategy. We also highlight how these Furthermore, let us define the last time sensor j transmitted results can be extended to the coupled case of a first-order data to the observer as system through a suitable approximation of the VoI. The rest of this paper is organized as follows. In Sec- τ = maxℓδ = 1 ∧ ℓk (2) j,k j,ℓ tion II, we formulate the problem and introduce the priority assignment scheme. The properties of the priority scheme with τ = −1 when no transmissions of sensor j have j,k N T are analyzed in Section III for decoupled systems, and in occurred yet. Let the vector s ∈1,...,M denote the k Section IV for coupled systems. In Section V, we illustrate indices of the sensors that obtain a transmission slot and z k the efficiency of the proposed innovations-based strategy on denote the data received by the central observer at time k. a cruise control problem in platoons. The data to be transmitted by each sensor will be defined in the following sections. II. PROBLEM FORMULATION Our problem formulation is divided into four parts in C. Control and filtering structure Sections II-A–II-D, which describe the model of the phys- The controller uses the certainty equivalent law ical process and the sensors, the priority-based transmis- sion scheme over a CAN-like network, the controller and u =−L xˆ (3) k k c,k observer, and our novel approach to synthesize priorities, where xˆ is an estimate of x , L = respectively. An overview of the networked control system c,k k k  −1 T T is given in Fig. 1. Q +B Ξ B B Ξ A and Ξ is the standard 2 k+1 k+1 k solution to the finite horizon Riccati equation. The observer A. Multiple sensor LQG framework is based on a Kalman filter that uses the received information We consider a set ofM sensors, indexed byj, 1≤j ≤M z and s . Its exact form will be introduced in the following k k that generate measurements y . The plant state evolves as sections. j,kThe cost function in (1) can be rewritten as defined as N−1 N−1 X X T C T T Δ =E (x −xˆ ) Γ (x −xˆ )I ,s =∅ J =Ex Ξ x +E w Ξ w j ℓ c,ℓ ℓ ℓ c,ℓ j,k k 0 0 k+1 k 0 k ℓ=k k=0 (4) N−1 N−1 X X T T ˆ −E (x −xˆ ) Γ (x −xˆ )I ,s =j. +E (u +L x ) Γ (u +L x ). ℓ c,ℓ ℓ ℓ c,ℓ j,k k k k k k k k k ℓ=k k=0 (6) T ˆ with Γ =B Ξ B+Q , k∈0,...,N−1 (see lemma k k+1 2 III. ANALYSIS OF DECOUPLED SYSTEMS 6.1 of chapter 8 in 20). By using the certainty equivalent law (3) and by noting that the first and second terms in (4) For M decoupled systems, we establish a link between areconstant,wecanrestrictourattentiontotheminimization theVoI-basedpriorityassignmentandtheoptimalscheduling of the following weighted mean square error cost policy minimizing cost J in (5). This enables us to specify " a performance guarantee of the VoI strategy obtained at the N−1 X T end of this section. J =E (x −xˆ ) Γ (x −xˆ ) (5) k c,k k k c,k k=0 A. Model assumptions T T with Γ =L (B Ξ B +Q )L , k ∈0,...,N −1. k k+1 2 k k We consider M isolated dynamical subsystems with ded- icated sensor and controller D. Synthesis of priorities (j) (j) (j) (j) (j) (j) x =A x +B u +w k+1 k k k (7) Our priority assignment scheme aims to minimize the (j) (j) y =C x +v =C x +v j,k j k j,k j,k k cost J in (5), through the use of two complementary (j) (j) (j) (j) n p concepts: VoI and rollout algorithms. The priorities are with x ∈R and u ∈R . The system matrix A k k (1) (M) determined based on the VoI associated with each sensor’s can therefore be written as A = diagA ,...,A . The information. In our scenario, the VoI is defined as the weightingmatricesinthecontrolcost(1),theinputmatrixB, improvement in the cost J due to transmitting a sensor’s and the covariance matrix of the process noise, R can also w data as against not transmitting it. A distinct feature in our be similarly written. approach is that each sensor computes the VoI based on Because of the decoupled system structure, the cost func- its own information structure, which varies based on the tion J defined in (5) can be written as follows   scenario considered. In the decoupled case, it is sufficient M N−1 XX to keep track of its own measurements and the transmission (j) (j) (j) (j) (j) T   J =E (x −xˆ ) Γ (x −xˆ ) (8) k k k k k sequence, whereas in the coupled case, previously transmit- j=1 k=0 ted data from other sensors is also required. (j) (j) where Γ is positive semidefinite and xˆ is the Kalman A full computation of the VoI in this problem setting is a k k (j) estimateofx attimestepk attainedattheremoteobserver. difficult task, in general, because scheduling choices must be k A local Kalman filter at each sensor node keeps track of made for the entire horizon, and not just for the current time (j) x based on the complete observation history at the sensor, instant.Furthermore,schedulingchoicesmadeusingsensors’ k denoted Y =y ,...,y . It computes the estimate local information lead to complex cost-to-go functions and j,k j,0 j,k impede tractability. Thus, we use a rollout strategy, which (j) (j) (j) (j) (j) x˜ =x˜ +K (y −C x˜ ) j,k k kk kk−1 kk−1 assumes that future scheduling decisions are predetermined (j) (j) (j) (j) by a baseline heuristic, to simplify computation of the VoI P = (I (j) −K C )P n kk k kk−1 19. (j) (j) (j) (j) (j) x˜ =A x˜ +B u k k+1k kk−1 In particular for decoupled subsystems, the advantages of (j) (j) (j) (j) T (j) using this suboptimal strategy are: (i) it gives us a means P =A P (A ) +R w k+1k kk to circumvent the curse of dimensionality as the VoI can be (j) (j) (j) (j) T (j) (j) T −1 whereK =P (C ) (C P (C ) +R ) v,j k kk−1 kk−1 computed explicitly, (ii) it allows us to obtain performance (j) (j) and x˜ = 0, P =R . When possible, the local 0−1 0 0−1 guarantees with respect to the baseline schedule, (iii) it (j) estimate x˜ is transmitted to the observer. This estimate kk enables us to determine distributed prioritization schemes, summarizes the new information y ,...,y . The j,τ j,k j,k which are generally difficult to design in the dynamic pro- received signal at time k is then defined as gramming framework.   T     The VoI of sensor j is defined as the difference between T T (s ) (s ) k,1 k,M z = x˜ ··· x˜ . (9) k the cost-to-go when no sensors transmit at time k and when kk kk sensor j transmits at time k. In both cases, we assume that a The observer for subsystem j can be described as baseline schedule s¯ ,...,s¯ is used in future steps. k+1 N−1 ( (j) Thecost-to-gofunctionsarecomputedbasedontheavailable x˜ δ = 1 j,k (j) kk xˆ = (10) information structure I at the sensor j to be defined in j,k c,k (j) xˆ δ = 0 j,k c,kk−1 the subsequent sections. Therefore, the VoI Δ at time k is j(j) (j) (j) (j) (j) (j) where xˆ = (A −B L )xˆ is the linear pre- of the estimate xˆ is independent of previous scheduling k c,k−1 ℓ c,kk−1 (j) (j) diction of the state, xˆ = 0 for δ = 0 and L is the choices, following a transmission at time ℓ. Define the first j,0 c,0 k control gain of subsystem j. transmission time after k of the baseline schedule as ¯ τ¯ = minℓδ = 1∧k ℓ≤N −1, j,k j,ℓ B. Computation of priorities where we define τ¯ =N −1 if no transmission is to occur Our measure for the priority of a sensor is based on the j,k in the future based on the baseline schedule. Then, we only VoI introduced in Section II-D. The decoupled structure of need to consider cost terms untilτ¯ in our VoI calculations, thesystemenablesustocalculateitsvalueexactly.Theinfor- j,k (j) as xˆ , τ¯ ≤ℓ≤N −1, will be the same for δ = 0 and mation structure for computing the VoI isI =Y ,τ . j,k j,k j,k j,k j,k ℓ for δ = 1. Hence, the VoI can be computed as Roughly speaking, the last transmission time τ from (2) j,k j,k summarizes all required information on the triggering of τ¯ −1 j,k X (j) transmissionsforsensorj.Theinformationstructurecanalso ˜ Δ = tr Γ P (14) j ℓ ℓ be recursively expressed as I =I ,y ,δ . j,k+1 j,k j,k+1 j,k ℓ=k Becauseofthefactthatdatafromsensorj isnotbeneficial ˜ where P is recursively given by ℓ for state estimation in the other subsystems i = 6 j, we obtain T the following simplified expression of the VoI based on (6). ˜ P =e˜ e˜ k j,k j,k (j) (j) T ˜ ˜ Δ = j P =A P (A ) (15) ℓ+1 ℓ N−1 X (j) (j) (j) (j) (j) for k ≤ℓτ¯ with e˜ given by (13). T j,k j,k E (x −xˆ ) Γ (x −xˆ )I ,δ = 0 j,k j,k ℓ c,ℓ ℓ ℓ c,ℓ Remark 1: It follows from (14)–(15) that the VoI Δ at j ℓ=k time k takes the form of a quadratic function of e˜ , which N−1 j,k X (j) (j) (j) (j) (j) T can be defined as the discrepancy between the estimates of −E (x −xˆ ) Γ (x −xˆ )I ,δ = 1 j,k j,k ℓ c,ℓ ℓ ℓ c,ℓ (j) x at the sensor j and the remote observer. The discrep- ℓ=k k (11) ancye˜ is a linear combination of the innovationsy˜ with j,k j,n n ∈ τ +1,...,k given by (13). The VoI need only be j,k We implicitly assume that the baseline schedule computed k−τ¯ steps in the future and therefore allows j,k s¯ ,...,s¯ applies in the future, and implies a k+1 N−1 for the consideration of large horizons N. ¯ ¯ transmission outcome of δ ,...,δ for sensor j. j,k+1 j,N−1 The first term of the running cost can be written as C. Performance guarantee (j) (j) (j) (j) (j) T E(x −xˆ ) Γ (x −xˆ )I ,δ = 0 j,k j,k k c,k k k c,k We provide a performance guarantee for the cost using the h i (j) (j) (j) (j) (j) T VoI strategy, in comparison to the cost using the baseline = tr Γ E(x −xˆ )(x −xˆ ) I j,k k k k c,kk−1 c,kk−1 schedule. For this purpose, we introduce the centralized (j) (j) (j) (j) Define, e =x −x˜ and e˜ =x˜ −xˆ . decision rule that chooses N sensors using the complete j,k j,k T k kk kk c,kk−1 Then, we have information I = I ,...,I . Though this scheme k 1,k M,k violates the imposed restrictions in the information structure (j) (j) (j) (j) T E(x −xˆ )(x −xˆ ) I j,k k k c,kk−1 c,kk−1 to compute priorities, it is only used to derive a performance T (12) =E(e +e˜ )(e +e˜ ) I guarantee for the VoI-based prioritization scheme. j,k j,k j,k j,k j,k T T A centralized scheduler that aims to minimise cost J in =Ee e I +e˜ e˜ . j,k j,k j,k j,k j,k (8) assuming a rollout strategy with a deterministic baseline T The last equality holds becauseEe I = 0 and because j,k j,k schedules¯ ,...,s¯ , must solve the following problem: 1 N−1 e˜ is computable for a given I as per j,k j,k M N−1 XX k (j) (j) (j) (j) (j) T X minE (x −xˆ ) Γ (x −xˆ )I (16) k (j) k−n ℓ c,ℓ ℓ ℓ c,ℓ s e˜ = (A ) K y˜ (13) k j,k j,n j,n j=1 ℓ=k n=τ +1 j,k where s is assumed to be a function of y and the side in- k k (j) where y˜ =y −C x˜ is the innovations process of j,n j,n j nn−1 formation xˆ ,P . As the systems are decoupled and kk−1 kk−1 the local Kalman filter at sensor j. As the first term in the we are using a deterministic baseline strategy, measurements last line of (12) cancels out the second term in (11), the of a sensor i6= j are independent of variables appearing in VoI with respect to the running cost can be computed by subsystem j. Therefore, the cost in (16) decomposes into (j) T trΓ e˜ e˜ . j,k k j,k M N−1 X X For the running cost of the second term in (11), we obtain (j) (j) (j) (j) (j) T E (x −xˆ ) Γ (x −xˆ )I . (17) j,k ℓ c,ℓ ℓ ℓ c,ℓ (j) (j) (j) (j) (j) T j=1 ℓ=k E(x −xˆ ) Γ (x −xˆ )I ,δ = 1 j,k j,k k c,k k k c,k h i (j) (j) This implies that each subsystem can evaluate its costs = tr Γ P k kk independently. By selecting the N measurements that yield T Let us now look at the future terms of the cost-to-go func- the greatest benefit reflected by the difference of these cost tion in (11). The observer in (10) implies that the evolution terms, we obtain the optimal decision rule minimizing thecost (8). Hence, this rule coincides with the VoI-based A. Model assumptions priority assignment defined in (11). It should be noted that WeconsiderM sensors,measuringthestateofafirst-order we implicitly excluded cases in which the VoI is identical system, as described by for different subsystems as this occurs with probability zero. x =ax +bu +w , k+1 k k k Hence, we have the following intermediate result. (18) y =c x +v , for 1≤j ≤M . Lemma 1: Let the system be defined as in (7). Then, the j,k j k j,k VoI-based priority assignment is an optimal solution to the The initial value x , process noise w and measurement 0 k minimization problem posed in (16). noises v are all i.i.d. zero mean Gaussian noise processes j,k 2 2 2 Using this result, we provide a performance guarantee for with variances σ , σ and σ , respectively. x w v,j 0 the VoI-based strategy as stated in the subsequent theorem. B. Observer design Theorem 1: Let the system be defined as in (7) and let ¯ We present a design for the observer and filters at each s¯ ,...,s¯ be a baseline scheduler with cost J. Then, 1 N−1 ¯ sensor node for a generic transmission scheme that selects J is an upper bound for the cost resulting from the priority N out ofM sensors for transmission at any timek ≥ 0. As assignment based on the VoI Δ defined in (14) using the T j before, let s denote the indices of the sensors that transmit rollout strategy with baseline schedule s¯ ,...,s¯ . k 1 N−1 their data to the observer at time k. Each sensor transmits a Proof: Let y = y ,...,y . then, the k 1,k+1 M,k+1 local unbiased estimate xˆ and thus, the observer receives h i j,k T centralized information structure follows the recursion T T xˆ ··· xˆ z = .ItgeneratestheBestLinear k s ,k s ,k 1,k N ,k T I =I ,y ,s . k+1 k k k Unbiased Estimate (BLUE) 22, xˆ , using c,k X RO Lets =π (I ) be the rollout strategy based on the heuris- k k k xˆ = α xˆ , (19) c,k j,k j,k tic s¯ ,...,s¯ , 0≤k≤N −1. Let the running cost at 1 N−1 j∈s k time k be defined as P where the weights α must satisfy α = 1 to j,k j,k j∈s k M X (j) (j) (j) (j) (j) ensure an unbiased estimate. The variance of the estimation T c (I ,s ) =E (x −xˆ ) Γ (x −xˆ )I ,s . k k k k k k c,k k k c,k error is given by j=1 2 T RO σ =α P α , (20) s,k k Define the cost-to-go of the rollout strategy as J (I ) c,k k k k   ¯ T and the cost-to-go of the heuristic as J (I ) at time k, k k where α = α ... α and P is k 1,k N ,k s,k T respectively. Similar to the result for rollout algorithms with the error covariance matrix corresponding to the full-state information in 19, we prove inductively that there th transmitted estimates, with the (i,j) element given is a cost improvement of the rollout strategy at each time k, by (P ) =E(x −xˆ )(x −xˆ ). The weights s,k i,j k s ,k k s ,k i,k j,k RO ¯ i.e., J (I )≤J (I ). k k k k are chosen to minimize the estimation error variance and RO ¯ For k = N, we have J (I ) = J (I ) = N N N N we obtain −1 −1 T 0 as there is no terminal cost in J. Assume that α =P U/(U P U), (21) k s,k s,k RO ¯ J (I )≤J (I ) for all I . Then, we have from k+1 k+1 k+1 k+1 k+1 where U is a vector of ones. The observer transmits its (16) estimate xˆ to all the nodes in the network. c,k RO J (I ) k k Each sensor runs a local filter to generate an estimate of RO RO RO k the state, using its measurement historyy along with =Ec (I ,π (I ))+J (I ,y ,π (I ))I j,l k k k k k+1 k k l=0 k k+1 k the information available to the observer. The local filter runs RO RO ¯ ≤Ec (I ,π (I ))+J (I ,y ,π (I ))I k k k k+1 k k+1 k k k k three updates: a prediction update, an initial filtering update ¯ ≤Ec (I ,s¯ )+J (I ,y ,s¯ )I k k k k+1 k k+1 k k and a final filtering update. The prediction update results in ¯ =J (I ) k k the estimate xˆ , as given by j,kk−1 The first inequality is due to the induction hypothesis, while xˆ =axˆ +bu , and xˆ = 0, j,kk−1 j,k−1k−1 k−1 j,0−1 RO 2 2 2 2 the second inequality arises from the fact thatπ (I ) solves k k σ =a σ +σ . j,kk−1 j,k−1k−1 w (16). This completes the induction. (22) As shown in Lemma 1, the centralized decision rule is Here, xˆ denotes the final filtered estimate from j,k−1k−1 identical to using tournaments with the VoI-based priority the previous time step. Next, the sensor node uses its own assignment in (11). Hence, we conclude the proof. measurement y to generate the initial filtered estimate j,k xˆ =xˆ +κ y˜ , j,k j,k j,k j,kk−1 (23) 2 2 2 2 σ =σ −κ σ , IV. ANALYSIS OF COUPLED SYSTEMS j,k j,kk−1 j,k y˜,j,k 2 2 2 2 where y˜ =y −c xˆ , σ =c σ +σ j,k j,k j j,kk−1 y˜,j,k j j,kk−1 v,j 2 2 We now examine the case of coupled subsystems, and and κ =c σ /σ . This is the estimate that each j,k j j,kk−1 y˜,j,k present an extension of our VoI-based prioritization scheme sensor node tries to transmit to the rest of the network. Some for this case. succeed and each node receives xˆ from the observer. The c,k nodes combine it with their own estimates to generate the 40 BLUE final filtered estimate 35 xˆ =β xˆ +(1−β )xˆ , j,kk j,k j,k j,k c,k 30    2   σ ρ β jc,k 2 j,k j,k 25 σ = β 1−β , j,k j,k j,kk 2 ρ σ 1−β jc,k j,k c,k 20 (24) (1) x P k x ˆ 15 pri,k where ρ =E(x −xˆ )(x −xˆ ) = α ρ jc,k k j,k k c,k i,k ij,k i∈s k x ˆ per,k and ρ =E(x −xˆ )(x −xˆ ). The weight β is ij,k k i,k k j,k j,k 10 5 10 15 20 25 30 2 chosen to minimize σ and we obtain Time index j,kk 2 σ −ρ jc,k (1) c,k Fig. 2. Typical sample path of the state x and the state estimates β = . k j,k 2 2 xˆ ,xˆ with priority-based scheduling and with periodic scheduling, σ +σ −2ρ jc,k pri,k per,k c,k j,k respectively, for subsystem 1 with M =2, N =1. T An important term used in the above calculations is ρ =E(x −xˆ )(x −xˆ ), and this can be computed ij,k k i,k k j,k We present a distance tracking example for a platoon of as follows: vehicles. We wish to estimate the distances of M vehicles 2 ρ = a (1−κ c )(1−κ c ) β β ρ ij,k i,k i j,k j i,k−1 j,k−1 ij,k−1 in the platoon to our own vehicle. We model each vehicle’s 2 (j) +(1−β )(1−β )σ distance as an independent random walk (A = 1) subject i,k−1 j,k−1 c,k−1  toazero-meanGaussiandisturbancewithvariance1.Anoisy +β (1−β )ρ +(1−β )β ρ i,k−1 j,k−1 ic,k−1 i,k−1 j,k−1 jc,k−1 (j) 2 distance measurement with C = 1 and v ∼N(0,0.01) j,k +(1−κ c )(1−κ c )σ , i,k i j,k j w from each vehicle’s radar is to be transmitted to us. Our aims 2 (j) where ρ = (1−κ c )(1−κ c )σ . ij,0 i,0 i j,0 j tominimizethecostJ in(8)withΓ = 1forthisdecoupled x 0 k To reduce the computational burden on the sensor nodes, scenario using the observer in (10). The performance is the observer could pre-compute β for all j ∈1,...,M j,k evaluated in Table I for the priority-based scheduling and a and transmit this information along with its estimate xˆ c,k periodic scheduling by conducting a Monte Carlo simulation to the nodes in the network. Then, the nodes can simply with a horizon of N = 100,000 each. The priority-based combine its estimate with the observer’s estimate using (24). scheme assumes a periodic baseline strategy. As stated in Note that this would require the observer to replicate the Theorem 1, the performance J is upper bounded by the priority 2 2 filtering constants σ , κ and σ of each sensor node, j,k performance of the periodic scheme denoted as J . The y˜,j,k j,k periodic and maintain a full cross-covariance matrix of the elements cost is almost halved by the priority scheme. In Fig. 2, a ρ , for every i,j ∈1,...,M. ij,k typical sample path is drawn for the state evolution and its corresponding estimates that use either periodic or priority- C. Computation of priorities based scheduling. Here, we observe that the priority-based scheme adapts faster to critical changes in the distance We now return to the definition of VoI in (6), and apply compared to the periodic schedule. it to a network of coupled subsystems. In this network, the lack of a transmission can also convey information to other sensor nodes and the observer, due to the nature of the M 2 3 4 6 8 scheduling policy. Using this information would render the J 0.5 1.5 3.1 8.5 17 priority innovations process at each sensor node non-Gaussian, and J 1.0 3.0 6.0 15.0 28 periodic make this formulation analytically intractable. We overcome such difficulties by simplifying the information patterns at TABLE I the sensor nodes. PERFORMANCE COMPARISON FOR STATE TRACKING There are three important aspects to our VoI formulation for such a network. Firstly, the information available to Next, we present a cruise control example to illustrate each sensor I is limited to its local information and the j,k the prioritization method for coupled systems. We use a transmitted information from the rest of the network. Any simple mathematical model for the motion of the car, as side information that can be gleamed from the scheduling given by mv˙ = F −F , where m is the total mass of the d policy is not included. Secondly, at any transmission instant, vehicle, v is the speed of the car, F is the force generated the scheduling sequences considered are simply s = j k by the engine torque and F are the disturbance forces d or s = ∅, as in (6). Finally, the future transmission k due to gravity, friction and air drag. The expressions for sequences are obtained from a baseline scheduler. Note that each of these forces and the parameters for our model are this VoI formulation requires each sensor node to replicate taken from 23. By linearizing around v = 27 m/s and 0 the parameters used by the filter at the observer. discretizing the resulting differential equation, we arrive at a first-order state space representation, such as the one in (18), V. AUTOMOTIVE EXAMPLES where the state x = v −v and the control signal u = k k 0 k In order to illustrate the efficiency of our prioritisation υ −υ denote the difference from the respective equilibrium k 0 scheme, we consider two automotive examples. values. The control signal at equilibrium can be computed Distance−1 as υ =b (1−a)v . The system parameters are computed the innovations-based prioritization scheme to the case of 0 0 to be a = 0.9766 and b = 1781.9, and the variances are coupled systems by suitable approximating the VoI. The 2 2 chosen to be σ = σ = 0.01. The car contains a number numerical simulations indicate a significant performance x w 0 of sensors to measure or estimate its own velocity, such as a gain when using the proposed innovations-based approach radar, an accelerometer, a GPS, etc. We assume that there are compared with periodic sensor scheduling. four sensors withc = 1 for 1≤j ≤ 4 and the measurement j REFERENCES noise variances set to 0.01, 0.02, 0.03 and 0.04, respectively. 1 RobertBoschGmbH, Bosch CAN Specification, ver. 2. Stuttgart,1991. Typically, the variance values are chosen to best fit a training 2 G.WalshandH.Ye,“Schedulingofnetworkedcontrolsystems,”IEEE sequence of measurements while parameterizing the plant Control Systems Magazine, vol. 21, no. 1, pp. 57–65, 2001. model and calibrating the sensors. 3 P. G. Otanez, J. R. Moyne, and D. M. Tilbury, “Using deadbands to reduce communication in networked control systems,” in Proc. of the For the purpose of reference tracking, we introduce the American Control Conf., vol. 4, pp. 3015–3020, 2002. integral state i = i + r − xˆ , where xˆ is k+1 k k c,kk c,kk 4 J. K. Yook, D. M. Tilbury, and N. R. Soparkar, “Trading computation the estimate at the observer. Using the augmented state h i for bandwidth: reducing communication in distributed control systems ⊤ ⊤ ⊤ using state estimators,” IEEE Trans. on Control Systems Technology, xˆ i χ = , we design and implement a standard k k c,kk vol. 10, pp. 503–518, July 2002. LQG reference tracking controller. We use the VoI computed 5 M. Tabbara and D. Nesic´, “Input-Output Stability of Networked at every sensor with respect to the observer’s estimate to ControlSystemswithStochasticProtocolsandChannels,”IEEETrans. on Automatic Control, vol. 53, no. 5, pp. 1160–1175, 2008. synthesize the priority of the sensor. We compare the results 6 D. Christmann, R. Gotzhein, S. Siegmund, and F. Wirth, “Realization of a reference change experiment against a static periodic of try-once-discard in wireless multi-hop networks,” IEEE Trans. on scheduler in Fig. 3, and find that the VoI prioritization Industrial Informatics, vol. 10, pp. 17–26, feb 2014. 7 J. Araujo, M. Mazo, A. Anta, P. Tabuada, and K. Johansson, “System improves tracking. A Monte carlo simulation also shows that architectures, protocols and algorithms for aperiodic wireless control theVoIschemeresultsinasmallercost,asshowninTableII. systems,” IEEE Trans. on Industrial Informatics, vol. 10, pp. 175–184, February 2014. 8 C. Ramesh, H. Sandberg, and K. H. Johansson, “Multiple access with 28 r attention-based tournaments for monitoring over wireless networks,” VoI Case: x VoI Case: x ˆc,kk 27 in Proc. of the European Control Conf., pp. 4302–4307, 2009. Per Case: xˆc,kk Per Case: x 26 9 M. Mamduhi, A. Molin, and S. Hirche, “On the stability of prioritized 25 error-based scheduling for resource-constrained networked control 24 systems,”in4thIFACWorkshoponDistributedEstimationandControl 12 14 16 18 20 22 24 26 Time Index in Networked Systems (NecSys 13), pp. 356–362, 2013. -3 x 10 2.5 10 M. H. Mamduhi, A. Molin, and S. Hirche, “Stability analysis of VoI Case: u 2 Per Case: u stochastic prioritized dynamic scheduling for resource-aware hetero- 1.5 geneous multi-loop control systems,” in Decision and Control (CDC), 1 2013 IEEE 52nd Annual Conf. on, pp. 7390–7396, IEEE, 2013. 0.5 0 11 R. A. Howard, “Information value theory,” Systems Science and -0.5 Cybernetics, IEEE Trans. on, vol. 2, no. 1, pp. 22–26, 1966. 12 14 16 18 20 22 24 26 Time Index 12 K. J. Arrow, The Econonmics of Information, vol. 4. Harvard University Press, 1984. Fig. 3. This plot compares the performance of a periodic scheduler against 13 S. Bikchandani, J. G. Riley, and J. Hirshleifer, The analytics of theVoIprioritizationschemeinareferencetrackingexperimentonthecruise uncertainty and information. Cambridge University Press, 2013. control system. We can see that the VoI scheme results in a better tracking 14 M. M. Hunink, M. C. Weinstein, E. Wittenberg, M. F. Drummond, J. S. Pliskin, J. B. Wong, and P. P. Glasziou, Decision making in health performance. and medicine: integrating evidence and values. Cambridge University Press, 2014. 15 V.Gupta,T. H.Chung,B.Hassibi, andR.M.Murray,“On astochastic sensor selection algorithm with applications in sensor scheduling and Scheduler Cost J sensor coverage,” Automatica, vol. 42, no. 2, pp. 251–260, 2006. VoI Prioritization Scheme 0.1902 16 A. Krause and C. Guestrin, “Optimal value of information in graphical Periodic Scheduler 0.5022 models,” Journal of Artificial Intelligence Research, vol. 35, pp. 557– 591, 2009. 17 Y. Zhang and Q. Ji, “Efficient sensor selection for active information TABLE II fusion,” Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE A TABLE COMPARING THE ESTIMATION COSTSJ FROM A MONTE Trans. on, vol. 40, no. 3, pp. 719–728, 2010. CARLO SIMULATION 18 D.Antunes,W.P.M.H.Heemels,andP.Tabuada,“Dynamicprogram- ming formulation of periodic event-triggered control: Performance guaranteesandco-design,”inDecisionandControl(CDC),2012IEEE 51st Annual Conf. on, pp. 7212–7217, Dec 2012. VI. CONCLUSIONS 19 D. P. Bertsekas, Dynamic programming and optimal control, vol. 1. We have shown that innovations-based priority assignment Athena Scientific Belmont, MA, 1995. ˚ 20 K. J. Astro¨m, Introduction to Stochastic Control Theory. Dover strategies for sensor scheduling can improve the control Publications, 2006. performance over a CAN-like bus. We demonstrated how the 21 B. D. O. Anderson and J. B. Moore, Optimal filtering. Courier concept of VoI can be applied to systematically synthesize Corporation, 2012. 22 L. Lyons, D. Gibaut, and P. Clifford, “How to combine correlated dynamic priorities, while obtaining a performance guarantee estimates of a single physical quantity,” Nuclear Instruments and for the resulting cost using rollout algorithms with a static Methods in Physics Research Section A: Accelerators, Spectrometers, baseline schedule. In addition, the priorities were found to be Detectors and Associated Equipment, vol. 270, pp. 110–117, 1988. 23 K. J. Astro¨m and R. M. Murray, Feedback systems: an introduction computed efficiently by a quadratic form of the innovations for scientists and engineers. Princeton university press, 2010. process at each sensor. We also presented an extension of Controls u State x

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.