---
_id: '633'
abstract:
- lang: eng
  text: 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.
alternative_title:
- LNCS
author:
- first_name: Stanley
  full_name: Bak, Stanley
  last_name: Bak
- first_name: Sergiy
  full_name: Bogomolov, Sergiy
  id: 369D9A44-F248-11E8-B48F-1D18A9856A87
  last_name: Bogomolov
  orcid: 0000-0002-0686-0365
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Aviral
  full_name: Kumar, Aviral
  last_name: Kumar
citation:
  ama: 'Bak S, Bogomolov S, Henzinger TA, Kumar A. Challenges and tool implementation
    of hybrid rapidly exploring random trees. In: Abate A, Bodo S, eds. Vol 10381.
    Springer; 2017:83-89. doi:<a href="https://doi.org/10.1007/978-3-319-63501-9_6">10.1007/978-3-319-63501-9_6</a>'
  apa: 'Bak, S., Bogomolov, S., Henzinger, T. A., &#38; Kumar, A. (2017). Challenges
    and tool implementation of hybrid rapidly exploring random trees. In A. Abate
    &#38; S. Bodo (Eds.) (Vol. 10381, pp. 83–89). Presented at the NSV: Numerical
    Software Verification, Heidelberg, Germany: Springer. <a href="https://doi.org/10.1007/978-3-319-63501-9_6">https://doi.org/10.1007/978-3-319-63501-9_6</a>'
  chicago: Bak, Stanley, Sergiy Bogomolov, Thomas A Henzinger, and Aviral Kumar. “Challenges
    and Tool Implementation of Hybrid Rapidly Exploring Random Trees.” edited by Alessandro
    Abate and Sylvie Bodo, 10381:83–89. Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-63501-9_6">https://doi.org/10.1007/978-3-319-63501-9_6</a>.
  ieee: 'S. Bak, S. Bogomolov, T. A. Henzinger, and A. Kumar, “Challenges and tool
    implementation of hybrid rapidly exploring random trees,” presented at the NSV:
    Numerical Software Verification, Heidelberg, Germany, 2017, vol. 10381, pp. 83–89.'
  ista: 'Bak S, Bogomolov S, Henzinger TA, Kumar A. 2017. Challenges and tool implementation
    of hybrid rapidly exploring random trees. NSV: Numerical Software Verification,
    LNCS, vol. 10381, 83–89.'
  mla: Bak, Stanley, et al. <i>Challenges and Tool Implementation of Hybrid Rapidly
    Exploring Random Trees</i>. Edited by Alessandro Abate and Sylvie Bodo, vol. 10381,
    Springer, 2017, pp. 83–89, doi:<a href="https://doi.org/10.1007/978-3-319-63501-9_6">10.1007/978-3-319-63501-9_6</a>.
  short: S. Bak, S. Bogomolov, T.A. Henzinger, A. Kumar, in:, A. Abate, S. Bodo (Eds.),
    Springer, 2017, pp. 83–89.
conference:
  end_date: 2017-07-23
  location: Heidelberg, Germany
  name: 'NSV: Numerical Software Verification'
  start_date: 2017-07-22
date_created: 2018-12-11T11:47:37Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:07:06Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-319-63501-9_6
editor:
- first_name: Alessandro
  full_name: Abate, Alessandro
  last_name: Abate
- first_name: Sylvie
  full_name: Bodo, Sylvie
  last_name: Bodo
intvolume: '     10381'
language:
- iso: eng
month: '01'
oa_version: None
page: 83 - 89
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Moderne Concurrency Paradigms
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
publication_identifier:
  isbn:
  - 978-331963500-2
publication_status: published
publisher: Springer
publist_id: '7159'
quality_controlled: '1'
scopus_import: 1
status: public
title: Challenges and tool implementation of hybrid rapidly exploring random trees
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10381
year: '2017'
...