Technical Summary: A Reward-Petri-Net Interpretation of Temporal Behavior Trees

Problem Statement

Reinforcement Learning (RL) faces significant challenges in long-horizon environments characterized by sparse rewards. In such settings, agents struggle with effective credit assignment and exploration because the reward signal is delayed and infrequent. While specification languages (e.g., Linear Temporal Logic or Automata) have been used to automatically derive reward functions, they often lack user control over the relative importance of sub-tasks. Conversely, manual reward shaping is difficult for complex tasks with hierarchical structures and temporal constraints. The core problem addressed is how to generate dense, informative reward functions from formal task specifications that preserve user intuition regarding task hierarchy and sub-task criticality, particularly for tasks involving sequences, fallbacks, and temporal constraints.

Methodology

The authors propose a framework that interprets Temporal Behavior Trees (TBTs) as Reward Petri Nets (RPNs) to guide RL agents.

1. Temporal Behavior Trees (TBTs)

TBTs extend conventional Behavior Trees (BTs) by incorporating Linear Temporal Logic (LTL) formulas into leaf nodes.

• Structure: TBTs utilize standard BT operators: Sequence (sequential execution), Fallback (try alternatives until one succeeds), and Parallel (execute multiple branches, requiring a specific number to succeed).
• Leaf Nodes: Instead of simple actions, leaves contain LTL formulas (e.g., $\Diamond a$, meaning "eventually $a$").
• Semantics: The tree defines a trace satisfaction condition. A trace satisfies the TBT if the execution history satisfies the logical constraints defined by the operators and leaf formulas.

2. Construction of Reward Petri Nets (RPNs)

The paper formalizes a translation from TBT specifications to RPNs. An RPN is a Petri Net extended with guards, actions, and rewards.

• Mapping:
  • Places ($P$): Represent TBT nodes (both control flow nodes and leaf nodes).
  • Transitions ($T$): Represent the satisfaction or violation of a node.
  • Tokens: Track the progress of the agent toward satisfying the TBT.
  • Guards ($G$): Boolean expressions based on the output of automata derived from LTL formulas. Transitions fire only if the guard evaluates to true (e.g., a leaf node's LTL formula is satisfied).
  • Actions ($Act$): Manage the lifecycle of the underlying automata (start/stop) to handle backtracking. If a leaf node fails (returns false), the automaton is reset, allowing the agent to retry, which is crucial for non-monotonic properties.
• Determinism: The construction ensures deterministic behavior by using control places (e.g., cT) to manage token flow in Fallback and Parallel nodes, preventing infinite loops or ambiguous states.

3. Reward Assignment and Distribution

The RPN framework allows for automatic reward assignment based on the TBT structure.

• Distribution Functions: The authors define recursive functions ($f_{nLeaf}, f_{nFback}, f_{nParM}, f_{nSeq}$) to distribute a total reward $r$ across the tree.
  • Leaf Nodes: Assign positive rewards for satisfaction ($R(t_\phi) = r$) and small penalties for failure ($R(t_{\neg\phi}) = -\alpha r$).
  • Control Nodes:
    • Fallback: Forwards the full reward to subtrees; the agent is rewarded for satisfying any branch.
    • Sequence: Distributes rewards such that later sub-tasks can be weighted higher or lower depending on the scheme (e.g., monotonically increasing rewards to prioritize task completion).
    • Parallel: Distributes rewards based on the number of satisfied branches.
• Embedding in MDP: The RPN is embedded into the Markov Decision Process (MDP). At each step, the RPN state (marking) is updated based on the agent's observations and the verdicts of the LTL automata. The total reward emitted is the sum of rewards from all firing transitions.

Key Contributions

1. Formal Translation: The paper provides a rigorous construction method to translate TBT specifications into Reward Petri Nets, bridging the gap between high-level temporal logic specifications and low-level RL reward signals.
2. Modular Reward Shaping: By leveraging the hierarchical structure of TBTs, the method allows users to intuitively control reward distribution (e.g., prioritizing specific sub-tasks in a sequence) without manually designing dense reward functions.
3. Handling Backtracking: The integration of automata with RPNs enables a "backtracking" mechanism where failed leaf nodes are reset, allowing agents to retry sub-tasks while still receiving appropriate penalties, which is essential for learning in non-deterministic environments.
4. Scalability: The approach demonstrates that TBT-based rewards can scale to increasingly complex environments where vanilla RL fails, offering a structured way to handle hierarchical and temporal constraints.

Experimental Results

The authors evaluated the approach using the MiniGrid framework with the PPO algorithm across four increasingly difficult environments:

1. Unlock: Sequential key pickup and door unlocking.
2. UnlockPickup: Adds a goal object retrieval after unlocking.
3. BlockedUnlockPickup: Introduces obstacles that must be moved before unlocking.
4. ObstructedMaze-2Dlh & ObstructedMaze-1Q: Complex mazes with multiple locked doors, obstacles, and long horizons, known to be difficult for standard PPO.

Comparative Approaches:

• Vanilla Baseline: Standard sparse rewards.
• TBT-Baseline: TBT in observation space, unit reward only upon full task completion.
• TBT-Uniform: Unit reward distributed evenly across all TBT nodes.
• TBT-MONINC: Unit reward distributed to leaf nodes with strictly monotonically increasing values (prioritizing later sub-goals).

Findings:

• Learning Success: Vanilla RL failed to learn in the hardest environments (ObstructedMaze). All TBT-based approaches enabled learning.
• Sample Efficiency: TBT-based methods significantly improved sample efficiency compared to the vanilla baseline.
• Reward Distribution Impact: The TBT-MONINC variant showed a slight advantage in learning speed for the most complex environments, suggesting that prioritizing later sub-goals helps guide the agent toward task completion more effectively than uniform distribution.
• Robustness: The approach proved robust to procedural generation variations in the environment.

Significance and Claims

The paper claims that interpreting TBTs as RPNs offers a flexible and intuitive mechanism for reward generation in long-horizon RL.

• Expressivity: TBTs offer strictly higher expressivity than standard LTL or Signal Temporal Logic (STL) due to their hierarchical operators.
• Control: Unlike fully automated reward derivation from automata, this method preserves user control over the weighting of sub-tasks through the TBT structure and reward distribution functions.
• Modularity: The approach facilitates modular construction, allowing complex tasks to be built from simpler, reusable TBT components.
• Future Directions: The authors note that this framework is well-suited for multi-agent RL (due to the inherent concurrency handling of Petri Nets) and plan to explore automatic reward shaping via value iteration on RPNs and using TBTs as "shields" during learning.

The work positions TBTs not just as a specification tool, but as a direct generator of dense, structured reward signals that overcome the exploration and credit assignment bottlenecks inherent in sparse reward environments.