Research map / Multi-agent systems and games / Human-AI and goal-conditioned
PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PARCO, a parallel autoregressive RL framework that jointly decodes actions for all agents with communication layers, a multiple pointer mechanism, and priority-based conflict handlers, evaluated on min-max HCVRP, OMDCPDP and FFSP.
Problem
Multi-agent combinatorial optimization (routing and scheduling) suffers from poor agent coordination, poor generalization across problem sizes and agent counts, and high latency from sequential autoregressive decoding.
Approach
Decode actions for all agents in parallel each step using transformer communication layers among agent queries, a multi-pointer decoder producing per-agent logits, and a priority-based conflict handler that resolves duplicate actions using learned action probabilities as priorities.
Key results
- On HCVRP N=60, M=3, PARCO (sampling) achieves objective 6.82 with 3.81% gap in 0.05s, matching 2D-Ptr (s.) quality at lower latency.
- On OMDCPDP N=100, M=10, PARCO (sampling) reaches 63.20 objective (0.00% gap by definition of best-known), beating MAPDP (s.) at 63.64 and HAM (s.) at 66.91.
- On FFSP N=100, M=12, PARCO (greedy) gets 2.0% gap in 0.89s versus MatNet (greedy) 2.4% in 4.97s, i.e. over 4x faster.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use transformer-based Communication Layers instead of no communication, MLP, or MHA queries (ablation) | PARCO · FFSP N=50 | decoding steps and training time | Helped |
| Use learned model-output probabilities for conflict priorities instead of random, smallest-cost, or closest-agent tie-breaking (ablation) | PARCO · Multi-agent CO | conflict rate: 4% reduction in conflict rates | Helped |
| Use parallel construction with PARCO instead of 2D-Ptr | HCVRP N=100 M=7 greedy · HCVRP N=100 M=7 | Obj.: 4.92 -> 4.79 | Helped |
| Use parallel construction with PARCO instead of MatNet | FFSP N=50 M=30 greedy · FFSP N=50 M=30 | Obj.: 23.65 -> 20.29 | Helped |
| Use parallel construction with PARCO instead of MatNet | FFSP N=50 M=30 greedy · FFSP N=50 M=30 | Time: 3.09s -> 0.41s | Helped |
| Use PARCO rather than OR-Tools at large scale | OMDCPDP N=1000 M=200 · OMDCPDP N=1000 M=200 | Obj.: 584.27 -> 359.98 | Helped |
Surprising findings
- Gurobi cannot return solutions within the time limit for FFSP instances with N>20 even at 10 minutes.
Limitations
- Requires a fixed number of agents M; cannot directly handle unspecified agent counts.
- Conflict fallback (do-nothing) steps can add construction steps.
Experimental setup
Datasets: randomly generated instances (uniform coordinates, demands, capacities) 1280 test instances per setting from prior HCVRP benchmark 1000 new test instances per OMDCPDP setting
Benchmarks: HCVRP OMDCPDP FFSP
Metrics: objective value optimality gap inference time
Baselines: SISR Genetic Algorithm Simulated Annealing AM ET DPN DRL_Li 2D-Ptr OR-Tools HAM MAPDP Gurobi
Builds on: MatNet SymNCO Attention Model MAPDP
Closest papers by meaning
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.86)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.85)
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.85)
- Learning to Share: Selective Memory for Efficient Parallel Agentic Systems (ICML 2026 · similarity 0.85)
- Divide, Harmonize, Then Conquer It: Shooting Multi-Commodity Flow Problems with Multimodal Language Models (ICLR 2026 · similarity 0.85)
- Multiagent Gumbel MuZero: Efficient Planning in Combinatorial Action Spaces (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.