Research map / Learning theory and algorithms / Optimal transport
Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
Usman Khan, Joseph W Durham
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| prune graph using Sinkhorn shadow transport and solve reduced LP (P2+P3) instead of full P1 LP | MAPF-MMOT · grid K=2,500 to 22,500, T=30 | speedup / cost gap: 3.6x to 7.1x speedup; gap below 10% | Improved |
| increase grid size with shadow pruning | P2+P3 pipeline · grid scaling, T=30 | solve time scaling: K^1.68 -> K^1.15 | Improved |
| increase entropic parameter epsilon (ablation) | P2+P3 pipeline · K=10,000 grid, lambda=0 | cost gap vs P1 optimal (%): 2.3 (eps 0.1) -> 17.3 (eps 1.0) | Hurt |
| increase epsilon (ablation) | Sinkhorn iterations · K=10,000 grid | sweeps to convergence: 307 -> 39 | Improved |
| increase shadow-bias lambda in P3 cost (ablation) | P2+P3 pipeline · K=10,000 grid | cost gap vs P1 optimal (%): 4.3 -> 7.3 (eps 0.2, lambda 0 -> 5.0) | Hurt |
| use extreme epsilon (0.1 or 5.0) with fixed pruning threshold (ablation) | P2+P3 pipeline · K=10,000 grid, 260 runs | feasibility: 27 of 260 runs infeasible | Hurt |
| use robust default epsilon=0.2, lambda=0 (ablation) | P2+P3 pipeline · K=10,000 grid | cost gap / speedup: 4.3% gap at 5x speedup | Improved |
| apply integral projection P3 to fractional shadow P2 | Sinkhorn-MAPF · 40x40 grid, N=80, T=10 | transport cost: P2 3160 -> P3 436 (P1 402) | Improved |
| add shadow-based edge pruning | P1 LP · grid, large scale | edges eliminated / variables: P3 uses 32-43% of P1 variables | Improved |
Closest papers by meaning
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.88)
- Exponential Convergence Guarantees for Iterative Markovian Fitting (NeurIPS 2025 · similarity 0.87)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.87)
- Generalized Schrödinger Bridge Matching (ICLR 2024 · similarity 0.86)
- Momentum Multi-Marginal Schrödinger Bridge Matching (NeurIPS 2025 · similarity 0.86)
- Schrödinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres (NeurIPS 2025 · similarity 0.86)
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.
