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.
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.
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