Content deleted Content added
The text was edited. |
|||
| (35 intermediate revisions by 29 users not shown) | |||
Line 1:
{{Short description|Structured visual modeling technique}}
{{about|behavior trees for requirement handling|another use|Behavior tree (artificial intelligence, robotics and control)}}
{{Use dmy dates|date=May 2025}}{{Use American English|date=May 2025}}
Line 5 ⟶ 6:
[[File:Static Integrated View.jpg|thumb|320px|Building a system out of its requirements – static view]]
A '''behavior tree''' is a structured
== Overview ==
The extensive amount of detail involved in describing the numerous requirements
The behavior tree representation
=== Behavior tree forms ===
Line 17 ⟶ 18:
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
* '''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.
Line 24 ⟶ 25:
=== Behavior engineering process ===
Critical aspects of behavior engineering representation and process are listed below.
* The composition tree's role in the overall process is to provide a means to overcome the imperfect knowledge associated with the large set of requirements for a system.
* Behavior engineering uses behavior trees to control complexity while growing a shared understanding of a complex system.
* A shared holistic understanding of a complex system integrates requirements to show its implied
== History ==
Behavior trees and the concepts for their application in [[systems engineering|systems]] and [[software engineering]] were originally developed by Geoff Dromey.<ref name="dromey06FormalizingTrans">R.G.Dromey, [http://www.behaviorengineering.org/publications/dromey/Dromey-Chapter-Final-20051.pdf "Formalizing the Transition from Requirements to Design"] {{Webarchive|url=https://web.archive.org/web/20110725053952/http://www.behaviorengineering.org/publications/dromey/Dromey-Chapter-Final-20051.pdf |date=25 July 2011 }}, in "Mathematical Frameworks for Component Software – Models for Analysis and Synthesis", Jifeng He, and Zhiming Liu (Eds.), World Scientific Series on Component-Based Development, pp. 156–187, (Invited Chapter) (2006)</ref><ref name="dromey03K1-Dromey">R.G.Dromey, [http://www.behaviorengineering.org/publications/dromey/K1-Dromey.pdf From Requirements to Design: Formalizing the Key Steps] {{Webarchive|url=https://web.archive.org/web/20110725054005/http://www.behaviorengineering.org/publications/dromey/K1-Dromey.pdf |date=25 July 2011 }}, (Invited Keynote Address), SEFM-2003, IEEE International Conference on Software Engineering and Formal Methods, Brisbane, Sept. 2003, pp. 2–11.</ref><ref>R.L.Glass, [http://www.behaviorengineering.org/publications/Bob-Glass-GSE-CACM.pdf "Is This a Revolutionary Idea or Not"] {{Webarchive|url=https://web.archive.org/web/20110725054100/http://www.behaviorengineering.org/publications/Bob-Glass-GSE-CACM.pdf |date=25 July 2011 }}, Communications of the ACM, Vol. 47(11), pp. 23–25, Nov. 2004.</ref><ref>R.G.Dromey, [http://www.behaviorengineering.org/publications/dromey/Dromey.pdf "Climbing Over the ‘No Silver Bullet’ Brick Wall"] {{Webarchive|url=https://web.archive.org/web/20110725054117/http://www.behaviorengineering.org/publications/dromey/Dromey.pdf |date=25 July 2011 }}, IEEE Software, Vol. 23, No. 2, pp. 118–120, (March 2006)</ref>
* They contained enough information as a set to allow them to be composed – with behavior trees, this allows a system to be built out of its requirements.
* The order in which the pieces were put together was not important – with requirements, this aids in coping with complexity.
* When all the members of the set were put together, the resulting integrated entity exhibited a set of important [[emergent properties]].
Line 47 ⟶ 51:
Since the behavior tree notation was originally conceived, several people from the Dependable Complex Computer-based Systems Group (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 usage.<ref>{{Cite web |title=Behavior Engineering World » History of Behavior Engineering |url=https://www.beworld.org/BE/home/history-of-behavior-engineering/ |access-date=2025-05-24 |language=en-US}}</ref>
Probabilistic timed behavior trees have been developed by
== Key concepts ==
Line 59 ⟶ 63:
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. Requirement behavior trees strictly use the vocabulary of the natural language requirements but use graphical forms for behavior composition to remove the risk of ambiguity. By doing this, they provide a direct and clearly traceable relationship between what is expressed in the natural language representation and its [[formal specification]].<ref name="geneticDesign05">Dromey, R.G. [http://www.behaviorengineering.org/publications/dromey/Dromey-LNCS-Final2-new.pdf "Genetic Design: Amplifying Our Ability to Deal With Requirements Complexity"] {{Webarchive|url=https://web.archive.org/web/20110725054508/http://www.behaviorengineering.org/publications/dromey/Dromey-LNCS-Final2-new.pdf |date=25 July 2011 }}, in S.Leue, and T.J. Systra, Scenarios, Lecture Notes in Computer Science, LNCS 3466, pp. 95–108, 2005.</ref>
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 "^^").
A behavior tree specifies state changes in components, how data and control
For a complete reference to behavior tree notation
=== Semantics ===
The [[Semantics of programming languages|formal semantics]] of behavior trees is given via a [[process algebra]] and its [[operational semantics]].<ref name = "colvinHayesNotation">Colvin, R., Hayes, I.J. 2006 [http://www.accs.uq.edu.au/documents/TechnicalReports/ACCS_TR_07_01.pdf A Semantics for Behavior Trees]</ref> The semantics
=== Requirements translation ===
[[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.
=== Requirement integration ===
Line 80 ⟶ 84:
* If the requirement is really part of the system, then some other requirement in the set must establish the precondition needed in (1).
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 requirement integration for two requirements, R1 and R3. In other words, it shows how these two requirements interact.
Line 90 ⟶ 94:
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
==== Simulation ====
A model behavior tree can be readily simulated to explore the dynamic properties of the system. Both a symbolic tool and a graphics tool have been constructed to support these activities.<ref name = "Integrare07">L.Wen, R.Colvin, K.Lin, J.Seagrott, N.Yatapanage, R.G.Dromey, 2007, [http://www98.griffith.edu.au/dspace/bitstream/10072/18625/1/43991_1.pdf "Integrare, a Collaborative Environment for Behavior-Oriented Design"], in Proceedings of the Fourth International Conference on Cooperative Design, Visualization and Engineering, LNCS 4674, pp. 122–131, 2007</ref><ref name = "realTimeColloab06">C. Sun, S. Xia, D. Sun, D. Chen. H.F. Shen, W. Cai: [http://portal.acm.org/citation.cfm?doid=1188816.1188821 "Transparent adaptation of single-user applications for multi-user real-time collaboration"], ACM Transactions on Computer-Human Interaction, Vol. 13, No.4, December 2006, pp. 531–582.</ref>
==== Model
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
==== Failure mode and effects analysis (FMEA) ====
[[Model
==== Requirement
The ideal sought when responding to a change in the [[functional requirements]] for a system is that it can be quickly determined:
* 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.<ref name = "buildEnv04" />
==== Code generation and execution ====
Line 117 ⟶ 121:
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 (CRTs) of individual components,
Several
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,
== Applications ==
Behavior tree
=== Large-scale systems ===
Modeling large-scale systems with
=== Embedded systems ===
Failure of a design to
=== Hardware – software systems ===
Many large-scale systems consist of a mixture of co-dependent software and hardware. The different nature of software and hardware means they’re often modeled separately using different approaches. This can subsequently lead to integration problems due to incompatible assumptions about hardware/software interactions.<ref name = "integratingSoftHard08">Myers, T., Fritzson, P., Dromey, R.G. 2008. [http://www.ida.liu.se/~petfr/paperlinks/2008-07-Myers-Fritzson-Dromey-EOOLT2008-HardwareSoftwareModeling.pdf Seamlessly Integrating Software & Hardware Modelling for Large-Scale Systems.] 2nd International Workshop on Equation-Based Object-Oriented Languages and Tools (EOOLT 2008), Cyprus, July 2008. pp. 5–15.</ref> These problems can be overcome by integrating behavior trees with the [[Modelica]]
=== Role-based access control ===
Line 139 ⟶ 143:
=== Biological systems ===
Because behavior trees describe complex behavior, they can be used for describing a range of systems not limited to those that are computer-based.<ref name = "contracts02" /> In a biological context,
=== Game AI modeling ===
{{main|Behavior tree (artificial intelligence, robotics and control)}}
While
=== Model-Based Testing ===
[[Model-based testing]] is an approach to software testing that requires testers to create test models from requirements of Software Under Test (SUT). Traditionally,
# 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; these greatly facilitate the creation of a traceability matrix from requirement to test artifact.<ref>{{
== Scalability and industry applications ==
[[File:Behavior Engineering Support Environment.png|thumb|225px|
[[File:Integrated Behavior Tree Larger System.png|thumb|225px|Integrated behavior tree – larger system (more than 1000 requirements)]]
The first industry trials to test the feasibility of the method and refine its capability were conducted in 2002. Over the last three years, a number of systematic industry trials on large-scale defense, transportation, and enterprise systems have been conducted.<ref name = "raytheonSysResearch" /><ref name="industryTrialsPaper">Powell, D. 2007. [http://www.behaviorengineering.org/docs/ASWEC07_Industry_Powell.pdf Requirements Evaluation Using Behavior Trees – Findings from Industry] {{Webarchive|url=https://web.archive.org/web/20110725061927/http://www.behaviorengineering.org/docs/ASWEC07_Industry_Powell.pdf |date=25 July 2011 }}</ref> This work has established that the method scales to systems with large numbers of requirements but also that it is important to use tool support<ref name = "Integrare07" /><ref name = "RaytheonAswec08" /> in order to efficiently navigate and edit the resultant large integrated views of graphical data. On average, over a number of projects, 130 confirmed major defects per 1000 requirements have consistently been found after normal reviews and corrections have been made.<ref name = "industryTrialsPaper" /> With less mature requirements sets, much higher defect rates have been observed.
<!--[[File:Behavior_Engineering_Support_Environment.png|frame|100px|Screen-shot of Behavior Engineering Support Environment Tool]]
[[File: Integrated_Behavior_Tree_Larger_System.png|frame|100px|Integrated behavior tree – larger system (more than 1000 requirements)]] -->
An important part of this work with industry has involved applying the analysis part of the method to six large-scale defense projects for [[Raytheon]] Australia. They see the method as "a key risk mitigation strategy, of use in both solution development and as a means of advising the customer on problems with acquisition documentation".<ref name = "boston08" /><ref>McNicholas, D., (Raytheon Australia), 2007. [http://www.behaviorengineering.org/images/publications/dromey2/be-industry-benefits.doc Behavior Engineering Industry Benefits]{{Dead link|date=November 2018 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> An outcome of these industry trials has been the joint development<ref name="raytheonAustJoint">Raytheon Australia, 2008. [http://www.raytheon.com.au/Files/Behavior%20Trees.pdf Understanding grows on Behavior Trees] {{Webarchive|url=https://web.archive.org/web/20090915050633/http://www.raytheon.com.au/Files/Behavior%20Trees.pdf |date=15 September 2009 }}</ref> with Raytheon Australia of an industry-strength tool to support the analysis, editing, and display of large integrated sets of requirements.<ref name="RaytheonAswec08">Phillips, V., (Raytheon Australia), [http://www.behaviorengineering.org/images/publications/dromey2/bese_master_v2.ppt "Implementing a Behavior Tree Analysis Tool Using Eclipse Development Frameworks"]{{Dead link|date=November 2018 |bot=InternetArchiveBot |fix-attempted=yes }}, Australian Software Engineering Conference (ASWEC’08), Perth, March 2008</ref> More extensive details of industry findings can be found on the Behavior Engineering website.<ref name = "BEWebsite">Behavior Engineering. [http://www.behaviorengineering.org/ Behavior Engineering website] {{Webarchive|url=https://web.archive.org/web/20090301170621/http://www.behaviorengineering.org/ |date=1 March 2009 }}</ref>
Dr. Terry Stevenson (chief technical officer, Raytheon Australia), Mr. Jim Boston (senior project manager, Raytheon Australia), Mr. Adrian Pitman from the [[Defence Materiel Organisation|Australian Defence Materiel Organisation]], Dr. Kelvin Ross (CEO, K.J. Ross & Associates) and Christine Cornish (Bushell & Cornish) have provided the special opportunities needed to support this research and to conduct the industry trials<ref name = "raytheonSysResearch" /><ref name = "industryTrialsPaper" /> and live project work. This work has been supported by the [[Australian Research Council]] – [[ARC Centre for Complex Systems]] and funds received from industry.{{citation needed|date=April 2015}}▼
▲Dr. Terry Stevenson (chief technical officer, Raytheon Australia), Mr. Jim Boston (senior project manager, Raytheon Australia), Mr. Adrian Pitman from the [[Defence Materiel Organisation|Australian
*[http://www.raytheon.com.au/Files/Behavior%20Trees.pdf Raytheon Australia – Behavior Trees Joint Development] {{Webarchive|url=https://web.archive.org/web/20090915050633/http://www.raytheon.com.au/Files/Behavior%20Trees.pdf |date=15 September 2009 }}
*[http://www.behaviorengineering.org/images/publications/dromey2/bese_master_v2.ppt "Implementing a Behavior Tree Analysis Tool Using Eclipse Development Frameworks"]{{Dead link|date=November 2018 |bot=InternetArchiveBot |fix-attempted=yes }} Vincent Phillips, Raytheon Australia.
Line 171 ⟶ 173:
== Advantages ==
As a behavior
* They employ a well-defined and effective strategy for dealing with requirement complexity, particularly where the initial needs of a system are expressed using hundreds or thousands of requirements written in natural language. This significantly reduces the risk on large-scale projects.<ref name = "industryTrialsPaper"/>
* By rigorously translating then integrating requirements at the earliest possible time, they provide a more effective means for uncovering requirement defects than competing methods.<ref name = "industryTrialsPaper"/><ref name="boston08">Boston, J., (Raytheon Australia), [http://www.behaviorengineering.org/images/publications/dromey2/sp8_powerpoint_jim_boston.pdf Behavior Trees – How they improve Engineering Behaviour?]{{Dead link|date=November 2018 |bot=InternetArchiveBot |fix-attempted=yes }}, 6th Annual Software and Systems Engineering Process Group Conference (SEPG 2008), Melbourne, Aug. 2008.</ref>
* 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
* 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
* Tool support is needed to navigate the huge integrated behavior trees for systems that have hundreds or thousands of requirements.
* Presentation to a large group can be difficult, given the inherent size of a complicated system's tree.
* There is a need to provide additional sophisticated tool support to fully exploit integrated behavior tree models.
Line 203 ⟶ 205:
[[Category:Enterprise modelling]]
[[Category:Modeling languages]]
[[Category:Software engineering]]
| |||