acceptodds
Under review as a conference paper at ICLR 2027

Discovery-Probability Graph Planning for Embodied Agents in Tasks with Hidden Cooperation Requirements

Abstract

Embodied agents are increasingly capable of perceiving, planning, and acting autonomously in dynamic environments, demonstrating strong performance on complex cooperative tasks. Recent advances typically assume that cooperative tasks are known in advance. In real-world applications, however, hidden-cooperation tasks are more common: the need for cooperation only becomes apparent after an agent observes or interacts with task-related targets. In this paper, we first present HiddenCoop, a benchmark for effectively evaluating agent cooperation in hidden-cooperation tasks. We further propose Discovery-Probability Graph Planning (DPGP), a method for enabling effective agent cooperation in such tasks. At the core of DPGP is a discovery-probability graph that encodes the probability distribution over the number and locations of task-related targets, facilitating effective and efficient information exchange among agents. A search algorithm is then used to derive action plans that minimize expected costs. Experiments show that DPGP achieves cooperative-task success rates of 99.3% on C-WAH and 58.3% on TDW-MAT, surpassing all compared baselines, while also reducing overall embodied execution time and substantially lowering LLM token usage.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Large Language Models, Multi-Agent Cooperation, Embodied Decision Making

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_8TqiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces HiddenCoop, a benchmark in which cooperation requirements are initially hidden and become known through valid interactions. It proposes Discovery-Probability Graph Planning, which separates confirmed facts from beliefs about undiscovered resource counts and locations. Exploration and transport candidates are evaluated on shared sampled worlds using deterministic joint search, and plans are revised as observations and messages arrive. Evaluation uses 50 matched ordinary/cooperative task pairs in C-WAH and 24 in TDW-MAT, with three runs per C-WAH task and one per TDW-MAT task. Cooperative-task success reaches 99.3% and 58.3% at the respective 200-second and 20-second embodied execution budgets. Additional analyses cover budget cutoffs, common-success efficiency, target completion, and model usage.

Critical strengths
  1. Hidden cooperation is defined through an explicit information and execution protocol. The distinction between confirmed facts, unknown requirements, and sampled hypotheses makes the task reproducible in principle and avoids treating hypothetical discoveries as observed state. This is a useful contribution to evaluating cooperation under partial observability.

  2. The full-system evaluation is comparatively careful. Matched ordinary/cooperative tasks, multiple budget cutoffs, common-success comparisons, and separate goal-level analyses help distinguish eventual completion from execution efficiency. The strong C-WAH results and low recorded model usage support the value of the complete framework within the stated interface. EET explicitly excludes model and planning wall-clock time, so the efficiency evidence should be interpreted within that definition.

Critical weaknesses
  1. The central probability mechanism is not isolated by a matched ablation. The appendix explicitly treats the single-point comparison as a contrast between system versions, and the illustrative traces differ in model-call counts and other behavior. The 29.1% EET reduction therefore cannot be attributed to the probability representation alone. The full-system comparison remains useful, but the specific methodological advance over alternative discovery and planning strategies is less firmly established.

  2. The strength of the TDW-MAT advantage is uncertain. Cooperative success of 58.3% versus PCE's 45.8% corresponds to 14/24 versus 11/24 tasks in a single run. Overall success is tied at 64.6%, and ordinary-task success is lower. The reported source-pair bootstrap principally estimates ordinary-to-cooperative changes, not the paired difference between methods. This limits the claim of robust superiority across both environments, although it does not negate the stronger C-WAH evidence.

Questions for authors
  1. Clarification of the probability comparison. What are all behaviorally relevant differences between the probability and single-point versions, including candidate generation, replanning triggers, semantic requests, and execution? Is there an existing comparison in which these components and budgets are held fixed and only the belief representation and its evaluation change?

  2. Clarification of the TDW-MAT results. Can you provide a paired success/failure cross-tabulation for DPGP versus PCE and an interval for their cooperative-task success difference? Are additional runs available, or should this result be interpreted strictly as a descriptive comparison on the single fixed run set?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 8Tqi — Part 1/2

Dear Reviewer 8Tqi, we thank you for your time, effort, and insightful comments. Please find our responses below.

1. Differences from the single-point version and additional component ablations (W1, Q1)

Thanks for pointing this out. We acknowledge that our previous ablation did not clearly isolate the influence of the probability mechanism. The single-point version requests definite target locations from the LLM, whereas DPGP uses LLM-derived semantic support to construct count and location distributions. The original 29.1% EET reduction compares the complete probability-based and single-point planners; the new ablations examine the three components separately.

We examine three components of probability-based planning: probability correction (P), multi-scene sampling (S), and joint candidate evaluation (E). The table below compares DPGP, the original single-point version, and the three component replacements.

VersionProbability correction (P)Multi-scene sampling (S)Joint candidate evaluation (E)
DPGP√√√
Single-point version×LLM-predicted sceneJoint A*
Replace P×√√
Replace S√Most probable scene√
Replace E√√Per-scene A* + voting

We evaluated the three replacements on the same C-WAH tasks with the same seeds and environment execution budgets. All three retain DPGP's communication, memory update, replanning triggers, and execution procedures, while changing the specified component.

  • Replace P: Retain the semantic prior, exclusion of inspected locations, and subtraction of discovered objects, while removing likelihood-based count correction and inspection-based location-weight correction.
  • Replace S: Replace the eight sampled scenes with the single scene of highest joint probability.
  • Replace E: Retain multi-scene sampling, run bounded joint A* search separately in each scene, and vote on the executable joint action sequences.

The following results report mean EET (s) for DPGP and the three replacements at six execution budgets.

Method100 s200 s300 s400 s500 s600 s
DPGP84.58694.89695.03695.03695.03695.036
Replace P87.528102.149102.469102.469102.469102.469
Replace S89.655105.984106.344106.344106.344106.344
Replace E89.409108.441108.774109.107109.441109.774
AuthorsOpenReview ↗

Response to Reviewer 8Tqi — Part 2/2

2. Additional TDW-MAT experiments (W2, Q2)

We added two full runs for each method, DPGP and PCE, to the original run. We evaluated both methods on the same 48 tasks in all three runs, yielding 144 episodes per method. We used different random seeds across runs. Within each run, both methods used the same environment settings and seed for each task. The results below use the 20 s budget. Overall, DPGP achieved higher task success (68.8% vs. 63.2%), lower mean EET (12.09 vs. 14.34 s), and higher TGC-AUC (0.6325 vs. 0.5474) than PCE.

&\text{Task SR (\\%)}\uparrow&\text{EET (s)}\downarrow&\text{TGC-AUC}\uparrow&\text{Tokens (k)}\downarrow\\\\ \hline \begin{array}{l}\text{Method}\\\\\text{PCE}\\\\\text{DPGP}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\63.2&\mathbf{84.7}&41.7\\\\\mathbf{68.8}&76.4&\mathbf{61.1}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\14.34&11.40&17.27\\\\\mathbf{12.09}&\mathbf{10.03}&\mathbf{14.16}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\0.5474&0.6431&0.4518\\\\\mathbf{0.6325}&\mathbf{0.6929}&\mathbf{0.5721}\end{array}& \begin{array}{c}\text{All}\\\\1128.53\\\\\mathbf{1.41}\end{array} \end{array}$$ On cooperative tasks, DPGP succeeded in 44/72 episodes (61.1%) and PCE in 30/72 (41.7%), a difference of 19.44 percentage points. Using an episode-level normal approximation for the paired success-rate difference across the 72 episode pairs, we obtained a 95% confidence interval of [4.22, 34.67] percentage points. The paired cooperative-task outcomes are shown by run below. |**Run**|**Both succeeded**|**Only DPGP succeeded**|**Only PCE succeeded**|**Both failed**|**Pairs**| |:---|:---:|:---:|:---:|:---:|:---:| |run_0|7|7|4|6|24| |run_1|7|8|3|6|24| |run_2|6|9|3|6|24| |Total|20|24|10|18|72|
Reviewer_fEd9OpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper addresses hidden-cooperation tasks, in which whether cooperation is required is not given in advance and becomes known only after an agent interacts with the target object. The paper claims two contributions. The first is HiddenCoop, a benchmark that extends C-WAH and TDW-MAT with matched ordinary/cooperative task pairs: 50 pairs for C-WAH and 24 pairs for TDW-MAT. The second is Discovery-Probability Graph Planning (DPGP), in which each agent maintains a fact graph of confirmed facts and a discovery belief over the number and locations of targets that have not yet been discovered. The prior of this belief is derived from the LLM's semantic knowledge and is updated with observations. Agents can share information through graph fusion. The authors report cooperative-task success rates of 99.3% on C-WAH and 58.3% on TDW-MAT. They also report lower embodied execution time (EET) and lower LLM token usage.

Critical strengths
  • A setting in which the need for cooperation becomes known only after interaction is a meaningful problem for real-world multi-agent embodied tasks. The existing C-WAH and TDW-MAT benchmarks do not cover this setting.
Critical weaknesses
  1. In Dec-POMDP-style problem formulations and in prior work such as CoELA, communication is a costly action. Sending a message is an action taken instead of a physical action, and it consumes one step. This paper only prohibits "starting a new physical action" in a step in which a message is sent. Ongoing actions therefore continue while the message is being sent. These include navigation and, in TDW-MAT, grasp/drop actions that span multiple steps. The authors state this intent explicitly: "charging each message one full action step would overstate its cost". As a result, memory fusion, an ongoing high-level action, and communication are all performed within a single step. Fig. 2 likewise shows receiving the partner's state, memory fusion, graph update, plan evaluation, and sending the action reply as all occurring within one step. Communicating while moving, i.e., communicating during an action, is a combination that the problem definitions of the existing baselines do not allow. Information transfer through communication has no cost in terms of steps. Communication that can be performed concurrently with an action cannot be called a cost. The replanning triggers include "relevant new evidence" and "action boundary," and no rule limits their frequency. During exploration, a new observation can occur at every step. If such events keep occurring, memory fusion and replanning can therefore occur at every step. This means that even while executing an action that spans multiple steps, the two agents' memories remain effectively synchronized and the validity of the action is checked continuously. Planning computation is charged neither in steps nor in EET. This setting is not valid as a decentralized cooperation problem.

  2. Each agent sends its fact graph, which contains observed objects, explored regions, confirmed cooperation requirements, and execution status, to its partner. The planning agent merges the received graph with its own fact graph, decides the actions of both agents, and sends the partner's action to the partner. Given this fusion, the agents cannot be said to act on their own histories. The structure is not decentralized control; it is one agent planning centrally over shared observations. The paper nevertheless claims that the benchmark addresses "partial observability and decentralized control." Decentralized control is difficult because agents must act on their own histories without sharing observations with one another (Bernstein et al., 2002[1]). If observations can be shared through cost-free communication, the problem reduces to a centralized POMDP (Pynadath & Tambe, 2002[2]; Goldman & Zilberstein, 2004[3]). The setting in this paper is exactly this case, and fusion incurs no separate step cost. The problem formulation in Sec. 3.1 provides neither a Dec-POMDP-style definition (states, observations, actions, and objective) nor a definition that treats communication as part of the problem (its cost, latency, and relation to actions). The communication rules appear only in the appendix (A.4). The authors should revisit the problem definitions in the baseline papers and in Bernstein et al. (2002)[1], and reconsider what decentralized control means in this field.

  3. C-WAH and TDW-MAT were originally evaluated in steps and frames, respectively. This paper replaces these units with EET (in seconds), which the authors newly define, and does not report results in terms of step counts. Tables 1 and 12 both report seconds; step numbers appear only in the case study. EET computes the duration of a step as the maximum of its physical time and its message time (Eq. 8). Message time is therefore absorbed by the physical action time of the same step and is not counted separately. DPGP sends 30.6 messages per episode on C-WAH and 98.8 on TDW-MAT, yet the added communication time is only 7.177 s and 0.590 s, respectively. Communication cost enters only through transmission rates chosen by the authors: 2,500 codepoints/s for C-WAH and 125,000 codepoints/s for TDW-MAT, with a maximum of 12,000 codepoints per message. No justification is given for the 50-fold difference between the two environments. It is difficult to accept using C-WAH and TDW-MAT as the problem environments while evaluating with EET. The authors should report step-based results under the original rule, in which sending a message costs one action step.

  4. For the reasons given in points 1–3, the comparison with CoELA and the other baselines is not meaningful. The baselines are decentralized methods designed under the assumption that communication consumes an action step. They do not receive DPGP's fused memory; more precisely, they have no memory-aggregation mechanism equivalent to memory fusion. The authors state that all methods use the same interface, but the baselines' decision structures cannot use the combination of communicating during an action. For example, the REVECA adapter does not call the LLM during ongoing steps in TDW-MAT (Table 7). DPGP is the only method designed around this protocol. In hidden cooperation, a method that fuses memory is expected to outperform methods that do not. Existing methods do not fuse memory not because they cannot implement it, but because they define the problem as a decentralized setting in which communication has a cost. The current comparison measures a difference in information structure, not the superiority of the method.

  5. The discovery-probability graph models only the number and locations of targets. Objects whose cooperation requirement has not been confirmed are treated as ordinary during planning, and the LLM does not predict cooperation requirements. What the title presents as handling hidden cooperation is therefore, in practice, "replanning after confirmation + memory fusion + joint A*." This is performed by fusion and centralized planning, not by the proposed graph. DPGP also achieves the lowest EET on ordinary tasks, which involve no hidden cooperation (C-WAH: 82.31 s vs. 90.07 s for PCE, Table 1). This indicates that a substantial part of the gain comes from an exploration and transport planner unrelated to hidden cooperation. For the only ablation, the single-point comparison, the authors themselves state that it is a "system-version contrast" and "not otherwise identical." There are no experiments with DPGP without memory fusion, nor with baselines given the same fused memory. There is therefore no basis for concluding that the discovery-probability graph contributes to the results.

[1] Bernstein, Daniel S., et al. "The complexity of decentralized control of Markov decision processes." Mathematics of operations research 27.4 (2002): 819-840. [2] Pynadath, David V., and Milind Tambe. "The communicative multiagent team decision problem: Analyzing teamwork theories and models." Journal of artificial intelligence research 16 (2002): 389-423. [3] Goldman, Claudia V., and Shlomo Zilberstein. "Decentralized control of cooperative systems: Categorization and complexity analysis." Journal of artificial intelligence research 22 (2004): 143-174.

Questions for authors

See weaknesses. If authors can properly address my concerns, I will raise my point.

7 comments
AuthorsOpenReview ↗

Response to Reviewer fEd9 — Part 1/3

Dear Reviewer fEd9, we thank you for your time, effort, and insightful comments.

1. Communication mode and message cost (W1, W2, W3, W4)

Communication mode. HiddenCoop's communication_mode has two settings. In exclusive_action, an agent may send a message or execute a physical action, but not both in one step. In parallel_side_channel, it can do both in the same step. Messages arrive in the recipient's next observation in either mode. In our experiments, all methods used exclusive_action mode. TDW-MAT blocks sending while the agent continues to navigate, grasp, or drop an object. Across all trajectories, no agent sent a message while executing a physical action.

Message cost. In the original C-WAH, a message of up to 500 characters costs one step. TDW-MAT allows 500 characters per frame [1], so any message up to that length fits in one frame. HiddenCoop caps each message at 12,000 characters. At fixed rate rr, transmitting LL characters takes L/rL/r, ignoring fixed latency and bandwidth fluctuations. TDW-MAT's default 250 frames/s gives 125,000 characters/s. For consistent timing, HiddenCoop uses the same 500 characters/frame reference for C-WAH, giving 2,500 characters/s at its default 5 frames/s. Equation (8) measures elapsed team time. Only transmission beyond concurrent physical execution adds to EET. Even when the other agent moves, sending still uses the sender's action for that step.

2. Planning frequency and computational cost (W1)

DPGP can request planning on target discovery, confirmation of a cooperation requirement, search completion, action exhaustion, or execution failure. With no minimum interval, consecutive events can trigger new requests. The following statistics count DPGP’s planning steps over 300 C-WAH episodes at 600 s and 144 TDW-MAT episodes at 20 s. For TDW-MAT, they also report the frames advanced during those steps (three runs of 48 tasks).

EnvironmentEpisodesTotal steps / framesPlanning steps / framesShare (steps / frames)
C-WAH30024,1503,83515.9%
TDW-MAT144177,744 / 399,6497,946 / 4,2654.47% / 1.07%

Planning time, LLM call time, and token use measure system overhead. Steps, frames, and EET measure environment execution. On the same C-WAH tasks, DPGP averaged 77.25 s of planning and 5.84 s of LLM calls per task. The four baselines averaged 236.23–545.40 s of LLM calls per task.

References

[1] Hongxin Zhang, Weihua Du, Jiaming Shan, Qinhong Zhou, Yilun Du, Joshua B. Tenenbaum, Tianmin Shu, and Chuang Gan. Building cooperative embodied agents modularly with large language models. In International Conference on Learning Representations, volume 2024, pp. 19373–19401, 2024.

AuthorsOpenReview ↗

Response to Reviewer fEd9 — Part 2/3

3. Local observations, explicit communication, and joint planning in DPGP (W1, W2, W4, W5)

As you note, one agent plans for both in each DPGP round. In a classical Dec-POMDP, each agent acts on its own observation history [2]. With explicit communication, delivered messages can also inform local decisions [4]. The centralized-POMDP reduction you cite applies when both agents can exchange all local observations at no cost and know the joint observation history before choosing actions [3]. In HiddenCoop, each agent acts only on its observations, execution feedback, and delivered messages, subject to the action cost and delivery timing in point 1.

In a completed round, the requesting agent sends an update at step tt. At t+1t+1, the planning agent merges it with local observations in its own task memory, plans for both agents, and sends back the assignment. Both start at t+2t+2. This is joint planning by one agent using locally available information, not direct access to the partner's memory. Each agent maintains its own task memory and, on TDW-MAT, its own visual and navigation maps. Section 3.1 will distinguish the task (local observations and costly communication) from the method (joint planning and local execution), specifying states, observations, actions, message timing and costs, and the shared objective under the task budget.

4. Motivation for EET (W3, W4)

We report both control steps and team execution time (EET). In C-WAH, grasping an object and opening a container each take one step, yet 5,521 simulated grasps averaged 1.77 s and 3,479 openings averaged 3.60 s. Steps alone miss differences in action duration and message transmission time, which varies with length. EET captures these costs, consistent with TDW-MAT measuring physical time in frames. The following comparisons use common-success episodes under HiddenCoop’s experimental communication rules.

Among the 264 C-WAH episodes completed by all five methods within a 600 s budget, PCE averaged fewer steps than DPGP (66.58 vs. 76.15). DPGP used more message-only steps but spent 29.98 s less on physical execution. Including communication and idle time, its mean EET was still 22.89 s lower. On the 114 cooperative episodes, mean steps were almost equal (PCE 86.25, DPGP 86.30), but EET was 143.49 vs. 100.70 s.

MethodEET (s)Physical time (s)Comm. time (s)Comm. extra (s)Total stepsPhysical stepsMessage-only stepsMessages
CoELA123.97123.681.1430.29284.3079.674.6323.27
CoTS165.85138.3728.25727.480114.9085.8529.0536.38
REVECA122.84120.982.7591.86181.7772.389.3920.62
PCE113.14113.140.0610.00166.5866.550.041.86
DPGP90.2583.1610.0677.08376.1557.1119.0230.39

Across three full TDW-MAT runs at the 20 s budget, DPGP and PCE shared 70 successes matched by task and run (50 ordinary, 20 cooperative). DPGP averaged fewer frames and lower EET.

MethodEET (s)Physical time (s)Comm. time (s)Comm. extra (s)Total framesTotal stepsPhysical stepsMessage-only stepsMessages
PCE10.8510.810.01210.00772,702.561,015.54999.238.7316.51
DPGP7.627.390.40560.22301,848.23630.49617.8911.7633.97

References

[2] Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The Complexity of Decentralized Control of Markov Decision Processes. Mathematics of Operations Research, 27(4), 819–840, 2002.

[3] David V. Pynadath and Milind Tambe. The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models. Journal of Artificial Intelligence Research, 16, 389–423, 2002.

[4] Claudia V. Goldman and Shlomo Zilberstein. Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis. Journal of Artificial Intelligence Research, 22, 143–174, 2004.

AuthorsOpenReview ↗

Response to Reviewer fEd9 — Part 3/3

5. Fairness of baseline comparisons (W4, W5)

Following PCE [5], all methods use the same tasks, observation interfaces, action constraints, communication rates, and message caps. CoELA retains memory- and dialogue-based macro-actions; CoTS, tree search and peer evaluation; REVECA, candidate retrieval and trajectory validation; PCE, planning, hypothesis generation, and evaluation. REVECA adds confirmed cooperation requests to candidates and continues ongoing TDW-MAT actions without a new LLM call.

At 600 s, all baselines completed 150/150 ordinary C-WAH episodes. Across three TDW-MAT runs, PCE completed 61/72 and DPGP 55/72 ordinary episodes. Baselines also use received messages in reasoning: CoELA and PCE include recent dialogue in their prompts. DPGP instead integrates communicated observations into structured local task memory for planning. The difference is how messages are processed and used, not whether messages are available. Joint planning uses only local observations and delivered messages under the same protocol. All component ablations retain DPGP's communication and memory update procedures.

6. Discovery-probability graph and component ablations (W5)

The graph guides where to search and how to divide search and transport. It models undiscovered target counts and locations on C-WAH. On TDW-MAT, required counts are public, so it mainly estimates locations. Objects are treated as ordinary until valid interaction reveals a cooperation requirement and triggers replanning. Even on ordinary C-WAH tasks, mean EET was 82.31 s for DPGP vs. 90.07 s for PCE.

The original 29.1% EET reduction compares the complete probability-based and single-point planners. To examine the contribution of probability-based planning while retaining DPGP’s communication and memory update procedures, we evaluated three component replacements: probability correction (P), multi-scene sampling (S), and joint candidate evaluation (E). The table below summarizes their differences.

VersionProbability correction (P)Multi-scene sampling (S)Joint candidate evaluation (E)
DPGP√√√
Single-point version×LLM-predicted sceneJoint A*
Replace P×√√
Replace S√Most probable scene√
Replace E√√Per-scene A* + voting

We evaluated the three replacements on the same C-WAH tasks with the same seeds and environment execution budgets. All three retain DPGP's communication, memory update, replanning triggers, and execution procedures, while changing the specified component.

  • Replace P: Retain the semantic prior, exclusion of inspected locations, and subtraction of discovered objects, while removing likelihood-based count correction and inspection-based location-weight correction.
  • Replace S: Replace the eight sampled scenes with the single scene of highest joint probability.
  • Replace E: Retain multi-scene sampling, run bounded joint A* search separately in each scene, and vote on the executable joint action sequences.

The following results report mean EET (s) for DPGP and the three replacements at six execution budgets.

Method100 s200 s300 s400 s500 s600 s
DPGP84.58694.89695.03695.03695.03695.036
Replace P87.528102.149102.469102.469102.469102.469
Replace S89.655105.984106.344106.344106.344106.344
Replace E89.409108.441108.774109.107109.441109.774

References

[5] SeungWon Seo, SooBin Lim, SeongRae Noh, Haneul Kim, and HyeongYeop Kang. From assumptions to actions: Turning LLM reasoning into uncertainty-aware planning for embodied agents. In C. Vondrick, B. Hariharan, C. Raffel, L. Pinto, D. Yang, and A. Faust (eds.), International Conference on Learning Representations, volume 2026, pp. 19927–19956, 2026.

Reviewer_xTBSOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces an interface on top of C-WAH and TDW-MAT, called HiddenCoop, which adds cooperative task constraints to underlying episodes. Two agents work together to solve pick-and-place kind of tasks with added constraint that some of the tasks need both the agents. The paper also introduces an algorithm called Discovery-Probabiity Graph Planning (DPGP) which uses symbolic information about the environment to create a probability graph of where task relevant objects may be found which guides the discovery and communication between agents. Communication is explicit and costs a step in C-WAH and nothing until message is <500 chars in TDW-MAT. C-WAH has symbolic solving only while TDW-MAT has an embodied component. DPGP matches or mostly beats baselines on this new HiddenCoop version with an impressively low token count for LLM usage. The evaluation is done across task success rate, earliness of accumulating solved subgoals and embodied execution time although the last one only pertains to TDW-MAT.

Critical strengths
  • Region based division is interesting for DPGP
  • Cooperative hidden constraints is novel
  • The prompts signal a strict structure to the problem which manifests as an impressively low token count overall while solving the problem just as well or better than baselines
Critical weaknesses
  • TDW-MAT is the more interesting benchmark with embodied execution yet has lower reps and only 24 episodes to begin with
  • Common-success subset is crippled due to bad performance of the lowest-performing baseline resulting in only 2 cooperative episodes to analyze solutions against each other. This is not enough to extrapolate any claims. This should maybe be capped to top-N so the subset has more signal
  • C-WAH is a symbolic-only benchmark with hidden objects being the interesting thing about it. It seems pretty saturated to be a good measure in the reported results
Questions for authors
  • The region based division is very interesting. How did you divide this up? What is a region? Is there any trade-off to region being larger or smaller as a unit?
  • How did you address line-of-sight between regions? A region may be more useful not because it may have objects but because it exposes more "other regions" to your line-of-sight. A very embodied concept.
  • Could you redo common-success subset analysis. As is I find it very limited to draw conclusions. Your metrics make sense but low seeding, reps and especially fewer embodied-x-cooperative episodes to analyse is problematic.
  • Example rollouts of episodes will be helpful to understand your approach better
4 comments
AuthorsOpenReview ↗

Response to Reviewer xTBS — Part 1/2

Dear Reviewer xTBS, we thank you for your time, effort, and insightful comments. Please find our responses below.

1. Additional TDW-MAT runs (W1)

Thanks for pointing this out. We evaluated our method on TDW-MAT with three runs. Due to time constraints, we only compared our method with the most competitive baseline, PCE, using the same three-run setup. We used different random seeds across runs. Within each run, both methods used the same environmental settings and seed for each task. The results below summarize 144 episodes per method under the 20 s budget: three runs of 48 tasks, with 24 ordinary and 24 cooperative tasks per run. As we can see, the conclusion remains the same: compared with PCE, our method has higher task success and TGC-AUC and lower EET on cooperative tasks, together with lower overall token usage.

&\text{Task SR (\\%)}\uparrow&\text{EET (s)}\downarrow&\text{TGC-AUC}\uparrow&\text{Tokens (k)}\downarrow\\\\ \hline \begin{array}{l}\text{Method}\\\\\text{PCE}\\\\\text{DPGP}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\63.2&\mathbf{84.7}&41.7\\\\\mathbf{68.8}&76.4&\mathbf{61.1}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\14.34&11.40&17.27\\\\\mathbf{12.09}&\mathbf{10.03}&\mathbf{14.16}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\0.5474&0.6431&0.4518\\\\\mathbf{0.6325}&\mathbf{0.6929}&\mathbf{0.5721}\end{array}& \begin{array}{c}\text{All}\\\\1128.53\\\\\mathbf{1.41}\end{array} \end{array}$$ **2. Common-success subset analysis (W2, Q3)** We agree that a common-success subset of only two cooperative episodes is too small to support a reliable conclusion. Using the original single TDW-MAT run at the 20 s budget, we conducted a pairwise analysis comparing DPGP with each baseline on the episodes that both methods completed successfully. The table below reports mean EET (s). DPGP achieved a lower mean EET than each baseline on the corresponding subset. |**Task type**|**Metric**|**CoELA**|**CoTS**|**REVECA**|**PCE**| |---|---|---|---|---|---| |**All**|Common successes|17|17|19|22| ||Baseline EET (s)|10.81|13.01|11.98|11.44| ||DPGP EET (s)|**7.24**|**8.00**|**7.25**|**7.57**| |**Ord.**|Common successes|13|13|12|15| ||Baseline EET (s)|9.90|11.97|10.21|10.14| ||DPGP EET (s)|**6.28**|**6.99**|**6.25**|**6.68**| |**Coop.**|Common successes|4|4|7|7| ||Baseline EET (s)|13.76|16.41|15.02|14.21| ||DPGP EET (s)|**10.37**|**11.26**|**8.96**|**9.49**| **3. Near-saturation on C-WAH (W3)** Task success rate is not the main metric for the original C-WAH benchmark, as it can approach 100% with a sufficiently large time budget. Therefore, studies such as CoELA [1] and PCE [2] also compare efficiency metrics, such as the number of steps required to complete successful tasks. On the C-WAH-based tasks in our HiddenCoop benchmark, optimal trajectories can achieve a mean EET below 73.37 s. However, under a 600 s execution-time budget, the current SOTA method (our DPGP) only achieves a mean EET of 95.04 s, with substantial room for improvement. **References** [1] Hongxin Zhang, Weihua Du, Jiaming Shan, Qinhong Zhou, Yilun Du, Joshua B. Tenenbaum, Tianmin Shu, and Chuang Gan. Building cooperative embodied agents modularly with large language models. In International Conference on Learning Representations, volume 2024, pp. 19373–19401, 2024. [2] SeungWon Seo, SooBin Lim, SeongRae Noh, Haneul Kim, and HyeongYeop Kang. From assumptions to actions: Turning LLM reasoning into uncertainty-aware planning for embodied agents. In C. Vondrick, B. Hariharan, C. Raffel, L. Pinto, D. Yang, and A. Faust (eds.), International Conference on Learning Representations, volume 2026, pp. 19927–19956, 2026.
AuthorsOpenReview ↗

Response to Reviewer xTBS — Part 2/2

4. Region definition and partitioning (Q1)

Before entering a C-WAH room, the model distinguishes the area visible on entry from containers that may conceal objects. After entry, each discovered and uninspected container becomes a separate region unless it is a delivery destination. On TDW-MAT, the model estimates target locations by environment-defined room. After entry, the agent scans from a specific viewpoint. Using rooms lets the planner compare search destinations and travel costs. A finer partition could capture differences in occlusion between viewpoints within a room but would add locations to evaluate.

5. Line of sight between regions (Q2)

We agree that a region’s value depends both on the likelihood that it contains a target object and on the opportunities it creates to discover target objects in other regions. Visiting a region that brings other regions into view can therefore be valuable even if the region itself is unlikely to contain a target. In Discovery-Probability Graph Planning (DPGP), we consider the downstream value of exploration at the room level through multi-step joint planning. We evaluate joint action candidates by their estimated planning costs across sampled scenes, including subsequent exploration and transport and a penalty for unfinished goals. This lookahead can favor a region when exploring it enables a lower-cost sequence of subsequent exploration and transport.

6. Example episode rollout (Q4)

Thanks for your suggestion. In C-WAH task 33 (run_id=2), the goal was to place three forks and one plate in the dishwasher. At step 3, Agent 0 was in the living room and Agent 1 in the bathroom. The step 6 plan had Agent 0 enter the kitchen, approach fork 385, and grasp it, while Agent 1 would approach and grasp fork 386. Neither knew that carrying the forks required cooperation. At step 10, Agent 1 tried to grasp fork 386 alone and received feedback that both agents were needed. At step 13, both agents jointly grasped fork 385. The revised appendix will include the full 76-step rollout.

StepAgent 0Agent 1Notes
3[walktowards] <kitchen> (56)[walktowards] <kitchen> (56)
4[walktowards] <kitchen> (56)[walktowards] <kitchen> (56)Agent 1 reaches the kitchen.
5[walktowards] <kitchen> (56)Send MessageAgent 1 first sees forks 385 and 386 and requests a plan. Agent 0 continues moving.
6Send MessageNoneAgent 0 replans from the received observation and replies. Agent 1 waits.
7[walktowards] <kitchen> (56)[walktowards] <cutleryfork> (386)
8[walktowards] <cutleryfork> (385)[walktowards] <cutleryfork> (386)

Thanks for your responses. Follow-ups:

  1. Thanks for the multi-run table. It makes it clear that DPGP's success rate drops on ordinary tasks compared to PCE. Can you discuss this trade-off? There is something in your algorithm specifically to support cooperation which does not work as well for ordinary tasks.
  2. It seems like your EET is only computer for successful tasks? If yes, please make that clear.
  3. LLM token gap is quite large which is notable. I do wonder how does DPGP fair if LLM "priors" response is replaced with statistically mined common-sense priors? E.g. forks are always in the kitchen. That would help qualify if the token reduction is really useful or a decorative reduction.

For now I keep my rating as is.

AuthorsOpenReview ↗

Response to Reviewer xTBS

Dear Reviewer xTBS, thank you for reading our responses further. We address your three follow-up questions below.

1. Performance on ordinary and cooperative tasks

PCE indeed achieves higher task and subgoal success rates on ordinary tasks, while DPGP achieves higher success rates on cooperative tasks and across all tasks. The table below reports the results of three complete TDW-MAT runs, with 144 episodes per method: 72 ordinary and 72 cooperative episodes.

&\text{Task SR (\\%)}\uparrow&\text{Subgoal SR (\\%)}\uparrow\\\\ \hline \begin{array}{l}\text{Method}\\\\\text{PCE}\\\\\text{DPGP}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\63.2&\mathbf{84.7}&41.7\\\\\mathbf{68.8}&76.4&\mathbf{61.1}\end{array}& \begin{array}{ccc}\text{All}&\text{Ord.}&\text{Coop.}\\\\83.7&\mathbf{93.5}&73.8\\\\\mathbf{85.1}&90.3&\mathbf{79.9}\end{array} \end{array}$$ DPGP uses the same search and transport planning process for both task types, treating objects with unconfirmed cooperation requirements as ordinary until these requirements are revealed through interaction. Discovering new objects, confirming cooperation requirements, or encountering action execution failures triggers replanning. DPGP uses the updated observations and execution status, together with the discovery-probability graph's estimates of the remaining target locations, to revise both agents' search and transport plans. This design therefore responds to new situations during task execution, of which confirming a cooperation requirement is one example. The results show differences in performance between the two task types, but do not by themselves establish that a particular cooperation component causes the lower success rate on ordinary tasks. **2. Scope of EET statistics** EET is recorded for all episodes, including both successes and failures. For failed episodes, EET is the accumulated execution time up to termination. In the full experimental results, the calculation of EET does not exclude failures. To eliminate the effect of the maximum time budget on failed episodes and to compare the execution time required by both methods to complete the same tasks, we additionally compare EET on the common-success subset in Figure 3(a). Thus, the common-success analysis is restricted to successful episodes. **3. LLM priors and statistical commonsense priors** Thank you for suggesting this alternative. Statistical commonsense priors extracted from separate training scenes or external data can serve as another source of priors for the discovery-probability graph. DPGP's planning process uses probability distributions and does not require these priors to be generated by an LLM. The current implementation uses an LLM to provide relative support for candidate locations based on target categories, candidate regions, and observed information, which is then used together with observations in subsequent planning. A commonsense association such as "forks are in the kitchen" indicates a location tendency rather than a deterministic rule that holds for every task instance, so the method retains nonzero probability for other candidate locations. The reported token gap reflects the role of the LLM in our framework: the LLM provides semantic priors, while candidate evaluation and action planning are performed programmatically. This result shows that the current implementation can complete tasks with few online LLM calls, but does not by itself establish that LLM priors outperform statistical priors.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.