BT Expansion: a Sound and Complete Algorithm for Behavior Planning of Intelligent Robots with Behavior Trees

Zhongxuan Cai, Minglong Li, Wanrong Huang, Wenjing Yang

Abstract

Behavior Trees (BTs) are widely used in robotics for their modularity and reactivity. However, automated synthesis of BTs often lacks formal guarantees. This paper introduces BT Expansion, an automated planning algorithm that is both sound and complete. By integrating STRIPS-style planning with an iterative expansion process, the algorithm generates BTs that are mathematically guaranteed to reach a goal state while maintaining the inherent robustness of the BT architecture.

Introduction

Designing Behavior Trees by hand for complex robotic tasks is labor-intensive and error-prone. While evolutionary algorithms and reinforcement learning have been used to automate BT generation, they typically lack theoretical guarantees of success. Existing analytic methods often sacrifice the reactive nature of BTs or fail to prove completeness—the assurance that a solution will be found if one exists. BT Expansion addresses these gaps by providing a state-space formulation that preserves the "classic" BT structure while ensuring formal rigor.

Methodology: The BT Expansion Algorithm

The core of the proposed approach is an iterative planning process that builds a tree from a goal condition back to the robot's initial state.

1. STRIPS-style Action Representation

Actions are defined using standard classical planning literals: preconditions, "add" effects (conditions made true), and "delete" effects (conditions made false). This allows the algorithm to logically determine which actions satisfy specific goals.

2. One-Step Expansion

The algorithm begins with a "Primary BT" consisting solely of the goal condition. When the goal is not met, the algorithm identifies actions that can achieve it. For each candidate action, it generates a sequence structure.

The core logic of expanding a condition 'c' into a sub-tree using actions that satisfy it.

As shown in the expansion logic above, a condition node is replaced by a Fallback (Selector) node. This node first checks if the condition is already met; if not, it attempts a sequence consisting of the action's preconditions followed by the action itself.

3. Iterative Growth and Pruning

The process repeats, treating the preconditions of newly added actions as new sub-goals to be expanded. This continues until the tree covers the initial state of the environment. To maintain efficiency and prevent infinite loops, the algorithm includes a pruning mechanism to remove redundant nodes.

The iterative process showing the primary goal BT expanding into a more complex structure after one iteration.

Experimental Evaluation

The algorithm was tested in a mobile manipulator simulation using a KUKA Youbot and across 10,000 randomized test cases.

Key Results

  • Soundness and Completeness: The algorithm successfully found solutions for all solvable tasks, confirming its theoretical completeness.
  • Efficiency: In complex scenarios (e.g., 100 literals), BT Expansion produced significantly more compact trees than existing baselines. While a state-of-the-art baseline generated trees with over 30,000 nodes, BT Expansion achieved the same goals with an average of just 41.5 nodes.
  • Robustness: Because the resulting structure is a reactive BT, the robot could handle dynamic disturbances—such as a human moving an object mid-task—without needing to re-plan from scratch. The tree's "tick" logic naturally falls back to the necessary corrective behavior.

Conclusion

BT Expansion represents a significant step forward in robotic autonomy by bridging the gap between formal planning and reactive execution. By providing a sound and complete framework, it allows for the automated generation of robust robot behaviors that are mathematically guaranteed to succeed even in unpredictable environments. Future work will explore extending this logic to handle non-deterministic actions and more complex temporal constraints.

Summary updated

Abstract

Behavior Trees (BTs) have attracted much attention in the robotics field in recent years, which generalize existing control architectures and bring unique advantages for building robot systems. Automated synthesis of BTs can reduce human workload and build behavior models for complex tasks beyond the ability of human design, but theoretical studies are almost missing in existing methods because it is difficult to conduct formal analysis with the classic BT representations. As a result, they may fail in tasks that are actually solvable. This paper proposes BT expansion, an automated planning approach to building intelligent robot behaviors with BTs, and proves the soundness and completeness through the state-space formulation of BTs. The advantages of blended reactive planning and acting are formally discussed through the region of attraction of BTs, by which robots with BT expansion are robust to any resolvable external disturbances. Experiments with a mobile manipulator and test sets are simulated to validate the effectiveness and efficiency, where the proposed algorithm surpasses the baseline by virtue of its soundness and completeness. To the best of our knowledge, it is the first time to leverage the state-space formulation to synthesize BTs with a complete theoretical basis.
BibTeX
@inproceedings{cai2021bt,
  author = {Zhongxuan Cai and Minglong Li and Wanrong Huang and Wenjing Yang},
  title = {{BT Expansion: a Sound and Complete Algorithm for Behavior Planning of Intelligent Robots with Behavior Trees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16755},
}
Figure