Writing study: Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges

ICML overviewCorpus atlasBy contribution typeVisual galleryRules & templateWriting patternsPaper studies

← ICML 2026 oral writing corpus

Usman Khan, Joseph W Durham · Official ICML 2026 oral record

Observed writing choices, not acceptance rules. This study examines the inspected manuscript version. It does not establish why the paper was accepted or that its presentation choices should be copied unchanged.

Figure, table and section ledger

Editorial contribution type: Efficiency, inference & systems (primary).

Layout extraction, not a required paper template. Counts are distinct caption labels; a multi-panel figure counts once. Section spans are estimated from heading positions, including floats and whitespace. Method and limitations.

Canonical PDF

31 physical pages

Before references / appendix

≈ 9.1 page-equivalents

Main figures / tables

4 / 1

Attached appendix figures / tables

14 / 3

Attached appendix span

≈ 19.6 page-equivalents

Before references / appendix: ≈ 29.35%References / intervening material: ≈ 7.42%Attached appendix: ≈ 63.23%Estimated layout envelopes, not text/artwork area. Unresolved appendix boundaries remain within the undivided post-body material.

Section-by-section lengths and source pages

The title/abstract/front matter precede the first numbered heading. A span ends at the next detected top-level heading, not at the last sentence; end-page whitespace is included. References and statements are listed separately. These are not measurements of text-only or artwork area.

Top-level heading	Starts on PDF page	Estimated span	Share of entire PDF
1. Introduction	1	≈ 0.97 pp.	3.13%
2. Background and Problem Formulation	2	≈ 1.32 pp.	4.26%
3. Integral and Optimal Solutions for MAPF	3	≈ 2.4 pp.	7.74%
4. MAPF and the Schrödinger Bridge Problem	6	≈ 1 pp.	3.23%
5. Integral Projection of Sinkhorn-MAPF	7	≈ 0.5 pp.	1.61%
6. Computational Complexity	7	≈ 0.34 pp.	1.1%
7. Experiments	7	≈ 0.95 pp.	3.06%
8. Conclusions	8	≈ 1.21 pp.	3.9%
Impact Statement	10	≈ 0.05 pp.	0.16%
References	10	≈ 2.3 pp.	7.42%
A. Proof of Lemma 3.2	12	≈ 0.23 pp.	0.74%
B. Proof of Lemma 3.3	12	≈ 0.75 pp.	2.42%
C. Proof of Theorem 3.4	13	≈ 0.48 pp.	1.55%
D. Proof of Lemma 3.6	13	≈ 0.67 pp.	2.16%
E. Proof of Lemma 4.1	14	≈ 0.29 pp.	0.94%
F. Proof of Lemma 4.2	14	≈ 0.57 pp.	1.84%
G. Sinkhorn-MAPF	15	≈ 2 pp.	6.45%
H. Detailed Experiments	17	≈ 14.62 pp.	47.16%

All detected figure and table locations

Main text

• Figure 1 · p. 8
• Table 1 · p. 8
• Figure 2 · p. 9
• Figure 3 · p. 9
• Figure 4 · p. 9

Attached appendix

• Table 2 · p. 18
• Figure 5 · p. 18
• Figure 6 · p. 19
• Table 3 · p. 19
• Figure 7 · p. 20
• Figure 8 · p. 20
• Table 4 · p. 21
• Figure 9 · p. 22
• Figure 10 · p. 23
• Figure 11 · p. 24
• Figure 12 · p. 25
• Figure 13 · p. 26
• Figure 14 · p. 27
• Figure 15 · p. 28
• Figure 16 · p. 29
• Figure 17 · p. 30
• Figure 18 · p. 31

Argument and organization

1. Problem and contribution

   Recasts anonymous robot-to-target assignment as transport on paths, distinguishing executable integral trajectories from a probabilistic shadow used for pruning.

2. Argument sequence

   The exact LP and its assumptions precede entropic relaxation; a separate projection restores integrality before runtime and cost-gap experiments.

3. Evidence and verification

   Scaling results report both solve time and cost gap, while the sensitivity table retains configurations exceeding the headline sub-10% gap; integrality is checked separately.

Problem, claim and contribution

Recasts anonymous robot-to-target assignment as transport on paths, distinguishing executable integral trajectories from a probabilistic shadow used for pruning.

Sections 2-3, pp. 2-4 · Main paper

Argument and section order

The exact LP and its assumptions precede entropic relaxation; a separate projection restores integrality before runtime and cost-gap experiments.

Sections 3-7, pp. 4-8 · Main paper

Figures, captions and visual explanation

The cost-design page pairs guarantees with numerical-instability caveats; time-indexed robot snapshots and a regularization-by-smoothness table make executability and approximation cost visible.

Lemmas 3.6-3.7, p. 5; Figure 1/Table 1, p. 8; both PNGs inspected · Main paper

Tables, comparisons and evidence

Scaling results report both solve time and cost gap, while the sensitivity table retains configurations exceeding the headline sub-10% gap; integrality is checked separately.

Section 7 and Table 1, p. 8 · Main paper

Appendix and reproducibility

The scaling study states its obstacle-free grid, density, horizon, hardware and solver; illustrative examples use a different solver and are not presented as timing evidence.

Appendix H.1-H.2, p. 17 · Main paper

Clarity and writing conventions

Named P1/P2/P3 formulations keep exact optimization, fractional relaxation and pruned projection distinct throughout the narrative.

Sections 3-7, pp. 4-8 · Main paper

What to reuse—and what not to infer

Transferable lesson: Expose the full route from relaxation to executable output, and plot approximation quality alongside system speed instead of transferring exact guarantees to the accelerated pipeline.

Boundary: The guarantees concern anonymous MAPF under stated graph, motion and cost assumptions; empirical scaling exponents and sub-10% cost gaps are configuration-specific, not universal complexity or approximation guarantees.

Apply this lesson using the argument and evidence worksheet.

Inspection record and sources

Checked

2026-10-07

Reading status

Writing-focused manuscript scan + selected visuals inspected

Main text

Writing-focused distributed manuscript scan, not exhaustive technical/proof validation. Sections 1-8, pp. 1-9: anonymous path-finding formulation, integrality/feasibility, cost design, entropic relaxation, integral projection and quality/runtime scaling.

Appendix / supplement

Writing-focused appendix scan; code, data and external assets not executed. Appendices A-H, pp. 12-31: result-specific proofs, Sinkhorn update details, scaling/sensitivity/baseline protocols and illustrative trajectories.

Visually inspected PDF pages

5, 8

This is a writing-focused scan of the manuscript and the stated supplementary scope: framing, organization, visual explanation, evidence presentation and wording. It is not a line-by-line proof audit, reproduction of results or exhaustive scientific review.

• Published ICML 2026 proceedings PDF, PMLR volume 306; retrieved 2026-10-07. Public OpenReview decision notes were not independently reverified. · 31 pages