Reachability Analysis of Linear Hybrid Systems via Block Decomposition

Bogomolov, Sergiy; Forets, Marcelo; Frehse, Goran; Potomkin, Kostiantyn; Schilling, Christian

Reachability Analysis of Linear Hybrid Systems via Block Decomposition

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2020

Autor:innen

Bogomolov, Sergiy

Forets, Marcelo

Frehse, Goran

Potomkin, Kostiantyn

Schilling, Christian

DOI (zitierfähiger Link)

https://doi.org/10.1109/TCAD.2020.3012859

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. IEEE. 2020, 39(11), pp. 4018-4029. ISSN 0278-0070. eISSN 1937-4151. Available under: doi: 10.1109/TCAD.2020.3012859

Zusammenfassung

Reachability analysis aims at identifying states reachable by a system within a given time horizon. This task is known to be computationally expensive for linear hybrid systems. Reachability analysis works by iteratively applying continuous and discrete post operators to compute states reachable according to continuous and discrete dynamics, respectively. In this article, we enhance both of these operators and make sure that most of the involved computations are performed in low-dimensional state space. In particular, we improve the continuous-post operator by performing computations in high-dimensional state space only for time intervals relevant for the subsequent application of the discrete-post operator. Furthermore, the new discrete-post operator performs low-dimensional computations by leveraging the structure of the guard and assignment of a considered transition. We illustrate the potential of our approach on a number of challenging benchmarks.

Fachgebiet (DDC)

004 Informatik

Schlagwörter

Decomposition, hybrid systems, reachability

Zitieren

ISO 690

BOGOMOLOV, Sergiy, Marcelo FORETS, Goran FREHSE, Kostiantyn POTOMKIN, Christian SCHILLING, 2020. Reachability Analysis of Linear Hybrid Systems via Block Decomposition. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. IEEE. 2020, 39(11), pp. 4018-4029. ISSN 0278-0070. eISSN 1937-4151. Available under: doi: 10.1109/TCAD.2020.3012859

BibTex

@article{Bogomolov2020Reach-52450,
  year={2020},
  doi={10.1109/TCAD.2020.3012859},
  title={Reachability Analysis of Linear Hybrid Systems via Block Decomposition},
  number={11},
  volume={39},
  issn={0278-0070},
  journal={IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
  pages={4018--4029},
  author={Bogomolov, Sergiy and Forets, Marcelo and Frehse, Goran and Potomkin, Kostiantyn and Schilling, Christian}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52450">
    <dc:creator>Forets, Marcelo</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/52450"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-01-15T09:14:02Z</dc:date>
    <dc:contributor>Schilling, Christian</dc:contributor>
    <dc:language>eng</dc:language>
    <dc:creator>Potomkin, Kostiantyn</dc:creator>
    <dc:creator>Frehse, Goran</dc:creator>
    <dcterms:issued>2020</dcterms:issued>
    <dc:contributor>Potomkin, Kostiantyn</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Bogomolov, Sergiy</dc:creator>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:contributor>Bogomolov, Sergiy</dc:contributor>
    <dc:creator>Schilling, Christian</dc:creator>
    <dcterms:title>Reachability Analysis of Linear Hybrid Systems via Block Decomposition</dcterms:title>
    <dc:contributor>Forets, Marcelo</dc:contributor>
    <dcterms:abstract xml:lang="eng">Reachability analysis aims at identifying states reachable by a system within a given time horizon. This task is known to be computationally expensive for linear hybrid systems. Reachability analysis works by iteratively applying continuous and discrete post operators to compute states reachable according to continuous and discrete dynamics, respectively. In this article, we enhance both of these operators and make sure that most of the involved computations are performed in low-dimensional state space. In particular, we improve the continuous-post operator by performing computations in high-dimensional state space only for time intervals relevant for the subsequent application of the discrete-post operator. Furthermore, the new discrete-post operator performs low-dimensional computations by leveraging the structure of the guard and assignment of a considered transition. We illustrate the potential of our approach on a number of challenging benchmarks.</dcterms:abstract>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-01-15T09:14:02Z</dcterms:available>
    <dc:contributor>Frehse, Goran</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja

Begutachtet

Unbekannt