| paper | d4-conf-aaai-2015-0062 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite graph \(G=(V,E)\), an explicit finite horizon \(H\), a finite set of routing types \(T\), a rational distribution \(\mu\) over \(T\), type-specific movement costs, and rational per-capita capacities \(\kappa_{v,q}\), let \(\mathcal P_t(H)\) be the legal whole paths for type \(t\), including goal occupancy through \(H\) after arrival. Choose \(x_{t,P}\ge 0\), the fraction of the whole population of type \(t\) assigned to path \(P\), with \(\sum_{P\in\mathcal P_t(H)}x_{t,P}=\mu_t\) and \(\sum_{t,P:(v,q)\text{ is occupied by }P}x_{t,P}\le\kappa_{v,q}\) for every vertex-time pair. Find a feasible assignment minimizing \(\sum_{t\in T}\sum_{P\in\mathcal P_t(H)}x_{t,P}c_t(P)\).
A capacitated, high-multiplicity cooperative MAPF model: each type carries mass \(\mu_t\), each unit of mass takes a legal whole path \(P\), and aggregate vertex-time occupancy is bounded by scaled capacity \(\kappa_{v,q}\); minimize mass-weighted path cost.
Covers Theorem 1's cooperative minimum-sum path allocation correspondence with mass and scaled vertex-time capacities; leaves the strategyproofness claims, iterative auction implementation, and empirical solver comparisons untouched.
The strongest honest anchor is Theorem 1, proved in this paper. The paper has no numbered theorem classifying a problem as in \(\mathrm{P}\), NP-hard, or similar, so this is a weaker anchor than a complexity result. It qualifies as an objective-preserving reduction that the authors then use to solve cooperative MAPF. Theorem 1 says: for a feasible MAPF instance \(\pi\), form the corresponding combinatorial auction \(R(\pi)\), set each agent’s value for reaching its goal to \(\mathrm{maxc}\cdot |K|\), where \(\mathrm{maxc}\) bounds the highest path cost in an optimal solution, and break welfare ties in favor of allocations including more agents. Then every welfare-maximizing allocation corresponds to a MAPF solution minimizing the sum of path costs.
I would mirror the cooperative optimization in that theorem, not the paper’s strategyproofness claims or its empirical comparison of solvers. My proposed problem is Per-Capita Capacity Continuous MAPF. Its instance is a finite graph \(G=(V,E)\), a finite horizon \(H\), a finite set of types \(T\), a rational mass distribution \(\mu\) with \(\sum_{t\in T}\mu_t=1\), type-specific movement and waiting costs, and rational capacities \(\kappa_{v,q}\) for each vertex \(v\) and time \(q\). A type records everything relevant to an agent’s routing problem: its start and goal, release time, and cost profile. A feasible path for a type is a legal sequence of moves and waits from its start at its release time to its goal by \(H\); after arrival, it reserves its goal location through \(H\), without adding travel cost.
For each type \(t\) and feasible path \(P\), choose \(x_{t,P}\ge 0\), the fraction of the whole population that has type \(t\) and takes \(P\). Require \(\sum_{P}x_{t,P}=\mu_t\) for every type, and require \(\sum_{t,P:\,(v,q)\text{ is occupied by }P}x_{t,P}\le\kappa_{v,q}\) for every vertex-time pair. The question is to find a feasible assignment \(x\) minimizing \(\sum_{t,P}x_{t,P}c_t(P)\), where \(c_t(P)\) is the path’s travel cost. Each infinitesimal agent still takes a whole, legal path; \(x\) describes how the population of a type is distributed across paths.
The regime I find credible is a large warehouse or airport fleet executing repeated job waves. Many robots have the same origin-destination class, release-time band, and movement-cost profile, while the fleet size is much larger than the number \(\tau=|T|\) of such classes. The capacity parameter captures a facility whose interchangeable routing slots scale with fleet size—for example, replicated lanes or equivalent crossing capacity. For \(N\) discrete robots, the corresponding normalized quantities are \(\mu_t=n_t/N\) and \(\kappa_{v,q}=b_{v,q}/N\), where \(b_{v,q}\) is the number of available slots at that vertex-time. This makes explicit the necessary capacity co-modification: the model aggregates a large population while retaining meaningful congestion constraints.
I expect this mirror to be tractable for explicit, polynomially bounded \(H\). Its path formulation has exponentially many possible paths, but it is equivalent to a multi-commodity flow LP on the time-expanded graph. There are polynomially many flow variables in \(|V|, |E|, H,\tau\); flow decomposition gives a distribution over whole paths, and shortest-path computations for each type provide the natural pricing subproblem. This is a prediction about the continuous problem, not a result established by the paper. With fixed unit-capacity vertex-time cells, normalization instead gives capacity \(1/N\); the nondegenerate high-multiplicity regime here relies on the stated scaling of available capacity.
I think the authors could recognize this as their problem’s continuous analogue: it preserves the central decision—assign agents paths to fixed goals while avoiding overuse of shared space—and preserves the sum-of-path-costs objective. The continuous allocation changes what is being counted: mass of interchangeable agents is assigned among integral paths. With all mass required to receive a path, maximizing a constant per-unit goal value minus path cost is exactly minimizing total mass-weighted cost, echoing Theorem 1’s welfare-to-cost correspondence.
The main weakness is that the paper’s vertex-time items have unit supply, while my mirror uses per-capita capacities. If a referee requires the original fixed graph and its unit collision constraints to remain unchanged as the population grows, this is not a nondegenerate continuous population regime. The case stands only as a capacitated, high-multiplicity MAPF model of scaled or replicated facilities. Further questions include whether discrete instances admit controlled rounding from the LP, how the needed horizon scales with fleet size and capacity, and which additional MAPF conflict rules preserve the flow formulation.
Theorem 1 is the only plausible anchor, but it proves an objective-preserving encoding, not a complexity result or an algorithmic guarantee. The paper’s distinctive computational story is the auction mechanism for individually identified agents, especially its strategyproofness claims and empirical implementation. Theorem 1 shows that a welfare-maximizing auction allocation represents a minimum-cost MAPF solution; it does not establish a new complexity boundary for that optimization problem.
The closest continuous mirror runs into a sharp modeling choice. In collision-free MAPF, each agent’s start determines its feasible paths, so it belongs in the agent’s complete type. With unit vertex-time capacity, agents must start at distinct vertices. On a fixed graph, the population is bounded by \(|V|\); as the graph grows, the number of start types grows with the population. That gives no regime with many agents per type and moderate support.
The proponent’s better version—grouping equivalent origins into types and scaling vertex-time capacities with population—is a coherent co-modification, as the programme allows. But it changes the operative constraint from individual collision avoidance to aggregate capacity, and its path assignment is the standard time-expanded multicommodity-flow LP. That is a sensible continuous routing model, but its tractability follows immediately from the LP formulation; it says little about the paper’s auction reduction or its strategic mechanism. In a nonatomic version, individual strategyproofness also loses force: one infinitesimal agent cannot materially affect the allocation or impose a VCG externality. A model retaining strategic agents as atoms alongside continuous background traffic might avoid that, but would no longer be a purely continuous mirror.
So the negative case is that the faithful model has no useful high-multiplicity regime, while the viable high-multiplicity model is an already familiar capacitated-flow problem that bypasses the paper’s distinctive result. That is a real objection to the anchor’s value for this programme. It is not airtight: if ChoCo counts a tractable, author-recognizable capacitated MAPF extension as worthwhile even when its LP is standard, I cannot honestly rule this mirror out.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.