Robotouille: An Asynchronous Planning Benchmark for LLM Agents

Authors: Gonzalo Gonzalez-Pumariega, Leong Su Yean, Neha Sunkara, Sanjiban Choudhury
Primary area: datasets and benchmarks
Keywords: benchmark, llm, agents, planning

Abstract:
Effective asynchronous planning, or the ability to efficiently reason and plan over states and actions that must happen in parallel or sequentially, is essential for agents that must account for time delays, reason over diverse long-horizon tasks, and collaborate with other agents. While large language model (LLM) agents show promise in high-level task planning, current benchmarks focus primarily on short-horizon tasks and do not evaluate such asynchronous planning capabilities. We introduce Robotouille, a challenging benchmark environment designed to test LLM agents' ability to handle long-horizon asynchronous scenarios. Our synchronous and asynchronous datasets capture increasingly complex planning challenges that go beyond existing benchmarks, requiring agents to manage over-
lapping tasks and interruptions Our results show that ReAct (gpt-4o) achieves 47% on synchronous tasks but only 11% on asynchronous tasks, highlighting significant room for improvement. We further analyze failure modes, demonstrating the need for LLM agents to better incorporate long-horizon feedback and self-audit their reasoning during task execution.

Decision: accept (poster)
Reviewer scores: 3, 8, 6

Reviews and discussion:
<thread>
creation date:
1730419799119

thread_type:
official_review

<thread_object>
creator: reviewer_nvj3

<content>
summary:
This paper introduces Robotouille, a benchmark designed to evaluate the planning capabilities of LLMs in asynchronous, long-horizon, and multi-agent environments. Authors highlight a significant performance gap for SOTA approaches (e.g., GPT-4o+ReAct), showing success rates of 47% in synchronous tasks and only 11% in asynchronous ones. The benchmark includes datasets with varying levels of complexity, along with a thorough failure analysis, offering key insights into where and why current approaches fall short.

strengths:
+ Well-written with clear illustrations of domain complexities.
+ Rigorous experimental design, featuring carefully curated datasets across multiple complexity levels and a detailed failure analysis.

weaknesses:
* 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.

* 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].

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

**Minor Suggestions**

* Include GAIA benchmark in your related work section (https://arxiv.org/abs/2311.12983).
* Use vectorized image formats to ensure quality remains high when zooming.
* Line 443: Add context to the caption: "The median separates failures into runs with lower and higher repeated transitions, with quartiles representing the mean of these two groups."

[1] David Brandfonbrener, Alberto Bietti, Jacob Buckman, Romain Laroche, and Joan Bruna. "When does return-conditioned supervised learning work for offline reinforcement learning?" In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL: https://openreview.net/forum?id=XByg4kotW5.

questions:
* 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?

* Line 520: I was surprised not to see value propagation and temporal difference learning listed under Feedback Incorporation techniques.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730707254808

thread_type:
official_review

<thread_object>
creator: reviewer_zubc

<content>
summary:
This paper introduces ROBOTOUILLE, a challenging benchmark environment designed to evaluate the capabilities of large language model (LLM) agents in handling asynchronous, long-horizon, and multi-agent scenarios. Specifically, ROBOTOUILLE serves as a simulator for cooking various recipes, aiming to stress-test LLM agents. It utilizes domain and problem JSONs to define the Markov Decision Process (MDP) and the language description of the environment and tasks. By testing models such as gpt-4-o in both synchronous and asynchronous datasets, the authors demonstrate that agents face greater challenges in completing assigned tasks under asynchronous conditions. Additionally, the paper provides a thorough analysis of failure modes towards the end.

strengths:
1. There is a notable gap in benchmarks for planning and decision-making tasks that involve asynchronous, long-horizon scenarios. The authors effectively compare their work to relevant literature, underscoring the significance of ROBOTOUILLE. Moreover, the cooking aspect of the tasks makes them relatable and easy to understand.

2. By conducting experiments across two different settings, the authors identify key reasons for failure modes in the asynchronous decision-making context, such as the ineffectiveness of failure recovery strategies. This provides valuable directions for future research in asynchronous planning.

3. The models used in the experiments represent the latest advancements in the field, showcasing the highest capabilities of current LLMs. Despite this, the agents still struggle to consistently complete asynchronous tasks, highlighting the relevance of the research direction proposed in the paper.

4. The authors supply essential code and detailed implementation explanations, demonstrating that the experimental results are reproducible and persuasive.

weaknesses:
1. 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.

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

3. 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.

questions:
1. 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?

2. Some results in the experiments struck me as peculiar. For instance, in Table 2, the Gemini model performs significantly better than ReAct using the I/O CoT method. What accounts for this discrepancy?

3. Furthermore, in Table 3, Task 5 under synchronous conditions is more complex than Task 4, yet ReAct has a higher success rate. A similar situation occurs in the asynchronous setting. The paper does not provide a clear explanation for this phenomenon. What might be the underlying reasons?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730731519163

thread_type:
official_review

<thread_object>
creator: reviewer_qy1d

<content>
summary:
This paper proposes a benchmark to evaluate LLMs’ planning ability, focusing in particular on their asynchronous planning capabilities. Here asynchronous means that the optimal solution is not to complete sub-tasks in a sequential manner. Rather, while “waiting for” some subtasks to complete, the agent should directly focus on other tasks. The benchmark contains 30 tasks, where existing LLMs suffer to perform well even with techniques such as chain-of-thought.

strengths:
- The paper proposes a benchmark for asynchronous planning based on an environment similar to overcooked.
- The paper demonstrates that many existing LLMs fail short at planning problems that requires to consider time delays of sub-tasks.

weaknesses:
- While this paper proposes a new benchmark for certain types of LLM reasoning tasks, it does not include sufficient experimental evaluation and analysis to highlight its main challenges. Specifically, while there are many LLMs as well as LLM-based planning algorithms to tackle planning problems, the paper only experimented with one LLM and two planning algorithms (CoT and ReAct). More baselines are needed to better illustrate the challenges posed by the proposed benchmark.

- It is unclear from the paper which components of asynchronous planning make it much harder than synchronous planning. In the failure mode analysis, it is unclear to me what does it mean to attribute failure in terms of uncertainty over the MDP. Additionally, this categorization seems to be irrelevant to the key ingredient of the benchmark: *asynchronous* planning. A detailed analysis of why “asynchronous” planning is harder is needed to understand in what ways do this benchmark challenges the methods.

- While the paper highlights that the benchmark requires long-horizon planning, the horizon counted by the paper is the number of required “atomic steps”, while the agent is performing high-level actions such as move an object to a place. This size of the graphs (e.g., in Figure 11) seems to be a better measure of the “planning depth”. Given this, it seems unclear what are the additionally challenges in this benchmarks compared to for example the AsyncHow dataset mentioned in the paper.

questions:
Which components of asynchronous planning make it much harder than synchronous planning?
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces Robotouille, an asynchronous planning benchmark, designed to evaluate how well agents can handle long-horizon tasks, time delays, interruptions, and collaboration. The benchmark found that current LLM agents struggle with asynchronous tasks, with ReAct (gpt-4o) achieving 47% on synchronous tasks but only 11% on asynchronous tasks. The authors also provide a failure mode analysis, showing that LLM agents need to improve in incorporating long-horizon feedback and self-auditing their reasoning. The authors demonstrate that the complexity of asynchronous planning increases due to time delays expanding the state space.

An an asynchronous planning benchmark would significantly propel the current state of the art in the AI Agents, and the benefit to the field outweighs the paper's current weaknesses.