Performance analysis of stochastic behavior trees
Authors:
- 1 May 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10504729,p. 3265-3272
Abstract
This paper presents a mathematical framework for performance analysis of Behavior Trees (BTs). BTs are a recent alternative to Finite State Machines (FSMs), for doing modular task switching in robot control architectures. By encoding the switching logic in a tree structure, instead of distributing it in the states of a FSM, modularity and reusability are improved. In this paper, we compute performance measures, such as success/failure probabilities and execution times, for plans encoded and executed by BTs. To do this, we first introduce Stochastic Behavior Trees (SBT), where we assume that the probabilistic performance measures of the basic action controllers are given. We then show how Discrete Time Markov Chains (DTMC) can be used to aggregate these measures from one level of the tree to the next. The recursive structure of the tree then enables us to step by step propagate such estimates from the leaves (basic action controllers) to the root (complete task execution). Finally, we verify our analytical results using massive Monte Carlo simulations, and provide an illustrative example of the results for a complex robotic task.Keywords
This publication has 9 references indexed in Scilit:
- Towards a unified behavior trees framework for robot control2014
- Interfacing Behavior Trees with the World Using Description Logic2013
- An integrated system for autonomous robotics manipulation2012
- Increasing Modularity of UAV Control Systems using Computer Game Behavior Trees2012
- Parameterizing Behavior Trees2011
- Evolving Behaviour Trees for the Mario AI Competition Using Grammatical Evolution2011
- Extending the JADE Agent Behaviour Model with JBehaviourTrees Framework2011
- Evolving Behaviour Trees for the Commercial Game DEFCON2010
- Norm conditions for convergence of infinite productsLinear Algebra and its Applications, 1997