Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2018
Autor:innen
Bogomolov, Sergiy
Forets, Marcelo
Frehse, Goran
Viry, Frédéric
Podelski, Andreas
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week). New York: Association for Computing Machinery, 2018, pp. 41-50. ISBN 978-1-4503-5642-8. Available under: doi: 10.1145/3178126.3178128
Zusammenfassung

Approximating the set of reachable states of a dynamical system is an algorithmic yet mathematically rigorous way to reason about its safety. Although progress has been made in the development of efficient algorithms for affine dynamical systems, available algorithms still lack scalability to ensure their wide adoption in the industrial setting. While modern linear algebra packages are efficient for matrices with tens of thousands of dimensions, set-based image computations are limited to a few hundred. We propose to decompose reach set computations such that set operations are performed in low dimensions, while matrix operations like exponentiation are carried out in the full dimension. Our method is applicable both in dense- and discrete-time settings. For a set of standard benchmarks, it shows a speed-up of up to two orders of magnitude compared to the respective state-of-the-art tools, with only modest losses in accuracy. For the dense-time case, we show an experiment with more than 10,000 variables, roughly two orders of magnitude higher than possible with previous approaches.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
HSCC '18: 21st International Conference on Hybrid Systems: Computation and Control, 11. Apr. 2018 - 13. Apr. 2018, Porto
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BOGOMOLOV, Sergiy, Marcelo FORETS, Goran FREHSE, Frédéric VIRY, Andreas PODELSKI, Christian SCHILLING, 2018. Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices. HSCC '18: 21st International Conference on Hybrid Systems: Computation and Control. Porto, 11. Apr. 2018 - 13. Apr. 2018. In: HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week). New York: Association for Computing Machinery, 2018, pp. 41-50. ISBN 978-1-4503-5642-8. Available under: doi: 10.1145/3178126.3178128
BibTex
@inproceedings{Bogomolov2018Reach-53639,
  year={2018},
  doi={10.1145/3178126.3178128},
  title={Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices},
  isbn={978-1-4503-5642-8},
  publisher={Association for Computing Machinery},
  address={New York},
  booktitle={HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)},
  pages={41--50},
  author={Bogomolov, Sergiy and Forets, Marcelo and Frehse, Goran and Viry, Frédéric and Podelski, Andreas 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/53639">
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Frehse, Goran</dc:creator>
    <dcterms:issued>2018</dcterms:issued>
    <dc:creator>Podelski, Andreas</dc:creator>
    <dc:creator>Forets, Marcelo</dc:creator>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:contributor>Podelski, Andreas</dc:contributor>
    <dc:creator>Bogomolov, Sergiy</dc:creator>
    <dc:language>eng</dc:language>
    <dc:creator>Schilling, Christian</dc:creator>
    <dcterms:abstract xml:lang="eng">Approximating the set of reachable states of a dynamical system is an algorithmic yet mathematically rigorous way to reason about its safety. Although progress has been made in the development of efficient algorithms for affine dynamical systems, available algorithms still lack scalability to ensure their wide adoption in the industrial setting. While modern linear algebra packages are efficient for matrices with tens of thousands of dimensions, set-based image computations are limited to a few hundred. We propose to decompose reach set computations such that set operations are performed in low dimensions, while matrix operations like exponentiation are carried out in the full dimension. Our method is applicable both in dense- and discrete-time settings. For a set of standard benchmarks, it shows a speed-up of up to two orders of magnitude compared to the respective state-of-the-art tools, with only modest losses in accuracy. For the dense-time case, we show an experiment with more than 10,000 variables, roughly two orders of magnitude higher than possible with previous approaches.</dcterms:abstract>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/53639"/>
    <dc:contributor>Bogomolov, Sergiy</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-05-11T09:12:27Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:title>Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices</dcterms:title>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-05-11T09:12:27Z</dc:date>
    <dc:contributor>Schilling, Christian</dc:contributor>
    <dc:contributor>Frehse, Goran</dc:contributor>
    <dc:creator>Viry, Frédéric</dc:creator>
    <dc:contributor>Forets, Marcelo</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Viry, Frédéric</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen