Task Graph

The fundamental data structure of a task graph is a Directed Acyclic Graph (DAG). This means:

• Directed: Edges have a direction, representing a flow of dependency or data from one task (node) to another.
• Acyclic: The graph contains no cycles, ensuring tasks cannot depend on themselves either directly or indirectly. This property is critical for guaranteeing that the workflow can terminate and prevents infinite execution loops.

This structure explicitly defines precedence constraints, making the order of operations unambiguous and schedulable.

Each node in the graph corresponds to a single, atomic unit of work. In a heterogeneous fleet context, a task node is defined by:

• Action Specification: The specific operation to perform (e.g., 'navigate to location A', 'pick item SKU-123').
• Resource Requirements: The formal capabilities needed for execution (e.g., a robot with a gripper, a forklift with 2-ton capacity).
• Estimated Parameters: Metadata such as expected duration, energy cost, or priority.

Nodes are the assignable entities for dynamic task allocation algorithms.

Edges (connections between nodes) encode the relationships that govern execution. There are two primary types of dependencies:

• Precedence/Control Dependency: A simple 'must-complete-before' relationship. Task B cannot start until Task A finishes.
• Data Dependency: Task B requires the output or product of Task A as an input. This is common in manufacturing or kitting workflows.

These edges create the partial order that allows a scheduler to identify which tasks are eligible for parallel execution (those with no unresolved dependencies).

A primary function of the task graph is to expose opportunities for parallel execution. By analyzing the DAG, a scheduler can determine the critical path (the longest sequence of dependent tasks) and identify independent branches that can be assigned to different agents simultaneously.

This analysis is key for minimizing makespan (total workflow completion time) in a multi-agent system. The width of the graph at any point indicates the maximum theoretical parallelism required.

The task graph serves as the definitive, machine-readable blueprint for schedulers and orchestrators. It allows algorithms to solve complex optimization problems, such as:

• Mapping tasks to heterogeneous agents based on capability matching.
• Ordering task execution to respect all dependencies.
• Allocating resources (like shared zones or charging stations) to avoid conflicts.

Algorithms like list scheduling or those based on the Hungarian algorithm for assignment operate directly on this graph structure.

While often constructed initially from a high-level plan, task graphs in real-world orchestration are not static. They must support dynamic modification to handle:

• Task Insertion: Adding new nodes for unexpected jobs or high-priority orders.
• Graph Pruning: Removing nodes associated with canceled tasks.
• Edge Rewiring: Adjusting dependencies in response to agent failure or task migration.

This requires the underlying orchestration middleware to manage graph versioning and propagate changes to all relevant agents in real-time.

In automated warehouses, a single customer order decomposes into a task graph where nodes represent discrete actions and edges enforce critical dependencies. For example:

• Pick Item A (Node 1)
• Pick Item B (Node 2)
• Merge Items at Pack Station (Node 3, depends on 1 & 2)
• Label & Route to Dock (Node 4, depends on 3) This structure allows parallel picking by multiple robots (AMRs) or workers, while ensuring items are merged correctly before packing. The graph's acyclic property prevents logical deadlocks, such as a robot waiting for an item that hasn't been picked yet.

Complex product assembly is modeled as a task graph to coordinate a heterogeneous fleet of robotic arms, automated guided vehicles (AGVs), and human stations. Each assembly step is a node, with edges dictating the sequence. For instance, a car door assembly graph might specify that welding must complete before painting, and painting must finish before handle installation. This enables just-in-time part delivery by AGVs and optimal station utilization. If a robot fails, the graph allows the scheduler to dynamically reassign the dependent downstream tasks to other available resources.

For a fleet of electric autonomous mobile robots (AMRs), daily operations form a spatial-temporal task graph. Nodes represent location-based tasks: Transport Pallet from A to B, Recharge Battery, or Perform Self-Diagnosis. Edges encode constraints like:

• A robot must be at the charging station (Node X) before it can execute the Recharge task (Node Y).
• A Transport task cannot start until the destination bay is clear (a dependency on another agent's task). The orchestrator continuously solves this graph to maximize throughput while adhering to battery and traffic constraints.

The real-time, automated process of assigning work items from a shared pool to agents based on capabilities, availability, and current system state. It is the primary mechanism for executing the plan defined by a task graph in a changing environment.

• Key Driver: Reacts to live events like new task arrivals, agent failures, or traffic delays.
• Contrast with Task Graph: The graph defines what needs to be done and in what order; dynamic allocation decides who does it and when.

The process of breaking down a complex, high-level goal into smaller, manageable sub-tasks that form the nodes of a task graph. This is a prerequisite for allocation.

• Hierarchical Planning: A 'Transport Pallet' job decomposes into: Navigate to Pickup, Lift Pallet, Navigate to Drop-off, Release Pallet.
• Granularity Impact: The level of decomposition directly affects allocation flexibility and parallelism opportunities.

The fundamental requirement in allocation that an assignment of tasks to agents must satisfy all hard constraints. The task graph's edges often define precedence constraints that must be respected.

• Common Constraints: Agent capability matches task requirements, temporal deadlines, spatial location, and the dependencies encoded in the task graph.
• Solver Role: Allocation algorithms are essentially constraint satisfaction solvers for a dynamic, optimization-weighted problem.

A class of algorithms that make task allocation decisions sequentially without complete future knowledge, which is the operational reality for most dynamic fleets. The task graph may be partially known or evolving.

• Reality Match: Tasks arrive unpredictably, and agent status changes in real-time.
• Algorithm Types: Includes greedy assignment, rolling-horizon optimization, and real-time auction mechanisms.

A decentralized coordination mechanism where tasks are treated as commodities to be traded among agents via auctions. This is one method to perform the allocation required by a task graph.

• Process: A manager announces a task (or sub-graph), agents bid based on cost or utility, and the contract is awarded.
• Protocol Example: The Contract Net Protocol is a canonical framework for this type of negotiation.

The simultaneous optimization of several, often conflicting, system-level goals during the allocation of a task graph's workload. The chosen allocation represents a trade-off.

• Common Objectives: Minimize makespan (total completion time), maximize fleet utilization, minimize energy consumption, and ensure fair workload distribution.
• Solution Set: The Pareto Frontier defines the set of optimal trade-off allocations.