Robotouille: An Asynchronous Planning Benchmark for LLM Agents

Thank you for taking the time to review our work. We will be updating the paper draft with our responses to improve its clarity. We also appreciate your concrete suggestions and have added GAIA to our table, converted our images to SVG, and clarified Figure 6’s caption.

The paper can be split into two main sections: 1) introducing and baselining the benchmark and 2) analyzing results. While the first part is strong, insights in the second part are somewhat obscured. For instance, in Q6, the majority of both successful (72.7%) and failed (52.8%) trajectories prioritized subtask completion. Does this indicate that subtask prioritization may not be a critical area for improvement in planning? I encourage authors to capitalize more on their analysis.

We have updated the paper with a clarified hypothesis in Q6 and include a clearer metric to support it. In Q6, we investigate how success rate changes with asynchronous task prioritization to understand the impact of asynchronous planning on the results. Our hypothesis is that prioritizing asynchronous subtasks leads to higher success rates as the planned trajectory is shorter and reaches the goal within the maximum step limit. We find that the success rate conditioned on prioritization is 16% compared to 6% without. This more clearly quantifies that task prioritization has a significant impact on success rate.

Please let us know about any other parts of our results analysis that can be improved so we can further strengthen the analysis.

The absence of stochastic elements in the environment and experimentation is notable. One of the significant challenges for LLM architectures lie in adapting to stochastic domains [1].

We initially avoided introducing stochasticity to minimize confounds and focus solely on investigating the asynchronous planning capabilities of LLMs. It is straightforward to incorporate stochasticity into Robotouille as we demonstrate below on a small subset of synchronous problems.

In the Stochastic Synchronous setting, we introduce a 33% chance that a cut item will revert to being uncut once per environment seed. We hypothesize that the LLM agent will follow its plan in an open-loop manner, without adapting to such changes. In the table below, Tasks 2 and 3 have a statistically significant performance drop. The LLM agent did indeed continue its plan without incorporating the stochastic change. In Task 2, the agent's only success occurred because it completed the task before the stochastic change happened. In Task 3, the change occurred immediately after an item was cut, allowing the agent a brief opportunity to adapt. We are happy to extend this for all synchronous tasks and add it to the paper.

Although the paper initially emphasizes the multi-agent aspect of the environment, this is not reflected in the empirical results.

Robotouille supports multi-agent environments and provides a dataset of 10 tasks for this setting; however, due to the low performance of LLM agents in the asynchronous setting, we defer this investigation to future work to focus on asynchronous planning. We expect the multi-agent setting to be strictly harder since it involves asynchronous planning.

Line 366: Could you clarify why (0.5, 1.0] implies minimal progress? Wouldn’t a score of 0.5 indicate the solution is halfway there?

The number indicates normalized “steps to go”, i.e. “in a failed attempt, (optimal distance from terminal state to goal / optimal distance from start to goal)”. Higher is worse, i.e. 0 implies success, >=1 implies that when the agent failed it was further away from the goal than at the start. Hence the (0.5, 1.0] bucket groups failures that are more than halfway at the goal.

We have updated the draft with a clear formula for this metric.

Line 520: I was surprised not to see value propagation and temporal difference learning listed under Feedback Incorporation techniques.

The Feedback Incorporation section was biased on in-context learning with LLM agents due to the prominence of prompting-based approaches in existing work [1]. However, we acknowledge that fine-tuning LLM agents is a crucial future direction and will add this to our discussion. Training LLM agents with RL techniques like TD learning and value propagation [2,3] remains an important and underexplored area for further research.

[1] FireAct: Toward Language Agent Fine-Tuning. Chen et. al 2023

[2] Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents. Putta et. al 2024

[3] RLEF: Grounding Code LLMs in Execution Feedback with Reinforcement Learning. Gehring et. al 2024.

Thank you very much for your thoughtful review. We are grateful for your detailed feedback and will incorporate our responses into the paper draft to improve its quality and clarity.

Given this, it seems unclear what are the additionally challenges in this benchmarks compared to for example the AsyncHow dataset mentioned in the paper.

We would like to clarify the key features of Robotouille and how it differs from related benchmarks such as ​​AsyncHow:

• Interactive Simulator: Robotouille has a game engine backend wrapped as an OpenAI Gym environment. This tests the closed-loop planning ability of LLM agents and their ability to recover from failures as it learns about the rules and constraints of the environment. This is different from benchmarks like AsyncHow [1] which do not use an interactive environment.
• Language Backend: Compared to benchmarks like Overcooked-AI [2], Robotouille offers a diverse number of tasks (30) with infinite procedurally generated kitchens, and a language backend that supports LLM agents
• Asynchronous Planning: Compared to benchmarks like VirtualHome [3] and Planbench [4], which have been used to benchmark LLM synchronous planning, Robotouille introduces time delays to benchmark LLM asynchronous planning.

[1] Graph-enhanced Large Language Models in Asynchronous Plan Reasoning. Lin et. al 2024

[2] On the Utility of Learning about Humans for Human-AI Coordination. Carroll et. al 2019

[3] VirtualHome: Simulating Household Activities via Programs. Puig et. al 2018

[4] PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change. Valmeekam et. al 2022

It is unclear from the paper which components of asynchronous planning make it much harder than synchronous planning. A detailed analysis of why “asynchronous” planning is harder is needed to understand in what ways do this benchmark challenges the methods.

Which components of asynchronous planning make it much harder than synchronous planning?

We provide a sketch of why asynchronous planning is harder than synchronous planning below by analyzing the complexity of search for both settings.

We can model time-delayed actions as expanding the state space of the MDP with timer variables that track how long such an action has been active for. Consider an MDP with time-delayed effects, represented as $<\mathcal{S}, \mathcal{A}, \mathcal{T}, \mathcal{R}>$, where:

• State Space $\mathcal{S}$: Each state $s \in \mathcal{S}$ is $s = (\hat{s}_t, H_t)$,
  • $\hat{s}_t$ represents observable state elements (e.g., objects, predicates).
  • $H_t$ is a set of timer variables $h \in H_t$, each created by actions with a countdown function $h(x) = d - (x - i)$, where $d$ is a delay constant, and $i$ is the timer’s activation step.
• Actions $a \in \mathcal{A}$ may introduce new timers
• Transition Function $T(s, a) = s’ = ( \hat{s}\_{t+1}, H_{t+1})$:
  • State Update: If any timer expires, $\hat{s}_{t+1} = \hat{s}_t$ $\cup$ { $\text{predicates}(h) \mid h \in H_t, h(t) = 0$ }
  • Timer Update: $H\_{t+1} =$ $(H\_t -$ { $h \mid h(t) = 0$ } $)$ $\cup$ { $h \mid a \text{ adds delay}$ }
• Reward Function $R$:
  • $R(s) = 0$ if $s = g$ (goal), else $R(s) = -1$

The complexity of search for synchronous and asynchronous is:

1. Synchronous Case $(d = 0)$: No delays, so the planner operates in $O(|S| + |A|)$.
2. Asynchronous Case $( d > 0 )$: Each delay expands the effective state space, yielding $O(|S| \times (d+1)^n + |A|)$ complexity, where $n$ is the number of timers.

Hence the expanded state space requires both a conventional planner or a LLM based planner to reason over a larger range of delayed effects. We are happy to update the paper draft with this simple analysis to show why asynchronous planning is harder.

Thank you for your help in improving our paper! We have updated the paper to clarify many of your points as we detail below.

The paper lacks a discussion on prompt design. The performance differences between the synchronous and asynchronous datasets may stem from variations in prompts, which often determine the practical limits of an agent's capabilities.

This is a great point and we have added this to the paper in Appendix A.3. For both datasets, we use the same set of instructions as input to I/O, I/O CoT, and ReAct as shown in Appendix A.3. Each method is few-shot prompted with an example optimal trajectory on a task unique to the dataset being evaluated on. Notably, the asynchronous example involves a time delay. We ensured that prompt formatting in both datasets was consistent and will include examples in the Appendix to make this transparent.

Additionally, the tasks in the synchronous and asynchronous datasets differ, making it inappropriate to directly compare results from both settings during the analysis.

We agree that direct comparison of results between the synchronous and asynchronous dataset would be an inappropriate apples to oranges comparison. Our intention when designing our datasets was to ensure that LLM planning capabilities would be stress tested on unique tasks such that an LLM agent performing well on the synchronous and asynchronous datasets could plan effectively in either setting. We have reviewed and edited the paper to remove any implications of such comparison.

We do, however, claim that asynchronous settings are strictly harder than synchronous settings. For some MDP with state space S and action space A, in synchronous settings, a classical planner (i.e. BFS) has a complexity of $O(|S| + |A|)$ whereas in the asynchronous setting with delay d the complexity increases to $O(|S| \times (d+1)^n + |A|)$ where n is the number of delays. This demonstrates the added computational burden in asynchronous scenarios.

To support this empirically, we adapt Tasks 1-3 in the asynchronous dataset to synchronous variants where there are no time delays (i.e. meat is cooked immediately). The results below demonstrate that ReAct gpt-4o performs better in the synchronous variants.

If possible, I suggest including experimental results from some open-source models in the model list. While these results may not surpass those of proprietary models, they could encourage the open-source community to pay more attention to this research area.

We fully agree and intend to incorporate open-source models into the results. We believe fine tuning open-source models for Robotouille is a promising direction for future research. Below are new experiments on the synchronous setting using top-performing open-source LLMs on the HuggingFace LLM leaderboard. The following experiments were run on 4 NVIDIA RTX 6000 Adas using FP8 quantization. We will be continuing these experiments for the remaining synchronous tasks and the entire asynchronous dataset.

The paper states that ROBOTOUILLE supports multi-agent environments by simply adding more players to the problem JSON. However, I did not see any related attempts or studies mentioned. Is this intended as a future research direction?

This is intended as a future research direction. We decided to focus on asynchronous planning due to the low performance of LLM agents in this setting and because we expect the multi-agent setting to be strictly harder since it involves asynchronous planning.