Abstract
In this paper, we propose Belief Behavior Trees (BBTs), an extension to Behavior Trees (BTs) that allows to automatically create a policy that controls a robot in partially observable environments. We extend the semantic of BTs to account for the uncertainty that affects both the conditions and action nodes of the BT. The tree gets synthesized following a planning strategy for BTs proposed recently: from a set of goal conditions we iteratively select a goal and find the action, or in general the subtree, that satisfies it. Such action may have preconditions that do not hold. For those preconditions, we find an action or subtree in the same fashion. We extend this approach by including, in the planner, actions that have the purpose to reduce the uncertainty that affects the value of a condition node in the BT (for example, turning on the lights to have better lighting conditions). We demonstrate that BBTs allows task planning with non-deterministic outcomes for actions. We provide experimental validation of our approach in a real robotic scenario and - for sake of reproducibility - in a simulated one.
Introduction
Classical robotics and game AI often rely on Behavior Trees (BTs) for high-level control due to their modularity and reactivity. However, standard BTs operate under a "closed-world" assumption, where every environment condition is known to be either true or false. In real-world scenarios, robots frequently encounter partial observability—situations where information is missing or noisy. For instance, a robot cannot know if a specific object is inside a closed container without first opening it.
Belief Behavior Trees (BBTs) address this by extending the BT framework to handle uncertainty explicitly, allowing robots to plan perception actions that resolve ignorance before attempting physical manipulation.
Methodology
The BBT framework introduces three core innovations to bridge the gap between high-level task planning and reactive execution:
1. Ternary Node Semantics
Standard BT condition nodes return Success or Failure. BBTs introduce a third state: Running, which signifies that the value of a condition is currently unknown. This allows the tree to distinguish between a known negative state and a state of ignorance.
2. Belief State Integration
Instead of mapping to a single physical state, BBTs operate on a Belief State—a probability distribution over possible world states. When a node is "ticked," it updates this distribution based on the probabilistic outcomes of its actions, effectively propagating uncertainty through the tree.
3. Automated Synthesis via Backchaining
Trees are synthesized automatically starting from a goal condition. The planner identifies missing preconditions and inserts appropriate subtrees:
- If a condition is False, it inserts an actuation action (e.g., "Move to Kitchen").
- If a condition is Unknown, it inserts a perception action (e.g., "Detect Object").
To optimize this, the authors utilize a "Deepest Failed Condition" heuristic, identifying the node with the highest cumulative probability of failure as the primary bottleneck to resolve.
Experimental Results
The approach was validated using the R1 humanoid robot in a domestic search task and a corresponding simulated environment. The robot was tasked with finding and grasping a soda can in an environment where object locations and lighting conditions were uncertain.
Key findings include:
- Adaptive Perception: When lighting was insufficient, the BBT automatically inserted a branch to turn on the lights before searching, recognizing that the "seen" condition was unknown due to low luminosity.
- Probabilistic Planning: The system successfully reached a target success probability of 0.875 by planning sequential searches across multiple locations (e.g., Table 1 then Table 2) until the cumulative probability of finding the object was high enough.
- Reactivity: Despite the planning overhead, the resulting BBT maintained the inherent reactivity of behavior trees, allowing the robot to respond to unexpected environmental changes during execution.
Discussion and Limitations
BBTs treat perception as a "first-class citizen," enabling a natural balance between acting and information gathering. However, the current implementation does not support Parallel nodes due to the complexity of managing overlapping probabilistic outcomes in belief space. Additionally, the system currently requires predefined success probabilities for actions, which the authors suggest could be learned through machine learning in future iterations.
Summary updated