CS Paper Radar

Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding

Masashi Aono

cs.ET cs.CCcs.DCcs.MA ·submitted 2026-10-19 12:28 UTC · v1
theory

Abstract

On ranked directed acyclic graphs coupled by vertex conflicts we study exact-arrival multi-agent path finding (departure and arrival pinned in place and time) posed as a distributed output task: every cell must emit its own bit of a valid joint path-support mask. The machines are cellular: one automaton per cell, state factored over cells, communication only along a fixed local fabric, synchronous rounds, a query-independent output round, no central decoder, and a per-topology transition code. "Necessary" here means: on an explicit hard topology, over all its feasible queries, no universally correct local-only architecture can renounce either temporal orientation; with global flags, impossibility becomes a bandwidth-round trade-off. The class is not vacuous: a flooding machine solves every instance in as many rounds as the diameter of the local fabric. The bound survives two concessions: we supply every agent's exact individual cavity, which alone solves the single-agent problem in zero rounds and makes the single-agent direction theorem vacuous; and we allow $k$ one-bit global aggregate flags. On a twelve-cell, two-agent, depth-three topology no forward-only machine with $k=0$ is correct on two feasible queries, for any number of rounds; the time-reversed topology does the same to backward-only machines. Placing $p$ copies side by side gives, for forward-only machines, $J_R+kR\ge p$ at constant depth, where $J_R$ measures how much of the query reaches the targets' cones and is $0$ here. A backward-only machine solves that family in constant rounds and a flag-streaming one in $\lceil p/k\rceil+O(1)$, so the bound is tight in order; on the composite family neither orientation can be renounced. The finite lemmas of the gadget and the pair-invariance contradictions are checked in Lean 4; the semantic bridge, the cone lemma and the counting are paper proofs. We report no benchmarks.

Comment
33 pages. Ancillary files: Lean 4 development for the finite gadget (theoremA.lean), exhaustive check scripts with frozen expected outputs, reproduction README and clean-run log. Companion paper: "Stability Certifies Validity: Amoeba-Inspired Rule Systems for SAT and Single-Agent Trajectory Constraints, Machine-Checked in Lean 4"

Closest papers

Nearest neighbours by meaning across the whole index.

Universal Rendezvous of Anonymous Agents with Footprints

cs.DC ·2026-08-10 ·Bibhuti Das
similarity 0.61
Abstract

Deterministic rendezvous for two anonymous mobile agents starting simultaneously from two distinct nodes of an anonymous connected graph and navigating synchronously in the graph requires that they meet at some node. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are the initial positions of the agents. Such an instance is said to be feasible if there is a deterministic algorithm guaranteeing rendezvous, possibly valid only for this instance. A rendezvous algorithm is said to be universal for a class of instances if it guarantees rendezvous for all feasible instances from this class. We consider the model with footprints: whenever an agent visits an unmarked node, it leaves a permanent footprint on it, and all footprints are identical. This paper aims at answering the open problem from the paper by Das and Pelc (SPAA 2026), asking whether there exists a universal rendezvous algorithm for the class of all instances in the model with footprints. We propose a universal rendezvous algorithm for the class of all instances where the underlying graph is connected (finite or countably infinite) in the model with footprints. This shows the existence of a universal algorithm for the class of all instances in the model with footprints, which is an affirmative answer to the open problem.

0.04

Routing Multiple Agents Below the Sum of Distances

cs.DS cs.DM ·2026-09-16 ·Matthias Bentert, Eduard Eiben, Fedor V. Fomin, Petr A. Golovach
theory similarity 0.60
Abstract · Full version of the IPEC 2026 paper

We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to designated destination vertices in a graph. We analyze the problem within the above-and-below-guarantee paradigm of parameterized complexity. In particular, we consider the natural upper bound \(L\), given by the sum of the shortest-path distances between pairs of agents' terminals (corresponding to sequential routing of the agents). The parameterization is given by the gap \(ζ= L - λ\) between this bound and the target makespan \(λ\), together with the number \(k\) of agents. Our main result establishes fixed-parameter tractability for the combined parameter \(k + ζ\). Matching lower bounds show that parameterization by \(k\) alone is W[1]-hard, and that parameterization by \(ζ\) alone is W[1]-hard when terminals are not required to be distinct. On the positive side, if all terminals are distinct, the problem becomes fixed-parameter tractable when parameterized solely by \(ζ\). Finally, we show that Transient Multiagent Pathfinding is unlikely to admit a polynomial kernel when parameterized by \(k + ζ\). Together, our results provide an almost complete characterization of the parameterized complexity landscape of the problem for the considered parameters.

0.20

Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding

cs.AI ·2026-11-05 ·Stephen Chang, Daniel Harabor
benchmark similarity 0.59
Abstract

LaCAM is a search-based solver for multi-agent pathfinding (MAPF) that runs a depth-first search over joint configurations, using PIBT to generate successors and lazily adding single-agent constraints to explore alternatives. Although LaCAM is complete, it can struggle on dense, corridor-heavy instances because extracting blocking agents from deadlocks requires coordinated moves of several agents, often away from their goals, which PIBT's greedy one-step successors rarely propose and which LaCAM can only reach by enumerating constraints one agent at a time. This paper proposes Goal-Branching, where blocking agents are given temporary goals, each tried as an additional branch of LaCAM's search. We examine random and corridor-aware rules for choosing these temporary goals and show that completeness is preserved for any such rule. On dense instances (60-90% of free cells occupied) of three maze and room maps, Goal-Branching solves 89% of instances against 44% for LaCAM*, and, on instances both solve, it finds a first solution 10-14x faster on maze-32-32-2 and room-32-32-4, and nearly 200x faster in median time at 75% density on room-32-32-4. Solution cost increases by 15-22% on instances both solve, while on open maps and the full MovingAI benchmark its solutions cost no more than those of LaCAM* and it is at most 3% slower.

0.20

H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs

cs.RO ·2026-11-05 ·Tolga Özaslan, Elif A. Özaslan
theory similarity 0.59
Abstract

Repeated directed reachability queries arise in online path planning, task-agent allocation, and swarm control on static grid maps, where reachability is asymmetric and full transitive closure is storage-prohibitive. We introduce H-BRICK, a Hierarchical Boundary Reachability Index with Compressed Kleene closure for exact cell-to-cell queries on directed grid graphs. H-BRICK partitions the graph into tiles, computes a local Boolean Kleene closure within each tile, and projects it onto the tile's boundary ports. The resulting directed port-to-port summaries are then composed recursively across shared interfaces up to a single root covering the graph. We prove algebraically that the construction is exact: in the Boolean Kleene algebra of binary relations, every composed summary equals the boundary projection of the regional reflexive transitive closure, and every cell-to-cell query agrees with reachability in the original graph. Experiments on directed grid graphs across diverse map topologies compare H-BRICK against directed search and component-based baselines, and compare its storage requirements against full transitive closure. A batched reachability evaluation further demonstrates that sharing endpoint lifts across many-source/many-target queries amortizes hierarchical traversal and, at k=64, yields a 5.0x-22.9x throughput improvement over the scalar query loop. The results show that hierarchical boundary compression is most advantageous in query-intensive spatial graphs where online search traverses large reachable regions and the hierarchy maintains compact boundary interfaces.

0.37

Beyond the Boundary: Optimal Grid Dispersion by Spread, Reverse, and Collect

cs.DC ·2026-10-12 ·Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, Subhajit Pramanick
theory similarity 0.58
Abstract

\emph{Dispersion} requires a set of mobile agents to occupy distinct nodes of a graph such that each node contains at most one agent. We study deterministic dispersion of $k\le n$ agents on an $n$-node oriented square grid, where each node has globally consistent North, East, South, and West port labels, from arbitrary initial configurations. This includes both \emph{rooted} configurations, where all agents are co-located initially, and \emph{general} configurations, where agents are initially distributed arbitrarily across the nodes. On oriented square grids, Kshemkalyani, Molla, and Sharma~\cite{KMS20} gave an $O(\min(k,\Side))$-round algorithm in the local-communication model, where only agents on the same node can exchange information, and an $O(\sqrt{k})$-round algorithm in the global-communication model, where any two agents can communicate regardless of position, both using $O(\log k)$ bits per agent. The bound in the local communication model is optimal when $k=Θ(n)$, but it remains open whether local communication alone can match the $Ω(\sqrt{k})$ time lower bound when $k=o(n)$. We solve this by presenting \textsc{Spread--Reverse--Collect} (SRC), a deterministic algorithm that disperses any $k\le n$ agents in $O(\sqrt{k})$ synchronous rounds using $O(\log k)$ bits of persistent memory per agent, matching both time and memory lower bounds. SRC is based on a geometric primitive, a \sharpS-shaped parallel sweep, together with a simple priority rule. Unlike earlier grid algorithms that gather agents at the boundary and spread out from there, each SRC sweep starts from the agents' current position, and when it reaches the boundary the group simply reflects its sweep back inside and continues. SRC therefore needs no knowledge of the grid size and runs unchanged on an infinite oriented grid.

0.24

Dense Interprocedural Dominance in Acyclic Graphs: Context Bounds and Compact Queries

cs.DS ·2026-09-05 ·Peisen Yao
similarity 0.57
Abstract · We identified a substantive technical issue in the proof of the main theorem that affects several downstream results. Addressing the issue r…

Interprocedural dominance asks which program points every matched call-and-return execution must pass on its way to a target. An analysis that writes out immediate dominance pays for the transitive reduction of this order, the minimal dominator graph. Measured instances of that graph look near-linear, with edge-to-node ratios around 1.1--1.26~\cite{DeSutter2007}, but no program property is known to force this: it is unclear which structural restrictions imply sparse output, and whether dense output also rules out cheap queries. This paper answers both through calling contexts. A static node stands for the group of its reachable configurations; write $κ$ for the largest group size and $α$ for how many nodes have more than one configuration. One context per node keeps the tree with $n-1$ edges. Two already allow $Θ(n^2)$ cover edges in a sparse, loop-free, recursion-free ICFG with total degree three, constant-size procedures, and logarithmic stack depth, while the reachable configuration graph itself stays linear, so the blowup comes from grouping, not from many configurations. Three keep $Θ(n^2)$ covers even when the explicit call/return graph is acyclic: all target-reaching runs visit the mandatory procedures in the same order, and extra runs that stop short of any target remove the comparabilities that would otherwise kill the covers. Complementing the lower bounds, $α$ ambiguous nodes admit at most $\min\{\floor{n^2/4},(α+1)(n-1)\}$ cover edges, with $Ω(αn)$ attainable at stack depth one. And for every ICFG with at most two contexts per node, deleting a context group reduces dominance to dual-failure reachability, giving $O(n)$-word, $O(1)$-query representation after polynomial preprocessing. Explicit cover size, context ambiguity, and query-space cost are three separate quantities.

0.26

Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability

cs.DC ·2026-11-01 ·Giuseppe A. Di Luna, Giovanni Viglietta
theory similarity 0.57
Abstract · 37 pages, 3 figures

We determine the exact round complexity of Counting in anonymous directed dynamic networks. Agents have no identifiers, but $\ell\geq1$ of them are designated as leaders. Every agent knows $\ell$ and its own leader status, while the population size $n$ is unknown and has to be determined by the agents. Communication proceeds in synchronous rounds; the directed communication graph may change arbitrarily and unpredictably from one round to the next, but is assumed to remain strongly connected. We solve Counting with a distributed algorithm that makes every agent output $n$ and halt after a number of rounds equal to $\begin{cases} n&\text{if }n=\ell\\ 2n-1&\text{if }n>\ell\text{ and }\ell=1\\ 2n-2&\text{if }n>\ell\text{ and }\ell\geq2. \end{cases}$ The algorithm works even for networks with loops and parallel arcs and even when agents learn their outdegree only after sending. We prove that this bound is worst-case tight over directed multigraphs for every $n$ and $\ell$ with $1\leq\ell\leq n$. Moreover, the local computation is polynomial (provided that each communication multigraph has at most $2^{\operatorname{poly}(n)}$ arcs): in every round, each agent solves at most one linear system with up to $n$ variables. By standard techniques, solving Counting also enables the evaluation of any computable function of the multiset of agents' input values within $2n-1$ communication rounds. The bound above optimizes the worst case over all networks. For an individual network, we show that even deciding whether an agent already has enough local information to determine $n$ is $\mathsf{coNP}$-complete (provided that the numbers of parallel arcs are encoded in binary). Thus, worst-case-optimal Counting admits polynomial local computation, whereas exact network-wise optimization is intractable under standard complexity assumptions.

0.21

Asymmetric Decomposition for Multi-Agent Path Finding with Unassigned Agents

cs.RO cs.MA ·2026-11-18 ·Xi Jin, Chen Qian, Renjun Zhang, Guowei Wu, Xiaobo Li +2 more
benchmarktheorycode/data similarity 0.57
Abstract

Robots without assigned tasks may obstruct active robots, while routing them to designated parking locations can cause unnecessary travel. This article proposes flow-oracle conflict-based search (FOCBS) for Multi-Agent Path Finding with unassigned agents (MAPF-UA). FOCBS searches over assigned-agent paths using conflict-based search (CBS) and routes targetless unassigned agents through a min-cost flow oracle. When the selected assigned-agent paths leave unassigned agents no collision-free paths, flow-conflict branching converts min-cut blockers into assigned-agent constraints, which guide the search without excluding optimal solutions. A batched zero-cost warm start accelerates the oracle, and start-avoiding tie-breaking reduces unassigned-agent movement. For feasible instances on finite graphs, we prove termination and global minimization of assigned-agent sum of service time, measured by last-arrival times. Unassigned-agent movement is minimized conditional on the selected assigned-agent paths, without a global lexicographic optimality guarantee. Benchmark experiments show that FOCBS scales well with the number of unassigned agents, and ablation studies show that, compared with discarding non-completable assigned-agent paths, flow-conflict branching solves substantially more instances while retaining optimality. Simulation and physical-robot experiments demonstrate plan executability, with laboratory tests reducing fleet travel by 40.8% relative to the parking-based coordination baseline. The source code and related resources are available at https://github.com/Chin-hsi/focbs

0.50