Planning Domain Definition Language (PDDL)

A PDDL domain file defines the static rules, capabilities, and logic of the planning environment. It is a reusable template that specifies:

• Types: A hierarchy of object categories (e.g., location, robot, package).
• Predicates: Boolean properties that describe the state of the world (e.g., (at ?robot ?location), (loaded ?package)).
• Actions: The operations an agent can perform. Each action is defined by:
  • Parameters: Variables that are instantiated with objects.
  • Preconditions: Logical statements that must be true for the action to be executable.
  • Effects: How the action changes the world state, including add effects (new true predicates) and delete effects (predicates that become false).

Example: A logistics domain defines types like truck and city, predicates like (at ?truck ?city), and an action drive with preconditions (at ?truck ?from) and effects (not (at ?truck ?from)) (at ?truck ?to).

A PDDL problem file defines a concrete planning instance within a given domain. It provides the specific details that the planner must reason about:

• Objects: The concrete instances of the domain's types (e.g., truck1 - truck, paris - city).
• Initial State: A complete snapshot of the world at the start, expressed as a conjunction of ground predicates that are true (e.g., (at truck1 london), (fuel truck1 100)). All unmentioned predicates are assumed false (the closed-world assumption).
• Goal Specification: A (possibly complex) logical formula describing the desired end state (e.g., (and (at packageA paris) (at packageB berlin))).

The planner's task is to find a sequence of instantiated domain actions that transforms the initial state into a state satisfying the goal.

Actions are the fundamental operators that drive state transitions. Their formal structure is what makes planning deterministic and verifiable.

• Preconditions: A conjunction of literals (positive or negated predicates) that must hold in the current state for the action to be legally applied. This enforces the causal laws of the domain.
• Effects: Describe the state change. PDDL uses the STRIPS assumption: effects explicitly list all predicates that change.
  • Add List: Predicates that become true.
  • Delete List: Predicates that become false (also known as negative effects).

This (precondition → effect) model allows planners to perform forward search (applying actions to the initial state) or backward search (regressing from the goal).

PDDL supports a simple type system to categorize objects and constrain action parameters, making domain models more compact and less error-prone.

• Objects are declared with a type (e.g., parcel23 - parcel).
• Types can be organized in an inheritance hierarchy using the either keyword or a direct subtype notation (in later PDDL versions), allowing for generality. For example, a type vehicle could have subtypes truck and airplane.
• Action parameters are typed, so (drive ?v - vehicle ?from ?to - location) can only be instantiated with objects of type vehicle and location. This typing is crucial for efficient grounding—the process of creating all possible concrete action instances from the domain and problem objects.

Derived predicates (or axioms) are a PDDL feature that allows certain facts to be inferred logically from the current state, rather than being directly changed by actions. They are defined by a logical rule.

• Syntax: (:derived (predicate ?args) (logical-formula))
• Use Case: They model state constraints or abstract properties. For example, (connected ?x ?y) might be derived from a complex graph structure of (road ?a ?b) facts. Or (above ?a ?b) could be derived from a stack of blocks.
• Semantics: The truth value of a derived predicate is re-evaluated in every state based on its rule. This separates definitional knowledge from causal knowledge (actions), leading to more expressive and maintainable domain models.

PDDL has evolved through standardized competition versions, each adding expressivity for more complex planning problems.

• PDDL 1.2 (STRIPS): The base level with types, actions (preconditions, add/delete effects).
• PDDL 2.1: Introduced numeric fluents (e.g., (fuel-level ?truck)) and durative actions for temporal planning.
• PDDL 3.0: Added state trajectory constraints and preferences, allowing for soft goals and constraints on the entire plan execution path.
• Later Extensions: Include probabilistic effects (for non-deterministic planning), hierarchical task networks (HTN) for task decomposition, and constraints for integrated planning and scheduling. This layered design allows planners to support only the features they need, from simple classical planners to complex temporal/numeric solvers.

STRIPS (Stanford Research Institute Problem Solver) is the foundational representation language and planning system from which PDDL was derived. It introduced the core logical formalism for describing planning problems using:

• States: Represented as conjunctions of ground literals (facts).
• Actions: Defined by preconditions (what must be true to execute), add effects (facts made true), and delete effects (facts made false).
• Goals: A set of literals the planner must make true. PDDL extends STRIPS with typing, conditional effects, and durative actions, but the core action representation remains STRIPS-based.

Automated planning is the overarching field of AI concerned with the algorithmic generation of action sequences (plans) to achieve specified goals. PDDL serves as the standard modeling language for defining problems within this field. Key sub-areas include:

• Classical Planning: Assumes a deterministic, fully observable, static environment (PDDL's primary domain).
• Temporal Planning: Incorporates time and concurrent actions (modeled in PDDL 2.1).
• Probabilistic Planning: Deals with uncertainty in action outcomes.
• Hierarchical Task Network (HTN) Planning: Decomposes high-level tasks into primitive actions. Planners that read PDDL files, like Fast Downward or POPF, are the solvers in this paradigm.

A Markov Decision Process (MDP) is a mathematical framework for modeling sequential decision-making under uncertainty. It contrasts with classical PDDL planning by incorporating:

• Probabilistic State Transitions: Actions lead to a distribution of possible next states.
• Reward Function: Quantifies the desirability of state-action pairs (vs. a Boolean goal in PDDL).
• Optimization Criterion: Seeks to maximize cumulative reward over time. While PDDL models deterministic environments for plan synthesis, MDPs model stochastic environments for policy learning (e.g., via Reinforcement Learning). They represent complementary approaches to solving action-selection problems.

Hierarchical Task Network (HTN) planning is an approach where the planner decomposes high-level tasks into networks of subtasks until primitive actions are reached. It differs from PDDL's state-space search:

• Domain Knowledge: Uses hand-crafted methods that define how to achieve a task, providing strong guidance.
• Task Reduction: Focuses on refining abstract tasks, not just satisfying preconditions.
• Expressivity: Often more natural for modeling complex, procedural domains. Extensions like PDDL3.0 allow for expressing some HTN-like constraints, but HTN remains a distinct, more knowledge-intensive planning paradigm.

SAT and SMT solving are core technologies behind many modern optimal PDDL planners. This approach, known as planning as satisfiability:

• Encodes the planning problem (states, actions, goals over n steps) into a gigantic logical formula.
• Uses a SAT/SMT solver to determine if a satisfying assignment exists, which corresponds to a valid plan.
• Enforces optimality by iteratively checking for plans of length k, finding the shortest possible plan. This method transforms the search problem into a logical inference problem, leveraging highly optimized solvers like Glucose or Z3 to handle the combinatorial complexity of planning.

Model Predictive Control (MPC) is an online, receding-horizon control technique used in robotics and process engineering. It shares a conceptual lineage with planning:

• Uses a Model: Relies on an explicit model of system dynamics (similar to a PDDL domain).
• Solves an Optimization: At each control cycle, it solves a finite-horizon planning/optimization problem to generate a sequence of actions.
• Implements First Action: Executes only the first action, then re-plans with new state feedback. While classical PDDL planners often seek a full plan to a fixed goal, MPC is characterized by continuous re-planning based on a changing objective and state, making it suitable for dynamic environments where PDDL alone is insufficient.