\section{Introduction}\label{sec:intro}

Developing multi-task agents that can accomplish a vast and diverse suite of tasks in an open-ended world has been viewed as one of the key milestones towards generally capable artificial intelligence~\cite{gato,flamingo,gpt3,minedojo}. To enable such capabilities, earlier works have suggested employing a hierarchical goal execution architecture~\cite{bacon2017option,saycan}, where a planner generates action plans that would then be executed by low-level goal-conditioned controllers. This architecture has been delivering promising progress in many robotics domains, including table-top and mobile manipulation~\cite{socraticmodels,saycan}, 2D shape drawing~\cite{codeaspolicies} and table rearrangement~\cite{innermonologue}. However, whether the success can be transferred to a more open-ended world like Minecraft remains open~\cite{minerl,minedojo,minerl-rel-1,minerl-rel-2,minerl-rel-3}. To understand the gap, we've identified two primary challenges of planning in these environments.

\begin{figure}[t]
    \centering
    \includegraphics[scale = 0.6]{figures/succ_vs_steps.pdf}
    \caption{

        \textbf{Planning success rates of tasks that require a different number of reasoning steps.}
        Complex tasks in open-ended environments usually comprise more sub-goals to be completed, which places a higher demand on the multi-step reasoning of the planner.
        The planning success rate is computed considering an oracle and perfect controller if provided.

        }
    \label{fig:succ_vs_steps}
    \vskip -0.2in
\end{figure}

First of all, many tasks in Minecraft can be rather complex, as they usually comprise multiple sub-goals to be completed, e.g. the task \texttt{build a bed} includes 7 sub-goals and therefore demand significantly longer reasoning steps of the planner. Meanwhile, many of these sub-goals have to be planned precisely with the exact object name and quantities, e.g. \texttt{mine 3 woods} \includegraphics[scale=0.2,valign=c]{minecraft/oak_wood}, \texttt{kill 3 sheep} \includegraphics[scale=0.2,valign=c]{minecraft/sheep}; otherwise, the subsequent sub-goals won't be executed due to failed preconditions. As demonstrated in Figure~\ref{fig:succ_vs_steps}, accurate multi-step reasoning indeed imposes a great challenge for the planners and we can observe a significant regression in tasks requiring longer steps to be completed.

Another challenge brought by the complicated tasks in an open-ended world is the efficiency of the produced plans, which is illustrated in Figure~\ref{fig:goal_model}. A complicated plan in an open-world environment usually includes multiple \textit{parallel} sub-goals that can be simultaneously executed. However, some orderings of these sub-goals are better than others, e.g. \texttt{kill sheep} \includegraphics[scale=0.2,valign=c]{minecraft/sheep} $\rightarrow$ \texttt{mine wood} \includegraphics[scale=0.2,valign=c]{minecraft/oak_wood} in Figure~\ref{fig:goal_model} is more efficient than other sequences given the agent situation. Unfortunately, canonical planners do not consider the current proximity of the sub-goals to the agent when devising the plans, thereby producing inefficient plans and ultimately leading to a lower success rate.

\begin{figure}[t]
    \centering
    \includegraphics[scale = 0.5]{figures/goal_model.pdf}
    \caption{

        \textbf{Comparison of plans produced by the planner with or without the ``Select'' component}. Given parallel sub-goals, i.e. \texttt{mine wood} \includegraphics[scale=0.2,valign=c]{minecraft/oak_wood}
 and \texttt{kill sheep} \includegraphics[scale=0.2,valign=c]{minecraft/sheep}, our Selector will determine the sequence in which to carry out these sub-goals based on their current proximity to the agent \includegraphics[scale=0.015,valign=c]{minecraft/steve2.jpg} and modify the original plan produced by the planner accordingly (\textbf{black} $\rightarrow$ \textbf{\color{red}red} plan). The resulting plan is more efficient and therefore yields a higher success rate.}
    \label{fig:goal_model}
    \vskip -0.2in
\end{figure}

To this end, we propose ``\underline{D}escribe, \underline{E}xplain, \underline{P}lan and \underline{S}elect'' (\textbf{DEPS}), an interactive planning approach based on Large Language Models (LLMs) to alleviate the aforementioned issues in most open-world environments. Whenever a failure happens when executing the current plan, a \textit{descriptor} will summarize the current situation as text and send it back to the LLM-based planner. The LLM-based planner will then be prompted as \textit{explainer} to locate the errors in the previous plan.
Finally, the \textit{planner} will re-plan the task to obtain a correct plan.
This allows the feedback from the agents to be better handled by the planner and increases the overall success rate on Minecraft tasks by 52.74\%.
Additionally, in the case when there are parallel sub-goals lining up, a goal-selector will be invoked to select the most accessible sub-task based on the proximity to the agent and edits the original plan accordingly. The complete DEPS system ultimately yields an 88.44\% gain in average success rate.

Our experiments are conducted on 71 tasks in Minecraft. We find DEPS outperforms all baselines by nearly doubling the overall success rate. Our ablation and exploratory studies then explain how our approach beats the counterparts and becomes the first planning-based agent that accomplishes the challenging \texttt{ObtainDiamond} task.

To summarize, our contributions are two fold:
\setlength{\leftmargini}{0.85em}
\begin{itemize}[topsep=0.8pt]
 \setlength\itemsep{0.6pt}
\item We propose ``\underline{D}escribe, \underline{E}xplain, \underline{P}lan and \underline{S}elect'' (DEPS), an interactive planning method based on Large Language Models to address the main issues in open-world planning, including multi-step reasoning and the lack of sense of agent's proximity to the sub-goals.

\item We conduct comprehensive studies on the popular yet challenging Minecraft domain with many strong baselines and our approach. Overall the results indicate the significant advantages of DEPS over its counterparts in terms of success rate. Notably, DEPS is the first agent with planning that ever achieves an above-zero success rate on the challenging \texttt{ObtainDiamond} task.

\end{itemize}

\section{Background}\label{sec:method}

\subsection{Problem Formulation}

We aim to learn an agent that can solve arbitrary long-horizon goal-reaching tasks with image observation and language goals.
To achieve this, we consider planning, which combines goal-conditioned policies trained to accomplish sub-goals with a planner that decomposes a long-horizon task into $K$ short-horizon sub-goals.
Specifically, the planner chooses $K$ sub-goals, $g_1, \ldots, g_K$, and attempts to accomplish them one by one.
At every time step $t$, for different sub-goal $g_k$, a goal-conditioned policy $\pi(a_t\mid s_t,g_k)$ samples an action $a_t$ considering the current state $s_t$.
A key benefit of this planning-based approach is that the same set of sub-goals can be reused and composed flexibly to carry out various tasks.
In this paper, we employ an LLM-based planner to leverage its encoded abundant knowledge.

\subsection{Challenges of Planning in Open Worlds}
\label{sec:challenges}

Compared to canonical domains such as robotics table rearrangement~\cite{innermonologue}, planning in open-world embodied environments poses the following additional challenges. \textbf{1) long-term planning.} Due to the richness of terrains, objects, and action spaces, tasks in open-world domains require exceptionally long planning horizons, while the plan still has to be precise and executable. As a result, the success rate degrades significantly as the number of reasoning steps required by the task increases (see Figure~\ref{fig:succ_vs_steps}); \textbf{2) planning efficiency.} Complicated plans in open-world environments usually comprise sub-goals that can be executed \textit{in parallel}, but canonical planners do not take into consideration the agent's proximity to every sub-goal, measured by the time steps required to accomplish it. Therefore, these planners tend to generate inefficient plans (an example can be found in Figure~\ref{fig:goal_model}). In this paper, we hope to address these two challenges that bottleneck planning-based agents in open-world environments.

\begin{figure*}[t]
    \centering
    \includegraphics[scale = 0.5]{figures/overview.pdf}
    \caption{
        \textbf{Overview of our proposed dynamic planner architecture}. Given a task $T$, our ``Describe, Explain, and Plan with LLM by interactive prompting'' pipeline generates executable and explainable plans $P_t$ iteratively. The horizon-predictive Selector selects as state-aware goal as the current goal $g_t$.
        The symbol $\land$ and $\vee$ in plan $P$ represent the relation \textit{AND} (all goals need to be finished, with no particular requirement on the order) and \textit{OR} (either needs to be finished), respectively.
        }
    \label{fig:pipeline}
    \vspace{-0.2 in}
\end{figure*}

\subsection{Planning with Large Language Models}

Previous works have shown that large language models (LLMs) such as InstructGPT \cite{instructGPT} and Codex \cite{codex} can be used as zero-shot planners to generate sub-goal sequences for various tasks in embodied environments \cite{huang2022language,progprompt}.
Formally, given the task description $T$ as prompt $p$, LLM acts as a planner to decode $T$ into $K$ sub-goals, $g_1, \ldots, g_K$, which are then executed one by one by the low-level controller $\pi(a_t \mid s_t, g_k)$ to accomplish the task.

One potential deficit of the above pipeline is that the LLM-based planner cannot receive feedback from the environment, which could lead to non-executable and redundant plans.
Prior works enabled feedback to the LLM through external components such as affordance functions \cite{saycan}, success detector \cite{codeaspolicies} or scene descriptor \cite{innermonologue} to ground the LLM plans executable by robots.
As discussed in Section~\ref{sec:challenges}, the long-horizon tasks in partially observed open-world domains make it more challenging for LLM-based planners.

\section{Towards Reliable Planning in Embodied Open-World Environments}

In this section, we first give an overview of our proposed interactive planning framework ``\underline{D}escibe, \underline{E}xplain, \underline{P}lan, and \underline{S}elect'' (DEPS) for solving complex and long-horizon tasks in open-world environments. Next, in Section~\ref{sec:descriptor}, we will walk through how our framework iterates its plan with feedback from the agent. In Section~\ref{sec:HPGM}, we take a closer look at how our ``Selector" optimizes the original plan to be more efficient by leveraging the agent's proximity to each sub-goal. Additional implementation details of DEPS are provided in Appendix ~\ref{sec:others}.

\subsection{DEPS Architecture}\label{sec:architecture}

As demonstrated in Figure~\ref{fig:pipeline}, our agent (DEPS) consists of an event-triggered \underline{D}escriptor, a Large Language Model (LLM) as \underline{E}xplainer and \underline{P}lanner, a goal \underline{S}elector based on horizon prediction and a goal-conditioned controller.

We take a large language model (LLM) as zero-shot \textbf{Planner} of the agent to complete tasks.
Given an instruction command (e.g., \texttt{ObtainDiamond}) as task $T$, the LLM-based planner extracts the high-level task into a sequence of sub-goals $\{g_1, \ldots, g_K\}$, as the initial plan $P_0$.
The goals are instructions in natural language, e.g., \texttt{mine oak wood} \includegraphics[scale=0.18,valign=c]{minecraft/oak_wood.png}. We provide a list of all possible goals in Appendix~\ref{sec:controller}.

Though many goals are sequential in nature, i.e., one is pre-conditoned on the completion of an other, some are connected through \textit{AND}$\land$ and \textit{OR}$\vee$. When goals are put together with \textit{AND}$\land$, all of them need to be completed, yet the order to carry out them does not matter as there is no interdependency among these goals. When goals are put together with \textit{OR}$\vee$, we can simply choose any of them to execute. For example, \texttt{mine coal} \includegraphics[scale=0.04,valign=c]{minecraft/coal.png} $\land$ \texttt{mine iron ore} \includegraphics[scale=0.04,valign=c]{minecraft/iron_ore.png}, and \texttt{mine oak wood} \includegraphics[scale=0.18,valign=c]{minecraft/oak_wood.png} $\vee$ \texttt{mine birch wood} \includegraphics[scale=0.18,valign=c]{minecraft/birch_wood.png} in Figure~\ref{fig:pipeline}.
Given in either case, any completion order is the same, these goals are referred to as \textit{parallel goals}.
The \textbf{Selector} is trained to predict the number of time steps remaining to achieve every goal $g_k$ in a set of parallel goals given the current state $s_t$. Using this information, it then selects the suitable goal as the current goal $g_t$.
For example, the Selector will choose \includegraphics[scale=0.04,valign=c]{minecraft/iron_ore.png} as current goal $g_t$ instead of \includegraphics[scale=0.04,valign=c]{minecraft/coal.png} as iron ore is closer to the agent.
More details on the Selector can be found in Section~\ref{sec:HPGM}.

Finally, the selected goal $g_t$ will be executed by the low-level multi-task \textbf{controller}.
The controller is denoted as a goal-conditioned policy $\pi(a|s,g)$ for decision-making, which can map the current state $s_t$ to action $a_t$ conditioned on goal $g_t$.
The policy $\pi$ can be trained by reinforcement learning~\cite{ppo} or imitation learning~\cite{vpt} methods.

However, the initial plan $P_0$ is difficult to execute successfully in one shot, because it often contains errors. For example, the goal \includegraphics[scale=0.04,valign=c]{minecraft/iron_ore.png} can not be finished only with a wooden pickaxe \includegraphics[scale=0.08,valign=c]{minecraft/wooden_pickaxe.png}.
When failure pops up, \textbf{Descriptor} will summarize the current state $s_t$ and execution outcome of the most recent goal into text $d_t$ and send it to the LLM.
The LLM will first try to locate the errors in the previous plan $P_{t-1}$ by \textbf{self-explanation}, e.g., the goal \includegraphics[scale=0.04,valign=c]{minecraft/iron_ore.png} need to be executed with a stone pickaxe \includegraphics[scale=0.08,valign=c]{minecraft/stone_pickaxe.png}.
Then it will re-plan the current task $T$ and generate a revised plan $P_t$ according to the explanation. In this process, the LLM is also treated as an \textbf{Explainer} in addition to the \textbf{Planner} role.
The Descriptor, Explainer, and Planner will be detailed in Section~\ref{sec:descriptor}.
\vskip -0.2in
\begin{equation}\label{eq:pipeline}
\begin{aligned}
	\text{Description}&: d_t = f_{\text{DESC}}(s_{t-1}), \\
	\text{Prompt}&: p_t = \text{CONCAT}(p_{t-1}, d_t), \\
	\text{Plan}&: P_t = f_{\text{LM}}(p_t), \\
	\text{Goal}&: g_t \sim f_{\text{S}}(\text{P}_t, s_{t-1}), \\
	\text{Action}&: a_{t} \sim \pi(a_t \mid s_{t-1}, g_{t})
\end{aligned}
\end{equation}
\vskip -0.1in

As shown in Equation~(\ref{eq:pipeline}), DEPS will iteratively update the plan $P_t$ until the task is finished, where $f_\text{DESC}$ is the descriptor model, $f_\text{LM}$ denotes the language model as explainer and planner, $f_\text{S}$ is the selector model, $\pi$ is goal-conditioned policies from the controller.

\subsection{Describe, Explain and Plan with LLM Generates Executable Plans}
\label{sec:descriptor}

\begin{figure*}[t]
    \centering
    \includegraphics[scale = 0.6]{figures/demonstration.pdf}
    \caption{
        \textbf{A demonstration of the process of ``describe, explain, plan and select'' with a LLM-based planner}.

        The context in the figure is modified for better visualization.
        The full interaction dialogue of our agent is listed in Appendix~\ref{sec:interaction}.
        }
    \label{fig:demonstration}
    \vspace{-0.2 in}
\end{figure*}

Current LLM-based planners usually query the LLM once at the beginning of every episode and use the output plan throughout the episode \cite{huang2022language,progprompt}.
However, as demonstrated by Figure~\ref{fig:succ_vs_steps}, such one-shot planning methods often fail on long-horizon tasks that require many sub-goals.
This is caused by two major issues.
First, since the correct plan for long-horizon tasks needs to respect various complex preconditions, it is extremely hard for the LLM to generate a flawless plan directly from the task instructions, resulting in failure when simply following the initial plan.
Additionally, due to the unpredictable transition dynamics, some incidents may happen during the execution and makes the initial plan non-executable.
To remedy these problems, existing methods introduce feedback (e.g., from success detector or scene descriptor) to reflect on the results of previous executions \cite{innermonologue,codeaspolicies,saycan}.
However, merely informing the LLM whether a sub-goal is completed is often insufficient to correct the planning error.

To remedy this, we propose ``describe, explain and plan'', a new interactive planning method to generate more executable and explainable plans.
We start with rewriting the prompt into an interactive dialogue format as in ChatGPT \cite{instructGPT} so that subsequent feedback can be passed to the LLM effectively.
The produced plan is also augmented with the preconditions and effects of each goal.
The structured prompt improves the readability and interpretability of the plan and facilitates error-locating when the execution fails later.
For example, we modify the original goal description \texttt{craft wooden pickaxe} into:
\lstset{
 basicstyle=\scriptsize,
 columns=fixed,
 frame=none,
 backgroundcolor=\color[RGB]{245,245,244},
 keywordstyle=\color[RGB]{40,40,255},
 numberstyle=\footnotesize\color{darkgray},
 commentstyle=\it\color[RGB]{0,96,96},
 stringstyle=\rmfamily\slshape\color[RGB]{128,0,0},
 showstringspaces=false,
 breaklines = true,
}
\begin{lstlisting}
craft({wooden_pickaxe:1}, {planks:3, stick:2}, crafting_table); # craft 1 wooden_pickaxe from 3 planks and 2 stick, on crafting_table
\end{lstlisting}

The \textbf{Descriptor} will then collect the feedback generated by the agent during the execution of the task.
The feedback can be practically obtained either by a person (human feedback~\cite{saycan}), or by a pre-trained vision-language model CLIP~\cite{clip}.
While the previous type of feedback needs intensive human involvement, the latter from the pre-trained model needs to be fine-tuned for the specific domain, which decreases the automation and generalization of the agent.
On the contrary, Minecraft returns the `info' and other high-level observations (such as biome, GPS, and compass), we can easily translate the unstructured information into structured language.
Therefore we take the symbolic information available in the game and translate it into feedback description $d_t$ in this work.
To avoid carrying unrelated information in the prompt, we further distill plan-related messages (e.g., inventory information, biome, action results, etc.) as final event-level description $d_t$ as demonstrated in Figure~\ref{fig:demonstration}.

Notably, we also treat the LLM as an \textbf{Explainer} to explain why the previous plans $P_{t-1}$ failed.
Specifically, by analyzing the current state from description $d_t$ and precondition of current goal $g_t$, the explainer can identify the reason why the current goal cannot be executed successfully.
As shown in Figure~\ref{fig:demonstration}, the reason may be \textit{the current goal requires the use of an iron pickaxe, but the tool is not prepared in advance, or the current goal requires the use of 3 planks, but the currently available planks are not enough}.
To implement this, we provide few-shot demonstrations to the LLM as in chain-of-thoughts prompting~\cite{chainofthought}.
Finally, the LLM goes back to its role as a \textbf{Planner} and re-plans the task with the explicit explanation of existing bugs in previous plan $P_{t-1}$, ultimately generating an updated plan $P_{t}$ according to the explanation.

\subsection{Horizon-Predictive Selector Yields Efficient Plans}\label{sec:HPGM}

Due to the abundance of objects and the compositional nature of their functionalities, there often exist multiple feasible plans to complete a task, i.e., there are usually multiple paths for the completion of a particular goal.
However, despite the feasibility of all such plans, most of them are highly inefficient to execute in the current episode.
For example, as shown in Figure~\ref{fig:pipeline}, obtaining a \texttt{wood} can be done by chopping oak trees \includegraphics[scale=0.2,valign=c]{minecraft/oak_wood.png}, birch trees \includegraphics[scale=0.2,valign=c]{minecraft/birch_wood.png}, or acacia trees \includegraphics[scale=0.08,valign=c]{minecraft/Acacia_Log.png}.
But only oak trees are available in the \texttt{plains} biome.
So the planner needs to choose oak trees since it is more efficient, as the agent does not need to travel to another biome.

On the other hand, there is no strict sequential requirement for some goals in the plan $P_t$, i.e., $g_i, g_j \sim P_t$ enjoy the same precondition, which means $g_i$ and $g_j$ can be executed in any order.
As shown in Figure~\ref{fig:goal_model}, the choice of different paths (sequences) may affect the execution efficiency of the plan $P_t$ as one goal might be closer to the agent.
Always choosing the closer goal to execute first could yield more efficient plans and improve the final success rate under a limited episode length.
Moreover, the dynamic nature of open-world environments further amplifies the impact of more efficient plans on the success rate.
For example, in Minecraft, if the agent chooses to execute a further goal like \texttt{collect wood} first, the much closer target \texttt{sheep} may have disappeared and hard to be found again.

In order to improve the efficiency of our plans, we propose to use a \textbf{Selector} that selects the most efficient path with the highest execution success rate as the final plan.
Specifically, we design a state-aware selector to choose the nearest goal under state $s_t$ as the current goal $g_t$ from the candidate goal sets in plan $P_t$.
It predicts the goal distribution $p(g_t |s_t, P_t)$ under the current state $s_t$ and plan $P_t$, where $g_t \in G_t$, $G_t$ describes all current executable goals in $P_t$. A straight way to implement the selector is to leverage the semantic similarity between the current state and the goal text using a vision-language model (VLM) such as CLIP \cite{clip}. Nevertheless, this may not exactly reflect the difficulty of completing the goal since VLM lacks practical experience. For example, an ``oak tree'' in front of the agent could lead to high semantic similarity for the ``chopping tree'' goal, but it may be inefficient to achieve this goal if a canyon is in the middle between the agent and the oak tree.

To mitigate this, we implement a horizon-predictive selector that embeds practical task experience to accurately rank the goal based on their efficiency and feasibility.
Here, we define the horizon of a goal $h_t(g) := T_g - t$  as the remaining time steps to complete the given goal, where $T_g$ is the time of completing goal $g$.
This metric accurately reflects how quickly we can achieve the given goal from the current state. To estimate the horizon, we learn a neural network $\mu$ to fit the offline trajectories by minimizing the entropy loss $-\text{log}\ \mu(h_t(g)|s_t, g)$, where $h_t$ is the ground-truth horizon in trajectories of completing goal $g$. Therefore, the goal distribution can be formulated as follows:
\begin{equation}
    f(g_t \mid s_t,P_t) = \frac{exp(-\mu(g_t, s_t))}{\sum_{g\in G_t} exp(-\mu(g, s_t))}.
\end{equation}
\vskip -0.1in
We set goal-sensitive Impala CNN~\cite{shaofei} as the backbone of the selector. In practice, the horizon predictive selector can be jointly trained with the controller policies and share the backbone parameters~\cite{shaofei}.

\section{Experiments}

This section analyzes and evaluates our proposed ``describe, explain, plan, and select" (DEPS) method.
To minimize performance variation caused by the low-level controller, we standardize all experiments with one controller learned by behavior cloning. We refer to the details of this controller in Appendix \ref{sec:controller}.
In Section~\ref{sec:setup}, we introduce our testing environments and our proposed Minecraft Task101, consisting of the hardest 71 tasks distilled from Minedojo~\citep{minedojo}.
In Section~\ref{sec:results}, we report our performance in the context of existing LLM-based planners.
Ablation studies are conducted in Section~\ref{sec:ablation}.
Finally, we pay close attention to the hardest among Task101, \texttt{ObtainDiamond}, which is long-hailed as a major challenge in the community.

\subsection{Experimental Setup}\label{sec:setup}

\input{tables/meta_task.tex}

We evaluate our proposed method in Minecraft, a popular open-world environment with both challenges discussed in ~\ref{sec:challenges}.
We distill the 1523 MineDojo \citep{minedojo} programmatic tasks and select the hardest setting (i.e., no task-specific tools are given for agents in advance) to form our proposed Minecraft Task101.
To better present the results, we divide the 71 Task101 tasks into 8 meta groups according to the ingredients and function of the tasks, i.e., MT1-MT8 as illustrated in Table~\ref{tab:meta_task}.
Considering how long it typically takes human players to complete each task as a ballpark \citep{minerl}, we set different maximum episode steps for different meta tasks from 3000 (for easiest \textbf{Basic} tasks) to 12000 (for the hardest \textbf{Challenge} tasks).
The names, number of required reasoning steps, and functions of all tasks are listed in Appendix~\ref{sec:task_details}.
Note that our agent will be summoned in different environments randomly for each evaluation. Biomes and initial positions are also different each time.
Following the previous work \cite{malmo}, we take the success rate as the evaluation metric.

\input{tables/main_results.tex}

\subsection{Main Results}\label{sec:results}

We compare our methods with other LLM-based planners, including Zero-shot Planner \cite{huang2022language}, ProgPrompt \cite{progprompt}, Chain of Thought \cite{chainofthought}, Inner Monologue \cite{innermonologue}, Code as Policies \cite{codeaspolicies}. Since these methods are not originally experimented in Minecraft, we reproduce them to conform to the Minecraft specification based on prompt and feedback template design.
All planner methods access the LLM model through OpenAI API (text-davinci-03 model \cite{instructGPT} for Zero-shot Planner, Chain of Thought, and Inner Monologue, and code-davinci-02 model \cite{codex} for Code as Policies, ProgPrompt, and Ours). All hyper-parameters of LLM are kept as default.

Every task is executed 30 times and the average results for every meta task are listed in Table~\ref{tab:main_results}.
Our approach achieves the best performance with all meta tasks.
As the complexity of the task increases from MT1-MT8, the planner usually needs to give more accurate task steps (i.e., longer goal sequence) to achieve the final task.
Therefore the success rate of all agents decreases with the reasoning steps increasing.
Starting from MT6, almost all existing LLM-based planners fail (nearly 0 success rate).
DEP (w/o Selector) already consistently beats existing LLM-based planners in all meta tasks with a significant margin.
This validates that ``describe, explain and plan'' can estimate the reason for current plan failure and correct the original flawed plans.
Due to the limited maximum episode length and restricted control success rate for a hard goal (e.g., \texttt{Mine diamond with iron\_pickaxe}), the final success rate is still capped.

In addition, \textbf{Selector} also greatly improves the final task success rate of the agent (from \textbf{DEP w/o Selector} to \textbf{DEPS}).
Hard meta tasks usually require the completion of multiple sub-goals (up to dozens of goals), thus bringing more flexibility and providing more candidate goals for the Selector. At the same time, as the agent conducts experiments with limited episode length, it also places high demands on the efficiency of the plan. Therefore, the Selector brings a significant improvement on efficiency-sensitive tasks such as MT7 (up to \textbf{+2.7} times success rate).

\subsection{Ablation Study}\label{sec:ablation}

We conduct ablation experiments to investigate the specific impact of the rounds of DEPS and the number of candidate executable goals for different Selector models.

\subsubsection{Ablation on DEPS rounds}
We evaluate our agent on all tasks with increasing maximum rounds of DEPS.
The round is defined as a cycle of interactive LLM-based planning with description, explanation, and planning and selecting, i.e., an updated plan.
All tasks for every maximum round are executed 30 times and the average success rate is reported in Table~\ref{tab:ablation_on_feedback}.
We take the agent without DEPS (i.e., 0 round) as the baseline model.
Our results in the previous subsection utilize the maximum rounds possible under 8000 tokens capped by OpenAI,
We also report the success rate increment of every meta task in column $\Delta$ in Table~\ref{tab:ablation_on_feedback}.
This set of experiments demonstrates that DEPS can iteratively improve its plan in open-world environments. More DEPS rounds produce better results, especially for hard tasks.

\input{tables/ablation_feedback.tex}

\subsubsection{Ablation on Selector}

We verify the robustness of our proposed Selector under different parallel goals.
The agent is asked to complete 2, 3, and 4 candidate goals (the precondition is consistent for all goals), respectively.
The goals of the task correspond to different kinds of mobs or materials.

We report the final success rate of our method (DEP) with different selector implementations, including using a fixed sequence of goals, a random sequence of goals, and selecting a goal based on MineCLIP~\cite{minedojo}, CLIP~\cite{clip}, and our horizon-predictive Selector (HPS).
As Figure~\ref{fig:ablation_goalmodel} shows, in one round of parallel candidate goals, an improvement of $\Delta$=+22.3\%, +29.2\%, +32.6\% is obtained using our horizon-predictive Selector compared to not any selector (i.e., fixed plan), respectively.

At a limited episode length, e.g., 1000 steps, goal-model shows a greater advantage, which proves that goal-model can improve the execution efficiency of the plan in embodied environments.
In addition, compared to using vision-language models such as CLIP\ \cite{clip} and MineCLIP \cite{minedojo} as a goal model, horizon-predictive has the best performance due to better estimation of the horizon information.
The curve trend also demonstrates that agents with Selector scale up under large amounts of goals in an open-world environment.

\begin{figure}[t]
    \centering
    \includegraphics[scale = 0.38]{figures/ablation_goalmodel.pdf}
    \caption{
        \textbf{Ablation experiments on different Selector implementations}.
        The success rates of different selectors under varying numbers of parallel goals and maximum episode lengths.}
    \label{fig:ablation_goalmodel}
    \vskip -0.2in
\end{figure}

\subsection{\texttt{ObtainDiamond} Challenge}\label{sec:bonus}

Mining diamonds in the open-world game Minecraft, i.e. MT8 in Table~\ref{tab:main_results}, has been a long-standing challenge for the community \cite{minerl}. It is challenging because mining diamonds from scratch in Minecraft involves acquiring a sequence of difficult-to-obtain items that require complex planning on goals like mining, inventory management, crafting with and without a crafting table, tool use, smelting iron ingot in a furnace, and mining at the lowest depths.
We take the \texttt{ObtainDiamond} task as a bonus experiment to show the capabilities of our zero-shot planner on complex tasks in embodied environments.
Previous methods' success rates on this challenge further vouch for its difficulty. \citet{skrynnik2021forgetful,patil2020align} leverages domain-secific reward functions and RL fine-tuning to achieve $\backsim$0.1\% success rate in 15 minutes of game play.
VPT further boosts the success rate to $2.5\%$ within 20 minutes of play through pre-training on collects $\backsim$70k hours human demonstrations \citep{vpt}.
DreamerV3 is the first to collect diamonds by training from scratch with a success rate of 2\%\citep{dreamerv3}.

Our DEPS manages to achieve on-par performance in this grand challenge; our agent achieves a 0.59\% success rate within 10 minutes of gameplay. Note our method does not specifically fine-tune for this challenge. It is designed to be multi-task in its nature. Furthermore, considering our planner operates with demonstration prompts on a fixed Large Language Model, it can be straightforwardly adapted to other open-ended environments with modifications.

\section{Related Works}\label{sec:related_works}

\paragraph{Task planning with LLMs}
There have been some methods leveraging the large language model to generate action plans for high-level tasks in embodied environments~\cite{socraticmodels,reporter}.
\citet{huang2022language} decompose natural language commands into sequences of executable actions by text completion and semantic translation, while SayCan generates feasible plans for robots by jointly decoding an LLM weighted by skill affordances from value functions \cite{saycan}.
For better executing the plan in embodied environments, some methods use an object detector describing the initial environment into the language prompt to produce environment-suitable plans and adopt success detectors to check that each step is executed successfully~\cite{innermonologue,codeaspolicies}.
\cite{progprompt} and \cite{codeaspolicies} use the pythonic-style prompt to produce more executable plans.
However, all of the above methods assume that the initial plan from the LLM is correct. When there are bugs in the initial plan, it's difficult for the agent to finish the task successfully.

\textbf{Interactive Planning with LLMs}: Inner Monologue~\cite{innermonologue} pilots the front of interactive planning with LLMs, which introduces the feedback (including success detection and scene description) to the planner. However, we found it could still suffer from accumulative planning error, especially in long-horizon open-world tasks. Rather, our ``\textit{Describe, Explain, Plan and Select}'' (DEPS) method can produce more reliable plans by leveraging chain-of-thought thinking and explanation to locate the errors in previous plans. Moreover, we also propose a goal Selector to further improve the efficiency of the plan, thereby yielding much better performances. Readers are encouraged to refer to the comparative results in Section~\ref{sec:results} between DEPS and these prior arts.

\paragraph{Agents in Minecraft}
Some previous works have employed the hierarchical architecture to solve long-horizon tasks in Minecraft \cite{oh2017zero,mao2022seihai,lin2021juewu}.
Recently, based on the internet-scale corpus, \citet{minedojo} pre-trains a language-conditioned reward function and learns multi-task MineAgent.
\citet{vpt} collects a vast amount of human demonstrations to train a behavior cloning agent. More recently, \citet{dreamerv3} utilized a learned world model to distill a policy that can efficiently explore in Minecraft. These efforts all focus on improving the low-level controller. Rather, the planner in our architecture emphasizes applying domain knowledge to propose and arrange the sub-goals. It significantly influences the complexity and breadth of tasks that the agent can handle. Moreover, our planner is zero-shot, making it possible to generalize to other long-horizon open worlds.

\vspace{-0.06 in}
\section{Conclusion}
\vspace{-0.05 in}

We investigate the problem of planning in open worlds. We identify two major challenges unique to these environments: 1) long-term planning requires precise and multi-step reasoning, and 2) planning efficiency could be compromised since canonical planners do not take the agent's proximity to parallel goals/subtasks into consideration. We propose ``\underline{D}escribe, \underline{E}xplain, \underline{P}lan and \underline{S}elect'' (\textbf{DEPS}), an interactive approach based on Large Language Models (LLMs) to tackle them both. Our experiments in the challenging Minecraft domain verify the advantages of our approach over counterparts by marking the milestone of robustly accomplishing 70+ Minecraft tasks and nearly doubling the overall performances. DEPS also becomes the first planning-based agent that can reach the diamond in this game.

\newpage