Skip to content
Preprint

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

Oct 2026 · 0 citations · 44 references
Computer Science

TL;DR

PACT (Plan-Augmented Coordination via Trace-graphs) 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.

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.

View source

Similar papers

GraphMAS: A Systematic Benchmark of Multi-Agent Coordination for Graph Learning

LLM-based multi-agent systems coordinate specialized reasoning through aggregation, interaction, and adaptive control, yet their potential for graph learning remains unexplored. Graph learning is a natural setting for such systems because useful evidence may arise from heterogeneous local, long-range, global structural...

Jia-Yi Yang, Yi-Fang Chen, Yuan-Fu Sun et al. · 0 citations
#artificial intelligence Preprint Oct 2026

DHCG: Dynamic Construction of Hierarchical Collaboration Graphs for LLM-Based Multi-Agent Reasoning

LLM-based multi-agent systems (MAS) have demonstrated strong capabilities in solving complex problems across diverse domains. Recently, the dynamic orchestration of agent systems has become an important research direction. However, existing methods suffer from limited composition, misaligned dependencies, and inflexibl...

Jie Ren, Jiakang Yuan, Chen-Yu Huang et al. · 0 citations
#artificial intelligence Preprint Oct 2026

MASBench: Benchmarking LLM-based Multi-Agent Collaboration under Partial Observability

MASBench is introduced, a multi-agent collaboration benchmark designed under partially observable constraints that provides deterministic evaluation metrics, including performance score, communication cost, and cost effectiveness, to characterize both collaboration outcomes and communication overhead.

Qi-Zhi Chu, Ze-Kai Yu, Si-Jie Wen et al. · 1 citation
#artificial intelligence Open access Jul 2025

LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions (Extended Abstract)

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all...

Da-Chuan Liu, Shuai Zhou, Shi-Zhe Zhao et al. · 3 citations
#natural language process... Preprint Oct 2026

From Agents to Edges: Paired Optimization for Multi-Agent Collaboration

Strong individual agents do not guarantee effective collaboration. Communication must align what one agent conveys with how another interprets and uses it. This dependency makes the communication edge a natural unit of optimization. We introduce Paired Automated Communication Optimization (PACO), which jointly optimize...

Feng Lin, Xiao-Tian Yu, Yi-Fan Yang et al. · 0 citations
Preprint Oct 2026

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

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

Zi-Huang Cai, Chang-Jian Chen, Zhuo Tang et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.