Exploratory Retrieval-Augmented Planning For Continual Embodied Instruction Following

Authors: minjong  yoo
jinwoo  jang
wei-jin  park
honguk  woo
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:30:48

Abstract: This study presents an Exploratory Retrieval-Augmented Planning (ExRAP) framework, designed to tackle continual instruction following tasks of embodied agents in dynamic, non-stationary environments. The framework enhances Large Language Models' (LLMs) embodied reasoning capabilities by efficiently exploring the physical environment and establishing the environmental context memory, thereby effectively grounding the task planning process in time-varying environment contexts. In ExRAP, given multiple continual instruction following tasks, each instruction is decomposed into queries on the environmental context memory and task executions conditioned on the query results. To efficiently handle these multiple tasks that are performed continuously and simultaneously, we implement an exploration-integrated task planning scheme by incorporating the information-based exploration into the LLM-based planning process. Combined with memory-augmented query evaluation, this integrated scheme not only allows for a better balance between the validity of the environmental context memory and the load of environment exploration, but also improves overall task performance. Furthermore, we devise a temporal consistency refinement scheme for query evaluation to address the inherent decay of knowledge in the memory. Through experiments with VirtualHome, ALFRED, and CARLA, our approach demonstrates robustness against a variety of embodied instruction following scenarios involving different instruction scales and types, and non-stationarity degrees, and it consistently outperforms other state-of-the-art LLM-based task planning approaches in terms of both goal success rate and execution efficiency.

Main paper: 
 introduction: 
 The application of Large Language Models (LLMs) in embodied AI is essential for harnessing common knowledge and immediately applying it to unseen tasks and domains without requiring additional training or data. Researchers are further enhancing task adaptation by integrating environmental information with the intrinsic common knowledge of LLMs [1, 2, 3, 4, 5, 6, 7] . This capability proves invaluable in fields such as home robotics and autonomous driving, where it enables embodied agents to learn across diverse instruction following tasks with minimal data requirements.For embodied agents, these tasks are often not mere single, one-time instructions but are multiple and persistent, necessitating continuous access to environmental knowledge to reason and plan effectively for user needs. In such scenarios, the efficiency of repeatedly collecting environmental knowledge through interaction each time the agent plans can be suboptimal. Furthermore, there is a clear need to integrate and manage multiple user requirements effectively. Exploration in reinforcement learning (RL). In the field of RL, exploration methods, designated to efficiently gather environmental information, have been a focus of research. Strategies were developed, that prioritize the exploration of new environmental information, by offering intrinsic rewards [28, 29] or through navigation schemes derived from offline demonstrations [30, 31, 32] . Particularly, in DREAM [33] , an exploration policy is formulated to adapt to varying conditions by using data gathered during initial exploration episodes. This policy is optimized by maximizing the information gain to better adapt to changes. Our work adapts this mutual information-based exploration strategy with RAG for embodied instruction following. Our proposed framework is the first to implement exploration-integrated task planning with LLMs, enabling the efficient execution of continuouslyperformed instructions and facilitating the dynamic adaptation to changing environmental conditions.3 Approach 
continual instruction following: 
 We consider a set of instructions for embodied tasks that are continuously and simultaneously conducted based on specific environmental contexts. In Figure 1 , the instructions entail conditional actions like "If the temperature is high, open the window" and "When watching TV, turn off the light." The agent continuously explores the environment to verify whether the conditions (e.g., temperature and TV status) are met. Upon confirmations, the agent executes the associated tasks within the environment. We refer to these scenarios, where multiple embodied tasks are conditioned on environmental contexts and conducted continuously, as continual instruction following. This concept aligns closely with continuous queries [34, 35] in database literature, which monitor updates of interest over time and return results when specific thresholds or conditions are met. This is in contrast to single in-situ instruction following, where each task is executed based on isolated, one-time directives.For continual instruction following tasks with conditional instructions I = {i 1 , ..., i M }, we consider a non-stationary embodied environment that changes over time. The conditions of continual instructions may or may not be satisfied over time, requiring continuous exploration in the environment. When certain conditions are met, the associated tasks should be performed promptly. For this continual instruction following tasks in the non-stationary environment, we evaluate agent performance in terms of task completion and efficiency. Our goal is to establish an embodied agent policy π * that maximizes the overall performance of continual instruction following tasks. Specifically, we formulate the reward as a combination of (i) the task success rate SR and (ii) the average pending step PS. SR is the rate of completed tasks whose conditions have been met, and PS is the average steps required to accomplish the task associated with instruction i ∈ I C whenever the condition is met. For instructions I and timestep t, we then formulate the agent policy π * performing a skill upon observation o t asEQUATIONOptimizing both SR and PS allows the agent not only to appropriately plan for multiple instruction following tasks but also to strategically integrate these instructions to improve overall efficiency. The resulting policy is able to minimize redundant skill executions by addressing multiple tasks in an integrated manner, taking into account the possible spatial and temporal overlap of the task requirements. For instance, as illustrated in Figure 1 , an integrated plan achieves a pending step of 7, the average of required timesteps 7, 4 and 10 for the three instructions. This is significantly shorter than 9.2, the average of 5, 9, and 14 achieved by an instruction-wise plan.To address the challenge of continual instruction following in a non-stationary embodied environment, we develop the ExRAP framework. It is designed to minimize the necessity for environmental interaction, by utilizing memory-augmented and exploration-integrated planning schemes while ensuring robust task performance.In ExRAP, each conditional instruction i ∈ I is decomposed into two primary components: query q and execution e. Queries function as conditions for task initiation and are evaluated against environmental information. Executions, on the other hand, involve physical interactive manipulations that are triggered based on the results of query evaluation. In a non-stationary environment, evaluating queries poses a unique challenge due to the need for the agent to continuously synchronize with constantly changing information. This synchronization often necessitates continual exploration, resulting in intensive interaction with the environment.As described in Figure 1 , ExRAP addresses this challenge through two components: (a) query evaluation using environmental context memory and (b) exploration-integrated task planning. In (a), the environmental context memory is established via a temporal embodied knowledge graph to effectively represent the dynamic environment. Augmented with this graph-based context memory, the LLM-based query evaluator responds to queries by checking if their conditions are met and provides confidence levels for these assessments. To address the information decay, which stems from synchronization uncertainty between the previously collected environmental context and the actual current state of the environment, we incorporate entropy-based temporal consistency refinement into the query evaluation process. In (b), ExRAP plans skills that are instrumental not only for achieving tasks from an exploitation perspective but also for boosting confidence in the query evaluations from an exploration perspective. To effectively plan skills that balance both perspectives, we integrate the exploitation value of skills, which is derived from the in-context learning ability of LLMs, with their exploration value, which is determined through information-based estimation.We represent both the environmental context memory and the observations perceived by the agent using a temporal embodied knowledge graph (TEKG), where the memory is established through the accumulation of these observations. Queries, derived from given instructions, are evaluated against the context memory, with consideration for inherent information decay within the previously accumulated data. The query evaluation procedure is described on the upper side of Figure 2 .TEKG and retriever. The TEKG comprises a set of quadruples τ = (se, re, te, t) consisting of source entity se, relation re, target entity te, and timesteps t. We represent the environmental context memory at a specific timestep t within the TEKG, defined asEQUATIONTo integrate the current observation o t+1 into previously established up-to-date memory G t , we employ an update function µ as follows:EQUATIONHere, c is a function that detects the semantic contradictions between quadruples, such as when τ and τ ′ indicate that a TV is both "off" and "on". It returns 1 if there is a contradiction, otherwise 0.Constructed memory G serves as a knowledge database for continual instruction following, enabling the retrieval of environmental information related to specific task directives such as instructions, queries, and executions. Specifically, for language-specified task directives L = {l}, the retriever Φ R The LLM-based exploitation planner v T estimates the value of skills based on their executions and relevant demonstrations in an in-context manner. Simultaneously, the exploration planner v R evaluates these skills using the subsequent TEKG through information-based value estimation. At each step, a skill is then selected based on the integrated skill value from the two estimations.interacts with the memory G and samples k quadruples {τ 1 , • • • , τk }. The sampling is based on the multinomial softmax distribution, where the likelihood of retrieving a quadruple τ is determined by the highest sentence embedding similarity between τ and any l in L.Instruction interpreter. The instruction interpreter Φ I processes continual instructions I = {i 1 , ..., i M }, translating them into queries Q and corresponding task executions E:Φ I (I) = (Q : (q 1 , . . . , q M ), E : (e 1 , . . . , e M ), C) where C(q j ) = e j for ∀j.Here, C is a conditional function that maps each query to its respective execution counterpart.Query evaluator. The memory-augmented query evaluator Φ M estimates the likelihood P (q|G t ) of query q ∈ Q being satisfied, using the historical memory accumulated over time, denoted asG 1:t = G 1 ∪ ... ∪ G t .Leveraging the memory-augmented LLM (Φ LLM ), we develop the query evaluator Φ M by incorporating the previous step's query evaluation P (q|G t-1 ) and a prior of query evaluation R(q|G t-1 ), which is defined in (7) .EQUATIONHere, Ĝ1:t ∼ Φ R (G 1:t , {q}) is retrieved quadruples, and the prior R(q|G t-1 ) is the retrospective query response evaluated at timestep t using G t-1 .Due to the inherent information decay in the memory over increasing timesteps, a decline in confidence should be considered for the likelihood estimation in (5) . To address this, we incorporate an entropy-based temporal consistency as an intermediate step in query evaluation. Specifically, when using the memory from G t-1 , we posit that the entropy of the prior query response at timestep t should be higher than at timestep t-1:EQUATIONTo enforce the temporal consistency, we compute the multiple query response priors using Φ LLM and discard any responses that do not align with the consistency constraint. Specifically, if the entropy of each prior of query response is smaller than previous step P (q|G t ), it is removed.R(q|G t-1 ) = E Ĝ1:t-1∼ΦR(G1:t-1,{q}) Φ LLM q, t, Ĝ1:t-1 , P (q|G t-1 ) with hold (6)Then, we select a set of corresponding executions E t that are likely to require manipulations in the environment, using a filtering threshold θ.EQUATIONTo facilitate integrated task planning for continual instructions, we devise exploitation and exploration planners. The former focuses on exploiting appropriate skills to complete tasks associated with given instructions using the LLM, and the latter focuses on exploring the environment to update the memory in a direction that maximizes information gain. We then integrate their plans to prioritize the next skills to be executed. The resulting planning directs to complete specific task executions E, ensuring effective maintenance of the environmental context memory. This maintenance process involves synchronizing the memory with the current state of the environment. The exploration-integrated task planning procedure is described on the lower side of Figure 2 .Exploitation planner. Given the memory G t and a language description of a skill z ∈ Z, the exploitation planner v T is responsible for estimating the value of the skill with respect to its effectiveness in accomplishing the executions E t . To do so, we harness the retrieved memory-augmented LLMs along with their in-context learning capabilities. Specifically, under the assumption that we can access expert planning dataset D e , we retrieve demonstrations D from D e based on the graph similarity between the current observation o t and the observation withinEQUATIONExploration planner. In conjunction with the exploitation planner, the exploration planner v R is responsible for assessing the value of the skill with respect to its utility for reducing the response uncertainty of the query evaluator Φ M . This assessment is intended for efficient environmental exploration, thereby facilitating the swift and precise identification of query conditions and maintaining the memory up-to-date. Specifically, we define the exploration value of skill z as the difference of mutual information for consecutive timesteps using the query evaluation result in (5) :EQUATIONwhere I denotes mutual information and G t+1 is the updated memory by execution of skill z.Direct computation of G t+1 is impractical without actual skill execution. Therefore, to evaluate the exploration value of skills before their execution, we focus on the entropy related only to the retrieved knowledge pertinent to the evaluated queries Q. This approach is feasible under the mild assumption that the entropy of the query evaluator reaches zero (indicating no uncertainty), once the TEKG memory is fully synchronized with the environment. Thus, we approximate the exploration value asEQUATIONwhere d represents the average distance function between the retrieved quadruples and the current agent's entity in TEKG, and G z t is the predicted partially updated knowledge graph after skill execution, where only quadruples containing the agent as an entity are altered. Note that the exploration value increases as the agent moves closer to the query-related environment parts on the graph through the skill execution. Consequently, the skill is selected by maximizing the integrated skill value, which is obtained by a weighted sum of exploitation and exploration values, as defined in ( 9) and ( 11) respectively:EQUATION 
experiments: 
 We evaluate ExRAP across various degrees of non-stationarity, scales of instructions, and instruction types. We also provide ablation studies and qualitative analysis. Further analysis is in Appendix D. Environments. We evaluate ExRAP in the context of household planning and skill-based autonomous driving with VirtualHome [8] , ALFRED [9] , and CARLA [10] , where we use 16 to 19 distinct instructions for continual instruction following tasks. Details are provided in Appendix A.Evaluation metric. We employ two evaluation metrics for the objective specified in (1) . The task success rate (SR) measures the proportion of completed tasks for continual instructions whose conditions are satisfied at each timestep. Given the continual instructions, the pending step (PS) represents the average number of timesteps required to complete the associated tasks from the moment the conditions of the instructions are actually satisfied in the environment. Note that the agent's detection time of such condition satisfaction may differ from its actual occurrence.Datasets. We use 100 trajectories across 10 different environment settings in VirtualHome, and 50 trajectories in ALFRED and CARLA. These are used for in-context learning of the exploitation planner in ExRAP and the baselines. Note that we use different environment settings for evaluation.Baselines. ZSP [11] is an LLM-based zero-shot task planner. Our experiments serve as a baseline to evaluate LLM-based task planning approaches. SayCan [1] is a state-of-the-art embodied agent framework, which integrates both language affordance scores derived from an LLM and embodied affordance scores learned through RL. In our experiments, we use the optimal affordance function for each environment. ProgPrompt [3] is a framework to enhance language models' capabilities in generating structured and logical outputs, by incorporating programming-like prompts. LLM-Planner [12] is a state-of-the-art embodied agent framework that utilizes LLMs' embodied knowledge to infer subtask sequences. It incorporates object detection information from the agent's interactions for enhanced task planning. To address continual instructions and adapt to non-stationary environments, we implement a variant of the LLM-Planner that infers skills in a step-wise manner.Non-stationarity. In ExRAP, the skill selection is guided by an integrated value derived from queries and executions, enabling the efficient handling of multiple instructions and concurrent memory updates.Instruction type. We also test the applicability of ExRAP for three types of continual instructions in VirtualHome with medium non-stationarity. Sentence-wise type organizes each instruction into individual sentences. This is the default setting in our experiments. Summarized type condenses multiple instructions into a fewer number of sentences. Object Ambiguation type contains abstract forms of target objects such as "something to read.". Table 3 demonstrates superior performance of ExRAP for those types. ExRAP adapts RAG with the environmental context memory to interpret instructions and decompose them into queries and executions. This memory-augmented approach, retrieving and utilizing the information relevant to given instructions, enables effective grounding of continual instructions in different types within the environment. Qualitative analysis. Figure 3 (a) and (b) compare the exploration strategies of ExRAP and LLM-Planner. Given multiple instructions, ExRAP demonstrates broader exploration. This reflects the exploration-integrated task planning in ExRAP, which rather focuses on the overall gain achieved from each exploration and skill execution.We conduct several ablation studies for ExRAP in VirtualHome with medium non-stationarity.Temporal consistency. We compare the performance of our ExRAP and its variant ExRAP-TC that performs query evaluation without temporal consistency-based refinement. As in Table 4 , ExRAP outperforms ExRAP-TC by 15.56% on average. As observed in Figure 3 Exploration strategy. We compare the performance of our ExRAP and two variants ExRAP-LLM and ExRAP-EXP using different planning strategies. ExRAP-LLM directly employs the LLM as the exploration planner, which fully relies on the LLM's capability without information-based exploration, by prompting the LLM with specific exploration commands, e.g., "explore the home." On the other hand, ExRAP-EXP employs only the exploitation planner with specific exploration commands, used only when there are no executions. As shown in Table 5 , ExRAP demonstrates higher performance of 26.76 and 17.46% on average than the two variants, respectively. As in Figure 3 (a) and (d), ExRAP-EXP exhibits reduced exploration capabilities, resulting in a narrower exploration area. LLMs for planning. While we tested several LLMs, ranging from relatively smaller models such as Gemma-2B [36] to larger ones such as Llama-3-70B [37] , our experiments thus far have utilized LLaMA-3-8B for ExRAP and the baselines. In Table 6 , we evaluate ExRAP and two baselines using different LLMs. Both LLM-Planner and SayCan exhibit improved performance with the larger Llama-3-70B, but experience a significant drop in performance with the smaller Gemma-2B model. Unlike those, ExRAP maintains robust performance even with the smaller model, highlighting the benefits of its memory-augmented, integrated planning approach. 
conclusion: 
 We introduced the ExRAP framework to facilitate efficient integrated planning for multiple instruction following tasks, which are conducted continuously and simultaneously in the embodied environment.With the extended RAG architecture, the framework incorporates memory-augmented query evaluation and exploration-integrated task planning schemes, thereby achieving both efficient environment exploration and robust task completion. Via experiments conducted in VirtualHome, ALFRED, and CARLA, we demonstrated the robustness of ExRAP across various continual instruction following scenarios, specifying its advantages over other LLM-driven task planning approaches. Limitation. ExRAP leverages LLMs, which makes its performance dependent on the capabilities of these models to some extent. Compared to other baselines, it also requires increased computation effort due to the management of environmental context memory with temporal consistency. The ablation studies demonstrate that ExRAP is able to deliver robust performance even with a relatively lightweight LLM, yet further investigation into runtime overhead is desired. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that there is no societal impact on the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for the responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make the best faith effort. 
licenses for existing assets: 
 Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All the baselines code, we write footnote for url.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Our work does not involve activities associated with negative societal impacts, such as disseminating disinformation, creating fake profiles, or conducting surveillance. Therefore, we do not expect any negative societal impacts from our research.We employ VirtualHome [8] , a complex simulation environment designed for embodied AI research, which offers a wide range of interactive household activities. This environment requires an agent to perform tasks by interacting with various objects and following high-level action commands. VirtualHome features 162 different object types (e.g., TV, sofa) and multiple room types (e.g., kitchen, living room) across various indoor scenes, providing a complex environment through diverse combinations of rooms. Additionally, to standardize the time duration of skill execution, we have imposed the following restrictions on the 'walk' skill: walking is only possible to adjacent rooms, and only permitted towards objects that are present in that same room. The embodied agent collects information about objects that come into its view and uses this as observations. Additionally, the agent utilizes seven skills to respond to the given continual instructions: walk object or walk room, grab object, switch object, put object, putin object, open object, and close object. For constructing TEKG, we use the graph based environment implemented in VirtualHome.For non-stationarity, the environment condition involves a single continual instruction from the set changing at every predefined timestep: 4 for high non-stationarity, 6 for medium non-stationarity, and 8 for low non-stationarity. For continual instruction following tasks, we implement 19 continual instructions. Table A .1 shows the details of instructions. We utilize ALFRED [9] , which provides vision-and-language navigation and rearrangement tasks for embodied AI. This environment requires an agent to follow language formatted instructions to as a skill-based environment. The agent can navigate within the environment using three skills: turn right, turn left, and go straight. Additionally, the agent is capable of loading and offloading goods. The objective of the agent is to transport goods from a designated building to a target building whenever the conditions specified in the given instructions are met.For non-stationarity, the environment condition involves a single continual instruction from the set changing at every predefined timestep: 4 for high non-stationarity, 6 for medium non-stationarity, and 8 for low non-stationarity. For continual instruction following tasks, we implement 16 continual instructions such as "If the green building calls, load the goods from the green building to the red building". We utilize a set of instructions as continual instructions.In this section, we provide the implementation details of our proposed framework ExRAP and each baseline. Our framework is implemented using Python v3.10 and trained on a system of an Intel(R) Core (TM) i9-10980XE processor and two NVIDIA RTX A6000 GPUs. Each experiment run takes 4 hours. We employ 4 different methods: ZSP [11] , SayCan [1] , ProgPrompt [3] , and LLM-Planner [12] .Although the format differs, the observed environmental knowledge used remains consistent across all baselines. This includes observations of objects, object positions, object states, room adjacencies, etc. For generating a plan, we utilize the Llama-3 [37] model.ZSP [11] capitalizes on the abilities of LLMs for embodied task planning by translating instructions into skill sequences, thereby enhancing the performance of embodied tasks. ZSP achieves this through the generation of detailed step-by-step prompts derived from examples of similar successful tasks, and then it utilizes the LLM to generate executable plans based on these examples. For implementation, we refer to the opensource2 .SayCan [1] integrates the affordance function with language models, generating plans that are feasible to the context. SayCan achieves this by learning the environment affordance function derived from the LLM with the agent's experiences. Similarly, we calculate optimal affordance scores using environmental information and domain-specific knowledge. For observation, we utilize the linearized retrieved knowledge graph as the prompt for SayCan as same as ExRAP. For implementation, we refer to the opensource 3 .ProgPrompt [3] utilizes the code-style policy for generating plans for the embodied environment.As it passes the available primitive actions such as walk object, grab object, etc., in the form of import statements in Python, an available object list, and example tasks to LLM, the LLM produces some plans to succeed in the task. ProgPrompt can also execute conditional action by assert-else statements in the codes which is the output of the LLM. For experiments, we provide the code examples for various tasks in VirtualHome and ALFRED. For implementation, we refer to the opensource 4 .LLM-Planner [12] leverages the LLMs using the demonstrations with retrieved in-context examples, empowering embodied agents to perform complex tasks in environments with observed information, guided by natural language instructions. For our experiments, the LLM-Planner performs inference at each timestep, gathering observed environmental knowledge through natural language. When a skill execution fails, it captures the error and infers an alternative action based on the error at the next timestep. For observation, we utilize the detection results from the environment and incorporate them as prompts for the LLM-Planner. For implementation, we refer to the opensource 5 .The hyperparameter settings for baselines are summarized in In ExRAP, we address multiple continual instruction-following tasks by decomposing each instruction into queries and task executions based on environmental context memory. To manage these tasks effectively, which are executed continuously and simultaneously, we introduce an explorationintegrated task planning scheme. This scheme incorporates information-based exploration into the LLM-based planning process, enhancing the balance between maintaining the validity of the environmental context memory and the demands of environment exploration, ultimately boosting overall task performance. Additionally, we implement a temporal consistency refinement scheme in our query evaluation to counteract the inherent decay of knowledge within the memory.For the update function µ of TEKG in (3), we design an algorithmic refinement function tailored for embodied environments. This refinement function operates under two simple rules. First, only the most recent timestep data is retained for quadruple related agents (i.e., where the source entity or target entity is an agent). This is because information related to agents in the environment is observable. Second, semantically contradictory information is categorized into two cases: one where object states are opposite, such as simultaneous quadruples indicating that a TV is both off and on, and another where an object exists in two places at TEKG. Both scenarios result in the removal of the outdated quadruple.The hyperparameter settings for the baselines are summarized in Table A .4. 1.0 Weights for exploitation value w T in (12) 0.01Table A .5 presents a performance comparison in terms of SR and PS. The environmental settings consist of two variables: the size of continual instructions and the degree of non-stationarity. As the size of continual instructions increases, the number of instructions that need to be addressed also grows, requiring the agent to collect more knowledge and perform more tasks. Furthermore, a higher // (a) Query evaluation in (for q in Q do 10:L Q = [ ] 11:for 1, 2, ..., 10 do12: Ĝ1:t-1 ∼ Φ R (G 1:t-1 , {q}) 13:R(q|G t-1 ) = Φ LLM q, t, Ĝ1:t-1 , P (q|G t-1 )14:if hold (6) then 15:L Q .append(P (q|G t-1 )) P (q|G t ) = Φ M (q, t, G 1:t-1 , R(q|G t-1 )) 20:end for 21:// (b) Exploration-integrated task planning in (12) 22:EQUATIONG t+1 = µ(G t , o t+1 ), t ← t + 1 25: end loop degree of non-stationarity means the environment changes more rapidly, necessitating that the agent focuses more on environmental information to adapt effectively. A .5, ExRAP demonstrates an increase in SR by 4.73% to 27.50% on average compared to the most competitive baseline, the LLM-Planner. Furthermore, ExRAP shows an average reduction in PS by 4.84 to 13.29 compared to the LLM-Planner. Similar to the experiments in the main text, ExRAP exhibits widening performance gaps as the complexity of tasks increases: the SR gap grows from 19.12% compared to the LLM-Planner with small continual instructions, to 19.93% with large continual instructions. Similarly, the PS gap expands from an average of 6.79 to 9.97. Moreover, ExRAP demonstrates robustness in embodied environments across varying levels of non-stationarity: the SR gap remains consistent, ranging from 17.77% compared to the LLM-Planner in low non-stationarity environments to 17.32% in high non-stationarity. The PS gap expands from an average of 6.96 to 9.27.We compare the performance of ExRAP and ExRAP-TC, which evaluates queries without temporal consistency-based refinement, to understand the impact of this feature. Additionally, ExRAP-LLM operates by directly inputting the instruction "Explore the home" into the LLM, thereby enabling it to function as an exploration planner. This approach contrasts with ExRAP-EXP, which evaluates skills using an exploitation-only planner. Here, ExRAP-EXP inputs "Find {query}" for each query that is not yet satisfied, focusing solely on achieving specific task objectives without incorporating exploration. Table A.6 presents the detailed results of the ablation study for Tables 4 and 5 in Section 4.2 of the main text. we noted that the increase in exploration is more larger in environments with higher non-stationarity, leading to enhanced exploration. This, in turn, resulted in a more frequent drop in exploration value.through an LLM without retrieval, using an RTX A6000 GPU and an i9-10980XE processor. By selecting relevant quadruples and demonstrations based on the query and instructions, ExRAP effectively reduces the context length, maintaining efficient LLM inference times. In our experiments, we retrieve only 3 demonstrations and 12 quadruples to generate prompts for each continual instruction, regardless of the size of the knowledge graph or dataset. Figures A.3 illustrate the changes in exploration value for a single query during the execution of continual instructions. We observed that the exploration value increased steadily over time and decreased rapidly once information relevant to the query was collected. Specifically, we noted that the increase in exploration was more larger in environments with higher non-stationarity, leading to enhanced exploration. This, in turn, resulted in a more frequent drop in exploration value. As the reviewer suggested, investigating the exploration dynamics is an interesting analysis that demonstrates how ExRAP improves performance.To analyze the behavior patterns of ExRAP, we map its generated plans to heuristic strategies such as Greedy, and Multiple Instruction First, and Max Staleness First. In our work, these heuristics are utilized only for analysis purposes, showing how ExRAP is able to achieve superior performance and how its exploration-integrated planning policy behaves differently in specific situations. When the entropy values of the queries are generally low and there are few executions required to complete, ExRAP operates in a manner similar to a greedy heuristic with respect to a single instruction. For example, in Table A .9, when there exist few executions required to complete and the entropy of the query responses is generally low, ExRAP operates similarly to a Greedy heuristic, executing instruction 1 independently. However, consistently applying this heuristic in all scenarios results in executing an instruction-wise plan, similar to the baselines. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).https://github.com/huangwl18/language-plannerhttps://github.com/google-research/google-research/tree/master/saycanhttps://github.com/NVlabs/progprompt-vhhttps://github.com/OSU-NLP-Group/LLM-Planner/ 


Decision: This paper presents the Exploratory Retrieval-Augmented Planning (ExRAP) framework to address the challenge of continual instruction following in non-stationary embodied environments. ExRAP enhances the reasoning capabilities of Large Language Models (LLMs) by efficiently exploring the environment and maintaining an environmental context memory to ground the task planning process. The paper provides insights into integrating LLMs, memory-augmented reasoning, and information-based exploration for continual instruction following. Authors have also replied and satisfactorily replied to the concerns raised by the reviewers during the rebuttal period. Overall a good paper.

Reviews: review: paper_summary: paper_summary: The paper considers a problem of continual instruction following where an instruction contains multiple query-execution pairs to be performed.
For this, the paper proposes ExRAP comprised of two components: query evaluation and exploration-integrated task planning.
Query evaluation incrementally updates the temporal embodied knowledge graph and selects a set of the most relevant executions.
The exploration-integrated task planning part uses both exploration and exploitation by weight-summing the predicted values of predefined skills whose weights are hyperparameters.
The performance in the experiment shows noticeable margins compared to the baseline models.
strength_weakness: strength_weakness: - While agreeing that addressing an instruction that contains multiple tasks, it is unclear why it should be in the explicit form of query(condition)-execution pairs. This is not well-justified. In addition, can't it be implicit?
- Regarding the first question, it looks like the proposed approach exploits the query-execution format of the proposed task setup (*e.g.*, query evaluator).
- The scale of the continual instruction following dataset is a bit limited. All the 3 datasets use less than 20 continual instructions, which may potentially raise a generalizability concern.
- High errors are observed across many tables in the experiments.
  - Why is this the case? Can this be related to the small scale of the dataset?
  - One argued contribution is a good performance of the proposed approach, but due to the high errors, it is unclear whether the argued outperformance is valid.
- The paper introduces many hyperparameters but it is unclear how much the proposed approach is sensitive to the choice of them.
- How to obtain the knowledge graph? is it obtained as GT values or predicted by some learned perception modules?
- In L184, why do the authors posit $H(R(q|G_{t-1})) > H(P(q|G_{t-1}))$? Any intuition behind this?

- Considering that the term "continual" also refers to learning some new tasks sequentially (*e.g.*, RL [a], IL [b], or even EIF [c]). Discussion about this aspect seems needed to clarify the usage of "continual" in this paper.

References\
[a] Xie and Finn. Lifelong robotic reinforcement learning by retaining experiences. CoLLAs, 2022.\
[b] Gao et al.  Cril: Continual robot imitation learning via generative and prediction model. IROS, 2021.\
[c] Kim et al. Online continual learning for interactive instruction following agents. ICLR, 2024
questions: questions: See weaknesses above.
limitations: limitations: The authors do not address the potential negative societal impact.
paper_summary: paper_summary: This paper presents the Exploratory Retrieval-Augmented Planning (ExRAP) framework to address the challenge of continual instruction following in non-stationary embodied environments. ExRAP enhances the reasoning capabilities of Large Language Models (LLMs) by efficiently exploring the environment and maintaining an environmental context memory to ground the task planning process.

The paper's main contributions are:

1.	A novel ExRAP framework integrating LLMs, memory-augmented reasoning, and information-based exploration for continual instruction following.
2.	Temporal consistency refinement and information-based exploration schemes tailored for ExRAP's integrated planning approach.
strength_weakness: strength_weakness: 1. ExRAP's performance still somewhat depends on the underlying LLM's reasoning abilities. While the ablation study shows robustness to smaller LLMs, it's unclear how the framework would perform with much weaker language models or in domains where the LLM's knowledge is limited.

2. The environments' non-stationary aspects are limited to a single instruction changing at fixed intervals. This does not fully capture the complexity and unpredictability of real-world non-stationary environments, where goals, conditions, and constraints can evolve in more intricate ways. 

3. The instructions used in the experiments seem to be largely independent of each other, without any significant long-term dependencies or relationships between tasks. An example from Table A.1 is: "If no one is watching the TV, turn it on." If you have an apple somewhere, bring it to your desk. "If you see a book somewhere unorganized, bring it to the sofa." These instructions in the table appear to be independent tasks without any clear long-term dependencies or relationships between them. Each instruction can be completed independently of the others.

That being said, the ExRAP framework does take important steps by incorporating memory-augmented reasoning and exploration-integrated planning. These components provide a way for handling evolving instructions and non-stationary environments. The authors' claims may be somewhat overextended given the current experimental setup, but the work still makes valuable contributions to embodied instruction following.
questions: questions: If authors can address points 2 and 3 from weaknesses, it will help in understanding whether there is a distinction between concurrent or multi-task instruction following and truly continual instruction following.
limitations: limitations: Authors have addressed some of the limitations of the work in the paper.
paper_summary: paper_summary: The paper introduces an Exploratory Retrieval-Augmented Planning (ExRAP) framework, that tackles the problem of embodied planning in dynamic environments. The study focuses on continual instruction following, which is when the task consists of multiple conditional subtasks. The execution of each subtask is dependent on the environment state. This requires continual exploration to keep up-to-date information and integrated planning abilities for efficiency. 

ExRAP combines Large Language Models (LLMs) with environmental context memory represented as a temporal embodied knowledge graph (TEKG), that captures the states of objects in the scene and their pairwise relationships. The TEKG is updated at each step using the most recent observation and an update function $\mu$. Each subtask is translated into a pair of a query about the scene and a corresponding execution command with an instruction interpreter $\Phi_l$. Next, the memory-augmented query evaluator $\Phi_{M}}$ estimates the likelihood of the query being satisfied, using quadruples retrieved by $\Phi_R$ as environmental context information for the LLM. Authors enforce a temporal-consistency constraint on the evaluator, resulting in a continual steady decrease of the entropy of the answer. The execution commands corresponding to the satisfied queries are then passed to the execution part of the model. This part consists of exploitation and exploration planners. The former assesses the effectiveness of the skill in accomplishing the execution task. The latter one does the same with regard to reducing the uncertainty of the query evaluator $\Phi_M$. The performed skill is chosen as the one providing the maximum weighted sum of the two scores, balancing exploration and exploitation.

In the experiments, the authors measure the Success Rate (SR) of the task completion and the Pending Step (PS), representing the average number of steps taken to complete the task. The evaluation is performed on the VirtualHome, ALFRED, and CARLA environments. Performance in various degrees of stationarity in the environment is assessed, showing the advantage of the method. The performance with respect to the number of instructions is also evaluated. The method seems to excel in integrated planning, effectively solving multiple tasks with fewer steps. Ablation studies demonstrate the importance of temporal consistency and exploration-integrated planning. Intrestingly, the study reveals a limited effect of choosing a larger LLM as a base model.
strength_weakness: strength_weakness: - The paper shows that the method is quite robust to the size of the base LLM. It could be a strength if there would be some training procedure possible. However, ExRAP relies exclusively on the in-context learning abilities of the LLM, thus the experiment shows that it scales poorly. The paper would benefit from an ablation study on the size of the retrieval dataset, so it can be shown that the method can scale with the context length of the model by increasing the number of examples.
- The method excels at following multiple simple parallel conditional instructions, but it is not clear if it will be as good at the long-term tasks that require multiple steps to achieve, like the ones on which the LLM-Planner was tested. The advantage of having an adaptable planner may become a disadvantage against the baselines, as it may require more queries to the environment context memory, which will create a large computational overhead. It is unclear whether the method is better than the baselines in integrating multiple complex tasks, each of which requires multiple steps, into an optimal plan. Unfortunately, this is not investigated in the paper.
- The applicability to the real-world setting is questionable and not investigated. Would the method scale appropriately with the number of objects in the scene? Methods like ConceptGraphs do not show robustness in that case.
- The termin "continual embodied instruction following" is a little misleading, as in the paper, the instructions are passed all at once, and not at random times, which would require replanning. The "conditional embodied instruction following in the dynamic environment" could be a better name, though this is not a significant issue.
questions: questions: - Are the environment settings used in the in-context learning retrieval dataset the same or different from the ones used for the test?
- What does the observation $o_t$ consist of for ExRAP? Is it a list of quadruples? How would the setup be adapted for the real-world case?
- How does the system handles contradicting instructions? Like “If there is a storm outside, turn off the electricity in the house. If the TV says that the storm is over, turn the electricity on.”
- To me, it is not clear why the temporal consistency works. Would a simple baseline of reducing the temperature of prediction perform as good as the temporal consistency constraint in the paper?
- It would be interesting to investigate the exploration dynamics of the agent. Does the exploration scores on average decrease steadily throughout the experience or more rapidly in some particular times?
limitations: limitations: - Runtime overhead not investigated, but mentioned.
- Applicability to the real world is not addressed.

Comments: title: Thank you!
Thank you!
Thank you!
Thank you for the response.
Response by Reviewer K6e1
comment: Thank you for raising your score. We greatly appreciate your thoughtful comments and feedback. We will include this discussion and further experiments in our final version.

Your recommendation to analyze the exploration dynamics is insightful, as it clarifies how our agent investigates its environment, enhancing the reader's understanding. Furthermore, the discussion on contradicting instructions points to potential approaches for resolving conflicts and offers constructive comments for our future work.

Thank you once again for your feedback. Our discussion is meaningful and highly motivating for us.
Thank you for your response. You addressed my concerns completely, and I will raise the score.
Thank you again for your considerate review. As the end of the author-reviewer discussion period approaches, we summarize the key points of our responses to the reviewer.

1. The scalablity of ExRAP
- ExRAP uses the sentence embedding techniques such as DPR and BM25 for knowledge graph retriever and demonstration retriever for exploitation value. Even as the knowledge graph grows, it maintains the inference time of the LLM and minimizes computational overhead through retreival-based approach. By selecting quadruples and demonstrations relevant to queries and instructions, it effectively reduces the context length and maintains the inference time of the LLM. In experiments, we retrieve only 3 demonstrations and 12 quadruples to generate prompts for each query and execution, regardless of the size of the knowledge graph or the dataset. 
To clarify the retrieval models used, we will add these computational overhead results in Appendix.
2. The applicability to the real-world setting.
- The environments used in our experiments (VirtualHome, ALFRED, and CARLA) are highly similar to real-world settings and are frequently used in prior works proposing embodied planning or LLM-based frameworks. For example, in VirtualHome, a single scene contains between approximately 20 to 100 objects, and there are 50 types of room structures, each with varying object states and positions.
- In ExRAP, a temporal embodied knowledge graph is used to efficiently manage and retrieve information on changing object states, enhancing adaptability and operational efficiency in dynamic environments.
3. Investigatation for the exploration dynamics of the agent.
- Figures 1 in the PDF file illustrate the changes in exploration value for a single query during the execution of continual instructions. We observed that the exploration value increased steadily over time and decreased rapidly once information relevant to the query was collected. Specifically, we noted that the increase in exploration was more larger in environments with higher non-stationarity, leading to enhanced exploration. This, in turn, resulted in a more frequent drop in exploration value. As the reviewer suggested, investigating the exploration dynamics is an interesting analysis that demonstrates how ExRAP improves performance. We will add this to the Appendix of the final version.

The reviewer's suggestion to analyze exploration dynamics offers valuable insight by demonstrating the characteristics of our agent's exploration, which helps readers' understanding. Additionally, the discussion on contradicting instructions points to potential approaches for resolving conflicts and offers constructive comments for our future work.

We will do our best to address any questions the reviewer may have until the end of the reviewer-author discussion period. Please feel free to ask any further questions. Thank you.
Thank you once again for your insightful feedback and thoughtful comments. 

In particular, the discussion on continual instructions with long-term dependencies or relationships between them is invaluable. 
This results highlight our ExRAP's capability not only to handle independent continual instructions with implicit overlapping subtasks but also to perform effectively in scenarios where these instructions influence each other, emphasizing the generality and scalability of our approach.

We will include these additional experimental results and the clarifications requested by the reviewers in the final version of our manuscript. Your review is constructive regarding our approach. Thank you!
Thank you for your detailed response. The response addressed my concerns.
Thank you for raising your score. We truly appreciate your consideration and constructive comment and feedback. We will incorporate this discussion and additional experiments into the final version. 

While our paper focus on solving continual instruction, your suggestion to extend our experiments to include what appears to be purely execution-based instruction is insightful feedback that can demonstrate the generality of our model.

Thank you once again for your response. The discussion with you is very meaningful and greatly encourages us.
I thank the authors for the response with the additional experiment. The response addressed my concerns and I am happy to increase the score.
Thank you for your kind feedback and the additional questions. Our responses are as follows:

**For W1.**

- Thank you for valuable insight. Our ExRAP can also be applied in situations where instructions consist solely of execution. Below table shows the performance of simple experiments on instructions that involve only execution and no conditions. Although the need for exploration has been reduced, ExRAP demonstrates an advantage over the baseline by efficiently executing multiple instructions through integrated task planning. We will include this results and experiments comparing the entire baselines in the Appendix of the final version.

| Model | SR (↑) | PS (↓) |
| --- | --- | --- |
| LLM-Planner | 74.17% | 8.80 |
| ExRAP | 79.86% | 7.20 | 

- As the reviewer mentioned, in environments where only the robot agent exists and there are no changes over time, the condition of "Always leave the stove open" can be True. However, in dynamic environments where other agents or users can interact with the stove, the instruction would need to be divided into a condition and execution: "If the stove is closed", then "open the stove". For instructions that appear to only involve execution, such as "put the mug in the sink",ExRAP addresses this by relating the condition to the goal, such as “if the mug is not in the sink". If we treat the condition as always true, it could force the repetition of an already completed task, potentially leading to performance degradation. These examples are considered important for explaining our framework, and we will ensure to include them in our paper.
- Converting to a query-execution format becomes a crucial part in optimizing exploration in ExRAP. 
However, simply separating query and execution does not fully resolve the continual instruction following problem in time-varing dynamic environment. We manage environmental observations through an knowledge graph-based approach, and efficiently utilize information through retrieval to evaluate queries. Additionally, an integrated exploration and exploitation planner enables efficient planning through multiple instructions.

**For W8.**
- Thank you for your thoughtful feedback. We will add the following statement to the main text, Line 108:

“The continual instruction does not refer to continual learning, which learns some new task sequentially.
It aligns closely with the concept of continual query, which are standing queries that monitor update of interest and return results whenever the update reaches specific thresholds.” 

We are very pleased that the reviewer's concerns and most of the identified weaknesses have been addressed. If you have any additional questions, please feel free to ask. Thank you!
Thank you for your detailed response. The response addressed my concerns but a few things still remain unclear.
- For W1, "Always leave the stove open" seems not implicit but explicit with the condition that is always `True`. The current continual instruction proposed is usually in the form of condition-execution pairs (i.e., if something is happening, then do something). My concern is why we need the "two", condition and execution. For instance, can't it be done with only execution?
- For W8, thank you for the clarification, but this can be quite confusing and it might be better to clarify this somewhere in the main paper.