Skip to main content
Back

Maryland Gives Robot Behavior Trees a Safety Net With Three-Valued Logic

A new ternary-logic formulation lets robots plan directly from Behavior Trees using mixed-integer optimization, turning graphical task specs into provably safe control policies.

Pro

Paper, Full Access
  • New paper encodes Temporal Behavior Trees as mixed-integer programs using three-valued Kleene logic.
  • Adds an "Unknown" truth value that natively models a BT node's Running state.
  • Enables correct-by-construction control synthesis for linear dynamical systems with safety guarantees.
  • Sequence and Selector operator encodings scale as O(T^(k+1)) with subformula count k.
  • Case study: 3-agent planner spontaneously queues through obstacle corridors under distance constraints.
  • Limited to linear dynamics and offline synthesis; no accompanying code release mentioned.

Behavior Trees (BTs) are the go-to structure for authoring long-horizon robot plans, whether that is a warehouse mover deciding when to recharge or a game NPC picking between attack and retreat. They are graphical, modular, and easy for humans to reason about, but turning one into a controller that provably respects safety constraints has been awkward. A new paper from the University of Maryland proposes a way to bridge that gap by encoding Temporal Behavior Trees into a mixed-integer program built on three-valued logic, so an optimizer can synthesize trajectories that are correct by construction.

Why two-valued logic was the wrong tool

The core mismatch is philosophical. Each node in a BT has three possible conditions: Success, Failure, and Running, but the classical Signal Temporal Logic (STL) used to formally verify robot behavior only knows True and False. That third state matters: while a robot is still driving toward a goal, the task is neither satisfied nor violated, it is simply in progress. Prior work handled this by running temporal logic monitors offline over completed traces and then repairing violations after the fact.

STL, for readers unfamiliar with it, is a formalism for writing constraints like "reach position y within 10 seconds and hold it for 3 seconds" against real-valued signals. It has become popular for autonomous systems because it can express both spatial and timing requirements, but STL-based task planning can quickly become intractable when modeling long-horizon temporal behaviors and fallback mechanisms, which is exactly what BTs are good at expressing.