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

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

作者：Masashi Aono

来源：arXiv cs.DC（分布式并行）

正文

Computer Science > Emerging Technologies

arXiv:2610.26272v1 (cs)

[Submitted on 19 Oct 2026]

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

Authors:Masashi Aono

View a PDF of the paper titled Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding, by Masashi Aono

View PDF

HTML (experimental)

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.

Comments:

33 pages. Ancillary files: Lean 4 development for the finite gadget (this http URL), 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”

Subjects:

Emerging Technologies (cs.ET); Computational Complexity (cs.CC); Distributed, Parallel, and Cluster Computing (cs.DC); Multiagent Systems (cs.MA)

Cite as:

arXiv:2610.26272 [cs.ET]

(or

arXiv:2610.26272v1 [cs.ET] for this version)

https://doi.org/10.48550/arXiv.2610.26272

Focus to learn more

arXiv-issued DOI via DataCite

主题

cs.ET · cs.CC · 分布式计算 · 多智能体

由「前沿雷达」于 2026-10-19 采集。正文取自原文页面，已保留出处链接。标题与正文版权归原作者所有。