> 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-5-extensions.md). # 3.5 Extensions: Temporal, Numeric & Multi-Agent Classical planning as defined in §3.1 assumes instantaneous actions and Boolean state. Three important extensions address real-world requirements that practitioners frequently encounter. ## Temporal Planning **PDDL 2.1** (Fox & Long, 2003) introduced **durative actions** — actions with explicit start time, duration, and end time, with conditions that must hold at the start, throughout, or at the end of execution. Temporal planning addresses scheduling problems where actions must be parallelized, deadlines must be met, or actions have ordering and overlap constraints. The temporal planning problem is **PSPACE-hard**, inheriting this lower bound from classical planning (since classical planning is a special case of temporal planning). For temporal planning with numeric fluents and continuous time effects — the full PDDL 2.1+ semantics — the problem may be harder or undecidable in the general case (Fox & Long, 2003, discuss these decidability concerns in §5 of their language specification paper; formal undecidability proofs for specific numeric planning fragments appear in subsequent complexity literature). The PSPACE-completeness result applies to restricted discrete-time fragments only. In practice, practical temporal planners — **OPTIC** (Benton et al., 2012) and **ENHSP** (Scala et al., 2016) — handle the durations of hundreds of actions in real scheduling scenarios. **Neuro-symbolic relevance:** Temporal planning is the natural setting for satellite scheduling (Remote Agent, §2.1), surgical workflow planning, and manufacturing line scheduling — all domains discussed in this book. ## Numeric Planning Numeric planning extends PDDL with **numeric fluents**: real-valued state variables that actions can increment, decrement, or set. This enables modeling resource consumption (fuel, battery, budget), accumulated quantities (total distance, total cost), and complex preconditions (temperature must be between 20 and 30°C). **Complexity:** Numeric planning is **undecidable in general** when numeric fluents are unbounded and actions can multiply or non-linearly update them — this follows from a reduction from the halting problem for counter machines (Helmert, 2002). Restricted fragments with bounded numeric state (e.g., only increment/decrement by constants) remain decidable. The decidable fragment with linear arithmetic on numeric fluents is PSPACE-hard, inheriting the lower bound from propositional planning. Practitioners should treat any problem with unbounded numeric values and multiplicative effects as potentially undecidable and verify termination empirically. **PDDL+ extensions** (Fox & Long, 2006) further add continuous change (a battery drains continuously while in use) and exogenous events (the tide rises at a predictable rate). These extensions are essential for energy management, logistics planning with costs, and any domain with physical resource constraints. ## Multi-Agent Planning Multi-agent settings — where multiple agents plan jointly, cooperatively, or competitively — introduce coordination, communication, and strategic reasoning that classical single-agent planning does not address. Key references: **MA-STRIPS** (Brafman & Domshlak, 2008) for cooperative multi-agent planning, and **Conflict-Based Search (CBS)** (Sharon et al., 2015) for Multi-Agent Path Finding (MAPF), which is one of the most practically deployed planning algorithms (in warehouse robots, drone coordination, game AI). **Neuro-symbolic relevance:** All three extensions are active research areas at ICAPS where neuro-symbolic approaches are beginning to appear: neural heuristics for temporal planning, learned numeric constraint approximators, and neural coordination policies for multi-agent settings. *** ## Chapter Summary The four components of a classical planning problem — $\langle F, A, I, G \rangle$ — provide the formal vocabulary for everything that follows. PDDL is the standardized language that lets practitioners express any problem in this vocabulary and hand it to any conformant solver. The computational complexity results (PSPACE-complete for plan existence; NP-complete for bounded planning) explain why heuristics are necessary and why learned approximations from neural components are valuable. The problem classes — OSP (NP-hard), conformant (Σ₂ᴾ-complete), contingent (PSPACE-complete), MDP (polynomial for finite state spaces), POMDP (PSPACE-hard for finite horizon, undecidable for infinite horizon), and HTN (EXPTIME-complete for total/partial order; undecidable for recursive methods) — capture the full spectrum of real-world planning challenges. HTN planning is particularly important for neuro-symbolic practitioners because it naturally bridges the gap between hierarchical LLM reasoning and formally verifiable planning. Neuro-symbolic systems address each of these settings, and Chapter 4 shows how. *** ## Open Problems **Open-world planning with partial knowledge.** The Closed World Assumption (Section 3.1) is fundamental to classical planning's tractability. Real-world agents operate in open worlds where many facts are unknown. Extending planning to open-world settings — with incomplete initial states, unknown action effects, and incomplete goal specifications — while maintaining useful computational guarantees is an active research frontier. **Learning domain models from interaction.** Classical planning requires a manually specified domain model. Methods for *learning* PDDL domain models from execution traces (action sequence + observed state transitions) are nascent. Recent work on FAMA (Aineto et al., 2019), LOCM (Cresswell et al. 2013), and LLM-based domain induction (Chapter 2) each tackle a fragment of this problem; a general solution remains elusive. **HTN method library acquisition.** SHOP2 and other HTN systems require manually authored method libraries. Learning HTN methods from demonstration (imitation learning with hierarchical structure) is an open problem with significant practical implications for the LLM decomposition connection described in Section 3.4. **Scalable POMDP solutions with neural belief representations.** Classical POMDP solvers do not scale to the raw observation spaces (images, language) that real-world agents encounter. Replacing the symbolic belief state with a neural representation (a latent variable model) while maintaining the formal planning guarantees of POMDP is an unsolved theoretical and engineering challenge. *** ## Exercises **Exercise 3.1 — PDDL Formulation.** Write a complete PDDL domain and problem file for the following scenario: A logistics company has two trucks, three cities, and five packages. Each truck can carry at most two packages. Packages must be delivered to specified destinations. Specify: types, predicates, action schemas (load, unload, drive), initial state, and a goal configuration. Verify your PDDL is valid using Pyperplan or Fast Downward (see Appendix). **Exercise 3.2 — Complexity Analysis.** The OSP problem is described as NP-hard in Section 3.3. Prove this by reduction: show that the 0/1 knapsack problem reduces in polynomial time to OSP. What does this imply for the tractability of exact OSP solvers versus approximate algorithms? **Exercise 3.3 — HTN vs. Classical Planning.** Consider a manufacturing domain where a robot must assemble a product from components. Design both a classical PDDL representation and an HDDL hierarchical representation for the same problem. Compare: (a) the size of the problem specification, (b) the expected planner search time, and (c) the interpretability of the resulting plan. Under what conditions would you prefer each formulation? **Exercise 3.4 — CWA Implications.** The Closed World Assumption (Section 3.1) assumes anything not listed in the initial state is false. Give three realistic scenarios where this assumption causes a planning system to behave incorrectly or unsafely. For each, describe how you would modify the planning model (e.g., using conformant planning, POMDP, or open-world extensions) to handle the uncertainty correctly. **Exercise 3.5 — HTN Decomposition from LLM Output.** Ask an LLM (e.g., GPT-4 or Claude) to plan a software product launch in 30 steps. Extract the hierarchical structure of the plan and encode it as HDDL methods. Identify: (a) where the LLM's decomposition violates HTN applicability conditions, (b) where it introduces circular dependencies, and (c) how a formal HTN verifier would improve reliability. *** ## References 1. Fikes, Richard E., and Nils J. Nilsson. "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving." *Artificial Intelligence* 2.3–4 (1971): 189–208. 2. Ghallab, Malik, et al. "PDDL — The Planning Domain Definition Language." *IPC Technical Report CVC TR-98-003*, Yale Center for Computational Vision and Control, 1998. 3. Ghallab, Malik, Dana Nau, and Paolo Traverso. *Automated Planning: Theory and Practice*. Morgan Kaufmann, 2004. 4. Fox, Maria, and Derek Long. "PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains." *Journal of Artificial Intelligence Research* 20 (2003): 61–124. 5. Baier, Jorge A., and Sheila A. McIlraith. "Planning with First-Order Temporally Extended Goals Using Heuristic Search." *Proceedings of AAAI*, 2006. 6. Bylander, Tom. "The Computational Complexity of Propositional STRIPS Planning." *Artificial Intelligence* 69.1–2 (1994): 165–204. 7. Erol, Kutluhan, Dana Nau, and V. S. Subrahmanian. "Complexity, Decidability and Undecidability Results for Domain-Independent Planning." *Artificial Intelligence* 76.1–2 (1995): 75–88. 8. Smith, David E. "Choosing Objectives in Over-Subscription Planning." *Proceedings of ICAPS*, 2004, pp. 393–401. 9. Van den Briel, Menkes, Romeo Sanchez Nigenda, Minh B. Do, and Subbarao Kambhampati. "Effective Approaches for Partial Satisfaction (Over-Subscription) Planning." *Proceedings of AAAI*, 2004, pp. 562–569. 10. Mirkis, Vitaly, and Carmel Domshlak. "Landmarks in Oversubscription Planning." *Proceedings of ECAI*, 2014. 11. Goldman, Robert P., and Mark S. Boddy. "Expressive Planning and Explicit Knowledge." *Proceedings of AIPS*, 1996, pp. 110–117. 12. Peot, Mark A., and David E. Smith. "Conditional Nonlinear Planning." *Proceedings of AIPS*, 1992, pp. 189–197. 13. Puterman, Martin L. *Markov Decision Processes: Discrete Stochastic Dynamic Programming*. Wiley, 1994. 14. Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. "Planning and Acting in Partially Observable Stochastic Domains." *Artificial Intelligence* 101.1–2 (1998): 99–134. 15. Reiter, Raymond. "On Closed World Data Bases." *Logic and Data Bases*, edited by Hervé Gallaire and Jack Minker, Plenum Press, 1978, pp. 55–76. 16. Erol, Kutluhan, James Hendler, and Dana S. Nau. "HTN Planning: Complexity and Expressivity." *Proceedings of AAAI*, 1994a, pp. 1123–1128. 17. Erol, Kutluhan, James Hendler, and Dana S. Nau. "Semantics for Hierarchical Task-Network Planning." *Technical Report CS-TR-3239*, University of Maryland, 1994b. 18. Alford, Ron, Pascal Bercher, and David Speck. "Tight Bounds for HTN Planning." *Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI)*, 2016, pp. 3112–3118. (Establishes EXPTIME-completeness of both total-order and partial-order HTN planning) 19. Nau, Dana, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, J. William Murdock, Dan Wu, and Fusun Yaman. "SHOP2: An HTN Planning System." *Journal of Artificial Intelligence Research* 20 (2003): 379–404. | Code (SHOP3, maintained successor): 20. Höller, Daniel, Gregor Behnke, Pascal Bercher, Susanne Biundo, Humbert Fiorino, Damien Pellier, and Ron Alford. "HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems." *Proceedings of AAAI*, 2020, pp. 9883–9891. 21. Sharon, Guni, et al. "Conflict-Based Search for Optimal Multi-Agent Pathfinding." *Artificial Intelligence* 219 (2015): 40–66. 22. Aineto, Diego, Sergio Jiménez, and Eva Onaindia. "Learning STRIPS Action Models with Classical Planning." *Proceedings of ICAPS*, 2019. 23. Sutton, Richard S., Doina Precup, and Satinder Singh. "Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning." *Artificial Intelligence* 112.1–2 (1999): 181–211. 24. Papadimitriou, Christos H., and John N. Tsitsiklis. "The Complexity of Markov Decision Processes." *Mathematics of Operations Research* 12.3 (1987): 441–450. (Establishes PSPACE-hardness of finite-horizon POMDP planning) 25. Madani, Omid, Steve Hanks, and Anne Condon. "On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems." *Proceedings of AAAI*, 1999; final version in *SIAM Journal on Computing*, 2003. (Establishes undecidability of infinite-horizon POMDP) 26. Rintanen, Jussi. "Constructing Conditional Plans by a Theorem-Prover." *Journal of Artificial Intelligence Research* 10 (1999): 323–352. (Establishes Σ₂ᴾ-completeness of conformant planning) 27. Rintanen, Jussi. "Complexity of Planning with Partial Observability." *Proceedings of ICAPS*, 2004. (PSPACE-completeness of contingent planning) 28. Helmert, Markus. "Decidability and Complexity Results for Planning with Numeric State Variables." *Proceedings of AIPS*, 2002, pp. 44–53. (Undecidability of numeric planning with unbounded state) 29. Littman, Michael L., Thomas L. Dean, and Leslie Pack Kaelbling. "On the Complexity of Solving Markov Decision Problems." *Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI)*, 1995, pp. 394–402. (P-completeness of finite MDP solving) --- # 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-5-extensions.md?ask=&goal= ``` `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.