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

Zihuang Cai; Changjian Chen; Zhuo Tang; Chang Tang; Kenli Li

cs.MAOct 19, 2026

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

Authors: Zihuang Cai, Changjian Chen, Zhuo Tang, Chang Tang, Kenli Li

Organizations: College of Computer Science and Electronic Engineering, Hunan University · Geely Holding Group, China

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 and 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. Our code is available at https://github.com/hnu-vis/DPGP.

Figures & tables

Figure 1: Representative agent cooperation settings. (a) Cooperation-Optional Tasks, where each task can be handled independently by a single agent, but involving multiple agents can further improve results. (b) Visible-Cooperation Tasks, where certain tasks inherently demand cooperation from multiple agents and this need is known in advance. (c) Hidden-Cooperation Tasks, where the need for cooperation only becomes apparent after an agent interacts with task-related targets.

Figure 2: Overview of DPGP, showing the time-step execution loop and a step example.

C-WAH Evaluation budget: 200 s
	Task SR (%) $\uparrow$			EET (s) $\downarrow$			TGC-AUC $\uparrow$			Tokens (k) $\downarrow$
Method	All	Ord.	Coop.	All	Ord.	Coop.	All	Ord.	Coop.	All
CoELA	91.7	99.3	84.0	125.54	106.76	144.31	0.6267	0.6890	0.5644	141.32
CoTS	71.0	99.3	42.7	153.64	125.38	181.89	0.4583	0.5898	0.3267	139.71
REVECA	84.0	100.0	68.0	125.92	92.27	159.56	0.5994	0.7267	0.4720	254.62
PCE	88.0	100.0	76.0	115.61	90.07	141.15	0.6397	0.7407	0.5387	112.03

Table 1: Main results comparing DPGP with baselines on HiddenCoop (C-WAH and TDW-MAT). The best results in each column are shown in bold , and the second-best is underlined .

Figure 3: Additional analyses of execution efficiency and planning performance on C-WAH.

Figure 4: Search decisions of DPGP and the single-point variant at step 6 of C-WAH task 16.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

	C-WAH	TDW-MAT
Tasks / source pairs	100 / 50	48 / 24
Ordinary / cooperative tasks	50 / 50	24 / 24
Targets in ordinary / cooperative variants	209 / 209	103 / 103
Ordinary / cooperative target instances	304 / 114	160 / 46
Total target instances	418	206

Appendix

Table 2: Benchmark composition. The ordinary and cooperative variants of each source task have the same number of target instances.

Stage	C-WAH	TDW-MAT
Grasp	Same object; holder Close to it, supporter Close to holder or object.	Same object; both agents within 2 m of it and each other, with free capacity.
Carry	One physical holder and one occupied supporter; soft/hard separation thresholds of 2/3 scene units.	One holder and one occupied supporter; soft/hard thresholds of 2/4 m.
Release	Matching object, destination, and placement type; actual release and On / Inside relation are verified.	Matching drop intents and valid roles and distance; delivery is checked after physical release.

Appendix

Table 3: Key conditions for paired handling. C-WAH uses its native Close relation for interactions; TDW-MAT uses metric distances.

Action	Segments	Mean (s)	Median (s)	p05–p95 (s)	Charge (s)
Grasp	5,521	1.77	1.40	1.40–4.40	1.6
Open	3,479	3.60	3.00	1.80–6.60	3.2
Put in	995	1.67	1.40	1.40–4.20	2.8
Put back	1,635	3.10	1.60	1.40–6.00	2.8
Navigation	165,973	–	–	–	1 unit/s
Turn	–	–	–	–	1.0

Appendix

Table 4: C-WAH action-duration statistics and standardized charges. Duration statistics are computed over verified successful segments from scripted executions under the original pre-compiled joint-script mode and provide an empirical reference for the fixed charges applied identically to all methods. Navigation is charged by horizontal displacement; its measured per-segment mean speed is 0.97 scene units/s (median 0.85). Turn yields no qualifying segments and is fixed by convention.

Parameter	C-WAH	TDW-MAT
Maximum joint candidates	6	6
Shared sampled worlds	8	8
Rollout event cap	160	160
A* expansion cap in uncertainty evaluation	2,000	2,000
Execution action length	8	5
Completion-delay weight	0.1	0.1

Appendix

Table 5: Planning settings. These are method parameters, separate from the public benchmark configuration.

Layer	C-WAH	TDW-MAT
Internal A*	Geometric movement plus unit interaction cost.	Navigation path length; grasp and put have zero proxy cost.
Candidate rollout	Estimated calibrated seconds, joint synchronization, and estimated message cost.	Penalized navigation path length and residual unfinished-work cost.
Public EET	Actual displacement, fixed action charges, idle time, and communication critical path.	Actual joint simulator frames/250, idle time, and communication critical path.

Appendix

Table 6: Cost layers used by the method and the evaluator. Planning proxies and recorded EET have different meanings.

Method	Retained core	HiddenCoop adaptation
CoELA	Communication and planning calls, object memory, and macro-actions.	Public goals and carrying capacity are mapped to native memory. Pairing waits are bounded, and reunion responds to public distance feedback.
CoTS	Tree construction, partner review, staged scoring, and action selection.	In C-WAH, partner review is exchanged through public messages. In TDW-MAT, Alice executes the tree locally with a Bob-role critic; partner state and the final plan are exchanged through public messages. Pending reviews and pairing attempts are bounded; TDW-MAT message compression preserves content and charges all delivered characters.
PCE	Planner–Composer–Evaluator chain, reflection, and utility ordering.	Public cooperation and capacity information is mapped into the original workflow. Pairing control is released after the specified rejection boundary, and ongoing TDW-MAT actions update public memory.
REVECA	Relevance and proximity retrieval, candidate selection, and trajectory validation.	Private initial-room sharing is removed. Exact public requests may occupy a candidate slot; cooperative distance considers both agents, and ongoing TDW-MAT steps do not trigger another LLM call.

Appendix

Table 7: Retained baseline components and behaviorally relevant HiddenCoop adaptations.

Figure 5: C-WAH cooperative-task success (left) and TGC-AUC (right) under offline budget cutoffs.

Group	$B$ (s)	CoELA	CoTS	REVECA	PCE	DPGP
C-WAH (three runs per task)
All	200	91.7	71.0	84.0	88.0	99.7
	600	100.0	95.0	95.3	95.7	100.0
Ord.	200	99.3	99.3	100.0	100.0	100.0
	600	100.0	100.0	100.0	100.0	100.0
Coop.	200	84.0	42.7	68.0	76.0	99.3

Appendix

Table 8: Task success (%) at selected offline cutoffs. Group labels are shown once.

C-WAH
Method	SR loss	AUC loss	$\Delta$ EET (s)
CoELA	0.0 [0.0, 0.0]	.0488 [.0376, .0615]	46.59 [37.50, 56.52]
CoTS	10.0 [5.3, 15.3]	.1851 [.1438, .2273]	141.70 [115.10, 170.22]
REVECA	9.3 [4.7, 14.7]	.1353 [.1007, .1752]	121.41 [95.22, 151.38]
PCE	8.7 [2.7, 16.0]	.1200 [.0699, .1770]	97.25 [64.44, 136.69]
DPGP	0.0 [0.0, 0.0]	.0265 [.0211, .0322]	25.46 [19.30, 32.13]

Appendix

Table 9: Ordinary-to-cooperative paired differences with source-pair bootstrap 95% intervals. SR losses are percentage points.

	C-WAH all ( $N=264$ )		C-WAH coop. ( $N=114$ )		TDW-MAT all ( $N=12$ )
Method	EET	AUC	EET	AUC	EET	AUC
CoELA	123.97	.8779	146.59	.8537	10.20	.6826
CoTS	165.85	.8176	219.07	.7576	11.78	.6532
REVECA	122.84	.8766	163.07	.8342	11.74	.6543
PCE	113.14	.8866	143.49	.8510	9.87	.6965
DPGP	90.25	.9003	100.70	.8888	7.04	.7725

Appendix

Table 10: Five-method common-success efficiency. EET is in seconds; higher TGC-AUC is better.

	C-WAH			TDW-MAT
Method	All	Ordinary	Coop.	All	Ordinary	Coop.
CoELA	627/627	285/285	342/342	69/103	41/57	28/46
CoTS	578/627	272/285	306/342	68/103	41/57	27/46
REVECA	592/627	283/285	309/342	72/103	46/57	26/46
PCE	595/627	285/285	310/342	80/103	46/57	34/46
DPGP	627/627	285/285	342/342	82/103	49/57	33/46

Appendix

Table 11: Terminal target completion in cooperative episodes (completed/required); C-WAH pools three runs, TDW-MAT one.

C-WAH (600 s)
Method	Physical (s)	Comm. extra (s)	Messages	Tokens (k)	Calls
CoELA	129.77	.300	23.5	143.56	128.0
CoTS	162.87	33.385	42.0	162.69	125.7
REVECA	149.11	2.300	24.9	287.17	199.6
PCE	138.69	.001	1.9	123.12	72.5
DPGP	87.85	7.177	30.6	7.16	2.6

Appendix

Table 12: All-episode execution and model-use means at the collection budgets. Tokens are thousands per episode.

Group	$B$ (s)	SR (%) P/D	EET P/D	AUC P/D
All	150	95.0/69.7	93.61/126.88	.5856/.4738
	600	100.0/100.0	95.04/133.98	.8957/.8649
Ord.	150	100.0/85.3	82.31/119.49	.6360/.5129
	600	100.0/100.0	82.31/120.92	.9090/.8776
Coop.	150	90.0/54.0	104.90/134.28	.5351/.4347
	600	100.0/100.0	107.76/147.04	.8825/.8521

Appendix

Table 13: C-WAH probability/single-point comparison (P/D); EET in seconds. Each task group is shown once.

Figure 6: Task16 goal progress against recorded embodied execution time. Both versions succeed.

Multi-Agent Planning

Multi-Agent Planning coordinates multiple decision-makers to assign tasks, plan actions and paths, and resolve conflicts under shared constraints.

See all 121 papers

Certifying cooperation: a novel approach to cooperative multi-agent task generation
Sep 6, 2026Yannick Molinghen, Hugo Charels, Tom LenaertsBounded Model Checking Multi-Agent Systems
Machine Learning Group, Universit´e Libre de Bruxelles, Belgium. · AI Lab, Vrije Universiteit Brussel, Belgium. · Center for Human-Compatible AI, UC Berkeley, USA.
LLawCo: Learning Laws of Cooperation for Modeling Embodied Multi-Agent Behavior
Jun 26, 2026Qinhong Zhou, Chuang Gan, Anoop CherianMulti-Agent Coordination AI Alignment
University of Massachusetts Amherst, USA. · 2Mitsubishi Electric Research Laboratories (MERL), USA.
CoCoBench: A Cooperative Coordination Benchmark for Embodied Multi-Agent Task Planning
Aug 28, 2026Yang Chen, Ye-Xin Xie, Lirong Che +8Multi-Agent Coordination AI Agent Benchmarks
Nanjing University · AgiBot · Tsinghua University

Sep 6, 2026J/K move · Enter open · S save

Certifying cooperation: a novel approach to cooperative multi-agent task generation

Yannick Molinghen, Hugo Charels, Tom Lenaerts

Machine Learning Group, Universit´e Libre de Bruxelles, Belgium. · AI Lab, Vrije Universiteit Brussel, Belgium. · Center for Human-Compatible AI, UC Berkeley, USA.

Bounded Model Checking Multi-Agent Systems Cooperative MARL

Open paper AskPDF arXiv

A shared reward gives agents a common objective, but leaves open when, how and even whether they must cooperate to succeed. We address these questions in the Laser Learning Environment, a multi-agent path-finding environment where cooperation materializes as one agent blocking a laser to let a teammate pass safely. We represent these interactions through temporal cooperation graphs whose timed edges connect helpers to beneficiaries, define six cooperation profiles as overlapping graph predicates, and prove that every cooperative trajectory satisfies at least one. By encoding the environment dynamics and profile predicates as propositional formulae, we distinguish tasks that admit}a profile in some winning trajectory from those that require it in every winning trajectory within a specified horizon. Used as filters, these queries turn a random layout sampler into a generator of tasks with certified cooperation requirements. Experiments with five multi-agent reinforcement learning algorithms show that training diversity improves joint success on unseen tasks when cooperation-free solutions exist. When cooperation is required, greater diversity improves individual-agent exits, but joint success remains near zero. Across five profile-certified pools, final exit rates averaged over algorithms separate the pools into four statistically distinguishable levels but this ordering primarily reflects partial completion: policies collect rewards for individual exits but rarely exhibit the profile required for joint success. Our framework exposes this gap between rewarded partial completion and realized cooperation by certifying what cooperation successful completion requires and using temporal cooperation graphs to reveal what policies exhibit.

Abstract

Multi-Agent Planning

Explore similar work

Certifying cooperation: a novel approach to cooperative multi-agent task generation

LLawCo: Learning Laws of Cooperation for Modeling Embodied Multi-Agent Behavior

CoCoBench: A Cooperative Coordination Benchmark for Embodied Multi-Agent Task Planning