Behavior tree: Difference between revisions

Revision as of 15:29, 19 May 2025

Revision as of 20:50, 19 May 2025

Line 16:

Both single and integrated (composite) behavior tree forms are both important in applying behavior trees in [[systems engineering|systems]] and [[software engineering]].

* '''Requirement behavior trees (RBT):''' Initially, individual requirement behavior trees are used to capture all the fragments of behavior in each individual natural language requirement by a process of rigorous, intent-preserving and vocabulary-preserving translation. The translation process can uncover a range of defects in original [[natural language]] requirements.

* '''Integrated behavior trees (IBT):''' Because a set of requirements imply the integrated behavior of a system, all the individual requirement behavior trees can be composed to construct an integrated behavior tree that provides a single holistic view of the emergent integrated behavior of the system. This enables the building of the integrated behavior of a system '''out of''' ''its requirements''.<ref name = "winters">Winter, K. 2007. [http://espace.library.uq.edu.au/eserv/UQ:100586/Formalising_behaviour_trees_with_csp.pdf Formalising Behaviour Trees with CSP]</ref> An analogy to help describe this process is the transition from a randomly arranged set of [[jigsaw puzzle]] pieces to putting each of the pieces in its appropriate place. When this happens, each piece of information is placed in its intended context and their collective emergent properties become clear.

Having all the requirements converted to behavior trees (RBT) is similar to having all the pieces for a [[jigsaw puzzle]] randomly spread out on a table – until all the pieces are connected, the emergent picture remains unclear, and it's uncertain whether any pieces are missing, or do not fit. Constructing an integrated behavior tree (IBT) reveals the emergent behavior and missing pieces.<ref name = "dromey06FormalizingTrans"/><ref name = "dromey03K1-Dromey"/>

=== Behavior engineering process ===

Critical aspects of behavior engineering representation and process are listed below.

;Representation used – (critical)

;<nowiki>Representation:</nowiki>

* The role of the composition tree role in the overall process is to provide a vehiclemeans forto overcomingovercome the imperfect knowledge associated with the large set of requirements for a system.

;Process used – (critical)

;<nowiki>Process:</nowiki>

* Behavior engineering uses behavior trees to control complexity while growing a shared understanding of a complex system.

* ThatA shared, holistic understanding of a complex system, becauseintegrates itrequirements integratesto theshow requirements,its shows theimplied [[emergent behavior]] of the system implied by requirements.

== History ==

Line 43 ⟶ 44:

Further weight for use of the term "genetic" came from eighteenth-century thinker [[Giambattista Vico]], who said, "To understand something, and not merely be able to describe it, or analyze it into its component parts, is to understand how it came into being – its genesis, its growth … true understanding is always genetic".<ref name = "Vico">Berlin, I. The Crooked Timber of Humanity: Chapters in the History of Ideas, Ed., H.Hardy, Princeton University Press, 1998 {{ISBN|0-691-05838-5}}</ref> Despite these legitimate genetic parallels, it was felt that this emphasis led to confusion with the concept of [[genetic algorithms]]. As a result, the term behavior engineering was introduced to describe the processes that exploit behavior trees to construct systems. The term "behavior engineering" has previously been used in a specialized area of artificial intelligence – robotics research. The present use embraces a much broader, rigorous formalization and integration of large sets of behavioral and compositional requirements needed to model large-scale systems.

Since the behavior tree notation was originally conceived, several people from the Dependable Complex Computer-based Systems Group (DCCS)–DCCS– a joint [[University of Queensland]], [[Griffith University]] research group) have made important contributions to the evolution and refinement of the behavior tree notation and to the use of behavior treesusage.{{Citation needed|date=May 2025}}

Probabilistic timed behavior trees have been developed by Rob Colvin, Lars Grunske, and Kirsten Winter of the DCCS so that reliability, performanceperformances, and other dependability properties can be expressed.<ref name="probTimedBTs">Colvin, R., Grunske, L., Winter, K. 2007 [http://www.behaviorengineering.org/publications/grunske/IFM1.pdf Probabilistic Timed Behavior Trees] {{Webarchive|url=https://web.archive.org/web/20110725054158/http://www.behaviorengineering.org/publications/grunske/IFM1.pdf |date=25 July 2011 }}</ref>

== Key concepts ==

Line 51 ⟶ 52:

=== Behavior tree notation ===

[[File:Core Elements of the Behavior Tree Notation.png|360px|thumb|Core elements of the behavior tree notation]]

A behavior tree is used to formally represent the ''fragment of behavior'' in each individual requirement. Behavior for a large-scale system in general, where [[Concurrency (computer science)|concurrency]] is admitted, appears abstractly as a set of [[communicating sequential processes]]. The behavior tree notation captures these composed component-states inand arepresents simplethem as a tree-like form.

Behavior is expressed in terms of components realizing states and components creating and breaking relations. Using the logic and graphic forms of conventions found in [[programming languages]], components can support actions, composition, events, control-flow, data-flow, and threads.<ref name = "dromey03K1-Dromey"/>

Line 61 ⟶ 62:

A behavior tree specifies state changes in components, how data and control is passed between components and how [[Threads (computer science)|threads]] interact. There are constructs for creating and breaking relations. There are also constructs for setting and testing [[State (computer science)|states]] of components as well as mechanisms for [[inter-process communication]] that include [[message passing]] (events), shared variable blocking and [[Synchronization (computer science)|synchronization]].

For a complete reference to behavior tree notation, version 1.0, see: ''Behavior Tree Notation v1.0'' (2007).<ref name = "BTNotation">Behavior Tree Group, [[ARC Centre for Complex Systems]], 2007. [https://projects.ui.ac.id/attachments/download/300/Behavior-Tree-Notation-1.0.pdf Behavior Tree Notation v1.0 (2007) ] {{webarchive |url=https://web.archive.org/web/20160304003828/https://projects.ui.ac.id/attachments/download/300/Behavior-Tree-Notation-1.0.pdf |date=2016-03-04}}</ref>

=== Semantics ===

Line 88 ⟶ 89:

In general, many defects become much more visible when there is an integrated view of the requirements<ref name = "dromey07EngLgeScale"/> and each requirement has been placed in the behavior context where it needs to execute. For example, it is much easier to tell whether a set of conditions or events emanating from a node is complete and consistent. The traceability tags<ref name = "BTNotation" /> also make it easy to refer back to the original natural-language requirements. There is also the potential to automate a number of defect and consistency checks on an integrated behavior tree.<ref name = "buildEnv04">Smith, C., Winter, K., Hayes, I., Dromey, R.G., Lindsay, P., Carrington, D.: [https://ieeexplore.ieee.org/document/1342775 An Environment for Building a System Out of Its Requirements], 19th IEEE International Conference on Automated Software Engineering, Linz, Austria, Sept. (2004).</ref>

When all defects have been corrected and the IBT is logically consistent and complete it becomes a model behavior tree (MBT) which serves as a [[formal specification]] for the system's behavior that has been constructed out of the original requirements. This is the clearly defined stopping point for the analysis phase. With other [[Modeling languages|modeling notations]] and methods (for instance, withi.e. [[Unified Modeling Language|UML]]) it is less clear-cut when modeling can stop.<ref name = "shuttle04" /> In some cases, parts of a model behavior tree may need to be transformed to make the specification [[executable]]. Once an MBT has been made executable it is possible to carry out a number of other dependability checks.

==== Simulation ====

Line 94 ⟶ 95:

==== Model-checking ====

A translator has been written to convert a model behavior tree into the "actions systems" language. This input can then be fed into the SAL Model-checker<ref name = "SAL2">Bensalem, S., Ganesh, V., Lakhnech, Y., Muñoz, C., Owre, et al.: "An Overview of SAL", Fifth NASA Langley Formal Methods Workshop (LFM 2000), 2000, pp. 187–196.</ref><ref>Rushby, J. [http://fm.csl.sri.com/AFM06/slides/Rushby-intro-tutorial.pdf Automated Formal Methods 2006] AFM-2006, Automated Formal Methods 2006, Seattle, August 2006, pp. 6–7.</ref> in order to allow checks to be made as to whether certain safety and security properties are satisfied.<ref name = "automatedFailEffect05" /><ref name="embeddedSys05">Zafar, S. and Dromey, R. G., 2005. [http://www.behaviorengineering.org/publications/dromey/Zafar-SETE2005-ManagingComplexity.pdf Managing Complexity in Modelling Embedded Systems.] {{Webarchive|url=https://web.archive.org/web/20110725054400/http://www.behaviorengineering.org/publications/dromey/Zafar-SETE2005-ManagingComplexity.pdf |date=25 July 2011 }} Systems Engineering/Test and Evaluation Conference 2005, 7–9 November, Brisbane, Australia</ref>

==== Failure mode and effects analysis (FMEA) ====