> 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.md).

# Chapter 3: Formal Foundations

> *"A problem well-defined is a problem half-solved."*\
> — Charles Kettering (adapted)

Before a neural network can be plugged into a planning system, someone must understand what a planning system actually is. This chapter provides that foundation. It establishes the mathematics that underpin every neuro-symbolic planning architecture covered in Chapter 4: the formal vocabulary of states, actions, and goals; why planning is computationally hard and what that hardness means in practice; the full spectrum of problem classes from deterministic to probabilistic to hierarchical; and the key extensions that real-world deployments require.

## What This Chapter Covers

* **§3.1** — The classical $\langle F, A, I, G \rangle$ planning formalism and PDDL, the universal solver interface.
* **§3.2** — Computational complexity results (PSPACE-completeness, NP-hardness) and why they justify neural approximations.
* **§3.3** — Real-world planning problem classes: OSP, conformant, contingent, MDP, and POMDP.
* **§3.4** — Hierarchical Task Network (HTN) planning and its structural connection to LLM task decomposition.
* **§3.5** — Extensions for temporal, numeric, and multi-agent settings, plus chapter summary, open problems, and exercises.

## Sections

* [3.1 The AI Planning Problem — Formal Definition](/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-1-planning-problem.md)
* [3.2 Computational Complexity of Planning](/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-2-complexity.md)
* [3.3 Planning Problem Classes](/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-3-problem-classes.md)
* [3.4 Hierarchical Task Network Planning](/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-4-htn.md)
* [3.5 Extensions: Temporal, Numeric, and Multi-Agent Planning](/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-5-extensions.md)


---

# 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.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.