Content deleted Content added
m I corrected this article's grammar and making it more readable. Tags: Reverted Visual edit Mobile edit Mobile web edit Newcomer task Newcomer task: copyedit |
Andromarined (talk | contribs) Grammatical errors, added a link |
||
Line 33:
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
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>
Line 63:
A behavior tree specifies state changes in components, how data and control are 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
=== Semantics ===
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 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) ====
Line 121:
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 has always been the major focus for testing behavior trees and the overall behavior engineering process. Conducting these evaluations and trials of the method has involved work with a number of industry partners and government departments in Australia. The systems studied have included a significant number of defense systems, enterprise systems, transportation systems, information systems, health systems, and sophisticated control systems with stringent safety requirements. The results of these studies have all been commercial-in-confidence. However, the results of the extensive industry trails<ref name = "raytheonSysResearch" /><ref name = "raytheonAustJoint" /> with [[Raytheon]] Australia are presented below in the Industry Section. This work has consistently shown that translating requirements and creating dynamic and static integrated views of requirements leads to discovery of a very significant number of major defects, over and above the defects that are found by current industry best-practice.<ref name = "industryTrialsPaper" /><ref name = "boston08" />
=== Embedded systems ===
Line 133:
=== 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 147:
=== 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, UML state charts, [[Finite-state machine|finite-state machines]], EFSM ([[Extended finite-state machine|Extended Finite-State Machines]]){{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 appeared. Behavior tree notation should be considered as a good modeling notation to MBT also, and it has a few advantages among other notations:
# 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.
Line 155:
[[File:Behavior Engineering Support Environment.png|thumb|225px|Screen-shot of behavior engineering support environment tool]]
[[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 Defense Materiel Organization]], 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}}
<ref>For further details see:
Line 173:
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 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-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 a lot of other applications. In each case, they deliver the same benefits in terms of managing complexity and seeing things as a whole. They can also be used for [[Safety-critical system|safety critical systems]],<ref name = "integratingSafety05" /> [[embedded system]]s<ref name = "embeddedSys05" />, and [[real-time systems]].<ref name="realTimeCollab05">Lin, K., Chen, D., Sun, C., Dromey, R.G., [http://www.behaviorengineering.org/publications/kailin/CDVEO5_Kevin.pdf A Constraint Maintenance Strategy and Applications in real-time Collaborative Environments]{{Dead link|date=November 2018 |bot=InternetArchiveBot |fix-attempted=yes }}, 2nd International Conference on Cooperative Design, Visualization and Engineering (CDVE2005), 2005.</ref><ref name="dataflowContstraint06">Lin, K., Chen, D., Dromey, R.G., Sun, CZ.: [http://www.behaviorengineering.org/publications/kailin/IEEE06_Kevin.pdf Multi-way Dataflow Constraint Propagation in Real-time Collaborative Systems] {{Webarchive|url=https://web.archive.org/web/20110725061427/http://www.behaviorengineering.org/publications/kailin/IEEE06_Kevin.pdf |date=25 July 2011 }}, IEEE, The 2nd International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom 2006), Atlanta, Georgia, USA, Nov, 2006.</ref><ref name="timeBT07">Grunske, L., Winter, K., Colvin, R., [http://www.behaviorengineering.org/publications/grunske/ASWEC20072.pdf "Timed Behavior Trees and their application to verifying real-time systems"] {{Webarchive|url=https://web.archive.org/web/20081118165542/http://www.behaviorengineering.org/publications/grunske/ASWEC20072.pdf |date=18 November 2008 }}, Proceedings of 18th Australian Conference on Software Engineering (AEWEC 2007), April 2007, accepted for publication.</ref>
== Disadvantages ==
| |||