Ch. 1 — Introduction

Chapter 1 of [[ai-ml/nvidia-certs/ncp-aai/cognition-planning-and-memory/Understanding-the-planning-of-LLM-agents-A-survey|Understanding the planning of LLM agents: A survey]]

Abstract

This chapter establishes the foundational framework for understanding the integration of Large Language Models (LLMs) within autonomous agent planning systems. It articulates a formal mathematical formulation for the planning procedure, delineates the limitations of conventional symbolic and reinforcement learning approaches, and proposes a systematic taxonomy categorized into Task Decomposition, Plan Selection, External Module, Reflection, and Memory. The chapter argues that LLMs serve as a paradigm shift capable of overcoming sample inefficiency and modeling rigidity inherent in prior methods, positioning the survey as the first comprehensive analysis of LLM-based agents specifically focused on planning capabilities across four evaluated benchmarks.

Key Concepts

• Autonomous Agents: Defined as intelligent entities capable of accomplishing specific tasks through a triad of capabilities: perceiving the environment, planning, and executing actions. The core motivation is to create systems that operate without constant human intervention by leveraging cognitive cores for complex reasoning.
• Planning Procedure: Described as a critical capability requiring complicated understanding, reasoning, and decision-making progress within an agent. It is formally modeled as the generation of a sequence of actions $a_t$ over time steps $t$, conditioned on the environment $E$ and task goal $g$.
• Symbolic Methods: Conventional planning approaches that rely on formalisms such as the Planning Domain Definition Language (PDDL). These methods typically require human experts to convert flexible natural language-described problems into rigid symbolic models, often resulting in a lack of error tolerance where minor input errors cause total failure.
• Reinforcement Learning (RL) Methods: Traditional decision-making techniques often combined with deep models serving as policy networks or reward models. The primary limitation identified is sample inefficiency, as these algorithms require a large number of interactions with the environment to learn an effective policy, which is impractical in costly or time-consuming scenarios.
• Large Language Models (LLMs): Recent neural architectures that have achieved remarkable success in reasoning, tool usage, planning, and instruction-following. They are proposed as the cognitive core of agents, offering the potential to improve planning ability by leveraging their general intelligence rather than task-specific training data.
• Task Decomposition: One of the five main categories in the proposed taxonomy, involving the breaking down of complex high-level goals into manageable sub-problems. This approach allows the agent to handle intricate planning scenarios by isolating components of the total action sequence.
• Plan Selection: A key direction in the taxonomy where the agent is required to evaluate and choose among multiple potential action sequences. This mechanism addresses the uncertainty inherent in generative planning by allowing the model to identify the most viable path toward the goal $g$.
• External Module-Aided Planning: A category suggesting the integration of specialized tools or modules to augment the LLM’s planning capabilities. This allows the agent to offload specific sub-tasks to external systems, thereby mitigating the limitations of the language model’s native computational boundaries.
• Reflection: A methodological direction where the agent analyzes its own past actions and outcomes to improve future decision-making. This process mimics feedback loops in human cognition, enabling the agent to correct errors and refine its policy without external retraining.
• Memory: A taxonomy category focusing on the retention of state and historical information to enhance context awareness during planning. Utilizing memory allows the agent to maintain a coherent long-term strategy rather than reacting solely to immediate environmental states.
• Taxonomy on LLM-Agent Planning: A systematic classification framework introduced by the authors to organize existing works. It divides the literature into five representative directions, facilitating a structured analysis of methodologies aiming to improve planning ability.
• Benchmark Evaluation: The survey includes an empirical component where representative methods are evaluated on four specific benchmarks. This quantitative assessment validates the theoretical claims regarding the planning capabilities of different LLM-agent architectures.

Key Equations and Algorithms

• General Planning Formulation: $p=(a_0,a_1,\cdots ,a_t)=\text{plan}(E,g;\Theta ,P)$ This equation defines the planning procedure $p$ as the generation of an action sequence where $a_t\in A$ is the action at time step $t$. The function depends on the environment $E$, the goal $g$, the LLM parameters $\Theta$, and the task prompts $P$.
• Action Space Constraint: $a_t\in A$ This condition specifies that at any given time step $t$, the selected action $a_t$ must belong to the predefined action space $A$, constraining the agent’s decision-making to valid operations available within the environment.
• Environment State: $E$ Represents the current state of the environment at time step $t$. The planning function takes $E$ as a primary input, indicating that the generated action sequence is context-dependent and must account for external factors.
• Goal Condition: $g$ Denotes the specific task goal that the agent aims to accomplish. The planning procedure is directed toward achieving $g$, making it a critical variable in the optimization of the action sequence $p$.
• Model Parameters and Prompts: $(\Theta ,P)$ These variables represent the static configuration of the system. $\Theta$ refers to the internal parameters of the LLM, determining its knowledge and weights, while $P$ represents the explicit instructions provided in the prompt to guide the specific planning task.
• Survey Organization Algorithm: $\text{Structure}=\{\text{Sec 1: Intro},\text{Sec 2-7: Categories},\text{Sec 9: Conclusion}\}$ The chapter outlines a meta-algorithmic structure for the survey itself. It begins with the introduction of the planning problem, progresses through five detailed sections analyzing specific directions (Sections 3 to 7), and concludes with future insights in Section 9.
• Taxonomy Generation Process: $\text{Taxonomy}=\text{Categorize}(\text{Works},\text{Motivations},\text{Essential Ideas})$ Although not a numerical algorithm, the text describes a systematic procedure used to derive the taxonomy. This process involves picking representative and influential works, analyzing their motivations, and grouping them based on essential ideas regarding planning ability.
• Evaluation Protocol: $\text{Evaluation}=\text{Evaluate}(\text{Methods},\text{Benchmarks}=4)$ The chapter states that several representative methods were evaluated on four benchmarks. This represents a validation algorithm where the performance of the taxonomy categories is measured against standard datasets to ensure comprehensive analysis.
• Error Tolerance Metric: $\text{Limitation}(\text{Symbolic})=\neg \text{Tolerant}(\text{Errors})$ This conceptual expression captures the claim that symbolic methods fail even if there are only a few errors. It highlights the brittleness of methods like PDDL compared to the potential robustness of LLM-based approaches.
• Sample Efficiency Comparison: $\text{Cost}(\text{RL})\gg \text{Cost}(\text{LLM})$ The text implies a comparative efficiency between Reinforcement Learning and LLM-based planning. RL requires a large number of samples (interactions), whereas LLMs leverage pre-trained intelligence, suggesting a lower cost for learning new policies in new environments.

Key Claims and Findings

• The emergence of Large Language Models (LLMs) marks a paradigm shift for autonomous agents, offering the potential to serve as the cognitive core for planning capabilities rather than just text generation tools.
• Conventional symbolic methods, such as those utilizing Planning Domain Definition Language (PDDL), are limited by the requirement for human expert efforts to convert natural language problems into symbolic modeling and exhibit a lack of error tolerance.
• Reinforcement learning-based planning methods are frequently hindered by sample inefficiency, requiring impractical numbers of interactions with the environment to learn an effective policy network in expensive scenarios.
• This survey constitutes the first work to comprehensively analyze LLM-based agents specifically from the perspective of their planning abilities, distinct from broader surveys on reasoning or tool learning.
• Existing literature on LLM agent planning can be systematically categorized into five representative directions: Task Decomposition, Plan Selection, External Module, Reflection, and Memory.
• The survey provides a novel and systematic taxonomy that divides existing works based on an analysis of representative and influential works regarding their motivations and essential ideas.
• Beyond theoretical categorization, the research includes an empirical evaluation of several representative methods across four different benchmarks to validate the analysis of planning ability.

Terminology

• Autonomous Agents: Intelligent entities capable of accomplishing specific tasks via perceiving the environment, planning, and executing actions, distinguished by their ability to operate independently within a given context.
• Planning: A critical capability for agents that requires complicated understanding, reasoning, and decision-making progress to generate a sequence of actions $p$ that satisfies a goal $g$.
• Environment ($E$): The external context or state in which the agent operates. At time step $t$, the environment provides the necessary input for the agent to determine the appropriate action $a_t$.
• Action Space ($A$): The set of all possible actions $a_t$ that the agent can execute. The planning procedure generates a sequence where each element is constrained to be within this valid set $A$.
• Goal ($g$): The specific task objective the agent must accomplish. It serves as a target variable in the planning function $\text{plan}(E,g;\Theta ,P)$, guiding the generation of the action sequence $p$.
• Parameters ($\Theta$): The internal weights and configurations of the Large Language Model (LLM) used by the agent. These parameters define the model’s pre-trained knowledge and capabilities prior to receiving specific task prompts.
• Prompts ($P$): The explicit instructions provided to the LLM to guide the planning task. These inputs condition the model’s generation of the action sequence along with the environmental state and internal parameters.
• Planning Domain Definition Language (PDDL): A symbolic modeling language used in conventional planning methods. It requires the conversion of natural language problems into a rigid formalism, often necessitating human expert intervention.
• PDDL: An abbreviation for Planning Domain Definition Language, representing the standard symbolic representation method noted for its lack of error tolerance and high effort in problem modeling.
• Policy Network: A deep model component typically combined with Reinforcement Learning (RL) methods. It serves to map observed states directly to actions, requiring extensive training data to optimize effectively.
• Reward Model: A component often used in conjunction with policy learning in RL methods. It evaluates the quality of actions taken, necessitating significant sample collection to derive effective gradients for learning.
• Taxonomy: A systematic classification of the existing works on LLM-Agent planning. In this context, it refers specifically to the division of methodologies into the five categories: Task Decomposition, Plan Selection, External Module, Reflection, and Memory.