Ordering Constraint

An ordering constraint is a binary relation, typically written as T1 < T2, which asserts that task T1 must be completed before task T2 can begin. This is not a suggestion but a hard requirement for plan validity.

• Strict Partial Order: The set of constraints forms a directed acyclic graph (DAG), preventing impossible circular dependencies (e.g., T1 < T2 and T2 < T1).
• Causal Link Enforcement: Often encodes causal relationships; a task that produces a resource must precede a task that consumes it.
• Foundation for Schedules: These constraints are the primary input for temporal planners and schedulers to generate executable timelines.

In Hierarchical Task Network (HTN) planning, ordering constraints are introduced by decomposition methods. When a compound task is decomposed into a network of subtasks, the method specifies not only the subtasks but also the necessary ordering between them.

• Method Specification: A method defines a partial order over its subtask network. For example, a Bake-Cake method may impose: [Mix-Ingredients] < [Pour-Into-Pan] < [Bake-In-Oven].
• Hierarchical Propagation: Constraints are propagated through the decomposition tree. A constraint on a high-level compound task translates into constraints on the primitive actions in its final decomposition.
• Flexibility vs. Rigidity: Methods can specify fully sequential, fully parallel, or partially ordered networks, offering different balances of flexibility to the planner.

Ordering constraints can vary in expressivity, allowing planners to model complex real-world processes.

• Simple Precedence (<): The most common type: T1 before T2.
• Concurrency (=): Specifies that two tasks can or must occur simultaneously (often modeled as an absence of an ordering constraint).
• Temporal Intervals: Advanced constraints may use Simple Temporal Networks (STNs), specifying minimum and maximum delays between tasks (e.g., [5min, 30min] between Apply-Primer and Apply-Paint).
• Resource-Based Ordering: Implicit constraints arise from shared resources. If two tasks require the same non-sharable resource (e.g., a robotic arm), a mutex (mutual exclusion) constraint is added, forcing an ordering.

Finding a valid sequence of tasks that satisfies all ordering constraints is a classic Constraint Satisfaction Problem (CSP). The planner's search algorithm must find a total linear order of tasks consistent with the partial order.

• Variables: The tasks to be scheduled.
• Domains: The possible time slots or positions in the sequence.
• Constraints: The set of ordering relations (<) between variables.
• Solution: A total ordering (a schedule) that does not violate any constraint. Algorithms like topological sort are used to find such an order if one exists.

Ordering constraints rarely exist in isolation; they interact with other domain limitations to define a feasible plan.

• Resource Constraints: Ordering must be resolved to avoid resource conflicts. For example, two tasks requiring the same machine must be ordered.
• Preconditions and Effects: A task's preconditions must be made true by the effects of earlier tasks. This creates implicit causal ordering constraints.
• Temporal Constraints: Must be consistent with deadlines, durations, and windows. A plan satisfying all ordering constraints may still fail if it violates a task's deadline.
• State Constraints: The world state must satisfy certain conditions throughout execution, which can force or prohibit specific orderings.

Consider an HTN for Deploy-Microservice. A method decomposes it into subtasks with critical ordering constraints:

1. Run-Unit-Tests < Build-Container-Image (Must pass tests before building.)
2. Build-Container-Image < Push-To-Registry
3. Update-Config-Map < Rollout-Deployment (New configuration must be set before deploying new pods.)
4. Rollout-Deployment < Run-Integration-Tests

These constraints prevent catastrophic errors like deploying untested code or new pods with old configuration. The HTN planner's role is to ensure any final sequence of primitive actions (e.g., shell commands) respects this partial order, potentially interleaving tasks from different method decompositions while maintaining all constraints.

A planning formalism where a high-level goal is recursively broken down into a network of subtasks using decomposition methods until only primitive, executable actions remain. Ordering constraints are explicitly defined within these method schemas to ensure subtasks are sequenced correctly.

• Core Concept: Represents tasks at multiple levels of abstraction.
• Relation to Ordering: Ordering constraints are embedded within the task network produced by each decomposition method.

A logical condition on the world state that must be true for a planning operator or HTN method to be applicable. While distinct, preconditions often create implicit ordering constraints; a task that establishes a precondition for another must logically precede it.

• Example: A Grasp(Object) operator may have the precondition Object is Reachable. A preceding MoveTo(Object) task would satisfy this, creating a temporal dependency.

A compound task whose decomposition yields subtasks that must be executed in a strict, predefined linear order. This is the most explicit and rigid form of an ordering constraint within an HTN.

• Implementation: Defined within a method's task network using a total order (e.g., (task1 < task2 < task3)).
• Contrast: Differs from Parallel Tasks or Iterative Tasks, which have different temporal structures.

The formal process of checking that a generated plan is executable and achieves the desired goals from the initial state. A critical step in this verification is ensuring all ordering constraints are satisfied and that no task violates the preconditions of a later task.

• Purpose: Guarantees plan validity before execution.
• Key Check: Validates that the sequence of primitive actions respects all declared temporal relations.

A mathematical problem defined by a set of variables, their domains, and a set of constraints limiting value combinations. Planning with ordering constraints can be framed as a CSP, where variables represent task start times and constraints encode the required temporal relations.

• Relation: Ordering constraints (e.g., Task A before Task B) are a specific type of binary constraint in this framework.
• Solver Use: CSP solvers can find feasible task orderings that satisfy all constraints.

A seminal, forward-search HTN planning algorithm that interleaves planning with state progression. SHOP dynamically enforces ordering constraints during its depth-first search by decomposing tasks in the order they appear in the method's task network.

• Key Trait: Operates on totally ordered task networks, making ordering constraint enforcement straightforward.
• Impact: Its efficiency demonstrated the practical value of explicit hierarchical ordering in planning.