PDDL (Planning Domain Definition Language)

The domain file is a reusable template that defines the types of objects, predicates (properties and relationships), and actions available in a planning world. It uses first-order logic to specify the rules of change.

• Types: Define hierarchies of object categories (e.g., robot, location - thing, package - thing).
• Predicates: Define properties that can be true or false about the world state (e.g., (at ?r - robot ?l - location), (loaded ?r - robot ?p - package)).
• Actions: Defined using :parameters, :precondition (logical formula that must be true to execute), and :effect (logical formula describing state changes).

The problem file defines a concrete planning instance by specifying the initial state and the goal condition using the predicates declared in the domain.

• Objects: Instantiates the domain's types with concrete instances (e.g., r1 - robot, locA locB - location, pkg1 - package).
• Init: A complete list of all predicates that are true in the starting world state. All unlisted predicates are assumed false (Closed World Assumption).
• Goal: A logical formula describing the set of world states that constitute a solution (e.g., (and (at pkg1 locB) (at r1 locA))).

An action schema is a parameterized operator that defines how the agent can transform the world. It is the core construct for modeling capabilities.

• Structure: (:action drive :parameters (?r - robot ?from ?to - location) :precondition (and (at ?r ?from) (connected ?from ?to)) :effect (and (not (at ?r ?from)) (at ?r ?to)))
• Precondition: A conjunction/disjunction of predicates that must hold for the action to be applicable.
• Effect: Specifies which predicates become true (add list) and which become false (delete list) after execution, directly addressing the frame problem by defining what changes.

PDDL is modular. The :requirements stanza in the domain declares which language features are needed, enabling planners to support advanced capabilities.

Core requirements include:

• :strips - The basic action representation (preconditions, add/delete effects).
• :typing - Support for object types.
• :equality - Support for the = predicate.
• :negative-preconditions - Allow not in preconditions.
• :disjunctive-preconditions - Allow or in preconditions.
• :conditional-effects - Effects that depend on state (when).
• :durative-actions - For temporal planning (PDDL 2.1).
• :numeric-fluents - For continuous numeric state variables.

STRIPS (Stanford Research Institute Problem Solver) is the historical and conceptual foundation for PDDL. A STRIPS-style domain in PDDL uses only the core :strips requirement.

Key STRIPS Assumptions:

• States are represented as sets of ground (instantiated) logical atoms.
• Actions have a precondition list (conjunction of positive literals).
• Actions have an add list and a delete list for effects.
• The world is static, fully observable, and deterministic. Most classical planners are designed to solve STRIPS problems efficiently, making it the most widely supported PDDL subset.

Domain Snippet (logistics-domain.pddl):

lispCopy
(define (domain logistics)
  (:requirements :strips :typing)
  (:types location vehicle - object package - object)
  (:predicates (at ?obj - object ?loc - location)
               (in ?pkg - package ?v - vehicle))
  (:action load
    :parameters (?pkg - package ?v - vehicle ?loc - location)
    :precondition (and (at ?pkg ?loc) (at ?v ?loc))
    :effect (and (not (at ?pkg ?loc)) (in ?pkg ?v)))
)

Problem Snippet (deliver-p1.pddl):

lispCopy
(define (problem deliver-p1)
  (:domain logistics)
  (:objects pkg1 - package truck1 - vehicle locA locB - location)
  (:init (at pkg1 locA) (at truck1 locA))
  (:goal (at pkg1 locB))
)

A valid plan: (load pkg1 truck1 locA), (drive truck1 locA locB), (unload pkg1 truck1 locB).

A search* is the quintessential algorithm for solving PDDL-specified planning problems optimally. It navigates the state space by evaluating nodes using the function f(n) = g(n) + h(n), where:

• g(n) is the actual cost from the initial state to node n.
• h(n) is a heuristic function estimating the cost from n to the goal. For optimality, h(n) must be an admissible heuristic (never overestimates). Modern planners use sophisticated, domain-independent heuristics like FF or LM-cut derived automatically from the PDDL description.

HTN Planning is a more knowledge-intensive paradigm than classical STRIPS planning. Instead of searching over primitive actions, it decomposes high-level tasks using domain-specific methods. While PDDL has a separate syntax for HTN (PDDL 3.1 with :htn), the core distinction is:

• Classical PDDL: Specifies what actions do.
• HTN PDDL: Also specifies how to combine them via task networks. This makes HTN planners like SHOP2 highly efficient for complex, structured domains like manufacturing or logistics where procedural knowledge is available.

SATPlan is a powerful alternative to state-space search that converts a bounded-length planning problem into a propositional logic formula. The process is:

1. Encode the PDDL problem (initial state, actions, goal) for a fixed plan length k into a Boolean Satisfiability (SAT) problem.
2. Use a high-performance SAT solver (e.g., Glucose, MiniSat) to find a satisfying assignment.
3. Decode the assignment back into a sequence of actions. This approach excels on highly combinatorial problems where logical reasoning outperforms direct search, leveraging decades of advances in SAT solver technology.

Plan validation is the critical process of verifying that a candidate plan (a sequence of action names) is a correct solution for a given PDDL problem. A validator (like VAL) performs a deterministic simulation:

• Starts from the defined initial state.
• For each action, checks all preconditions are met in the current state.
• Applies the action's effects to update the state.
• Confirms the final state satisfies all goal conditions. This provides a formal, executable proof of correctness, essential for deploying plans in safety-critical autonomous systems.

PDDL extends beyond classical Boolean logic to model real-world constraints via requirements like :durative-actions and :numeric-fluents.

• Temporal PDDL: Actions have explicit durations and can execute concurrently. Planners must satisfy complex temporal constraints.
• Numeric PDDL: State includes real-valued fluents (e.g., (battery-level rover1) 50.5). Actions can increment/decrement these values via numeric effects. Planners like OPTIC and Temporal Fast Downward solve these complex problems, enabling scheduling and resource management directly from a rich PDDL model.