Plan Verification

Verifies that the plan's sequence of actions is logically sound given the initial state and the defined preconditions and effects of each operator. This ensures no action is attempted in a state where its preconditions are false. For example, a plan to 'pick up block A' is invalid if the precondition 'block A is clear' is not met in the preceding state.

Formally demonstrates that executing the verified plan from the initial state will result in a world state where all specified goal conditions are satisfied. This is often done through state progression or theorem proving, simulating the plan forward to confirm the final state matches the goal description. A failure here indicates the plan solves the wrong problem.

Checks that the plan does not violate resource constraints, such as:

• Consumable resources (e.g., fuel, budget) are not exceeded.
• Reusable resources (e.g., tools, agents) are not double-booked.
• Temporal constraints (e.g., deadlines, durations) are respected. This prevents the generation of plans that are theoretically valid but practically impossible to execute.

Ensures the plan adheres to all safety invariants and domain-specific constraints that must never be violated. This is broader than preconditions and includes:

• Avoiding forbidden states (e.g., two agents in the same location).
• Maintaining critical conditions (e.g., a reactor temperature stays within safe bounds).
• Respecting ordering constraints between non-sequential tasks.

Confirms every action in the plan is primitive and mapped to a concrete, callable operation in the execution environment. In Hierarchical Task Networks (HTN), this means verifying the complete decomposition of all compound tasks into a sequence of primitive tasks. An abstract 'Navigate to site' task must be decomposed into specific 'Move forward', 'Turn', etc., commands.

The process of checking that a generated plan is syntactically correct and structurally sound according to the planning domain's formal specification. This is a prerequisite for full verification.

• Syntax Checking: Ensures the plan uses only defined operators with valid parameters.
• Constraint Satisfaction: Verifies that all ordering constraints and resource constraints are respected within the plan's structure.
• Precondition-Ordering Consistency: Checks that no action's preconditions are violated by the immediate effects of preceding actions, ignoring detailed state progression.

The dynamic process of executing a plan forward from the initial state within a model of the world to predict its outcomes. This is the core mechanism for verifying executability and goal achievement.

• State Progression: Starts with the initial state and sequentially applies each action's effects to generate a predicted future state.
• Precondition Checking: Before applying an action's effects, its preconditions are evaluated against the current simulated state. Failure indicates a non-executable plan.
• Goal State Test: The final predicted state is compared to the goal specification to confirm the plan's objective is met.

A formal verification method that exhaustively explores all possible states reachable by a system (or plan) to prove properties like safety ("nothing bad happens") and liveness ("something good eventually happens").

• State Space Exploration: Systematically traverses possible executions, often using techniques like symbolic model checking to handle large spaces.
• Temporal Logic: Properties are expressed in formal languages like Linear Temporal Logic (LTL) or Computation Tree Logic (CTL) (e.g., "Action B must always be preceded by Action A").
• Application in Planning: Used to verify plans for non-functional requirements, such as deadlock freedom or compliance with complex regulatory workflows.

The process of modifying an invalid plan to make it valid, rather than discarding it and replanning from scratch. It is often triggered by verification failure.

• Localized Fixes: Identifies the specific action or constraint causing the failure (e.g., a violated precondition) and makes minimal adjustments.
• Techniques: Includes action reordering, parameter substitution, inserting new corrective actions, or partial replanning for a segment of the plan.
• Efficiency: Can be significantly faster than full replanning, especially for large plans where only a small part is affected by a changing world state.

Fundamental properties of a planning algorithm that directly impact the verifiability of its outputs.

• Soundness: A planner is sound if every plan it generates is a verified solution (i.e., executable and achieves the goals). Sound planners produce correct-by-construction plans, simplifying downstream verification.
• Completeness: A planner is complete if it is guaranteed to find a plan whenever one exists for the given problem. Incomplete planners may fail to find valid plans, but the plans they do produce may still require verification.
• HTN Planners: Algorithms like SHOP are typically both sound and complete with respect to their domain description.

The standardized formal language used to define planning domains and problems. It provides the semantic foundation for plan verification.

• Domain File: Declares predicates (properties of the world), actions/operators (with preconditions and effects), and optionally HTN methods and tasks.
• Problem File: Specifies the initial state (a set of true predicates) and the goal condition.
• Verification Role: A plan verifier uses the PDDL domain and problem as the ground truth against which to simulate and validate a candidate plan. The plan itself is a sequence of instantiated actions from the domain.