TY - GEN
T1 - Challenges and tool implementation of hybrid rapidly-exploring random trees
AU - Bak, Stanley
AU - Bogomolov, Sergiy
AU - Henzinger, Thomas A.
AU - Kumar, Aviral
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - A Rapidly-exploring Random Tree (RRT) is an algorithm which can search a non-convex region of space by incrementally building a space-filling tree. The tree is constructed from random points drawn from system’s state space and is biased to grow towards large unexplored areas in the system. RRT can provide better coverage of a system’s possible behaviors compared with random simulations, but is more lightweight than full reachability analysis. In this paper, we explore some of the design decisions encountered while implementing a hybrid extension of the RRT algorithm, which have not been elaborated on before. In particular, we focus on handling non-determinism, which arises due to discrete transitions. We introduce the notion of important points to account for this phenomena. We showcase our ideas using heater and navigation benchmarks.
AB - A Rapidly-exploring Random Tree (RRT) is an algorithm which can search a non-convex region of space by incrementally building a space-filling tree. The tree is constructed from random points drawn from system’s state space and is biased to grow towards large unexplored areas in the system. RRT can provide better coverage of a system’s possible behaviors compared with random simulations, but is more lightweight than full reachability analysis. In this paper, we explore some of the design decisions encountered while implementing a hybrid extension of the RRT algorithm, which have not been elaborated on before. In particular, we focus on handling non-determinism, which arises due to discrete transitions. We introduce the notion of important points to account for this phenomena. We showcase our ideas using heater and navigation benchmarks.
UR - https://www.scopus.com/pages/publications/85026765890
U2 - 10.1007/978-3-319-63501-9_6
DO - 10.1007/978-3-319-63501-9_6
M3 - Conference contribution
AN - SCOPUS:85026765890
SN - 9783319635002
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 83
EP - 89
BT - Numerical Software Verification - 10th International Workshop, NSV 2017, Proceedings
A2 - Abate, Alessandro
A2 - Boldo, Sylvie
PB - Springer Verlag
T2 - 10th International Workshop on Numerical Software Verification, NSV 2017
Y2 - 22 July 2017 through 23 July 2017
ER -