A delta–sampling verification theorem for discrete–time, possibly discontinuous systems

R.V. Bobiti, M. Lazar

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

Abstract

This paper considers the problem of safety verification for discrete-time, possibly discontinuous dynamical systems. Typical solutions rely on finding invariant sets or Lyapunov functions and require solving optimization problems, which suffer from scalability and numerical solvers issues. Recently, a d-sampling method for verifying invariance for Lipschitz continuous dynamics was proposed, which does not make use of optimization. In this work we present a d-sampling verification theorem that extends the previous result to general discrete-time, possibly discontinuous dynamics. This opens up the application of d-sampling verification to hybrid systems. Moreover, this paper proposes verification of stability on a set by jointly verifying (finite-step) Lyapunov type functions on an annulus with a (finite-step) Lyapunov function on the inner hole. We further indicate that d-sampling can also be used to verify Lyapunov conditions on the annulus. Lastly, we employ finite-step invariant sets and finite-step Lyapunov functions, respectively, together with d-sampling to achieve more practical safety verification methods.
LanguageEnglish
Title of host publicationProceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
DOIs
StatePublished - 2015
Event18th International Conference on Hybrid Systems: Computation and Control (HSCC 2015) - Seattle, United States
Duration: 14 Apr 201516 Apr 2015
Conference number: 18
http://ljk.imag.fr/hscc2015/

Conference

Conference18th International Conference on Hybrid Systems: Computation and Control (HSCC 2015)
Abbreviated titleHSCC 2015
CountryUnited States
CitySeattle
Period14/04/1516/04/15
Internet address

Fingerprint

Sampling
Lyapunov functions
Invariance
Hybrid systems
Scalability
Dynamical systems

Cite this

Bobiti, R. V., & Lazar, M. (2015). A delta–sampling verification theorem for discrete–time, possibly discontinuous systems. In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington New York: Association for Computing Machinery, Inc. DOI: 10.1145/2728606.2728631
Bobiti, R.V. ; Lazar, M./ A delta–sampling verification theorem for discrete–time, possibly discontinuous systems. Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington. New York : Association for Computing Machinery, Inc, 2015.
@inproceedings{bb59b48bab3e4ccf8c030131bc57b105,
title = "A delta–sampling verification theorem for discrete–time, possibly discontinuous systems",
abstract = "This paper considers the problem of safety verification for discrete-time, possibly discontinuous dynamical systems. Typical solutions rely on finding invariant sets or Lyapunov functions and require solving optimization problems, which suffer from scalability and numerical solvers issues. Recently, a d-sampling method for verifying invariance for Lipschitz continuous dynamics was proposed, which does not make use of optimization. In this work we present a d-sampling verification theorem that extends the previous result to general discrete-time, possibly discontinuous dynamics. This opens up the application of d-sampling verification to hybrid systems. Moreover, this paper proposes verification of stability on a set by jointly verifying (finite-step) Lyapunov type functions on an annulus with a (finite-step) Lyapunov function on the inner hole. We further indicate that d-sampling can also be used to verify Lyapunov conditions on the annulus. Lastly, we employ finite-step invariant sets and finite-step Lyapunov functions, respectively, together with d-sampling to achieve more practical safety verification methods.",
author = "R.V. Bobiti and M. Lazar",
year = "2015",
doi = "10.1145/2728606.2728631",
language = "English",
booktitle = "Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

Bobiti, RV & Lazar, M 2015, A delta–sampling verification theorem for discrete–time, possibly discontinuous systems. in Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington. Association for Computing Machinery, Inc, New York, 18th International Conference on Hybrid Systems: Computation and Control (HSCC 2015), Seattle, United States, 14/04/15. DOI: 10.1145/2728606.2728631

A delta–sampling verification theorem for discrete–time, possibly discontinuous systems. / Bobiti, R.V.; Lazar, M.

Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington. New York : Association for Computing Machinery, Inc, 2015.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - A delta–sampling verification theorem for discrete–time, possibly discontinuous systems

AU - Bobiti,R.V.

AU - Lazar,M.

PY - 2015

Y1 - 2015

N2 - This paper considers the problem of safety verification for discrete-time, possibly discontinuous dynamical systems. Typical solutions rely on finding invariant sets or Lyapunov functions and require solving optimization problems, which suffer from scalability and numerical solvers issues. Recently, a d-sampling method for verifying invariance for Lipschitz continuous dynamics was proposed, which does not make use of optimization. In this work we present a d-sampling verification theorem that extends the previous result to general discrete-time, possibly discontinuous dynamics. This opens up the application of d-sampling verification to hybrid systems. Moreover, this paper proposes verification of stability on a set by jointly verifying (finite-step) Lyapunov type functions on an annulus with a (finite-step) Lyapunov function on the inner hole. We further indicate that d-sampling can also be used to verify Lyapunov conditions on the annulus. Lastly, we employ finite-step invariant sets and finite-step Lyapunov functions, respectively, together with d-sampling to achieve more practical safety verification methods.

AB - This paper considers the problem of safety verification for discrete-time, possibly discontinuous dynamical systems. Typical solutions rely on finding invariant sets or Lyapunov functions and require solving optimization problems, which suffer from scalability and numerical solvers issues. Recently, a d-sampling method for verifying invariance for Lipschitz continuous dynamics was proposed, which does not make use of optimization. In this work we present a d-sampling verification theorem that extends the previous result to general discrete-time, possibly discontinuous dynamics. This opens up the application of d-sampling verification to hybrid systems. Moreover, this paper proposes verification of stability on a set by jointly verifying (finite-step) Lyapunov type functions on an annulus with a (finite-step) Lyapunov function on the inner hole. We further indicate that d-sampling can also be used to verify Lyapunov conditions on the annulus. Lastly, we employ finite-step invariant sets and finite-step Lyapunov functions, respectively, together with d-sampling to achieve more practical safety verification methods.

U2 - 10.1145/2728606.2728631

DO - 10.1145/2728606.2728631

M3 - Conference contribution

BT - Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Bobiti RV, Lazar M. A delta–sampling verification theorem for discrete–time, possibly discontinuous systems. In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (HSCC '15), 14-16 April 2015, Seattle, Washington. New York: Association for Computing Machinery, Inc. 2015. Available from, DOI: 10.1145/2728606.2728631