CISPA
Browse
3641513.3650180.pdf (1.1 MB)

Temporal Behavior Trees: Robustness and Segmentation

Download (1.1 MB)
conference contribution
posted on 2024-05-22, 13:44 authored by Sebastian Schirmer, Jasdeep Singh, Emily Jensen, Johann Dauer, Bernd FinkbeinerBernd Finkbeiner, Sriram Sankaranarayanan
This paper presents temporal behavior trees (TBT), a specification formalism inspired by behavior trees that are commonly used to program robotic applications. We then introduce the concept of trace segmentation, wherein given a TBT specification and a trace, we split the trace optimally into sub-traces that are associated with various portions of the TBT specification. Segmentation of a trace then serves to explain precisely how a trace satisfies or violates a specification, and which portions of a specification are actually violated. We introduce the syntax and semantics of TBT and compare their expressiveness in relation to temporal logic. Next, we define robustness semantics for TBT specification with respect to a trace. Rather than a Boolean interpretation, the robustness provides a real-valued numerical outcome that quantifies how close or far away a trace is from satisfying or violating a TBT specification. We show that computing the robustness of a trace also segments it into subtraces.Finally, we provide efficient approximations for computing robustness and segmentation for long traces with guarantees on the result.We demonstrate how segmentations are useful through applications such as understanding how novice users pilot an aerial vehicle through a sequence of waypoints in desktop experiments and the offline monitoring of automated lander for a drone on a ship. Our case studies demonstrate how TBT specification and segmentation can be used to understand and interpret complex behaviors of humans and automation in cyber-physical systems.

History

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

ACM International Conference on Hybrid Systems: Computation and Control (HSCC)

Page Range

1-14

Publisher

Association for Computing Machinery (ACM)

Open Access Type

  • Not Open Access

BibTeX

@conference{Schirmer:Singh:Jensen:Dauer:Finkbeiner:Sankaranarayanan:2024, title = "Temporal Behavior Trees: Robustness and Segmentation", author = "Schirmer, Sebastian" AND "Singh, Jasdeep" AND "Jensen, Emily" AND "Dauer, Johann" AND "Finkbeiner, Bernd" AND "Sankaranarayanan, Sriram", year = 2024, month = 5, pages = "1--14", publisher = "Association for Computing Machinery (ACM)", doi = "10.1145/3641513.3650180" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC