text: Mutual Information Neural Estimation We would like to thank Martin Arjovsky, C¸ ag˘lar Gu¨lc¸ehre, Andrew M Fraser and Harry L Swinney. Independent coordinates Marcin Moczulski, Negar Rostamzadeh, Thomas Boquet, for strange attractors from mutual information. Physical review Ioannis Mitliagkas, Pedro Oliveira Pinheiro for helpful com- A, 33(2):1134, 1986. ments and advice. Shuyang Gao, Greg Ver Steeg, and Aram Galstyan. Efﬁcient esti- References mation of mutual information for strongly dependent variables. Arxiv preprint arXiv:1411.2003[cs.IT], 2014. A Achille and S Soatto. Emergence of invariance and Arnab Ghosh, Viveka Kulharia, Vinay Namboodiri, Philip HS disentanglement in deep representations. arXiv preprint Torr, and Puneet K Dokania. Multi-agent diverse generative 1706.01350v2[cs.LG], 2017. adversarial networks. arXiv preprint arXiv:1704.02906, 2017. Alexander A Alemi, Ian Fischer, Joshua V Dillon, and Kevin Mur- phy. Deep variational information bottleneck. arXiv preprint Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, arXiv:1612.00410, 2016. David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural Suguru Arimoto. An algorithm for computing the capacity of information processing systems, pp. 2672–2680, 2014. arbitrary discrete memoryless channels. IEEE Transactions on Information Theory, 18(1):14–20, 1972. L Gyo¨rﬁ and E. C van der Meulen. Density-free convergence properties of various estimators of entropy. Computational A Banerjee. On baysian bounds. ICML, pp. 81–88, 2006. Statistics and Data Analysis, 5:425?436, 1987. David Barber and Felix Agakov. The im algorithm: a variational K Hornik. Multilayer feedforward networks are universal approxi- approach to information maximization. In Proceedings of the mators. Neural Networks, 2:359–366, 1989. 16th International Conference on Neural Information Process- ing Systems, pp. 201–208. MIT Press, 2003. Aapo Hyva¨rinen, Juha Karhunen, and Erkki Oja. Independent component analysis, volume 46. John Wiley & Sons, 2004. Mohamed Ishmael Belghazi, Sai Rajeswar, Olivier Mastropietro, Jovana Mitrovic, Negar Rostamzadeh, and Aaron Courville. Sergey Ioffe and Christian Szegedy. Batch normalization: Acceler- Hierarchical adversarially learned inference. arXiv preprint ating deep network training by reducing internal covariate shift. arXiv:1802.01071, 2018. CoRR, abs/1502.03167, 2015. URL http://arxiv.org/ Atul J Butte and Isaac S Kohane. Mutual information relevance abs/1502.03167. networks: functional genomic clustering using pairwise entropy K Kandasamy, A Krishnamurthy, B Poczos, L Wasserman, and measurements. In Pac Symp Biocomput, volume 5, pp. 26, J.M Robins. Nonparametric von mises estimators for entropies, 2000. divergences and mutual informations. NIPS, 2017. Matthew Chalk, Olivier Marre, and Gasper Tkacik. Relevant sparse codes with variational information bottleneck. In Advances in Amor Keziou. Dual representation of ¨I-divergences and applica- Neural Information Processing Systems, pp. 1957–1965, 2016. tions. 336:857–862, 05 2003. Tong Che, Yanran Li, Athul Paul Jacob, Yoshua Bengio, and Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic Wenjie Li. Mode regularized generative adversarial networks. optimization. CoRR, abs/1412.6980, 2014. URL http:// arXiv preprint arXiv:1612.02136, 2016. arxiv.org/abs/1412.6980. Gal Chechik, Amir Globerson, Naftali Tishby, and Yair Weiss. In- Justin B Kinney and Gurinder S Atwal. Equitability, mutual infor- formation bottleneck for gaussian variables. Journal of Machine mation, and the maximal information coefﬁcient. Proceedings Learning Research, 6(Jan):165–188, 2005. of the National Academy of Sciences, 111(9):3354–3359, 2014. Djork-Arne´ Clevert, Thomas Unterthiner, and Sepp Hochreiter. Artemy Kolchinsky, Brendan D Tracey, and David H Wolpert. Non- Fast and accurate deep network learning by exponential linear linear information bottleneck. arXiv preprint arXiv:1705.02436, units (elus). CoRR, abs/1511.07289, 2015. 2017. Georges A Darbellay and Igor Vajda. Estimation of the information Alexander Kraskov, Harald Sto¨gbauer, and Peter Grassberger. Es- by an adaptive partitioning of the observation space. IEEE timating mutual information. Physical review E, 69(6):066138, Transactions on Information Theory, 45(4):1315–1321, 1999. 2004. Jeff Donahue, Philipp Kra¨henbu¨hl, and Trevor Darrell. Adversarial Solomon Kullback. Information theory and statistics. Courier feature learning. arXiv preprint arXiv:1605.09782, 2016. Corporation, 1997. M.D Donsker and S.R.S Varadhan. Asymptotic evaluation of certain markov process expectations for large time, iv. Com- Abhishek Kumar, Prasanna Sattigeri, and P Thomas Fletcher. Im- munications on Pure and Applied Mathematics, 36(2):183?212, proved semi-supervised learning with gans using manifold in- 1983. variances. arXiv preprint arXiv:1705.08850, 2017. Vincent Dumoulin, Ishmael Belghazi, Ben Poole, Alex Lamb, Mar- Nojun Kwak and Chong-Ho Choi. Input feature selection by mu- tin Arjovsky, Olivier Mastropietro, and Aaron Courville. Ad- tual information based on parzen window. IEEE transactions on versarially learned inference. arXiv preprint arXiv:1606.00704, pattern analysis and machine intelligence, 24(12):1667–1671, 2016. 2002. ##LTLine##

text: Mutual

text: Information

text: Neural

text: Estimation

text: We

text: would

text: like

text: to

text: thank

text: Martin

text: Arjovsky,

text: C¸

text: ag˘lar

text: Gu¨lc¸ehre,

text: Andrew

text: M

text: Fraser

text: and

text: Harry

text: L

text: Swinney.

text: Independent

text: coordinates

text: Marcin

text: Moczulski,

text: Negar

text: Rostamzadeh,

text: Thomas

text: Boquet,

text: for

text: strange

text: attractors

text: from

text: mutual

text: information.

text: Physical

text: review

text: Ioannis

text: Mitliagkas,

text: Pedro

text: Oliveira

text: Pinheiro

text: for

text: helpful

text: com-

text: A,

text: ments

text: and

text: advice.

text: Shuyang

text: Gao,

text: Greg

text: Ver

text: Steeg,

text: and

text: Aram

text: Galstyan.

text: Efﬁcient

text: esti-

text: References

text: mation

text: of

text: mutual

text: information

text: for

text: strongly

text: dependent

text: variables.

text: Arxiv

text: preprint

text: A

text: Achille

text: and

text: S

text: Soatto.

text: Emergence

text: of

text: invariance

text: and

text: Arnab

text: Ghosh,

text: Viveka

text: Kulharia,

text: Vinay

text: Namboodiri,

text: Philip

text: HS

text: disentanglement

text: in

text: deep

text: representations.

text: arXiv

text: preprint

text: Torr,

text: and

text: Puneet

text: K

text: Dokania.

text: Multi-agent

text: diverse

text: generative

text: adversarial

text: networks.

text: arXiv

text: preprint

text: Alexander

text: A

text: Alemi,

text: Ian

text: Fischer,

text: Joshua

text: V

text: Dillon,

text: and

text: Kevin

text: Mur-

text: phy.

text: Deep

text: variational

text: information

text: bottleneck.

text: arXiv

text: preprint

text: Ian

text: Goodfellow,

text: Jean

text: Pouget-Abadie,

text: Mehdi

text: Mirza,

text: Bing

text: Xu,

text: David

text: Warde-Farley,

text: Sherjil

text: Ozair,

text: Aaron

text: Courville,

text: and

text: Yoshua

text: Bengio.

text: Generative

text: adversarial

text: nets.

text: In

text: Advances

text: in

text: neural

text: Suguru

text: Arimoto.

text: An

text: algorithm

text: for

text: computing

text: the

text: capacity

text: of

text: information

text: processing

text: systems,

text: pp.

text: arbitrary

text: discrete

text: memoryless

text: channels.

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: L

text: Gyo¨rﬁ

text: and

text: E.

text: C

text: van

text: der

text: Meulen.

text: Density-free

text: convergence

text: properties

text: of

text: various

text: estimators

text: of

text: entropy.

text: Computational

text: A

text: Banerjee.

text: On

text: baysian

text: bounds.

text: ICML,

text: pp.

text: Statistics

text: and

text: Data

text: Analysis,

text: David

text: Barber

text: and

text: Felix

text: Agakov.

text: The

text: im

text: algorithm:

text: a

text: variational

text: K

text: Hornik.

text: Multilayer

text: feedforward

text: networks

text: are

text: universal

text: approxi-

text: approach

text: to

text: information

text: maximization.

text: In

text: Proceedings

text: of

text: the

text: mators.

text: Neural

text: Networks,

text: International

text: Conference

text: on

text: Neural

text: Information

text: Process-

text: ing

text: Systems,

text: pp.

text: MIT

text: Press,

text: Aapo

text: Hyva¨rinen,

text: Juha

text: Karhunen,

text: and

text: Erkki

text: Oja.

text: Independent

text: component

text: analysis,

text: volume

text: John

text: Wiley

text: Sons,

text: Mohamed

text: Ishmael

text: Belghazi,

text: Sai

text: Rajeswar,

text: Olivier

text: Mastropietro,

text: Jovana

text: Mitrovic,

text: Negar

text: Rostamzadeh,

text: and

text: Aaron

text: Courville.

text: Sergey

text: Ioffe

text: and

text: Christian

text: Szegedy.

text: Batch

text: normalization:

text: Acceler-

text: Hierarchical

text: adversarially

text: learned

text: inference.

text: arXiv

text: preprint

text: ating

text: deep

text: network

text: training

text: by

text: reducing

text: internal

text: covariate

text: shift.

text: CoRR,

text: URL

text: Atul

text: J

text: Butte

text: and

text: Isaac

text: S

text: Kohane.

text: Mutual

text: information

text: relevance

text: networks:

text: functional

text: genomic

text: clustering

text: using

text: pairwise

text: entropy

text: K

text: Kandasamy,

text: A

text: Krishnamurthy,

text: B

text: Poczos,

text: L

text: Wasserman,

text: and

text: measurements.

text: In

text: Pac

text: Symp

text: Biocomput,

text: volume

text: pp.

text: J.M

text: Robins.

text: Nonparametric

text: von

text: mises

text: estimators

text: for

text: entropies,

text: divergences

text: and

text: mutual

text: informations.

text: NIPS,

text: Matthew

text: Chalk,

text: Olivier

text: Marre,

text: and

text: Gasper

text: Tkacik.

text: Relevant

text: sparse

text: codes

text: with

text: variational

text: information

text: bottleneck.

text: In

text: Advances

text: in

text: Amor

text: Keziou.

text: Dual

text: representation

text: of

text: ¨I-divergences

text: and

text: applica-

text: Neural

text: Information

text: Processing

text: Systems,

text: pp.

text: tions.

text: Tong

text: Che,

text: Yanran

text: Li,

text: Athul

text: Paul

text: Jacob,

text: Yoshua

text: Bengio,

text: and

text: Diederik

text: P.

text: Kingma

text: and

text: Jimmy

text: Ba.

text: Adam:

text: A

text: method

text: for

text: stochastic

text: Wenjie

text: Li.

text: Mode

text: regularized

text: generative

text: adversarial

text: networks.

text: optimization.

text: CoRR,

text: URL

text: arXiv

text: preprint

text: Gal

text: Chechik,

text: Amir

text: Globerson,

text: Naftali

text: Tishby,

text: and

text: Yair

text: Weiss.

text: In-

text: Justin

text: B

text: Kinney

text: and

text: Gurinder

text: S

text: Atwal.

text: Equitability,

text: mutual

text: infor-

text: formation

text: bottleneck

text: for

text: gaussian

text: variables.

text: Journal

text: of

text: Machine

text: mation,

text: and

text: the

text: maximal

text: information

text: coefﬁcient.

text: Proceedings

text: Learning

text: Research,

text: of

text: the

text: National

text: Academy

text: of

text: Sciences,

text: Djork-Arne´

text: Clevert,

text: Thomas

text: Unterthiner,

text: and

text: Sepp

text: Hochreiter.

text: Artemy

text: Kolchinsky,

text: Brendan

text: D

text: Tracey,

text: and

text: David

text: H

text: Wolpert.

text: Non-

text: Fast

text: and

text: accurate

text: deep

text: network

text: learning

text: by

text: exponential

text: linear

text: linear

text: information

text: bottleneck.

text: arXiv

text: preprint

text: units

text: (elus).

text: CoRR,

text: Georges

text: A

text: Darbellay

text: and

text: Igor

text: Vajda.

text: Estimation

text: of

text: the

text: information

text: Alexander

text: Kraskov,

text: Harald

text: Sto¨gbauer,

text: and

text: Peter

text: Grassberger.

text: Es-

text: by

text: an

text: adaptive

text: partitioning

text: of

text: the

text: observation

text: space.

text: IEEE

text: timating

text: mutual

text: information.

text: Physical

text: review

text: E,

text: Transactions

text: on

text: Information

text: Theory,

text: Jeff

text: Donahue,

text: Philipp

text: Kra¨henbu¨hl,

text: and

text: Trevor

text: Darrell.

text: Adversarial

text: Solomon

text: Kullback.

text: Information

text: theory

text: and

text: statistics.

text: Courier

text: feature

text: learning.

text: arXiv

text: preprint

text: Corporation,

text: M.D

text: Donsker

text: and

text: S.R.S

text: Varadhan.

text: Asymptotic

text: evaluation

text: of

text: certain

text: markov

text: process

text: expectations

text: for

text: large

text: time,

text: iv.

text: Com-

text: Abhishek

text: Kumar,

text: Prasanna

text: Sattigeri,

text: and

text: P

text: Thomas

text: Fletcher.

text: Im-

text: munications

text: on

text: Pure

text: and

text: Applied

text: Mathematics,

text: proved

text: semi-supervised

text: learning

text: with

text: gans

text: using

text: manifold

text: in-

text: variances.

text: arXiv

text: preprint

text: Vincent

text: Dumoulin,

text: Ishmael

text: Belghazi,

text: Ben

text: Poole,

text: Alex

text: Lamb,

text: Mar-

text: Nojun

text: Kwak

text: and

text: Chong-Ho

text: Choi.

text: Input

text: feature

text: selection

text: by

text: mu-

text: tin

text: Arjovsky,

text: Olivier

text: Mastropietro,

text: and

text: Aaron

text: Courville.

text: Ad-

text: tual

text: information

text: based

text: on

text: parzen

text: window.

text: IEEE

text: transactions

text: on

text: versarially

text: learned

text: inference.

text: arXiv

text: preprint

text: pattern

text: analysis

text: and

text: machine

text: intelligence,

text: ##LTLine##


text: In practice, the variance can be regarded as the power of signals. Therefore, the message importance transfer capacity in the Theorem 1 may be applied to guide the signal transfer processing with an additive disturbance. V. CONCLUSION In this paper, we investigated the information transfer prob- lem in big data and proposed an information measure, i.e., MID. Furthermore, this information measure has its own dra- matic characteristics on paying more attention to the message importance hidden in big data. This makes the information measure as a promising tool for information transfer measure in big data. We presented the message importance transfer capacity measured by the MID which can give an upper bound for the information transfer with disturbance. Furthermore, we employed the MID to discuss the caching size selection in MEC. In addition, the MID was extended to the continuous case to investigate the correlation of message importance in the information transfer process. ACKNOWLEDGMENT We indeed appreciate the support of the China Major State Basic Research Development Program (973 Program) No.2012CB316100(2), and the National Natural Science Foun- dation of China (NSFC) No. 61771283. REFERENCES [1] Y. Bu, S. Zou, and V. V. Veeravalli, “Linear-complexity exponentially- consistent tests for universal outlying sequence detection,” in Proc. 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, June. 2017, pp. 988–992. [2] P. Fan, Y. Dong, J. Lu, and S. Liu, “Message importance measure and its application to minority subset detection in big data,” in Proc. IEEE Globecom Workshops (GC Wkshps), Washington D.C., USA, Dec. 2016, pp 1–5. [3] K. M. Carter, R. Raich, and A. O. Hero, “On local intrinsic dimension estimation and its applications,” IEEE Trans. Signal Process., vol. 58, no. 2, pp. 650–663, Feb. 2010. [4] S. Liu, R. She, P. Fan, and K. B. Letaief. (2017). “Non-parametric mes- sage important measure: storage code design and transmission planning for big data. [Online]. Available: https://arxiv.org/abs/1709.10280 [5] R. She, S. Y. Liu, and P. Fan, “Amplifying inter-message distance: on information divergence measures in big data,” IEEE Access, vol. 5, pp. 24105–24119, Nov. 2017. [6] L. Zhao, Y. H. Kim, H. H. Permuter, and T. Weissman, “Universal estimation of directed information,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Austin, USA, June. 2010, pp. 230–234. [7] T. Schreiber, “Measuring information transfer,” Physical Review Letters, vol. 85, no. 2, pp. 461–464, July, 2000. [8] S. Sinha and U. Vaidya, “Causality preserving information transfer measure for control dynamical system, in Proc. IEEE 55th Conference on Decision and Control (CDC) , Las Vegas, USA, Dec. 2016, pp. 7329– 7334. [9] S. Huang, A. Makur, L. Zheng, and G. W. Wornell, “An information- theoretic approach to universal feature selection in high-dimensional inference,” in Proc. 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, June. 2017, pp. 1336–1340. [10] L. Liu, Z. Chang, X. Guo, and T. Ristaniemi, “Multi-objective opti- mization for computation ofﬂoading in mobile-edge computing, In Proc. IEEE Symposium on Computers and Communications (ISCC), Heraklion, Greece, July. 2017, pp 832–837.

text: In

label: paragraph

text: practice,

text: the

text: variance

text: can

text: be

text: regarded

text: as

text: the

text: power

text: of

text: signals.

text: Therefore,

text: the

text: message

text: importance

text: transfer

text: capacity

text: in

text: the

text: Theorem

text: may

text: be

text: applied

text: to

text: guide

text: the

text: signal

text: transfer

text: processing

text: with

text: an

text: additive

text: disturbance.

text: V.

label: section

text: CONCLUSION

text: In

text: this

text: paper,

text: we

text: investigated

text: the

text: information

text: transfer

text: prob-

text: lem

text: in

text: big

text: data

text: and

text: proposed

text: an

text: information

text: measure,

text: i.e.,

text: MID.

text: Furthermore,

text: this

text: information

text: measure

text: has

text: its

text: own

text: dra-

text: matic

text: characteristics

text: on

text: paying

text: more

text: attention

text: to

text: the

text: message

text: importance

text: hidden

text: in

text: big

text: data.

text: This

text: makes

text: the

text: information

text: measure

text: as

text: a

text: promising

text: tool

text: for

text: information

text: transfer

text: measure

text: in

text: big

text: data.

text: We

text: presented

text: the

text: message

text: importance

text: transfer

text: capacity

text: measured

text: by

text: the

text: MID

text: which

text: can

text: give

text: an

text: upper

text: bound

text: for

text: the

text: information

text: transfer

text: with

text: disturbance.

text: Furthermore,

text: we

text: employed

text: the

text: MID

text: to

text: discuss

text: the

text: caching

text: size

text: selection

text: in

text: MEC.

text: In

text: addition,

text: the

text: MID

text: was

text: extended

text: to

text: the

text: continuous

text: case

text: to

text: investigate

text: the

text: correlation

text: of

text: message

text: importance

text: in

text: the

text: information

text: transfer

text: process.

text: ACKNOWLEDGMENT

text: We

text: indeed

text: appreciate

text: the

text: support

text: of

text: the

text: China

text: Major

text: State

text: Basic

text: Research

text: Development

text: Program

text: Program)

text: and

text: the

text: National

text: Natural

text: Science

text: Foun-

text: dation

text: of

text: China

text: (NSFC)

text: No.

text: REFERENCES

text: Y.

text: Bu,

text: S.

text: Zou,

text: and

text: V.

text: V.

text: Veeravalli,

text: “Linear-complexity

text: exponentially-

text: consistent

text: tests

text: for

text: universal

text: outlying

text: sequence

text: detection,”

text: in

text: Proc.

text: IEEE

text: International

text: Symposium

text: on

text: Information

text: Theory

text: (ISIT),

text: Aachen,

text: Germany,

text: June.

text: pp.

text: P.

text: Fan,

text: Y.

text: Dong,

text: J.

text: Lu,

text: and

text: S.

text: Liu,

text: “Message

text: importance

text: measure

text: and

text: its

text: application

text: to

text: minority

text: subset

text: detection

text: in

text: big

text: data,”

text: in

text: Proc.

text: IEEE

text: Globecom

text: Workshops

text: (GC

text: Wkshps),

text: Washington

text: D.C.,

text: USA,

text: Dec.

text: pp

text: K.

text: M.

text: Carter,

text: R.

text: Raich,

text: and

text: A.

text: O.

text: Hero,

text: “On

text: local

text: intrinsic

text: dimension

text: estimation

text: and

text: its

text: applications,”

text: IEEE

text: Trans.

text: Signal

text: Process.,

text: vol.

text: no.

text: pp.

text: Feb.

text: S.

text: Liu,

text: R.

text: She,

text: P.

text: Fan,

text: and

text: K.

text: B.

text: Letaief.

text: “Non-parametric

text: mes-

text: sage

text: important

text: measure:

text: storage

text: code

text: design

text: and

text: transmission

text: planning

text: for

text: big

text: data.

text: [Online].

text: Available:

text: R.

text: She,

text: S.

text: Y.

text: Liu,

text: and

text: P.

text: Fan,

text: “Amplifying

text: inter-message

text: distance:

text: on

text: information

text: divergence

text: measures

text: in

text: big

text: data,”

text: IEEE

text: Access,

text: vol.

text: pp.

text: Nov.

text: L.

text: Zhao,

text: Y.

text: H.

text: Kim,

text: H.

text: H.

text: Permuter,

text: and

text: T.

text: Weissman,

text: “Universal

text: estimation

text: of

text: directed

text: information,”

text: in

text: Proc.

text: IEEE

text: Int.

text: Symp.

text: Inf.

text: Theory

text: (ISIT),

text: Austin,

text: USA,

text: June.

text: pp.

text: T.

text: Schreiber,

text: “Measuring

text: information

text: transfer,”

text: Physical

text: Review

text: Letters,

text: vol.

text: no.

text: pp.

text: July,

text: S.

text: Sinha

text: and

text: U.

text: Vaidya,

text: “Causality

text: preserving

text: information

text: transfer

text: measure

text: for

text: control

text: dynamical

text: system,

text: in

text: Proc.

text: IEEE

text: Conference

text: on

text: Decision

text: and

text: Control

text: (CDC)

text: Las

text: Vegas,

text: USA,

text: Dec.

text: pp.

text: S.

text: Huang,

text: A.

text: Makur,

text: L.

text: Zheng,

text: and

text: G.

text: W.

text: Wornell,

text: “An

text: information-

text: theoretic

text: approach

text: to

text: universal

text: feature

text: selection

text: in

text: high-dimensional

text: inference,”

text: in

text: Proc.

text: IEEE

text: International

text: Symposium

text: on

text: Information

text: Theory

text: (ISIT),

text: Aachen,

text: Germany,

text: June.

text: pp.

text: L.

text: Liu,

text: Z.

text: Chang,

text: X.

text: Guo,

text: and

text: T.

text: Ristaniemi,

text: “Multi-objective

text: opti-

text: mization

text: for

text: computation

text: ofﬂoading

text: in

text: mobile-edge

text: computing,

text: In

text: Proc.

text: IEEE

text: Symposium

text: on

text: Computers

text: and

text: Communications

text: (ISCC),

text: Heraklion,

text: Greece,

text: July.

text: pp


text: sufﬁcient condition for the system stability, ﬁnd the steady- ∆(t) K4 state distribution of the underlying state-space, and give closed K3 form expressions for the average peak age and a lower bound on the average age of the regular stream and compare them K2 to the average age of the high priority stream. Q3 Q4 This paper is structured as follows: in Section , we start by deﬁning the model and the different variables needed in K1 our study. In Section we derive the stability condition of Q2 the system and its stationary distribution. The closed form Z3 Z4 ethxepraevsesriaognes aogfetohfethaveerreagguelapresatkreaamgeaarnedcothmepulotwederinbSoeucntdionon. ∆0 Q1 X3 T3X4 T4 Finally, in Section we present numerical results of our results. 0 t1 D1 t2 t(cid:48)1 t3 D1(cid:48) D2 t(cid:48)2D2(cid:48) t(cid:48)3 D3(cid:48) D3 t(cid:48)4t4 D4(cid:48) D4 t II. SYSTEM MODEL We consider a source that generates packets (or updates) System busy serving stream U 2 according to a Poisson process of rate λ. Each packet, inde- U pendently of the previous packets, is of type−1 with probability Fig. 1. Variation of the instantaneous age of stream 1. p and of type 2 with probability p = 1 p . We can thus 1 2 1 see our source as generating two independent Poisson streams Uλ1=anλd U+2 λwith(sreaete[s10λ]1).=Asλpn1otaenddiλn2th=e λinpt2rordeuscpteiocnti,vetlhye, pthloet,itthi paancdkeDt iofresftereratmo tUh1e wgehnileeratt(cid:48)iioanndanDdi(cid:48)daerleivtehrey sttiamrtesanodf differen1t strea2ms can be used to model packets of different end times of the ith period dUuring which the system is busy serving packets from stream only. types of content, for example, emergency messages, alerts, 2 error messages, warnings, notices, etc. III. SYSTEM STABILITY AND STATIONARY DISTRIBUTION U We also assume that the updates are sent through a single The fact that we wish to receive all of stream updates U 1 server (or transmitter) queue to a monitor. The service time of and that stream has higher priority and preempts stream U 2 each packet is considered to be exponentially distributed with might lead to an unstable system. In order to derive U U 1 rate µ for stream and rate µ for stream . The difference the necessary and sufﬁcient condition for the stability of the 1 1 2 2 in service rates between the two streams is to account for system we study the Markov chain of the number of packets the possible difference in compression, packet length, etc., in the system (in service and waiting) shown in Fig. 2. In between the two streams. this chain, q is the idle state where the system is completely 0 Given this model, we impose on the transmitter that all empty. States q , i > 0, in the upper row refer to states where U i U (cid:48) packets from stream should be sent. Hence the server the queue is serving a packet from stream while states q , 1 U 1 i applies a FCFS policy on the packets from stream with a i > 0, in the row below correspond to the queue serving a 1 U − buffer to save waiting updates. On the other hand, we assume packet from stream . In both cases there are i 1 stream U U 2 that the information carried by stream is more time sensi- updates waiting in the buffer. 2 1 tive (or has higher priority) and thus we aim at minimizing its The system leaves state q at rate λ to state q when U 0 1 1 average age. To this end, the transmitter is allowed to perform a packet from stream is generated ﬁrst and it leaves q (cid:48) 1 U 0 packet management: in this case we assume the server applies at rate λ to state q when a packet from stream is U 2 1 2 a preemption policy whenever a packet from is generated. generated ﬁrst. However, when the system enters state q , 2 i This means that if a newly generated packet from stream i > 0, three exponential clocks start: a clock with rate µ U U U U 1 ﬁnds the system busy (serving a packet from or ), which corresponds to the service time of the stream packet 2 1 2 1 the server preempts the update currently in service and start being served, a clock with rate λ which corresponds to the U 1 serving the new packet. Moreover, if the preempted packet generation time of stream packets and a clock with rate λ U 1 U 2 belongs to , this packet is placed back at the head of the which corresponds to the generation time of stream packets. U 1 2 -buffer so that it can be served once the system is idle again. If the µ -clock ticks ﬁrst, the system goes to state q − : this 1 U 1 U i 1 If the preempted packet belongs to then it is discarded. means that the current stream packet was delivered and U 2 1 However, if a newly generated -packet ﬁnds the system busy the queue begins the service of the next one in the buffer U 1 serving a -packet, it is placed in the buffer and served when (if there is any). However, if the λ -clock ticks ﬁrst, a new 2 U 1 the system becomes idle. This choice of policy for the age stream update is generated and added to the buffer and 1 sensitive stream is motivated by the conclusion reached in [9] hence the system goes to state q . On the other hand, if the i+1 that for exponentially distributed packet transmission times, λ -clock ticks ﬁrst, the system preempts the packet currently 2 the M/M/1/1 with preemption policy is the optimal policy in service and places it back at the head of the buffer and U among causal policies. starts the service of the newly generated stream update. (cid:48) 2 These ideas are illustrated in part in Fig. 1 which also shows Thus the system goes to state q . When the system enters U (cid:48) i+1 the variation of the instantaneous age of stream . In this a state q , i > 0, two exponential clocks start: the clock with 1 i ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: sufﬁcient

text: condition

text: for

text: the

text: system

text: stability,

text: ﬁnd

text: the

text: steady-

text: ∆(t)

text: state

text: distribution

text: of

text: the

text: underlying

text: state-space,

text: and

text: give

text: closed

text: form

text: expressions

text: for

text: the

text: average

text: peak

text: age

text: and

text: a

text: lower

text: bound

text: on

text: the

text: average

text: age

text: of

text: the

text: regular

text: stream

text: and

text: compare

text: them

text: to

text: the

text: average

text: age

text: of

text: the

text: high

text: priority

text: stream.

text: This

text: paper

text: is

text: structured

text: as

text: follows:

text: in

text: Section

text: we

text: start

text: by

text: deﬁning

text: the

text: model

text: and

text: the

text: different

text: variables

text: needed

text: in

text: our

text: study.

text: In

text: Section

text: we

text: derive

text: the

text: stability

text: condition

text: of

text: the

text: system

text: and

text: its

text: stationary

text: distribution.

text: The

text: closed

text: form

text: ethxepraevsesriaognes

text: ∆0

text: Finally,

text: in

text: Section

text: we

text: present

text: numerical

text: results

text: of

text: our

text: results.

text: t

text: II.

text: SYSTEM

text: MODEL

text: We

text: consider

text: a

text: source

text: that

text: generates

text: packets

text: (or

text: updates)

text: System

text: busy

text: serving

text: stream

text: U

text: according

text: to

text: a

text: Poisson

text: process

text: of

text: rate

text: λ.

text: Each

text: packet,

text: inde-

text: U

text: pendently

text: of

text: the

text: previous

text: packets,

text: is

text: of

text: with

text: probability

text: Fig.

text: Variation

text: of

text: the

text: instantaneous

text: age

text: of

text: stream

text: p

text: and

text: of

text: type

text: with

text: probability

text: p

text: p

text: We

text: can

text: thus

text: see

text: our

text: source

text: as

text: generating

text: two

text: independent

text: Poisson

text: streams

text: pthloet,itthi

text: paancdkeDt

text: iofresftereratmo

text: sttiamrtesanodf

text: can

text: be

text: used

text: to

text: model

text: packets

text: of

text: different

text: end

text: times

text: of

text: the

text: ith

text: period

text: dUuring

text: which

text: the

text: system

text: is

text: busy

text: serving

text: packets

text: from

text: stream

text: only.

text: types

text: of

text: content,

text: for

text: example,

text: emergency

text: messages,

text: alerts,

text: error

text: messages,

text: warnings,

text: notices,

text: etc.

text: III.

text: SYSTEM

text: STABILITY

text: AND

text: STATIONARY

text: DISTRIBUTION

text: U

text: We

text: also

text: assume

text: that

text: the

text: updates

text: are

text: sent

text: through

text: a

text: single

text: The

text: fact

text: that

text: we

text: wish

text: to

text: receive

text: all

text: of

text: stream

text: updates

text: U

text: server

text: (or

text: transmitter)

text: queue

text: to

text: a

text: monitor.

text: The

text: service

text: time

text: of

text: and

text: that

text: stream

text: has

text: higher

text: priority

text: and

text: preempts

text: stream

text: U

text: each

text: packet

text: is

text: considered

text: to

text: be

text: exponentially

text: distributed

text: with

text: might

text: lead

text: to

text: an

text: unstable

text: system.

text: In

text: order

text: to

text: derive

text: U

text: U

text: rate

text: µ

text: for

text: stream

text: and

text: rate

text: µ

text: for

text: stream

text: The

text: difference

text: the

text: necessary

text: and

text: sufﬁcient

text: condition

text: for

text: the

text: stability

text: of

text: the

text: in

text: service

text: rates

text: between

text: the

text: two

text: streams

text: is

text: to

text: account

text: for

text: system

text: we

text: study

text: the

text: Markov

text: chain

text: of

text: the

text: number

text: of

text: packets

text: the

text: possible

text: difference

text: in

text: compression,

text: packet

text: length,

text: etc.,

text: in

text: the

text: system

text: (in

text: service

text: and

text: waiting)

text: shown

text: in

text: Fig.

text: In

text: between

text: the

text: two

text: streams.

text: this

text: chain,

text: q

text: is

text: the

text: idle

text: state

text: where

text: the

text: system

text: is

text: completely

text: Given

text: this

text: model,

text: we

text: impose

text: on

text: the

text: transmitter

text: that

text: all

text: empty.

text: States

text: q

text: i

text: in

text: the

text: upper

text: row

text: refer

text: to

text: states

text: where

text: U

text: i

text: U

text: packets

text: from

text: stream

text: should

text: be

text: sent.

text: Hence

text: the

text: server

text: the

text: queue

text: is

text: serving

text: a

text: packet

text: from

text: stream

text: while

text: states

text: q

text: U

text: i

text: applies

text: a

text: FCFS

text: policy

text: on

text: the

text: packets

text: from

text: stream

text: with

text: a

text: i

text: in

text: the

text: row

text: below

text: correspond

text: to

text: the

text: queue

text: serving

text: a

text: U

text: buffer

text: to

text: save

text: waiting

text: updates.

text: On

text: the

text: other

text: hand,

text: we

text: assume

text: packet

text: from

text: stream

text: In

text: both

text: cases

text: there

text: are

text: i

text: stream

text: U

text: U

text: that

text: the

text: information

text: carried

text: by

text: stream

text: is

text: more

text: time

text: sensi-

text: updates

text: waiting

text: in

text: the

text: buffer.

text: tive

text: (or

text: has

text: higher

text: priority)

text: and

text: thus

text: we

text: aim

text: at

text: minimizing

text: its

text: The

text: system

text: leaves

text: state

text: q

text: at

text: rate

text: λ

text: to

text: state

text: q

text: when

text: U

text: average

text: age.

text: To

text: this

text: end,

text: the

text: transmitter

text: is

text: allowed

text: to

text: perform

text: a

text: packet

text: from

text: stream

text: is

text: generated

text: ﬁrst

text: and

text: it

text: leaves

text: q

text: U

text: packet

text: management:

text: in

text: this

text: case

text: we

text: assume

text: the

text: server

text: applies

text: at

text: rate

text: λ

text: to

text: state

text: q

text: when

text: a

text: packet

text: from

text: stream

text: is

text: U

text: a

text: preemption

text: policy

text: whenever

text: a

text: packet

text: from

text: is

text: generated.

text: generated

text: ﬁrst.

text: However,

text: when

text: the

text: system

text: enters

text: state

text: q

text: i

text: This

text: means

text: that

text: if

text: a

text: newly

text: generated

text: packet

text: from

text: stream

text: i

text: three

text: exponential

text: clocks

text: start:

text: a

text: clock

text: with

text: rate

text: µ

text: U

text: U

text: U

text: U

text: ﬁnds

text: the

text: system

text: busy

text: (serving

text: a

text: packet

text: from

text: or

text: which

text: corresponds

text: to

text: the

text: service

text: time

text: of

text: the

text: stream

text: packet

text: the

text: server

text: preempts

text: the

text: update

text: currently

text: in

text: service

text: and

text: start

text: being

text: served,

text: a

text: clock

text: with

text: rate

text: λ

text: which

text: corresponds

text: to

text: the

text: U

text: serving

text: the

text: new

text: packet.

text: Moreover,

text: if

text: the

text: preempted

text: packet

text: generation

text: time

text: of

text: stream

text: packets

text: and

text: a

text: clock

text: with

text: rate

text: λ

text: U

text: U

text: belongs

text: to

text: this

text: packet

text: is

text: placed

text: back

text: at

text: the

text: head

text: of

text: the

text: which

text: corresponds

text: to

text: the

text: generation

text: time

text: of

text: stream

text: packets.

text: U

text: -buffer

text: so

text: that

text: it

text: can

text: be

text: served

text: once

text: the

text: system

text: is

text: idle

text: again.

text: If

text: the

text: µ

text: -clock

text: ticks

text: ﬁrst,

text: the

text: system

text: goes

text: to

text: state

text: q

text: this

text: U

text: U

text: i

text: If

text: the

text: preempted

text: packet

text: belongs

text: to

text: then

text: it

text: is

text: discarded.

text: means

text: that

text: the

text: current

text: stream

text: packet

text: was

text: delivered

text: and

text: U

text: However,

text: if

text: a

text: newly

text: generated

text: -packet

text: ﬁnds

text: the

text: system

text: busy

text: the

text: queue

text: begins

text: the

text: service

text: of

text: the

text: next

text: one

text: in

text: the

text: buffer

text: U

text: serving

text: a

text: -packet,

text: it

text: is

text: placed

text: in

text: the

text: buffer

text: and

text: served

text: when

text: (if

text: there

text: is

text: any).

text: However,

text: if

text: the

text: λ

text: -clock

text: ticks

text: ﬁrst,

text: a

text: new

text: U

text: the

text: system

text: becomes

text: idle.

text: This

text: choice

text: of

text: policy

text: for

text: the

text: age

text: stream

text: update

text: is

text: generated

text: and

text: added

text: to

text: the

text: buffer

text: and

text: sensitive

text: stream

text: is

text: motivated

text: by

text: the

text: conclusion

text: reached

text: in

text: hence

text: the

text: system

text: goes

text: to

text: state

text: q

text: On

text: the

text: other

text: hand,

text: if

text: the

text: that

text: for

text: exponentially

text: distributed

text: packet

text: transmission

text: times,

text: λ

text: -clock

text: ticks

text: ﬁrst,

text: the

text: system

text: preempts

text: the

text: packet

text: currently

text: the

text: with

text: preemption

text: policy

text: is

text: the

text: optimal

text: policy

text: in

text: service

text: and

text: places

text: it

text: back

text: at

text: the

text: head

text: of

text: the

text: buffer

text: and

text: U

text: among

text: causal

text: policies.

text: starts

text: the

text: service

text: of

text: the

text: newly

text: generated

text: stream

text: update.

text: These

text: ideas

text: are

text: illustrated

text: in

text: part

text: in

text: Fig.

text: which

text: also

text: shows

text: Thus

text: the

text: system

text: goes

text: to

text: state

text: q

text: When

text: the

text: system

text: enters

text: U

text: the

text: variation

text: of

text: the

text: instantaneous

text: age

text: of

text: stream

text: In

text: this

text: a

text: state

text: q

text: i

text: two

text: exponential

text: clocks

text: start:

text: the

text: clock

text: with

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Status Updates in a multi-stream M/G/1/1 preemptive queue Elie Najm Emre Telatar LTHI, EPFL, Lausanne, Switzerland LTHI, EPFL, Lausanne, Switzerland Email: elie.najm@epﬂ.ch Email: emre.telatar@epﬂ.ch Abstract— We consider a source that collects a multiplicity of streams of updates and send them through a network to a In this paper, we assume that an ‘observer’ (which we monitor. However, only a single update can be in the system at will call source), generating updates according to a Poisson a time. Therefore, the transmitter always preempts the packet being served when a new update is generated. We consider process with rate λ, observes M streams of data. At each Poisson arrivals for each stream and a common general service generation instant, the source chooses to ‘observe’ stream i and time, and refer to this system as the multi-stream M/G/1/1 send its observation (update) of this stream with probability queue with preemption. Using the detour ﬂow graph method, p , i = 1, . . . , M. This probability distribution is a design we compute a closed form expression for the average age and i parameter that one can control. Moreover, we assume that the the average peak age of each stream. Moreover, we deduce that system can handle only one update at a time without any buffer although all streams are treated equally from a transmission point of view (they all preempt each other), one can still prioritize to store incoming updates. This means that whenever a new a stream from an age point of view by simply increasing its update is generated and the system is busy, the transmitter generation rate. However, this will increase the sum of the ages preempts the packet being served and starts sending the new which is minimized when all streams have the same update rate. update instead. Since we consider a general service time distri- bution for the updates, we denote this transmission scheme by I. INTRODUCTION M/G/1/1 preemptive queue. It has been shown that for a single- Previous work on status update ( [1]–[6]) used an Age of stream source and exponential update service time, preemption Information (AoI) metric in order to assess the freshness of ensures the lowest average age [2]. However, the work in randomly generated updates sent by one or multiple sources [5] suggests that under the assumption of gamma distributed to a monitor through the network. In these papers, updates are service time, preemption might not be the best policy. In [8], assumed to be generated according to a Poisson process and the authors derive a closed form expression for the average the main metric used to quantif(cid:90)y the age is the time average age of a single-stream source and M/G/1/1 preemptive queue. age (which we will call average age) given by As a generalization of the result in [8], we derive in this paper a closed form expression for the average age and average 1 τ peak age per stream of the multi-stream source M/G/1/1 ∆ = lim ∆(t)dt, (1) τ→∞ τ preemptive queue. To that end we use the detour ﬂow graph 0 method which is also used to ﬁnd an upper bound on the where ∆(t) is the instantaneous age of the last successfully error probability of a Viterbi decoder (see [9]). A special received update. If this update was generated at time u(t) then case of the problem we study here, when the service time − its age at time t is ∆(t) = t u(t). When the system is idle is exponential, was studied in [10], and the average age of or an update is being transmitted then the instantaneous age each stream was obtained in closed form using a stochastic increases linearly with time, as depicted in Fig. 1. Once an hybrid system. Another related work, [11] gives closed form (cid:48) update generated at time t is received by the monitor at t , expressions for the average peak age of multi-stream source (cid:48)i− i ∆(t) drops to the value t t . This results in the sawtooth M/G/1 queues as well as M/G/1/1 queues with blocking. In i i sample path seen in Fig. 1. this last model, if a newly generated update ﬁnds the system Moreover, in [7] the authors introduce another age metric: busy, it is discarded. the average peak age deﬁned as the time average of the In addition to that, given a ﬁxed total update rate λ, we maximum value of the instantaneous age ∆(t) right before show in this work that the lowest if we want to decrease the the reception by the monitor of a new update. In Fig. 1 the age of a certain stream i with respect to other streams we need peak age right before the reception of the jth successfully to increase its update rate (by increasing its choice probability transmitted update is denoted by Kj. Hence the average peak pi) and thus decreasing the update rates of the other streams. age is given by (cid:88) Moreover, if we choose the sum of the ages as our performance metric and we wish to minimize then we prove that we need N 1 to adopt a fair strategy: all streams should be given the same ∆ = lim K . (2) peak N→∞ N j update rate. j=1 ##LTLine## ##LTLine##

text: Status

label: title

text: Updates

text: in

text: a

text: multi-stream

text: preemptive

text: queue

text: Elie

label: author

text: Najm

text: Emre

text: Telatar

text: LTHI,

text: EPFL,

text: Lausanne,

text: Switzerland

text: LTHI,

text: EPFL,

text: Lausanne,

text: Switzerland

text: Email:

text: elie.najm@epﬂ.ch

text: Email:

text: emre.telatar@epﬂ.ch

text: Abstract—

text: We

label: abstract

text: consider

text: a

text: source

text: that

text: collects

text: a

text: multiplicity

text: of

text: streams

text: of

text: updates

text: and

text: send

text: them

text: through

text: a

text: network

text: to

text: a

text: In

text: this

text: paper,

text: we

text: assume

text: that

text: an

text: ‘observer’

text: (which

text: we

text: monitor.

text: However,

text: only

text: a

text: single

text: update

text: can

text: be

text: in

text: the

text: system

text: at

text: will

text: call

text: source),

text: generating

text: updates

text: according

text: to

text: a

text: Poisson

text: a

text: time.

text: Therefore,

text: the

text: transmitter

text: always

text: preempts

text: the

text: packet

text: being

text: served

text: when

text: a

text: new

text: update

text: is

text: generated.

text: We

text: consider

text: process

text: with

text: rate

text: λ,

text: observes

text: M

text: streams

text: of

text: data.

text: At

text: each

text: Poisson

text: arrivals

text: for

text: each

text: stream

text: and

text: a

text: common

text: general

text: service

text: generation

text: instant,

text: the

text: source

text: chooses

text: to

text: ‘observe’

text: stream

text: i

text: and

text: time,

text: and

text: refer

text: to

text: this

text: system

text: as

text: the

text: multi-stream

text: send

text: its

text: observation

text: (update)

text: of

text: this

text: stream

text: with

text: probability

text: queue

text: with

text: preemption.

text: Using

text: the

text: detour

text: ﬂow

text: graph

text: method,

text: p

text: i

text: M.

text: This

text: probability

text: distribution

text: is

text: a

text: design

text: we

text: compute

text: a

text: closed

text: form

text: expression

text: for

text: the

text: average

text: age

text: and

text: i

text: parameter

text: that

text: one

text: can

text: control.

text: Moreover,

text: we

text: assume

text: that

text: the

text: the

text: average

text: peak

text: age

text: of

text: each

text: stream.

text: Moreover,

text: we

text: deduce

text: that

text: system

text: can

text: handle

text: only

text: one

text: update

text: at

text: a

text: time

text: without

text: any

text: buffer

text: although

text: all

text: streams

text: are

text: treated

text: equally

text: from

text: a

text: transmission

text: point

text: of

text: view

text: (they

text: all

text: preempt

text: each

text: other),

text: one

text: can

text: still

text: prioritize

text: to

text: store

text: incoming

text: updates.

text: This

text: means

text: that

text: whenever

text: a

text: new

text: a

text: stream

text: from

text: an

text: age

text: point

text: of

text: view

text: by

text: simply

text: increasing

text: its

text: update

text: is

text: generated

text: and

text: the

text: system

text: is

text: busy,

text: the

text: transmitter

text: generation

text: rate.

text: However,

text: this

text: will

text: increase

text: the

text: sum

text: of

text: the

text: ages

text: preempts

text: the

text: packet

text: being

text: served

text: and

text: starts

text: sending

text: the

text: new

text: which

text: is

text: minimized

text: when

text: all

text: streams

text: have

text: the

text: same

text: update

text: rate.

text: update

text: instead.

text: Since

text: we

text: consider

text: a

text: general

text: service

text: time

text: distri-

text: bution

text: for

text: the

text: updates,

text: we

text: denote

text: this

text: transmission

text: scheme

text: by

text: I.

text: INTRODUCTION

text: preemptive

text: queue.

text: It

text: has

text: been

text: shown

text: that

text: for

text: a

text: single-

text: Previous

text: work

text: on

text: status

text: update

text: used

text: an

text: Age

text: of

text: stream

text: source

text: and

text: exponential

text: update

text: service

text: time,

text: preemption

text: Information

text: (AoI)

text: metric

text: in

text: order

text: to

text: assess

text: the

text: freshness

text: of

text: ensures

text: the

text: lowest

text: average

text: age

text: However,

text: the

text: work

text: in

text: randomly

text: generated

text: updates

text: sent

text: by

text: one

text: or

text: multiple

text: sources

text: suggests

text: that

text: under

text: the

text: assumption

text: of

text: gamma

text: distributed

text: to

text: a

text: monitor

text: through

text: the

text: network.

text: In

text: these

text: papers,

text: updates

text: are

text: service

text: time,

text: preemption

text: might

text: not

text: be

text: the

text: best

text: policy.

text: In

text: assumed

text: to

text: be

text: generated

text: according

text: to

text: a

text: Poisson

text: process

text: and

text: the

text: authors

text: derive

text: a

text: closed

text: form

text: expression

text: for

text: the

text: average

text: the

text: main

text: metric

text: used

text: to

text: the

text: age

text: is

text: the

text: time

text: average

text: age

text: of

text: a

text: single-stream

text: source

text: and

text: preemptive

text: queue.

text: age

text: (which

text: we

text: will

text: call

text: average

text: age)

text: given

text: by

text: As

text: a

text: generalization

text: of

text: the

text: result

text: in

text: we

text: derive

text: in

text: this

text: paper

text: a

text: closed

text: form

text: expression

text: for

text: the

text: average

text: age

text: and

text: average

text: τ

text: peak

text: age

text: per

text: stream

text: of

text: the

text: multi-stream

text: source

text: lim

text: ∆(t)dt,

text: τ→∞

text: τ

text: preemptive

text: queue.

text: To

text: that

text: end

text: we

text: use

text: the

text: detour

text: ﬂow

text: graph

text: method

text: which

text: is

text: also

text: used

text: to

text: ﬁnd

text: an

text: upper

text: bound

text: on

text: the

text: where

text: ∆(t)

text: is

text: the

text: instantaneous

text: age

text: of

text: the

text: last

text: successfully

text: error

text: probability

text: of

text: a

text: Viterbi

text: decoder

text: (see

text: A

text: special

text: received

text: update.

text: If

text: this

text: update

text: was

text: generated

text: at

text: time

text: u(t)

text: then

text: case

text: of

text: the

text: problem

text: we

text: study

text: here,

text: when

text: the

text: service

text: time

text: its

text: age

text: at

text: time

text: t

text: is

text: ∆(t)

text: t

text: u(t).

text: When

text: the

text: system

text: is

text: idle

text: is

text: exponential,

text: was

text: studied

text: in

text: and

text: the

text: average

text: age

text: of

text: or

text: an

text: update

text: is

text: being

text: transmitted

text: then

text: the

text: instantaneous

text: age

text: each

text: stream

text: was

text: obtained

text: in

text: closed

text: form

text: using

text: a

text: stochastic

text: increases

text: linearly

text: with

text: time,

text: as

text: depicted

text: in

text: Fig.

text: Once

text: an

text: hybrid

text: system.

text: Another

text: related

text: work,

text: gives

text: closed

text: form

text: update

text: generated

text: at

text: time

text: t

text: is

text: received

text: by

text: the

text: monitor

text: at

text: t

text: expressions

text: for

text: the

text: average

text: peak

text: age

text: of

text: multi-stream

text: source

text: i

text: ∆(t)

text: drops

text: to

text: the

text: value

text: t

text: t

text: This

text: results

text: in

text: the

text: sawtooth

text: queues

text: as

text: well

text: as

text: queues

text: with

text: blocking.

text: In

text: i

text: i

text: sample

text: path

text: seen

text: in

text: Fig.

text: this

text: last

text: model,

text: if

text: a

text: newly

text: generated

text: update

text: ﬁnds

text: the

text: system

text: Moreover,

text: in

text: the

text: authors

text: introduce

text: another

text: age

text: metric:

text: busy,

text: it

text: is

text: discarded.

text: the

text: average

text: peak

text: age

text: deﬁned

text: as

text: the

text: time

text: average

text: of

text: the

text: In

text: addition

text: to

text: that,

text: given

text: a

text: ﬁxed

text: total

text: update

text: rate

text: λ,

text: we

text: maximum

text: value

text: of

text: the

text: instantaneous

text: age

text: ∆(t)

text: right

text: before

text: show

text: in

text: this

text: work

text: that

text: the

text: lowest

text: if

text: we

text: want

text: to

text: decrease

text: the

text: the

text: reception

text: by

text: the

text: monitor

text: of

text: a

text: new

text: update.

text: In

text: Fig.

text: the

text: age

text: of

text: a

text: certain

text: stream

text: i

text: with

text: respect

text: to

text: other

text: streams

text: we

text: need

text: peak

text: age

text: right

text: before

text: the

text: reception

text: of

text: the

text: jth

text: successfully

text: to

text: increase

text: its

text: update

text: rate

text: (by

text: increasing

text: its

text: choice

text: probability

text: transmitted

text: update

text: is

text: denoted

text: by

text: Kj.

text: Hence

text: the

text: average

text: peak

text: pi)

text: and

text: thus

text: decreasing

text: the

text: update

text: rates

text: of

text: the

text: other

text: streams.

text: age

text: is

text: given

text: by

text: Moreover,

text: if

text: we

text: choose

text: the

text: sum

text: of

text: the

text: ages

text: as

text: our

text: performance

text: metric

text: and

text: we

text: wish

text: to

text: minimize

text: then

text: we

text: prove

text: that

text: we

text: need

text: N

text: to

text: adopt

text: a

text: fair

text: strategy:

text: all

text: streams

text: should

text: be

text: given

text: the

text: same

text: lim

text: K

text: peak

text: N→∞

text: N

text: j

text: update

text: rate.

text: ##LTLine##

text: ##LTLine##


text: [19] M. Z. Romdlony and B. Jayawardhana, “Stabilization with guaranteed Mohamadreza Ahmadi M. Ahmadi joined the In- safety using control Lyapunov-barrier function,” Automatica, vol. 66, stitute for Computational Engineering and Sciences no. Supplement C, pp. 39 – 47, 2016. (ICES) at the University of Texas at Austin as a [20] A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier postdoctoral scholar in Fall 2016. He received his function based quadratic programs for safety critical systems,” IEEE DPhil in Engineering Science (Controls) from the Transactions on Automatic Control, 2016. University of Oxford in Fall 2016 as a member of [21] X. Xu, P. Tabuada, J. W. Grizzle, and A. D. Ames, “Robustness of con- Keble College and a Clarendon Scholar. His current trol barrier functions for safety critical control,” in IFAC-PapersOnLine, research interests are at the intersection of learning vol. 48, no. 27, 2015, pp. 54 – 61, analysis and Design of Hybrid and control, games on Markov decision processes, Systems ADHS. and computational methods for analysis of PDEs. [22] Q. Nguyen and K. Sreenath, “Exponential control barrier functions for enforcing high relative-degree safety-critical constraints,” in 2016 American Control Conference (ACC), July 2016, pp. 322–328. [23] C. Fefferman, Smooth Interpolation of Data by Efﬁcient Algorithms. Boston: Birkha¨user Boston, 2013, pp. 71–84. [24] A. Herbert-Voss, M. J. Hirn, and F. McCollum, “Computing minimal interpolants in C1,1(Rd),” Revista Matematica Iberoamericana, vol. 33, no. 1, pp. 22–69, 2017. [25] J. P. Aubin and H. Frankowska, Set-Valued Analysis. Boston: Birkha¨user, 2009. [26] J. P. Aubin and A. Celina, Differential Inclusions. Springer-Verlag, Berlin, 1984. [27] P. Seiler, “Stability analysis with dissipation inequalities and integral quadratic constraints,” IEEE Transactions on Automatic Control, vol. 60, no. 6, pp. 1704–1709, June 2015. [28] M. Ahmadi, A. Israel, and U. Topcu, “Safety-assessment for physically- viable data-driven models,” in The 56th IEEE Conference on Decision and Control, Melbourne, Australia, Dec 2017. [29] H. Whitney, “Analytic extensions of differentiable functions deﬁned in closed sets,” Transactions of the American Mathematical Society, vol. 36, no. 1, pp. 63–89, 1934. [30] C. L. Fefferman, “A sharp form of Whitney’s extension theorem,” Annals of Mathematics, vol. 161, no. 1, pp. 509–577, 2005. [31] C. Fefferman and B. Klartag, “Fitting a Cm-smooth function to data i,” Rev. Mat. Iberoamericana, vol. 25, no. 1, pp. 49–273, 2009. [32] C. Fefferman and A. Israel, “The jet of an interpolant on a ﬁnite set,” Ufuk Topcu Ufuk Topcu joined the Department of Rev. Mat. Iberoamericana, vol. 27, no. 1, pp. 355–360, 2011. Aerospace Engineering at the University of Texas at [33] C. Fefferman, “Fitting a Cm -smooth function to data, III,” Annals of Austin as an assistant professor in Fall 2015. He Mathematics, vol. 170, no. 1, pp. 427–441, 2009. received his Ph.D. degree from the University of [34] C. de Boor, A Practical Guide to Splines, ser. Applied Mathematical California at Berkeley in 2008. He held research Sciences. Springer New York, 2001. positions at the University of Pennsylvania and Cal- [35] P. Lancaster and K. Sˇalkauskas, Curve and Surface Fitting: An Intro- ifornia Institute of Technology. His research focuses duction, ser. Computational mathematics and applications. Academic on the theoretical, algorithmic and computational Press, 1986. aspects of design and veriﬁcation of autonomous [36] G. Farin, “Cubic spline interpolation,” in Curves and Surfaces for systems through novel connections between formal Computer-Aided Geometric Design (Third Edition), third edition ed., methods, learning theory and controls. G. Farin, Ed. Boston: Academic Press, 1993, pp. 133 – 155. Arie Israel Arie Israel joined the Department of [37] E. Grosse, “Tensor spline approximation,” Linear Algebra and its Mathematics at the University of Texas at Austin as Applications, vol. 34, no. Supplement C, pp. 29 – 41, 1980. an assistant professor in Fall 2014. He received his [38] A. F. Filippov, Differential Equations with Discontinuous Right-Hand Ph.D. degree from Princeton University in 2011, and Sides, ser. Mathematics and Its Applications. Kluwer, 1988. held a postdoctoral position at New York University. [39] P. Glotfelter, J. Cortes, and M. Egerstedt, “Nonsmooth barrier functions His primary research focus has been on the theoreti- with applications to multi-robot systems,” IEEE Control Systems Letters, cal and algorithmic foundations of extension and in- vol. 1, no. 2, pp. 310–315, Oct 2017. terpolation problems in smooth function spaces. His [40] M. Putinar, “Positive polynomials on compact semi-algebraic sets,” work draws on tools from Harmonic Analysis and Indiana University Mathematics Journal, vol. 42, no. 3, pp. 969–984, PDE. Recently he has been exploring applications 1993. of his work to machine learning and control theory. [41] M. Schweighofer, “Optimization of polynomials on compact semialge- braic sets,” SIAM Journal on Optimization, vol. 15, no. 3, pp. 805–825, 2005. [42] P. Parrilo, “Structured semideﬁnite programs and semialgebraic ge- ometry methods in robustness and optimization,” Ph.D. dissertation, California Institute of Technology, 2000. [43] S. Prajna, A. Papachristodoulou, P. Seiler, and P. Parrilo, “SOSTOOLS: Sum of squares optimization toolbox for MATLAB V3.00,” 2013. [44] J. F. Sturm, “Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones,” 1998. [45] J. P. Aubin, A. M. Bayen, and P. Saint-Pierre, Viability Theory: New Directions, 2nd ed. Springer, 2011. [46] R. L. Smith, L. M. Howser, and J. M. Price, A smoothing algorithm using cubic spline functions. Washington: National Aeronautics and Space Administration, Technical Report, 1974. [47] M. Posa, M. Tobenkin, and R. Tedrake, “Stability analysis and control of rigid-body systems with impacts and friction,” IEEE Transactions on Automatic Control, vol. 61, no. 6, pp. 1423–1437, 2016. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

label: reference

text: M.

text: Z.

text: Romdlony

text: and

text: B.

text: Jayawardhana,

text: “Stabilization

text: with

text: guaranteed

text: Mohamadreza

text: Ahmadi

text: M.

text: Ahmadi

text: joined

text: the

text: In-

text: safety

text: using

text: control

text: Lyapunov-barrier

text: function,”

text: Automatica,

text: vol.

text: stitute

text: for

text: Computational

text: Engineering

text: and

text: Sciences

text: no.

text: Supplement

text: C,

text: pp.

text: (ICES)

text: at

text: the

text: University

text: of

text: Texas

text: at

text: Austin

text: as

text: a

text: A.

text: D.

text: Ames,

text: X.

text: Xu,

text: J.

text: W.

text: Grizzle,

text: and

text: P.

text: Tabuada,

text: “Control

text: barrier

text: postdoctoral

text: scholar

text: in

text: Fall

text: He

text: received

text: his

text: function

text: based

text: quadratic

text: programs

text: for

text: safety

text: critical

text: systems,”

text: IEEE

text: DPhil

text: in

text: Engineering

text: Science

text: (Controls)

text: from

text: the

text: Transactions

text: on

text: Automatic

text: Control,

text: University

text: of

text: Oxford

text: in

text: Fall

text: as

text: a

text: member

text: of

text: X.

text: Xu,

text: P.

text: Tabuada,

text: J.

text: W.

text: Grizzle,

text: and

text: A.

text: D.

text: Ames,

text: “Robustness

text: of

text: con-

text: Keble

text: College

text: and

text: a

text: Clarendon

text: Scholar.

text: His

text: current

text: trol

text: barrier

text: functions

text: for

text: safety

text: critical

text: control,”

text: in

text: IFAC-PapersOnLine,

text: research

text: interests

text: are

text: at

text: the

text: intersection

text: of

text: learning

text: vol.

text: no.

text: pp.

text: analysis

text: and

text: Design

text: of

text: Hybrid

text: and

text: control,

text: games

text: on

text: Markov

text: decision

text: processes,

text: Systems

text: ADHS.

text: and

text: computational

text: methods

text: for

text: analysis

text: of

text: PDEs.

text: Q.

text: Nguyen

text: and

text: K.

text: Sreenath,

text: “Exponential

text: control

text: barrier

text: functions

text: for

text: enforcing

text: high

text: relative-degree

text: safety-critical

text: constraints,”

text: in

text: American

text: Control

text: Conference

text: (ACC),

text: July

text: pp.

text: C.

text: Fefferman,

text: Smooth

text: Interpolation

text: of

text: Data

text: by

text: Efﬁcient

text: Algorithms.

text: Boston:

text: Birkha¨user

text: Boston,

text: pp.

text: A.

text: Herbert-Voss,

text: M.

text: J.

text: Hirn,

text: and

text: F.

text: McCollum,

text: “Computing

text: minimal

text: interpolants

text: in

text: Revista

text: Matematica

text: Iberoamericana,

text: vol.

text: no.

text: pp.

text: J.

text: P.

text: Aubin

text: and

text: H.

text: Frankowska,

text: Set-Valued

text: Analysis.

text: Boston:

text: Birkha¨user,

text: J.

text: P.

text: Aubin

text: and

text: A.

text: Celina,

text: Differential

text: Inclusions.

text: Springer-Verlag,

text: Berlin,

text: P.

text: Seiler,

text: “Stability

text: analysis

text: with

text: dissipation

text: inequalities

text: and

text: integral

text: quadratic

text: constraints,”

text: IEEE

text: Transactions

text: on

text: Automatic

text: Control,

text: vol.

text: no.

text: pp.

text: June

text: M.

text: Ahmadi,

text: A.

text: Israel,

text: and

text: U.

text: Topcu,

text: “Safety-assessment

text: for

text: physically-

text: viable

text: data-driven

text: models,”

text: in

text: The

text: IEEE

text: Conference

text: on

text: Decision

text: and

text: Control,

text: Melbourne,

text: Australia,

text: Dec

text: H.

text: Whitney,

text: “Analytic

text: extensions

text: of

text: differentiable

text: functions

text: deﬁned

text: in

text: closed

text: sets,”

text: Transactions

text: of

text: the

text: American

text: Mathematical

text: Society,

text: vol.

text: no.

text: pp.

text: C.

text: L.

text: Fefferman,

text: “A

text: sharp

text: form

text: of

text: Whitney’s

text: extension

text: theorem,”

text: Annals

text: of

text: Mathematics,

text: vol.

text: no.

text: pp.

text: C.

text: Fefferman

text: and

text: B.

text: Klartag,

text: “Fitting

text: a

text: Cm-smooth

text: function

text: to

text: data

text: i,”

text: Rev.

text: Mat.

text: Iberoamericana,

text: vol.

text: no.

text: pp.

text: C.

text: Fefferman

text: and

text: A.

text: Israel,

text: “The

text: jet

text: of

text: an

text: interpolant

text: on

text: a

text: ﬁnite

text: set,”

text: Ufuk

text: Topcu

text: Ufuk

text: Topcu

text: joined

text: the

text: Department

text: of

text: Rev.

text: Mat.

text: Iberoamericana,

text: vol.

text: no.

text: pp.

text: Aerospace

text: Engineering

text: at

text: the

text: University

text: of

text: Texas

text: at

text: C.

text: Fefferman,

text: “Fitting

text: a

text: Cm

text: -smooth

text: function

text: to

text: data,

text: III,”

text: Annals

text: of

text: Austin

text: as

text: an

text: assistant

text: professor

text: in

text: Fall

text: He

text: Mathematics,

text: vol.

text: no.

text: pp.

text: received

text: his

text: Ph.D.

text: degree

text: from

text: the

text: University

text: of

text: C.

text: de

text: Boor,

text: A

text: Practical

text: Guide

text: to

text: Splines,

text: ser.

text: Applied

text: Mathematical

text: California

text: at

text: Berkeley

text: in

text: He

text: held

text: research

text: Sciences.

text: Springer

text: New

text: York,

text: positions

text: at

text: the

text: University

text: of

text: Pennsylvania

text: and

text: Cal-

text: P.

text: Lancaster

text: and

text: K.

text: Sˇalkauskas,

text: Curve

text: and

text: Surface

text: Fitting:

text: An

text: Intro-

text: ifornia

text: Institute

text: of

text: Technology.

text: His

text: research

text: focuses

text: duction,

text: ser.

text: Computational

text: mathematics

text: and

text: applications.

text: Academic

text: on

text: the

text: theoretical,

text: algorithmic

text: and

text: computational

text: Press,

text: aspects

text: of

text: design

text: and

text: veriﬁcation

text: of

text: autonomous

text: G.

text: Farin,

text: “Cubic

text: spline

text: interpolation,”

text: in

text: Curves

text: and

text: Surfaces

text: for

text: systems

text: through

text: novel

text: connections

text: between

text: formal

text: Computer-Aided

text: Geometric

text: Design

text: (Third

text: Edition),

text: third

text: edition

text: ed.,

text: methods,

text: learning

text: theory

text: and

text: controls.

text: G.

text: Farin,

text: Ed.

text: Boston:

text: Academic

text: Press,

text: pp.

text: Arie

text: Israel

text: Arie

text: Israel

text: joined

text: the

text: Department

text: of

text: E.

text: Grosse,

text: “Tensor

text: spline

text: approximation,”

text: Linear

text: Algebra

text: and

text: its

text: Mathematics

text: at

text: the

text: University

text: of

text: Texas

text: at

text: Austin

text: as

text: Applications,

text: vol.

text: no.

text: Supplement

text: C,

text: pp.

text: an

text: assistant

text: professor

text: in

text: Fall

text: He

text: received

text: his

text: A.

text: F.

text: Filippov,

text: Differential

text: Equations

text: with

text: Discontinuous

text: Right-Hand

text: Ph.D.

text: degree

text: from

text: Princeton

text: University

text: in

text: and

text: Sides,

text: ser.

text: Mathematics

text: and

text: Its

text: Applications.

text: Kluwer,

text: held

text: a

text: postdoctoral

text: position

text: at

text: New

text: York

text: University.

text: P.

text: Glotfelter,

text: J.

text: Cortes,

text: and

text: M.

text: Egerstedt,

text: “Nonsmooth

text: barrier

text: functions

text: His

text: primary

text: research

text: focus

text: has

text: been

text: on

text: the

text: theoreti-

text: with

text: applications

text: to

text: multi-robot

text: systems,”

text: IEEE

text: Control

text: Systems

text: Letters,

text: cal

text: and

text: algorithmic

text: foundations

text: of

text: extension

text: and

text: in-

text: vol.

text: no.

text: pp.

text: Oct

text: terpolation

text: problems

text: in

text: smooth

text: function

text: spaces.

text: His

text: M.

text: Putinar,

text: “Positive

text: polynomials

text: on

text: compact

text: semi-algebraic

text: sets,”

text: work

text: draws

text: on

text: tools

text: from

text: Harmonic

text: Analysis

text: and

text: Indiana

text: University

text: Mathematics

text: Journal,

text: vol.

text: no.

text: pp.

text: PDE.

text: Recently

text: he

text: has

text: been

text: exploring

text: applications

text: of

text: his

text: work

text: to

text: machine

text: learning

text: and

text: control

text: theory.

text: M.

text: Schweighofer,

text: “Optimization

text: of

text: polynomials

text: on

text: compact

text: semialge-

text: braic

text: sets,”

text: SIAM

text: Journal

text: on

text: Optimization,

text: vol.

text: no.

text: pp.

text: P.

text: Parrilo,

text: “Structured

text: semideﬁnite

text: programs

text: and

text: semialgebraic

text: ge-

text: ometry

text: methods

text: in

text: robustness

text: and

text: optimization,”

text: Ph.D.

text: dissertation,

text: California

text: Institute

text: of

text: Technology,

text: S.

text: Prajna,

text: A.

text: Papachristodoulou,

text: P.

text: Seiler,

text: and

text: P.

text: Parrilo,

text: “SOSTOOLS:

text: Sum

text: of

text: squares

text: optimization

text: toolbox

text: for

text: MATLAB

text: J.

text: F.

text: Sturm,

text: “Using

text: sedumi

text: a

text: matlab

text: toolbox

text: for

text: optimization

text: over

text: symmetric

text: cones,”

text: J.

text: P.

text: Aubin,

text: A.

text: M.

text: Bayen,

text: and

text: P.

text: Saint-Pierre,

text: Viability

text: Theory:

text: New

text: Directions,

text: ed.

text: Springer,

text: R.

text: L.

text: Smith,

text: L.

text: M.

text: Howser,

text: and

text: J.

text: M.

text: Price,

text: A

text: smoothing

text: algorithm

text: using

text: cubic

text: spline

text: functions.

text: Washington:

text: National

text: Aeronautics

text: and

text: Space

text: Administration,

text: Technical

text: Report,

text: M.

text: Posa,

text: M.

text: Tobenkin,

text: and

text: R.

text: Tedrake,

text: “Stability

text: analysis

text: and

text: control

text: of

text: rigid-body

text: systems

text: with

text: impacts

text: and

text: friction,”

text: IEEE

text: Transactions

text: on

text: Automatic

text: Control,

text: vol.

text: no.

text: pp.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: differential inclusion (9) for a system with only one state and x(t), x˙(t) σ(t) = 1, t > 0. x(tN) We are interested in solving the following safety analysis problem. x(0) Problem 1: Consider the data-driven differential ≡ X ⊂ R x˙(t ) inclusion (9) with u 0. Given n and T > t , check N ∈ X u N whether x(T) / . u t In addition, we are interested in addressing the following safe controller synthesis problem. x˙(0) Problem 2: Consider the data-driven differential X ⊂ R Fig. 1: Data samples (black dots), actual system state evo- inclusion (9). Given n and T > t , ﬁnd a u ∈ X N lution (dashed lines), and the solution set of the data-driven feedback law u(x) such that x(T) / . u differential inclusion (blue). In the next section, we discuss differential inclusions in the form of (9) and we address Problem 1 and Problem 2. cases in which, in addition to state and input samples, some IV. SAFETY ANALYSIS AND SAFE CONTROLLER prior regularity knowledge (that we also call side information) SYNTHESIS FOR DIFFERENTIAL INCLUSIONS on the state evolutions may be available. We capture such We start by deriving a safety theorem based on barrier information by constraints in the form of certiﬁcates for convex differential inclusions and then show (cid:107) (cid:107) ≤ how this result can be applied to the data-driven differential x C M, 2 inclusion (9) for safe controller synthesis. { } for a constant M > 0. For mechanical systems, for example, Let fi(t, x, u) mi=1 Tbe×aXfa×miUly →of R(piecewiseX) s⊆moRoth the above constraint represents bounds on maximum acceler- functions, where f : n with n, T ⊆ R U ⊆i R ∈ L∞ ation. ≥ , and m. We further assume u . Deﬁne F T ×0X × U → R In order to account for the uncertainty in approximating x˙ : 2 n with with the function X˙ , we introduce a function σ : R≥ → R≥ F { } 0 0 (t, x, u) = co f (t, x, u), . . . , f (t, x, u) . such that 1 m (cid:40) Consider the following differential inclusion | − | ≤ X˙ (t) x˙(t) Mσ(t). (8) ∈ F ≥ x˙ (t, x, u), t t , 0 (10) In the case of piecewise-polynomial approximation of the x(t0) = x0. data, we have (7). From the side information (8), we have ≤ ≤ − Well-posedness conditions of differential inclusions [38, X˙ − x˙ X˙ , where X˙ − = X˙ (t) Mσ(t) and X˙ = F + + Theorem 1, p. 106] require the set-valued map to be closed X˙ (t) +Mσ(t) and X˙ (t) is given as (7). Hence, the dynamics and convex for all t, x, and u, and also measurable in u. of the system for t > t can be described by the following F data-driven d(cid:40)ifferential i(cid:8)Nnclusion (cid:9) The set (t, x, u) is closed and convex, because it is deﬁned as the convex hull of a ﬁnite set. Furthermore, the mapping F · X → R (t, , u) : 2 n is upper hemi-continuous in x, for all t ∈ x˙(t) co X˙ −(t), X˙ (t) , and u, because it can be written as a convex combination of + (9) · F x(tN) = xN. ssmatiosoﬁtehs mthaepopnineg-ssidfeid(t,Li,pus)c.hiFtzincaollnyd, itthioenmapping (t, x, u) − − ≤ (cid:107) − (cid:107) ∀ Note that the above dynamics are dependent on the control (x x )T (v v ) C x x 2, t > 0, 1 2 1 2 1 2 signal through (7). ∈ X ∈ X ∈ F Differential inclusion (9) in fact over-approximates the for∈soFme C > 0 and all x1 , x2 , v1 (tF, x1, u· ) and dynamics after t > t . Note that the information on the v2 (t, x2, u), which follows from the fact that (t, , u) is system state is only aNvailable for 0 < t < t and the a convex hull of smooth and Lipschitz functions for all t and regularity information (M and σ) provides the meanNs using (9) u. A. Safety Analysis for Autonomous Differential Inclusions to predict the behavior of system state. The rate of growth of the approximation error for t > t can be approximated In order to propose a solution to Problem 1, we extend the N by the application of Gronwall’s inequality [26]. This rate concept of barrier certiﬁcates to differential inclusions. is a linear function of the Lipschitz constant of the inter- Before stating the result, we require a deﬁnition of the polant. Nonetheless, cubic-spline polynomials are the best derivative for set-valued maps [25]. Denote by − interpolants in terms of minimizing the Lipschitz constant for C V (x + hv) V (x) 2 trajectories [24]. Figure 1 illustrates the solution set of the D+V (x)(f) = →lim in→f h 0+, v f h ##LTFigure## ##LTLine##

text: differential

text: inclusion

text: for

text: a

text: system

text: with

text: only

text: one

text: state

text: and

text: x(t),

font: default

text: x˙(t)

text: σ(t)

text: t

text: x(tN)

text: We

text: are

text: interested

text: in

text: solving

text: the

text: following

text: safety

text: analysis

text: problem.

text: Problem

text: Consider

text: the

text: data-driven

text: differential

text: X

text: R

text: x˙(t

text: inclusion

text: with

text: u

text: Given

text: n

text: and

text: T

text: t

text: check

text: N

text: X

text: u

text: N

text: whether

text: x(T)

text: u

text: t

text: In

text: addition,

text: we

text: are

text: interested

text: in

text: addressing

text: the

text: following

text: safe

text: controller

text: synthesis

text: problem.

text: Problem

text: Consider

text: the

text: data-driven

text: differential

text: X

text: R

text: Fig.

text: Data

text: samples

text: (black

text: dots),

text: actual

text: system

text: state

text: evo-

text: inclusion

text: Given

text: n

text: and

text: T

text: t

text: ﬁnd

text: a

text: u

text: X

text: N

text: lution

text: (dashed

text: lines),

text: and

text: the

text: solution

text: set

text: of

text: the

text: data-driven

text: feedback

text: law

text: u(x)

text: such

text: that

text: x(T)

text: u

text: differential

text: inclusion

text: (blue).

text: In

text: the

text: next

text: section,

text: we

text: discuss

text: differential

text: inclusions

text: in

text: the

text: form

text: of

text: and

text: we

text: address

text: Problem

text: and

text: Problem

text: cases

text: in

text: which,

text: in

text: addition

text: to

text: state

text: and

text: input

text: samples,

text: some

text: IV.

text: SAFETY

text: ANALYSIS

text: AND

text: SAFE

text: CONTROLLER

text: prior

text: regularity

text: knowledge

text: (that

text: we

text: also

text: call

text: side

text: information)

text: SYNTHESIS

text: FOR

text: DIFFERENTIAL

text: INCLUSIONS

text: on

text: the

text: state

text: evolutions

text: may

text: be

text: available.

text: We

text: capture

text: such

text: We

text: start

text: by

text: deriving

text: a

text: safety

text: theorem

text: based

text: on

text: barrier

text: information

text: by

text: constraints

text: in

text: the

text: form

text: of

text: certiﬁcates

text: for

text: convex

text: differential

text: inclusions

text: and

text: then

text: show

text: how

text: this

text: result

text: can

text: be

text: applied

text: to

text: the

text: data-driven

text: differential

text: x

text: C

text: M,

text: inclusion

text: for

text: safe

text: controller

text: synthesis.

text: for

text: a

text: constant

text: M

text: For

text: mechanical

text: systems,

text: for

text: example,

text: Let

text: fi(t,

text: x,

text: u)

text: Tbe×aXfa×miUly

text: →of

text: R(piecewiseX)

text: s⊆moRoth

text: the

text: above

text: constraint

text: represents

text: bounds

text: on

text: maximum

text: acceler-

text: functions,

text: where

text: f

text: n

text: with

text: n,

text: T

text: R

text: U

text: ⊆i

text: R

text: L∞

text: ation.

text: and

text: m.

text: We

text: further

text: assume

text: u

text: Deﬁne

text: F

text: T

text: U

text: R

text: In

text: order

text: to

text: account

text: for

text: the

text: uncertainty

text: in

text: approximating

text: x˙

text: n

text: with

text: with

text: the

text: function

text: X˙

text: we

text: introduce

text: a

text: function

text: σ

text: R≥

text: R≥

text: F

text: (t,

text: x,

text: u)

text: co

text: f

text: (t,

text: x,

text: u),

text: f

text: (t,

text: x,

text: u)

text: such

text: that

text: m

text: Consider

text: the

text: following

text: differential

text: inclusion

text: X˙

text: (t)

text: x˙(t)

text: Mσ(t).

text: F

text: x˙

text: (t,

text: x,

text: u),

text: t

text: t

text: In

text: the

text: case

text: of

text: piecewise-polynomial

text: approximation

text: of

text: the

text: data,

text: we

text: have

text: From

text: the

text: side

text: information

text: we

text: have

text: Well-posedness

text: conditions

text: of

text: differential

text: inclusions

text: X˙

text: x˙

text: X˙

text: where

text: X˙

text: X˙

text: (t)

text: Mσ(t)

text: and

text: X˙

text: F

text: Theorem

text: p.

text: require

text: the

text: set-valued

text: map

text: to

text: be

text: closed

text: X˙

text: (t)

text: +Mσ(t)

text: and

text: X˙

text: (t)

text: is

text: given

text: as

text: Hence,

text: the

text: dynamics

text: and

text: convex

text: for

text: all

text: t,

text: x,

text: and

text: u,

text: and

text: also

text: measurable

text: in

text: u.

text: of

text: the

text: system

text: for

text: t

text: t

text: can

text: be

text: described

text: by

text: the

text: following

text: F

text: data-driven

text: The

text: set

text: (t,

text: x,

text: u)

text: is

text: closed

text: and

text: convex,

text: because

text: it

text: is

text: deﬁned

text: as

text: the

text: convex

text: hull

text: of

text: a

text: ﬁnite

text: set.

text: Furthermore,

text: the

text: mapping

text: F

text: X

text: R

text: (t,

text: u)

text: n

text: is

text: upper

text: hemi-continuous

text: in

text: x,

text: for

text: all

text: t

text: x˙(t)

text: co

text: X˙

text: −(t),

text: X˙

text: (t)

text: and

text: u,

text: because

text: it

text: can

text: be

text: written

text: as

text: a

text: convex

text: combination

text: of

text: F

text: x(tN)

text: xN.

text: ssmatiosoﬁtehs

text: itthioenmapping

text: (t,

text: x,

text: u)

text: Note

text: that

text: the

text: above

text: dynamics

text: are

text: dependent

text: on

text: the

text: control

text: (x

text: x

text: )T

text: (v

text: v

text: C

text: x

text: x

text: t

text: signal

text: through

text: X

text: X

text: F

text: Differential

text: inclusion

text: in

text: fact

text: over-approximates

text: the

text: for∈soFme

text: C

text: and

text: all

text: (tF,

text: u·

text: and

text: dynamics

text: after

text: t

text: t

text: Note

text: that

text: the

text: information

text: on

text: the

text: (t,

text: u),

text: which

text: follows

text: from

text: the

text: fact

text: that

text: (t,

text: u)

text: is

text: system

text: state

text: is

text: only

text: aNvailable

text: for

text: t

text: t

text: and

text: the

text: a

text: convex

text: hull

text: of

text: smooth

text: and

text: Lipschitz

text: functions

text: for

text: all

text: t

text: and

text: regularity

text: information

text: (M

text: and

text: σ)

text: provides

text: the

text: meanNs

text: using

text: u.

text: A.

text: Safety

text: Analysis

text: for

text: Autonomous

text: Differential

text: Inclusions

text: to

text: predict

text: the

text: behavior

text: of

text: system

text: state.

text: The

text: rate

text: of

text: growth

text: of

text: the

text: approximation

text: error

text: for

text: t

text: t

text: can

text: be

text: approximated

text: In

text: order

text: to

text: propose

text: a

text: solution

text: to

text: Problem

text: we

text: extend

text: the

text: N

text: by

text: the

text: application

text: of

text: Gronwall’s

text: inequality

text: This

text: rate

text: concept

text: of

text: barrier

text: certiﬁcates

text: to

text: differential

text: inclusions.

text: is

text: a

text: linear

text: function

text: of

text: the

text: Lipschitz

text: constant

text: of

text: the

text: inter-

text: Before

text: stating

text: the

text: result,

text: we

text: require

text: a

text: deﬁnition

text: of

text: the

text: polant.

text: Nonetheless,

text: cubic-spline

text: polynomials

text: are

text: the

text: best

text: derivative

text: for

text: set-valued

text: maps

text: Denote

text: by

text: interpolants

text: in

text: terms

text: of

text: minimizing

text: the

text: Lipschitz

text: constant

text: for

text: C

text: V

text: (x

text: hv)

text: V

text: (x)

text: trajectories

text: Figure

text: illustrates

text: the

text: solution

text: set

text: of

text: the

text: D+V

text: (x)(f)

text: →lim

text: in→f

text: h

text: v

text: f

text: h

text: ##LTFigure##

text: ##LTLine##