PDDLEGO : Iterative Planning in Textual Environments (2024)

Abstract: Planning in textual environments have been shown to be a long-standing challenge even for current models. A recent, promising line of work uses LLMs to generate a formal representation of the environment that can be solved by a symbolic planner. However, existing methods rely on a fully-observed environment where all entity states are initially known, so a one-off representation can be constructed, leading to a complete plan. In contrast, we tackle partially-observed environments where there is initially no sufficient information to plan for the end-goal. We propose PDDLEGO that iteratively construct a planning representation that can lead to a partial plan for a given sub-goal. By accomplishing the sub-goal, more information is acquired to augment the representation, eventually achieving the end-goal. We show that plans produced by few-shot PDDLEGO are 43% more efficient than generating plans end-to-end on the Coin Collector simulation, with strong performance (98%) on the more complex Cooking World simulation where end-to-end LLMs fail to generate coherent plans (4%).

## introduction planning with llms has witnessed a surge of interest in the nlp community, not only because it showcases ai systems' ability to reason about complex events, but also because of the need of many downstream applications like goal-driven robotics @xcite and intelligent planning assistants @xcite . the most intuitive approach of this task is using llms as planners to produce a sequence of actions executed to arrive at a goal state @xcite . while applicable in many domains, this llm-based approach is found to underperform in textual simulated environments (valmeekam figure 1 : a fully-observed environment like blocksworld (upper, to rearrange objects from and to a given configuration) can be tackled by generating a pddl problem file, while a partially observed one like coin collector (lower, to look for an object in an unknown location) cannot until sufficient exploration. @xcite and to lack interpretability compared to symbolic planning methods that derive a plan from a formal representation of the environment. we join the efforts that combine both approaches, effectively translating the textual input into a symbolic representation expressed in the planning domain definition language (pddl) (see appendix a for an introduction), which can then be solved by a symbolic planner @xcite @xcite @xcite . this neurosymbolic approach has gained popularity as it combines llms' flexibility to understand rich nl and classical planners' determinism and faithfulness. all previous work on llm generating pddl has only experimented on fully-observed environments where all entity states are initially known, thus requiring no exploration. take blocksworld, a common benchmark for such work, as an example (figure 1 , upper), both the initial and goal states are initially spelled out, in which case the llm's job is akin to translating the textual descriptions of the environment into a pddl problem file which specifies the initial and goal entity states. assuming also a domain file, a one-off plan can be found and executed to reach the end-goal. in contrast, many real-world environments are partially-observed (figure 1 , lower), where the entity states dynamically get uncovered during exploration. since the necessary initial and goal states might also be unknown (e.g., looking for an item without knowing where it is), the previous approach falls apart due to the impossibility to specify a complete problem file. this causes a chicken-and-egg problem where a plan is required for exploration, while exploration is required to build pddl that results in a plan. given this challenge, past work on partiallyobserved environments has only used llms to directly generate plans @xcite , but not a planning representation. to break the above stalemate, we propose pddlego, a methodology to use llms to iteratively build a pddl problem file from textual observations from the environment. in this problem file, the initial states (or rather current states) reflect the current knowledge of the environment, while the goal states can be dynamically adjusted. in case the problem file does not contain sufficient information to plan for the end-goal (e.g., find a coin), pddlego recursively falls back to a provided sub-goal (e.g., go to an unvisited room). this way, a plan can be found to reach the sub-goal, leading to new observations by exploring the environment, and iteratively refine the problem file until a plan can be found for the end-goal. we evaluate pddlego on benchmarks of textual interactive virtual environments akin to the robotic planning simulations where pddl is known for. our pddl-induced plans are 43% more efficient than llms generating plans directly on the coin collector simulation. on one setting of the more complex cooking world simulation pddlego achieves near-perfect 98% success rate where llms that predict action achieves only 4%, while on a more challenging setting, 46% over 0%. ## methodology our approach is illustrated in figure 2 . we operate in a partially-observed, textual, simulated environment which functions as a multi-turn interaction between the environment and the agent (e.g., a game to find an item). specifically, the environment provides an observation (objects in a room) along with a list of permitted actions (move, pick up). then, the agent selects on of these actions, and repeats. the environment can be seen as a finite state machine where each state consists of the conjunction of all entity states and determines the permitted actions. the agent succeeds when a goal state is reached (the sought item is in hand); it fails when it cannot possibly reach goal state. like most prior work in using llms to generate a planning representation like pddl, we assume that a domain file that defines the available actions is provided; this domain file can solve a problem file that defines the initial and goal entity states (where the agent is, where the item is, how are these two locations connected) when possible to result in a plan (go west, pick up item). we also assume a sub-goal structure, namely, an array of goal states defined in pddl that a model can fall back to when the current goal is unattainable. formally, we are initially presented with the first observation o 1 with the end-goal g. we use an llm to construct an initial problem file p f 1 ({current states, goal states}) to plan for this end-goal. ## environments we experiment with two goal-oriented, partiallyobserved simulated environments, or text games, that span a variety of difficulty and flavor. coin collector @xcite focuses on navigation, which is an indispensable element of most simulations. the agent's task is to explore rooms, some connected by locked doors, and find a coin, similar to the running example above. just as previously discussed, the previous approach on generating a pddl problem file cannot be applied to coin collector because the location of the coin is unknown until the agent enters the same room as the coin. therefore, the sub-goal structure for this tasks is defined as: 1. pick up coin (requires the location of the coin) 2. go to a room that has not been visited (reveals location of the coin) the sub-goal of "going to an unvisited room" results in monotonously increasing progress to the end-goal of "finding the coin". in similar searchrelated tasks, this singular sub-goal or strategy suf-fices, though it may not work for all situations. cooking world @xcite subsumes coin collector with more complex tasks. the agent' task is to first explore rooms to find ingredients required by a recipe, much like coin collector. next, it should cook the ingredient in some specified location using some specified appliance. finally, when all ingredients are cooked correctly, a meal can be successfully prepared. therefore, the sub-goal structure for this tasks is defined as: ## evaluation for both simulations, we use the implementation from @xcite . for coin collector, we use the most complex setting; for cooking world, we consider an easy and a hard setting with varying number of locations and ingredients. see more details in appendix c. for the choice of llm, we consider gpt-3.5-turbo-1106 (gpt 3.5 turbo) and gpt-4-1106-preview (gpt 4 turbo) across baseline methods (i.e., action-gen, pddl-gen, and pddl-edit). for action-gen, we prompt the llm with a full description of the simulation, and for pddl methods, with a handannotated domain file containing well-defined actions. for the pddl-edit setting, we prompt the llm to generate templated edits (add, replace, and delete lines in the problem file). the prompt of each method include a 1-shot demonstration of the output format. see details of prompt design and domain file annotation in the appendix b. regarding performance, by lessen the burden on llms, pddl-edit notably ameliorates but cannot eliminate this issue. on coin collector, issues frequently arise in a loop, where opening a new door leads to a visited room. notably, gpt3.5 is far worse than gpt4 in generating pddl, in line with the observations by zhang et al. (2024) and silver et al. (2023). regarding efficiency, figure 3 shows that on coin collector, pddl-edit is no less efficient than action-gen on 7 out 8 examples (red crosses are often lower than the blue circles) in the development set where pddl-edit terminates successfully. scaling up to the entire test set, with gpt4, pddledit has an average step to success of 7.8 compared to action-gen's 13.6 among successful attempts, a 43% improvement on efficiency. among these steps, 3.3 of action-gen are invalid (e.g., moving through a closed door) compared to merely 0.2 of pddlego, a significant difference when trials and errors are expensive. pddlego also shows better stability. in figure 3 , pddl-edit exhibits a much smaller variance across runs than action-gen. for example, if the coin happens to be immediately to the west of the initial room, deciding to go west initially would result in a prompt success, while exploring the east portion initially would result in a notable detour. our approach of pddl generation leaves only the task of parsing environmental configuration to the llm, while the planning task is done deterministically by the solver, leading to more consistent plans across runs. regarding interpretability and correctability, the black-box nature of llms results in no faithful 0 1 2 3 4 5 6 7 8 9 0 10 20 30 40 example id num. steps to success action-gen pddl-edit figure 3 : on coin collector, the mean and standard deviation of number of steps to success (less is better) for each development example, each over 5 trials with different random seeds of gpt-4-1106-preview, comparing action-gen and pddl-edit. the error bar represents the sample standard deviation. on example 0 and 6, pddl-edit fails and thus not shown. ## conclusion we propose pddlego, the first approach to use llms to iteratively learn a planning representation while exploring partially-observed environments. we quantitatively show the improvement of performance, efficiency and stability, while qualitatively argue the benefit of interpretability and correctability. future work might remove the assumption of a domain file and a sub-goal structure.