Newest papers

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

Xiao Zhou, Alex Schutz, Victor-Alexandru Darvariu, Nick Hawes · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.26671 · cited by 0 works (OpenAlex) · open-access PDF

Chinese

现有的方法假定所有问题实例信息是先知的,然而,现实世界的问题往往是动态的:相关信息随着代理人采取行动逐渐被揭示(例如,在路由问题中到达边缘只有发现它是不可穿越的)。在这种情况下,现有的方法未能协调代理人探索和利用逐渐揭示的信息。 为了解决出现的协调挑战,我们引入PACT(计划增加协调通过轨道图表)。 PACT通过代表代理人的计划的辅助节点来增加环境,这些节点连接到资源节点来表明未来的依赖性。 建议的信息传递系统通过在环境中增强的图表间接协调和可再生效,而不是转移到PACT的相对集中式解决方案,我们表明,在冲突的解决方案中,我们可以更大程度地启示到增强

Machine translation (Meta M2M100); the English original follows.

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.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Computer science, Scalability, Exploit, Graph, Reinforcement learning, Distributed computing

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange