KOPS - The Institutional Repository of the University of Konstanz

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

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

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BOGOMOLOV, 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, Apr 11, 2018 - Apr 13, 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, pp. 41-50. ISBN 978-1-4503-5642-8. Available under: doi: 10.1145/3178126.3178128

@inproceedings{Bogomolov2018Reach-53639, title={Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices}, year={2018}, doi={10.1145/3178126.3178128}, isbn={978-1-4503-5642-8}, address={New York}, publisher={Association for Computing Machinery}, 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 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/rdf/resource/123456789/53639"> <dc:language>eng</dc:language> <dc:contributor>Forets, Marcelo</dc:contributor> <dc:creator>Bogomolov, Sergiy</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>2018</dcterms:issued> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Bogomolov, Sergiy</dc:contributor> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:rights>terms-of-use</dc:rights> <dc:creator>Podelski, Andreas</dc:creator> <dc:creator>Forets, Marcelo</dc:creator> <dc:creator>Frehse, Goran</dc:creator> <dc:creator>Schilling, Christian</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Frehse, Goran</dc:contributor> <dc:contributor>Schilling, Christian</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/53639"/> <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> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-05-11T09:12:27Z</dcterms:available> <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> <dc:contributor>Podelski, Andreas</dc:contributor> <dc:creator>Viry, Frédéric</dc:creator> <dc:contributor>Viry, Frédéric</dc:contributor> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account