Challenges and tool implementation of hybrid rapidly exploring random trees Conference Paper


Author(s): Bak, Stanley; Bogomolov, Sergiy; Henzinger, Thomas A; Kumar, Aviral
Title: Challenges and tool implementation of hybrid rapidly exploring random trees
Title Series: LNCS
Affiliation IST Austria
Abstract: 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.
Conference Title: NSV: Numerical Software Verification
Volume: 10381
Conference Dates: July 22 - 23, 2017
Conference Location: Heidelberg, Germany
ISBN: 978-331963500-2
Publisher: Springer  
Date Published: 2017-01-01
Start Page: 83
End Page: 89
Sponsor: his work was partly supported by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award) and by the ARC project DP140104219 "Robust AI Planning for Hybrid Systems".
DOI: 10.1007/978-3-319-63501-9_6
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work