PACT: Plan-Augmented Coordination via Trace-Graphs for Dynamic Multi-Agent Combinatorial Optimization

Xiao Zhou; Alex Schutz; Victor-Alexandru Darvariu; Nick Hawes

cs.LGOct 19, 2026

PACT: Plan-Augmented Coordination via Trace-Graphs for Dynamic Multi-Agent Combinatorial Optimization

Authors: Xiao Zhou, Alex Schutz, Victor-Alexandru Darvariu, Nick Hawes

Organizations: Oxford Robotics Institute University of Oxford OX1 3PJ, Oxford, United Kingdom.

Abstract

Multi-agent approaches have been investigated recently as a means of improving the scalability of reinforcement learning for neural combinatorial optimization. Existing methods assume that all problem instance information is known upfront. However, real-world problems are often dynamic: relevant information is progressively revealed as the agents take actions (e.g., arriving at an edge in a routing problem only to discover it is untraversable). In such cases, existing methods fail to coordinate agents to explore and exploit the progressively revealed information. To address the arising coordination challenge, we introduce PACT (Plan-Augmented Coordination via Trace-graphs). PACT augments the environment graph with auxiliary nodes representing the plans of agents, which are connected to the resource nodes to indicate future dependencies. The proposed message-passing scheme over the augmented graph grounds inter-agent coordination in the environment and enables proactive, rather than reactive, conflict resolution. We show that PACT improves solution quality in dynamic problems relative to baselines and exhibits the best transfer to larger instances on which, remarkably, it outperforms centralized oracles with privileged access to instance uncertainty.

Figures & tables

Figure 1: PACT with plan-level coordination prevents goal conflicts exhibited by MARL methods with step-level coordination.

Figure 2: Overview of PACT. After encoding graph observations, agents independently generate candidate plans to form a plan-augmented trace-graph for multi-step coordination. The joint action

\mathbf{a}_{t}

comprises the initial step of each selected plan.

Panel of Figure 3 — Figure 3: Validation return during training. Curves show the mean across ten seeds; shaded regions indicate one standard deviation. Higher is better.

Panel of Figure 4 — Figure 4: Analysis of PACT components.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Illustration of the DFJSP task. The upper panel pairs ordered job chains with machine-specific eligibility sets, where the lightning bolts mark machines that may have latent breakdowns. The lower panel gives a machine-wise schedule, where the dashed block records a failed dispatch to a broken machine and the solid block shows successful operation dispatch.

Figure 6: Illustration of the NCFFSP task. Jobs operate from left to right through consecutive parallel machine stages, where the lightning bolts mark machines that may have unrevealed duration factors.

Resource	Type	License
Gurobi ( Gurobi Optimization, LLC, 2026 )	Solver (commercial)	Commercial, academic license
OR-Tools ( Perron & Furnon, )	Solver (open-source library)	Apache License 2.0
BenchMARL ( Bettini et al., 2024 )	Library (MAPPO, IPPO, and VDN)	MIT License
DCG ( Böhmer et al., 2020 )	Code	Apache License 2.0
PARCO ( Berto et al., 2025 )	Code	MIT License
MACSIM ( Luttmann & Xie, 2026 )	Code	Apache License 2.0

Appendix

Table 2: Summary of licenses for baselines.

Shared settings
Hyperparameter	Value
Training steps	500,000
Validation interval	20,000 steps
Validation episodes	64
Random seeds	10
Optimizer	Adam

Appendix

Table 3: Training configuration for PACT and the MARL baselines.

Panel of Figure 7 — Figure 7: Validation return during training for PARCO on the three DMACO problems.

Panel of Figure 8 — Figure 8: Validation return during training for MACSIM on the three DMACO problems.

Method	Evaluation	Success (%) $\uparrow$	Cost $\downarrow$	Objective $\downarrow$	Perf. ratio $\downarrow$	Time (s) $\downarrow$
$16\times 4\times 6$ (ID)

MAPPO	Greedy	96.8 $\pm$ 2.1	3.83 $\pm$ 0.25	3.53 $\pm$ 0.06	1.046	0.027 $\pm$ 0.030
IPPO	Greedy	97.1 $\pm$ 2.0	3.92 $\pm$ 0.36	3.57 $\pm$ 0.11	1.071	0.015 $\pm$ 0.007
VDN	Greedy	98.9 $\pm$ 0.9	3.52 $\pm$ 0.20	3.33 $\pm$ 0.04	0.962	0.012 $\pm$ 0.004
DCG	Greedy	99.3 $\pm$ 0.7	3.68 $\pm$ 0.47	3.55 $\pm$ 0.26	1.005	0.011 $\pm$ 0.003

Appendix

Table 4: Complete results for learning-based methods on MACTP. The first configuration is in-distribution (ID), and the remaining configurations are evaluated zero-shot (ZST).

Method	Evaluation	Success (%) $\uparrow$	Cost $\downarrow$	Objective $\downarrow$	Perf. ratio $\downarrow$	Time (s) $\downarrow$
$20\times 8\times 6$ (ID)

MAPPO	Greedy	100.0 $\pm$ 0.0	170.2 $\pm$ 3.2	170.2 $\pm$ 3.2	1.047	0.022 $\pm$ 0.008
IPPO	Greedy	96.1 $\pm$ 9.4	207.7 $\pm$ 83.7	176.2 $\pm$ 7.1	1.278	0.051 $\pm$ 0.017
VDN	Greedy	54.4 $\pm$ 48.2	632.1 $\pm$ 486.7	181.7 $\pm$ 6.4	3.890	0.056 $\pm$ 0.028
DCG	Greedy	15.1 $\pm$ 32.1	986.6 $\pm$ 411.5	187.8 $\pm$ 14.6	6.071	0.088 $\pm$ 0.004

Appendix

Table 5: Complete results for learning-based methods on DFJSP. The first configuration is in-distribution (ID), and the remaining configurations are evaluated zero-shot (ZST).

Method	Evaluation	Success (%) $\uparrow$	Cost $\downarrow$	Objective $\downarrow$	Perf. ratio $\downarrow$	Time (s) $\downarrow$
$20\times 4\times 3$ (ID)

MAPPO	Greedy	97.4 $\pm$ 3.5	46.5 $\pm$ 2.3	44.2 $\pm$ 1.0	1.120	0.019 $\pm$ 0.006
IPPO	Greedy	98.5 $\pm$ 1.9	47.3 $\pm$ 1.7	45.4 $\pm$ 1.5	1.140	0.017 $\pm$ 0.004
VDN	Greedy	97.8 $\pm$ 2.2	50.0 $\pm$ 2.1	48.6 $\pm$ 1.5	1.205	0.017 $\pm$ 0.005
DCG	Greedy	71.7 $\pm$ 31.6	84.1 $\pm$ 50.6	56.1 $\pm$ 17.0	2.027	0.036 $\pm$ 0.011

Appendix

Table 6: Complete results for learning-based methods on NCFFSP. The first configuration is in-distribution (ID), and the remaining configurations are evaluated zero-shot (ZST).

Multi-Agent System Optimization

Multi-Agent System Optimization studies how to improve agent teams’ coordination, performance, resource use, and reliability.

See all 160 papers

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning
Jun 1, 2026Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders JonssonMulti-Objective Reinforcement Learning Multi-Agent System Optimization
Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain
Multi-Agent Coordination Adaptation via Structure-Guided Orchestration
May 25, 2026Haoran Li, Shulun Chen, Shaoyuan Sun +1Multi-Agent LLM Systems Multi-Agent System Optimization
Nanjing University · University of Technology Sydney, Sydney, Australia · University of New South Wales, Sydney, Australia
Action-Graph Policies: Learning Action Co-dependencies in Multi-Agent Reinforcement Learning
Feb 19, 2026Nikunj Gupta, James Zachary Hare, Jesse Milzman +2Multi-Agent Coordination Decentralized MARL
University of Southern California, Los Angeles, CA, USA · DEVCOM Army Research Laboratory, Adelphi, MD, USA · DEVCOM ARL Army Research Office, Los Angeles, CA, USA.

Jun 1, 2026J/K move · Enter open · S save

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders Jonsson

Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain

Multi-Objective Reinforcement Learning Multi-Agent System Optimization Constrained RL Constrained Optimization Cooperative MARL Constrained MARL

Open paper AskPDF arXiv

Constrained Multi-agent reinforcement learning (CMARL) faces two intertwined challenges: the joint action space grows exponentially with the number of agents, and additional requirements couple agents in ways that reward structure alone does not capture. We introduce Coordination Graphs for Constrained Multi-Agent Reinforcement Learning (CG-CMARL), a framework that addresses both challenges by combining coordination graphs with Lagrangian duality. The system decomposes the joint problem into pairwise regions, each served by a set of shared Q-functions, one for the primary objective and one for each of the constraints, so that the number of learned models is independent of the number of agents. At execution time, Max-Sum message passing coordinates actions across the factor graph, while a Lagrangian multiplier controls the objective--constraint tradeoff, allowing a single trained model to trace a Pareto front without retraining. We provide convergence guarantees under mild conditions, together with a compositional error bound that decomposes into separate interpretable sources, each traceable to a specific design choice and independently controllable. Experiments on cooperative navigation tasks (where teams of up to 10 agents must coordinate to reach target positions while satisfying pairwise constraints) show that our method produces Pareto fronts dominating established baselines trained at fixed reward-shaping ratios, while scaling to team sizes where centralized approaches become intractable.

Abstract

Multi-Agent System Optimization

Explore similar work

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

Multi-Agent Coordination Adaptation via Structure-Guided Orchestration

Action-Graph Policies: Learning Action Co-dependencies in Multi-Agent Reinforcement Learning