Parallel Task

The defining feature of a parallel task is that its constituent subtasks are designed to be executed concurrently, not sequentially. This is formally represented in the task network by a lack of ordering constraints between the subtasks, allowing a planner or executor to schedule them in parallel, subject to resource availability. For example, in a data processing pipeline, subtasks like 'Fetch User Data', 'Fetch Product Catalog', and 'Load Pricing Rules' could be modeled as parallel subtasks to minimize overall latency.

While subtasks can run in parallel, their execution is not unconstrained. Key limitations include:

• Resource Constraints: Subtasks may compete for finite resources (e.g., CPU cores, memory, network bandwidth, specialized hardware). A valid plan must ensure the sum of required resources does not exceed availability.
• Synchronization Points: Some subtasks may produce outputs that are required as inputs for others, creating implicit ordering. This is often managed through dataflow dependencies or explicit post-conditions and preconditions. For instance, 'Compile Module A' and 'Compile Module B' can run in parallel, but 'Link Final Executable' must wait for both to complete.

In Hierarchical Task Network (HTN) planning, a parallel task is decomposed using a method that specifies a network of subtasks without imposing a total order. The planner's role is to further decompose these subtasks (which may themselves be compound) and then schedule the resulting primitive actions, respecting all constraints. This differs from a Sequential Task, where the method explicitly defines a strict order for subtask execution.

Parallel tasks manifest in several concrete software and system patterns:

• MapReduce Operations: The 'map' phase is inherently a parallel task, applying the same function to many data elements simultaneously.
• Microservice Orchestration: A coordinator service may invoke multiple downstream services (e.g., payment, inventory, notification) in parallel to fulfill a single user request.
• Computer Vision Pipelines: Tasks like object detection, optical character recognition, and depth estimation on a single image frame can be executed in parallel.
• Multi-Agent Collaboration: In a Multi-Agent System, agents may be assigned parallel subtasks of a larger mission, operating independently before reconvening.

Integrating parallel tasks into a planner introduces complexity. The planner must:

1. Resolve Resource Contention: Allocate shared resources (locks, pools) to prevent deadlock or starvation.
2. Handle Partial Failures: Manage the failure of one subtask without necessarily aborting all sibling tasks, requiring robust error-handling logic.
3. Optimize for Throughput vs. Latency: Decide the degree of parallelism based on system load and cost. Excessive parallelism can lead to thrashing and increased overhead. Algorithms like Graphplan and HTN planners with concurrency extensions are designed to reason about these parallel action effects and constraints.

It's crucial to distinguish a Parallel Task from similar structures:

• vs. Sequential Task: Subtasks have a strict, predefined execution order.
• vs. Iterative Task: Involves repeatedly executing a (sub)task loop until a condition is met, which may be sequential or parallel internally.
• vs. Conditional Task: Execution path depends on runtime state evaluation; only one branch is taken.
• vs. Independent Tasks: While parallel tasks imply concurrency, they are part of a coordinated parent task with shared goals and constraints, unlike completely independent processes.

A compound task whose subtasks must be executed in a strict, predefined order. This is the fundamental counterpart to a parallel task.

• Key Mechanism: Enforces a total or partial ordering over subtasks.
• Example: In a manufacturing HTN, the task Assemble Product might decompose into sequential subtasks: 1. Attach Component A, 2. Attach Component B, 3. Perform Quality Check. Step 2 cannot begin until Step 1 is confirmed complete.
• Contrast with Parallel: While parallel tasks exploit concurrency, sequential tasks model necessary dependencies and causal relationships where the output of one subtask is the input for the next.

A temporal relation specifying that one task or action must be performed before another within a plan. These constraints define the permissible execution schedules for parallel and sequential tasks.

• Formal Role: In an HTN, methods impose ordering constraints on the subtask network they create.
• Types: Can be strict (A < B) or allow concurrency (A || B). Parallel tasks have minimal ordering constraints, often only where resource conflicts or state dependencies exist.
• Example: For a parallel task Process Batch, constraints might state Validate Input < Transform Data and Validate Input < Log Transaction, but allow Transform Data and Log Transaction to run in parallel.

A limitation on the availability of consumable or reusable assets (e.g., CPU cores, memory, robotic arms, network bandwidth) that must be respected during task decomposition and plan execution. This is the primary factor limiting true parallelism.

• Critical for Parallelism: A planner cannot schedule two subtasks to run concurrently if they both require exclusive access to the same non-shareable resource.
• Modeling: Defined in the HTN domain description. A method for a parallel task must account for the resource profiles of its subtasks.
• Example: An Analyze Sensor Data parallel task may have three identical subtasks, but if the system only has two available GPU instances, the planner must serialize the third subtask or find an alternative decomposition.

A high-level, abstract task in an HTN that must be decomposed into subtasks before it can be executed. Parallel and Sequential tasks are specific types of compound tasks.

• Hierarchical Nature: Serves as a placeholder for complexity. The planner's job is to replace it with a concrete network of subtasks using applicable methods.
• Parent Class: Parallel Task is a specialization of Compound Task where the chosen method's subtask network is designed for concurrent execution.
• Example: Coordinate Disaster Response is a compound task. One of its methods might decompose it into parallel subtasks like Dispatch Medical Teams, Set Up Communications, and Assess Structural Damage, each of which are themselves compound tasks.

A schema that defines a possible way to decompose a compound task into a network of subtasks, given certain preconditions are met. It is the rulebook for creating parallel, sequential, or other task structures.

• Architect's Tool: Different methods for the same compound task can represent different strategies, some parallel, some sequential.
• Components: Contains (1) the compound task it decomposes, (2) preconditions, and (3) a subtask network with ordering constraints.
• Example for Parallelism: A method for Generate Quarterly Report could have a subtask network where Compile Sales Data, Analyze Marketing Spend, and Calculate Operational Costs are all siblings with no ordering constraints between them, defining a parallel task.

The phase where a generated plan's primitive actions are carried out in the real world or a simulated environment. For parallel tasks, this requires a runtime capable of managing concurrency, synchronization, and failure handling.

• Runtime System: Must spawn and manage multiple execution threads/processes for parallel subtasks, respecting the plan's ordering and resource constraints.
• Critical for Parallel Tasks: The executor must monitor all concurrent branches and implement failure policies (e.g., kill all parallel tasks if one critical subtask fails).
• Link to Replanning: If a parallel subtask fails or a resource becomes unavailable, the system may need to trigger replanning to find a new viable decomposition or schedule.