Task Graph

Nodes are the fundamental units of computation in a task graph. Each node represents a discrete task, action, or subgoal. In robotics and planning, nodes can be categorized hierarchically:

• Primitive Actions: Atomic, directly executable commands (e.g., Grasp(object_A), MoveTo(pose_x)).
• Abstract Tasks: High-level goals that require decomposition (e.g., Assemble(table)). Nodes are often annotated with preconditions (state requirements for execution) and effects (state changes after execution).

Edges are directed connections between nodes that encode dependencies and constraints. They define the partial order of execution. Key edge types include:

• Causal Edges: An edge from node A to node B indicates B requires the effects of A as its preconditions.
• Temporal Edges: Enforce ordering (e.g., B must start after A finishes).
• Resource Edges: Indicate shared resource usage, requiring sequential or managed concurrent access. Collectively, edges prevent invalid execution sequences and ensure logical consistency.

The overall structure or shape of the graph determines planning complexity and execution characteristics.

• Directed Acyclic Graph (DAG): The most common form, where edges have direction and no cycles exist, representing a strict partial order. This guarantees tasks can be sequenced.
• Cyclic Graphs: Contain loops, often used to represent repetitive or maintenance behaviors, requiring special execution semantics.
• Hierarchical Graphs: Contain subgraphs within nodes, where a parent node's execution involves traversing its internal child graph. This relates directly to Hierarchical Task Network (HTN) planning.

A task graph is grounded in a symbolic state representation. The world is modeled as a set of logical propositions or predicates (e.g., InGripper(block_1), OnTable(block_2)).

• Initial State: The set of propositions true at the start of planning.
• Goal State: The set of propositions that must be true upon successful plan completion. Node preconditions and effects are defined as operations on this state. This formalism connects task graphs to classical planning languages like PDDL.

These rules define how the graph is traversed and executed by a runtime system.

• Sequential Semantics: Nodes are executed one after another, respecting all edge dependencies.
• Concurrent Semantics: Independent nodes (with no path connecting them) can be executed in parallel, increasing efficiency.
• Reactive Semantics: The graph can be dynamically modified during execution (replanning) based on execution monitoring feedback, such as task failure or environmental change.

In embodied AI and robotics, a task graph sits at the task planning layer. Its primitive action nodes are typically motion planning problems. For example, a NavigateTo(room) task node triggers a path planning algorithm, while a PickUp(obj) node invokes grasp planning and trajectory optimization. This creates a hierarchical pipeline where the task graph provides the high-level logic and sequence, and lower-level planners solve the geometric and dynamic feasibility.

In robotics, a task graph decomposes a high-level command (e.g., 'make coffee') into a network of symbolic actions and geometric motions. This hierarchical representation is central to TAMP systems.

• Nodes represent actions like Grasp(mug), NavigateTo(sink), or Pour(water).
• Edges encode preconditions (e.g., Grasp(mug) must precede Pour(water)) and causal links. The graph is then grounded by a motion planner that converts each symbolic action into a feasible trajectory, checking for kinematic constraints and collisions. This separation of logical task structure from continuous motion planning is a cornerstone of advanced autonomy.

Within compilers, a Data Dependency Graph (DDG) or Task Graph is constructed from a program's intermediate representation. This graph is fundamental for optimization.

• Nodes are individual machine instructions or operations.
• Edges represent data dependencies (true, anti, and output dependencies) and control dependencies. The compiler uses this graph to perform instruction scheduling, reordering operations to maximize instruction-level parallelism while preserving program semantics. It also enables dead code elimination (removing nodes with no outgoing edges to live outputs) and register allocation by analyzing the lifetime of values.

In EDA tools, the circuit's logical structure is represented as a Directed Acyclic Graph (DAG), a specific type of task graph.

• Nodes represent logic gates (AND, OR) or complex functional blocks.
• Edges represent the wires carrying signals between gates. This graph model is used for:
• Static timing analysis: Calculating critical paths by summing delays along dependency chains.
• Logic synthesis and optimization: Applying transformations to the graph to reduce gate count or power consumption.
• Test pattern generation: Analyzing the graph to determine inputs that can detect faults at specific nodes.

Complex manufacturing and logistics operations are modeled as task graphs to optimize throughput and resource allocation.

• Nodes represent manufacturing stages, inspection points, or shipping legs.
• Edges represent temporal constraints (Task B cannot start until Task A finishes) and resource dependencies (both tasks require the same machine). This application involves temporal planning with durations and deadlines. Algorithms analyze the graph to identify the critical path—the sequence of tasks that determines the minimum total project time—enabling managers to focus optimization efforts. It also facilitates what-if analysis for schedule disruptions.

A hierarchical planning formalism that decomposes abstract tasks into subtasks using a library of pre-defined methods until primitive, executable actions are reached. Unlike a task graph, which represents a specific plan, an HTN is a planning domain containing the rules for decomposition.

• Key Mechanism: Uses task reduction via methods that map compound tasks to networks of subtasks.
• Relation to Task Graph: An HTN planner generates a task graph (or similar plan) as its output by applying its methods to an initial task.

A modular, hierarchical control architecture for autonomous agents that structures decision-making and task execution using a tree of nodes. It is often used for reactive execution and is more dynamic than a static task graph.

• Key Components: Includes action, condition, selector, and sequence nodes.
• Contrast with Task Graph: A Behavior Tree is an executable controller that ticks nodes repeatedly, allowing for interruption and recovery. A task graph is a static plan representation showing dependencies but not the runtime control flow.

A class of automated planning that explicitly reasons about the duration of actions, concurrency, and strict timing constraints between events. It extends classical planning to handle continuous time.

• Key Capability: Can generate plans where actions overlap or have minimum/maximum delays between them.
• Relation to Task Graph: A task graph for a temporal planning problem includes temporal edges annotated with constraints (e.g., Action B must start at least 5 seconds after Action A finishes).

A standardized, formal language used to model planning problems for classical and temporal planners. It defines predicates, actions, objects, and an initial and goal state.

• Role: Serves as the input specification for automated planners.
• Relation to Task Graph: A planner (e.g., a temporal planner) takes a PDDL domain and problem file as input and outputs a plan, which can be directly represented as a task graph where nodes are grounded PDDL actions and edges are causal or temporal links.

The algorithmic process of computing a sequence of valid configurations or states for a robot to move from a start to a goal while avoiding obstacles and respecting kinematic and dynamic constraints. It operates at a lower level than task planning.

• Key Distinction: Concerned with feasible geometry and dynamics, not high-level logic.
• Integration with Task Graph: In Task and Motion Planning (TAMP), a high-level task graph's primitive action nodes (e.g., "Pick up cup") are sent to a motion planner to compute the detailed joint trajectories.

A curated repository of reusable, parameterized motion primitives or behavioral modules that a robot can sequence to accomplish complex tasks. Each skill is a robust, closed-loop controller for a specific action like "peg-insert" or "door-open".

• Purpose: Abstracts away low-level motion planning and control, providing reliable building blocks.
• Relation to Task Graph: The leaf nodes (primitive actions) in a task graph are often calls to skills in a skill library, parameterized with specific objects and locations (e.g., GraspSkill(object=cup_1)).