Content deleted Content added
Crmccull000 (talk | contribs) m Minor copyediting. Noted that paragraph "Model Based Testing" needs a reference. |
The text was edited. |
||
Line 5:
[[File:Static Integrated View.jpg|thumb|320px|Building a system out of its requirements – static view]]
A '''behavior tree''' is a structured [[visual modeling]] technique used in systems and [[software engineering]]. It represents a system's function with a tree-shaped diagram and provides a clear visual overview of behavior. This is
== Overview ==
Line 17:
Both single and integrated (composite) behavior tree forms are 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
* '''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 construction of the system's integrated behavior from 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
=== Behavior engineering process ===
Line 38:
For behavior trees, important emergent properties include:
* The integrated behavior of the system is implied by the requirements.
* The coherent behavior of each component is referred to in the requirements.
These genetic parallels, in another context, were originally spelled out by Adrian Woolfson.<ref>A. Woolfson, Life Without Genes, Flamingo, 2000, {{ISBN|0-00-255618-9}}</ref>
Line 53:
=== 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
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"/>
Traceability tags (see Section 1.2 of behavior tree notation<ref name = "BTNotation" />) in behavior tree nodes link the formal representation to the corresponding [[natural language]] requirement. Behavior trees accurately capture behavior expressed in the natural language representation of functional requirements.
A basis of the notation is that behavior is always associated with some component. Component-states which represent nodes of behavior are composed sequentially or concurrently to construct a behavior tree that represents the behavior expressed in the natural language requirements. A behavior tree with leaf nodes may revert (symbolized by adding the [[caret]] operator "^") to an ancestor node to repeat behavior or start a new thread (symbolized by two carets "^^").
Line 71:
[[File:Requirement Translation Example.jpg|240px|thumb|Example requirement translation]]
[[File:Requirements Behavior Tree Integration.png|thumb|240px|Requirements behavior tree integration]]
What is clear from the outcome of this process is that apart from pronouns, definite articles, etc., essentially all the words in the sentences that contribute to the behavior they describe have been accounted for and used.
===
Once the set of requirements is formalized as individual requirement behavior trees, two joint properties of systems and requirements need to be exploited
* In general, a fragment of behavior described by a requirement always has an associated precondition that must be satisfied before the behavior can occur. This precondition may or may not be explicitly stated in the requirement.
* If the requirement is really part of the system, then some other requirement in the set must establish the precondition needed in (1).
Line 82:
For requirements represented as behavior trees this amounts to finding where the root node of one tree occurs in some other behavior tree and integrating the two trees at that node.
The example below illustrates
=== Operations on integrated behavior trees ===
Line 90:
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 (i.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 96:
==== 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> to allow checks to be made
==== Failure mode and effects analysis (FMEA) ====
[[Model checking|Model-checking]] has often been applied to system models to check that hazardous states
====
The ideal
* where to make the change
* how the change affects the architecture of the existing system
* which components of the system are affected by the change, and?
* what behavioral changes will need to be made to the components (and their interfaces) that are affected by the change of requirements.<ref name="dromey07FormalPath">Wen, L., Dromey, R.G. 2007. [http://www.behaviorengineering.org/images/publications/wen_l_dromey_r_g_gse_change.pdf From Requirements Change to Design Change: A Formal Path]{{Dead link|date=November 2018|bot=InternetArchiveBot|fix-attempted=yes}}</ref>
Because a system is likely to undergo many changes over its service life, it is necessary to record, manage and optimize its evolution driven by these changes.
A traceability model, which uses behavior trees as a formal notation to represent functional requirements, reveals change impacts on different types of design constructs (documents) caused by the changes of the requirements.<ref>Wen, L., Dromey, R.G. 2005. [http://www.behaviorengineering.org/publications/wen/journal.pdf Architecture Normalization for Component-Based Systems] {{Webarchive|url=https://web.archive.org/web/20110725054411/http://www.behaviorengineering.org/publications/wen/journal.pdf |date=25 July 2011 }} Proceedings of the 2nd International Workshop on Formal Aspects of Component Software FACS'05, pp. 247–261.</ref> The model introduces the concept of evolutionary design documents that record the change history of the designs. From these documents, any version of a design document as well as the difference between any two versions can be retrieved. An important advantage of this model is that automated tools can support a major part of the procedure to generate these evolutionary design documents
==== Code generation and execution ====
Line 117:
Behavior tree models are executed in a virtual machine called the behavior run-time environment (BRE). The BRE links together [[Component-based software engineering#Software component|components]] using [[middleware]],<ref name="middleware">RTI Inc. 2007 "Meeting Real-Time Requirements in Integrated Defense Systems", [http://www.rti.com/mk/defense_systems.html RTI White Paper] {{Webarchive|url=https://web.archive.org/web/20080920033015/http://www.rti.com/mk/defense_systems.html |date=20 September 2008 }}.</ref> allowing components to be independent programs written in one of several languages that can be executed in a [[Distributed computing|distributed environment]]. The BRE also contains an expression [[parser]] that automatically performs simple operations to minimize the amount of code required to be manually implemented in the component.
The [[Implementation (computing)|implementation]] of components is supported by views that are automatically able to be extracted from the DBT. These views provide the component behavior trees (
Several BRE can be linked together to form complex systems using a system-of-systems construct and the behavior engineering component integration environment (BECIE). BECIE is also used to monitor and control the behavior tree models being executed within a BRE, similar to [[SCADA|supervisory control and data acquisition (SCADA)]] systems used in industrial process control.
Executable behavior trees have been developed for case studies<ref name="shuttle04">Dromey, R.G. [http://www.behaviorengineering.org/publications/dromey/Dromey-SCESM-2004N.pdf Using Behavior Trees to Model the Autonomous Shuttle System] {{Webarchive|url=https://web.archive.org/web/20110725054354/http://www.behaviorengineering.org/publications/dromey/Dromey-SCESM-2004N.pdf |date=25 July 2011 }}, 3rd International Workshop on Scenarios and State Machines: Models, Algorithms, and Tools (SCESM04) ICSE Workshop W5S, Edinburgh, 25 May 2004</ref> including automated train protection, <ref name = "integratingSoftHard08" /> mobile robots with a dynamic object following, an ambulatory infusion pump<ref name = "integratingSafety05" /> and traffic light management systems. A version of the BRE suited for embedded systems (eBRE) is also available that has reduced functionality to tailor it to small footprint [[Microcontroller|micro-controllers]].
== Applications ==
Line 127:
=== Large-scale systems ===
Modeling large-scale systems with large sets of natural-language requirements
=== Embedded systems ===
Failure of a design to satisfy a system's requirements can result in schedule and cost overruns.<ref>Barker, D. 2000. [https://ieeexplore.ieee.org/document/890177 Requirements modeling technology: a vision for better, faster, and cheaper systems.] Proceedings from VHDL International Users Forum Fall Workshop, 2000. pp. 3–6.</ref> If there are also critical dependability issues, not satisfying system requirements can have life-threatening consequences.<ref>Leveson, N. G. Safeware: System Safety and Computers: [a guide to preventing accidents and losses caused by technology]. Addison-Wesley Publishing Company, 1995. {{ISBN|0-201-11972-2}}</ref> However, in current approaches, ensuring requirements are satisfied is often delayed until late in the development process during a cycle of testing and debugging.<ref>Futrell, R. T., Shafer, D.F., Shafer, L.I. Quality Software Project Management (Software Quality Institute Series). Prentice Hall, 2002 {{ISBN|0-13-091297-2}}</ref> This work describes how the system development approach, behavior engineering, can be used to develop software for [[embedded system]]s.<ref name = "embeddedSys05" /> The result is a [[model-driven development]] approach that can create embedded system software that satisfies its requirements as a result of applying the development process.
===
Many large-scale systems consist of a mixture of co-dependent software and hardware. The different nature of software and hardware means
=== Role-based access control ===
Line 144:
{{main|Behavior tree (artificial intelligence, robotics and control)}}
While BT
=== Model
[[Model-based testing]] is an approach to software testing that requires testers to create test models from requirements of Software Under Test (SUT). Traditionally, UML state charts, [[Finite-state machine|finite-state machines]], EFSM{{expand acronym|ab|date=April 2025}}, and flow charts are used as the modeling language. Recently, an interesting approach in which Event-Driven Swim Lane Petri Net (EDSLPN) is used as the modeling language also
# It has the same expressiveness level as UML state charts and EDSLPN.
# It is intuitive to use as a modeling notation due to its graphical nature.
# Each behavior tree node has a requirement tag;
== Scalability and industry applications ==
Line 172:
== Advantages ==
As a behavior modelling representation, behavior trees have a number of significant benefits and advantages:
* They employ a well-defined and effective strategy for dealing with
* By rigorously translating then integrating requirements at the earliest possible time they provide a more effective means for uncovering
* They employ a single, simple notation<ref name = "BTNotation" /> for [[analysis]], [[Specification (computing)|specification]] and to represent the behavior design of a system.
* They represent the system behavior as an executable integrated whole.
* They build the behavior of a system out of its [[functional requirements]] in a directly traceable way which aids [[verification and validation]].<ref name = "Integrare07" /><ref name="verifValid06">Zafar, S., K.Winter, R.Colvin, R.G.Dromey, [http://www.behaviorengineering.org/publications/dromey/Zafar_Integrated_BTRBAC.pdf "Verification of an Integrated Role-Based Access Control Model"] {{Webarchive|url=https://web.archive.org/web/20110725061854/http://www.behaviorengineering.org/publications/dromey/Zafar_Integrated_BTRBAC.pdf |date=25 July 2011 }}, 1st International Workshop – Asian Working Conference on Verified Software (AWCVS'06), pp 230-240, Macao, Oct. 2006.</ref>
* They can be understood by [[Stakeholder (corporate)|stakeholders]] without the need for [[formal methods]] training. By strictly retaining the vocabulary of the original requirements, this eases the burden of understanding.
* They have a [[Semantics of programming languages|formal semantics]],<ref name = "colvinHayesNotation" /> they support [[Concurrency (computer science)|concurrency]], they are [[executable]] and they can be [[simulated]], [[Model checking|model-checked]] and used to undertake [[failure mode and effects analysis]].<ref name = "automatedFailEffect05" />
* They can be used equally well to model human processes, to analyze contracts,<ref name = "contracts02">Milosevic, Z., Dromey, R.G. [https://ieeexplore.ieee.org/document/1137692 On Expressing and Monitoring Behavior in Contracts], EDOC 2002, Proceedings, 6th International Enterprise Distributed Object Computing Conference, Lausanne, Switzerland, Sept. 2002, pp. 3-14.</ref> to represent forensic information, to represent biological systems, and
== Disadvantages ==
* For small textbook level examples, their tree-like nature means that the graphic models produced are sometimes not as compact as the [[state diagram]] or [[state machine]] behavior specifications.
* Tool support is needed to navigate the
* A group walk-through for
* There is a need to provide additional sophisticated tool support to fully exploit integrated behavior tree models.
| |||