RQ1: How can control structures and mission concepts be modeled with the formalisms?

This page summarizes how four mission-specification formalisms: Behavior Trees (BT), State Machines (SM), Hierarchical Task Networks (HTN), and BPMN, represent fundamental control-flow constructs and mission-level concepts.

On this page

Overview

We compare the formalisms along two dimensions: (i) how they encode core control-flow constructs (sequential, conditional, parallel, and loop), and (ii) how they capture mission concepts such as skills, tasks, data, communication, events, errors, and pre/post-conditions at the mission level.

Control structures

The following blocks summarize the primary constructs used by each formalism.

Sequential

  • BT: Sequence / Fallback nodes (left-to-right execution).
  • SM: event-driven progression through states.
  • HTN: ordered methods (subtasks executed left-to-right).
  • BPMN: sequence flow from start to end events.

Parallel

  • BT: Parallel node executes children concurrently.
  • SM: Fork activates multiple states.
  • HTN: unordered methods (parallelism depends on executor).
  • BPMN: AND gateway splits into concurrent branches.

Conditional

  • BT: conditions + fallback/sequence patterns.
  • SM: Choice pseudostate with guarded transitions.
  • HTN: alternative methods with preconditions.
  • BPMN: XOR gateway with conditional flows (and optional default).

Loop

  • BT: Repeat decorators or looping subtrees.
  • SM: transition cycles (self-loops / cyclic transitions).
  • HTN: recursion via repeated task decomposition.
  • BPMN: loop activities, gateways, and multi-instance tasks.

Mission concepts

We adopt a mission-level perspective and focus on how each formalism expresses core abstractions: skills (basic robot capabilities), tasks (compositions of skills), and missions (coordinated tasks with precedence and concurrency). We also consider how data, events, errors, communication, and pre/post-conditions can be represented.

Concept mapping across formalisms

Concept BT SM HTN BPMN
Skill Action node (leaf) Simple state Primitive task Task (atomic activity)
Task Subtree Composite state Compound task Subprocess / Call activity
Data Inputs / blackboard (implementation-dependent) State variables (implementation-dependent) Task parameters (limited built-in storage) Data objects + process variables
Communication Implementation-dependent Implementation-dependent Implementation-dependent Message / signal events
Events Not first-class (via ticking + conditions) Event-triggered transitions Not first-class First-class events (multiple types)
Errors Failure propagation Error transitions (when state active) Not first-class Error events
Pre/Post-conditions Patterns (e.g., guarded actions) Guards / protocol transitions Native (tasks + methods) Not native (approximations/extensions)

This mapping reflects typical mission-level usage patterns and the constructs most commonly employed in robotics toolchains.

Key takeaways

  • All formalisms can express core control structures, but with different execution semantics.
  • BT/SM are strong for mission execution and reactive control; many mission concepts depend on implementation details.
  • HTN emphasizes planning and refinement via decomposition and preconditions.
  • BPMN offers explicit constructs for communication and coordination, especially for human/external-system interaction.