ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems

Andrei Sandler; Olga Tveretina

ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems

Andrei Sandler, Olga Tveretina

Biocomputation Research Group

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

60 Downloads (Pure)

Abstract

We present the ParaPlan tool which provides the reachability analysis of planar hybrid systems defined by differential inclusions (SPDI). It uses the parallelized and optimized version of the algorithm underlying the SPeeDI tool. The performance comparison demonstrates the speed-up of up to 83 times with respect to the sequential implementation on various benchmarks. Some of the benchmarks we used are randomly generated with the novel approach based on the partitioning of the plane with Voronoi diagrams.

Original language	English
Title of host publication	Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification
Subtitle of host publication	GandALF 2017
Editors	Patricia Bouyer, Andrea Orlandini, Pierluigi San Pietro
Publisher	Electronic Proceedings in Theoretical Computer Science
Pages	283-296
Number of pages	14
Volume	256
Publication status	Published - 6 Sept 2017
Event	8th International Symposium on Games, Automata, Logics, and Formal Verification: GandALF 2017 - Rome, Italy Duration: 20 Sept 2017 → 22 Sept 2017 Conference number: 8th http://gandalf2017.istc.cnr.it/

Conference

Conference	8th International Symposium on Games, Automata, Logics, and Formal Verification
Country/Territory	Italy
City	Rome
Period	20/09/17 → 22/09/17
Internet address	http://gandalf2017.istc.cnr.it/

Keywords

Hybrid systems, the reachability problem

Access to Document

Published VersionFinal published version, 780 KBLicence: CC BY

https://arxiv.org/pdf/1709.02108.pdfLicence: CC BY

Cite this

Sandler, A., & Tveretina, O. (2017). ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems. In P. Bouyer, A. Orlandini, & P. San Pietro (Eds.), Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification: GandALF 2017 (Vol. 256, pp. 283-296). Electronic Proceedings in Theoretical Computer Science. https://arxiv.org/pdf/1709.02108.pdf

Sandler, Andrei ; Tveretina, Olga. / ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems. Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification: GandALF 2017. editor / Patricia Bouyer ; Andrea Orlandini ; Pierluigi San Pietro. Vol. 256 Electronic Proceedings in Theoretical Computer Science, 2017. pp. 283-296

@inproceedings{ea10b2e7e2da4e33b187cf5acd06bb9b,

title = "ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems",

abstract = "We present the ParaPlan tool which provides the reachability analysis of planar hybrid systems defined by differential inclusions (SPDI). It uses the parallelized and optimized version of the algorithm underlying the SPeeDI tool. The performance comparison demonstrates the speed-up of up to 83 times with respect to the sequential implementation on various benchmarks. Some of the benchmarks we used are randomly generated with the novel approach based on the partitioning of the plane with Voronoi diagrams. ",

keywords = "Hybrid systems, the reachability problem",

author = "Andrei Sandler and Olga Tveretina",

note = "Andrei Sandler, and Olga Tveretina, {\textquoteleft}ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems{\textquoteright}, in Patricia Bouyer, Andrea Orlandini and Pierluigi San Pietro, eds. Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2017), Rome, Italy, 20-22 September 2017, Electronic Proceedings in Theoretical Computer Science, Vol. 256: 283-296, September 2017. {\textcopyright} 2017 The Author(s). This work is licensed under the Creative Commons Attribution License CC BY 4.0 https://creativecommons.org/licenses/by/4.0/ ; 8th International Symposium on Games, Automata, Logics, and Formal Verification : GandALF 2017 ; Conference date: 20-09-2017 Through 22-09-2017",

year = "2017",

month = sep,

day = "6",

language = "English",

volume = "256",

pages = "283--296",

editor = "Patricia Bouyer and Andrea Orlandini and {San Pietro}, Pierluigi",

booktitle = "Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification",

publisher = "Electronic Proceedings in Theoretical Computer Science",

url = "http://gandalf2017.istc.cnr.it/",

}

Sandler, A & Tveretina, O 2017, ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems. in P Bouyer, A Orlandini & P San Pietro (eds), Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification: GandALF 2017. vol. 256, Electronic Proceedings in Theoretical Computer Science, pp. 283-296, 8th International Symposium on Games, Automata, Logics, and Formal Verification, Rome, Italy, 20/09/17. <https://arxiv.org/pdf/1709.02108.pdf>

ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems. / Sandler, Andrei; Tveretina, Olga.
Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification: GandALF 2017. ed. / Patricia Bouyer; Andrea Orlandini; Pierluigi San Pietro. Vol. 256 Electronic Proceedings in Theoretical Computer Science, 2017. p. 283-296.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems

AU - Sandler, Andrei

AU - Tveretina, Olga

N1 - Conference code: 8th

PY - 2017/9/6

Y1 - 2017/9/6

N2 - We present the ParaPlan tool which provides the reachability analysis of planar hybrid systems defined by differential inclusions (SPDI). It uses the parallelized and optimized version of the algorithm underlying the SPeeDI tool. The performance comparison demonstrates the speed-up of up to 83 times with respect to the sequential implementation on various benchmarks. Some of the benchmarks we used are randomly generated with the novel approach based on the partitioning of the plane with Voronoi diagrams.

AB - We present the ParaPlan tool which provides the reachability analysis of planar hybrid systems defined by differential inclusions (SPDI). It uses the parallelized and optimized version of the algorithm underlying the SPeeDI tool. The performance comparison demonstrates the speed-up of up to 83 times with respect to the sequential implementation on various benchmarks. Some of the benchmarks we used are randomly generated with the novel approach based on the partitioning of the plane with Voronoi diagrams.

KW - Hybrid systems, the reachability problem

UR - http://eptcs.web.cse.unsw.edu.au/content.cgi?GANDALF2017

M3 - Conference contribution

VL - 256

SP - 283

EP - 296

BT - Proceedings Eight International Symposium on Games, Automata, Logics and Formal Verification

A2 - Bouyer, Patricia

A2 - Orlandini, Andrea

A2 - San Pietro, Pierluigi

PB - Electronic Proceedings in Theoretical Computer Science

T2 - 8th International Symposium on Games, Automata, Logics, and Formal Verification

Y2 - 20 September 2017 through 22 September 2017

ER -

ParaPlan: A Tool for Parallel Reachability Analysis of Planar Polygonal Differential Inclusion Systems

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this