> For the complete documentation index, see [llms.txt](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-1-planning-problem.md).

# 3.1 The AI Planning Problem

A **Classical Planning Problem** is a 4-tuple (Fikes & Nilsson, 1971; Ghallab et al., 1998; Ghallab et al., 2004):

$$\Pi = \langle F, A, I, G \rangle$$

The objective is to **find a sequence of actions** $a\_1, a\_2, \ldots, a\_n \in A$ such that applying them sequentially from initial state $I$ yields a state $s$ satisfying the goal $G$.

Let us unpack each component precisely.

## F — Fluents (Facts)

$F$ is a finite set of **Boolean state variables**, called *fluents* or *propositions*, that describe every relevant aspect of the world. Examples:

```pddl
on(A, B)             -- block A is on block B
at(truck1, city1)    -- truck1 is at city1
holding(robot, box3) -- robot is holding box3
fuel-level(rover, 80) -- rover fuel is 80 units (numeric fluent)
```

A **state** $s \subseteq F$ is any subset of fluents — those that are currently true. Fluents not in $s$ are assumed false. This is the **Closed World Assumption (CWA)**: *what is not explicitly stated is false* (Reiter, 1978). This assumption dramatically simplifies reasoning — there is no notion of "unknown" — and it is one of the key differences between planning and open-world knowledge representation.

**Numeric fluents** extend the basic Boolean model, allowing fluents to hold real-valued quantities (fuel levels, time, cost). Most modern planners support numeric fluents via PDDL2.1 (Fox & Long, 2003).

## A — Actions (Operators)

$A$ is a finite set of **action schemas**, each parameterized over typed object variables. An instantiated action $a$ has:

* **Preconditions** $\text{pre}(a) \subseteq F$: the set of fluents that must hold in the current state for $a$ to be *applicable*.
* **Add effects** $\text{eff}^+(a) \subseteq F$: fluents that become true after $a$ executes.
* **Delete effects** $\text{eff}^-(a) \subseteq F$: fluents that become false after $a$ executes.

State transition: if action $a$ is applicable in state $s$ (i.e., $\text{pre}(a) \subseteq s$), then the successor state is:

$$s' = (s \setminus \text{eff}^-(a)) \cup \text{eff}^+(a)$$

A **PDDL action definition** looks like this (from the Blocksworld domain):

```pddl
(:action stack
  :parameters (?x ?y - block)
  :precondition (and (holding ?x)
                     (clear ?y))
  :effect (and (on ?x ?y)
               (not (holding ?x))
               (not (clear ?y))
               (handempty)))
```

The `stack` action is applicable when the robot is `holding` block `?x` and block `?y` is `clear` (nothing is on top of it). After execution: `?x` is on `?y`; the robot is no longer holding `?x`; `?y` is no longer clear; the robot hand is empty.

**Durative actions** extend this model by adding explicit time durations and invariant conditions (fluents that must hold *throughout* the action's duration, not merely at its start) (Fox & Long, 2003).

## I — Initial State

$I \subseteq F$ is the **complete description of the world at time $t\_0$**. Every fluent is either in $I$ (true) or not (false, by CWA). The initial state must be complete — no fluent may be "unknown" in the classical model.

In practice, $I$ is specified in the PDDL *problem file*:

```pddl
(:init
  (on A B)
  (on B C)
  (on C table)
  (clear A)
  (handempty))
```

This completely specifies the initial configuration. Any fluent not listed (e.g., `holding robot box`) is false.

## G — Goal

$G \subseteq F$ is a **partial specification** of the desired world state. A state $s$ satisfies $G$ if and only if $G \subseteq s$ — the goal fluents hold, with all other fluents unconstrained. This partial specification is a critical design choice: goals describe *what must be true*, not *what the complete world looks like*.

In PDDL:

```pddl
(:goal (and (on C A)
            (on A table)))
```

This goal says: "C must be on A, and A must be on the table." It says nothing about what is on top of C, or where other objects are.

**Extended goal types** in modern problem classes include soft goals (desirable but not required, with assigned utility values), metric objectives (minimize plan cost, minimize makespan), temporal goals (achieve G before time T), and LTL goals (goals specified as Linear Temporal Logic formulas) (Baier & McIlraith, 2006).

## PDDL — The Standard Interface

The **Planning Domain Definition Language (PDDL)** is the standard input format for AI planners (Ghallab et al., 1998). Introduced for the 1998 International Planning Competition (IPC), PDDL has evolved through versions 1.0, 2.1, 2.2, 3.0, and 3.1, each adding expressiveness.

PDDL separates the specification into two files:

| File             | Contents                                            |
| ---------------- | --------------------------------------------------- |
| **Domain file**  | Types, predicates, function symbols, action schemas |
| **Problem file** | Objects, initial state, goal specification, metric  |

This separation enables **solver-agnosticism**: any PDDL-conformant planner can be swapped in or out without changing the problem specification. This modularity is directly exploited in neuro-symbolic pipelines (Chapter 4), where an LLM generates the PDDL and a classical planner solves it.

> \[!NOTE] PDDL is to planning what SQL is to databases: a declarative, domain-independent language that separates *what* to compute from *how* to compute it (Ghallab et al., 2004).

A related but distinct reasoning paradigm is **Answer Set Programming (ASP)**, which uses *stable model semantics* to support non-monotonic reasoning — defaults, exceptions, and incomplete knowledge. Unlike classical planning's Closed World Assumption (everything unspecified is false), ASP explicitly represents uncertainty through negation-as-failure. ASP is widely used for encoding planning problems with complex constraint structures and for reasoning about exceptions. Neuro-symbolic systems built on ASP are discussed in §4.2.3.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-1-planning-problem.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.