Content deleted Content added
The text was edited. |
m Fixed some grammar and spelling mistakes |
||
Line 31:
== 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> with the first publication of some of the key ideas in 2001.<ref>R.G.Dromey, Genetic Software Engineering – Simplifying Design Using Requirements Integration, IEEE Working Conference on Complex and Dynamic Systems Architecture, Brisbane, Dec 2001.</ref> Early publications on this work used the terms "genetic software engineering" and "genetic design" to describe the application of behavior trees. The reason for originally using the word "genetic" was because sets of genes, sets of jigsaw puzzle pieces, and sets of requirements represented as behavior trees all appeared to share several key properties:
* 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 43:
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>
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 the integration of large sets of behavioral and compositional requirements that are required to model large-scale systems.
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:
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, 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 ===
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]]
Requirements’ translation is the vehicle used to cross the informal-barrier. Consider the process of translation for requirement R1 below. The first tasks are to identify the components ('''bold'''), identify the behaviors (<u>underlined</u>), and identify indicators of the order (''italics'') in which behaviors take place. The corresponding behavior tree can then be constructed.
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:
* 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 103:
==== Requirement change ====
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:
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, together with the interfaces of individual components. This information, together with the information in the integrated composition tree (ICT) captured about each component, provides the information needed to implement each component.
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.
| |||