Behavior tree: Difference between revisions

Revision as of 21:48, 4 June 2025

Revision as of 11:25, 5 June 2025

Line 47:

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 researchers such as Rob Colvin, Lars Grunske, and Kirsten Winter of the DCCS, so that reliability, performance, and other dependability properties cancould 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 95:

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- 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) ====

[[Model checking|Model-checking]] has often been applied to system models to check that hazardous states can’t be reached during normal operation of the system.<ref name = "probabilistic07">Grunske, L., Colvin, R., Winter, K. Probabilistic Model-Checking Support for FMEA Quantitative Evaluation of Systems. QEST 2007. Fourth International Conference on the Quantitative Evaluation of Systems, 17-19 Sept. 2007 pp. 119–128</ref> It is possible to combine model-checking with behavior trees to provide automated support for [[failure mode and effects analysis]] (FMEA).<ref name = "automatedFailEffect05" /> The advantage of using behavior trees for this purpose is that they allow the [[formal method]] aspects of the approach to be hidden from non-expert users.

==== Requirement changes ====

Line 124:

== Applications ==

Behavior tree modellingmodeling can and has been applied to a diverse range of applications over a number of years. Some of the main application areas are described below.

=== 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 trailstrials<ref name = "raytheonSysResearch" /><ref name = "raytheonAustJoint" /> with [[Raytheon]] Australia are presented below in the Industry Section. This work has shown that translating requirements into integrated static and dynamic behavior-tree views revealed substantially more major defects than the company’s standard review processes detected.<ref name = "industryTrialsPaper" />

=== Embedded systems ===

Line 178:

* 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 ofmany 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 ==

* 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 huge integrated behavior trees for systems that have hundreds or thousands of requirements.

* A group walk-through for huge systems, good display facilities are needed.