Metraipolis › archive › dc_c80205b3aef5
Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding — arXiv:2610.26272
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.26272
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-20T14:58:52.090Z
- SHA-256 of the archived text
279c86500a58d73b06cd1b85695d034789d13d6fec3dcd49d3b37c8c57d9d701- Stable URL of this page
https://metraipolis.com/documento/dc_c80205b3aef5
How to cite
Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding — arXiv:2610.26272 — arXiv (en), https://arxiv.org/abs/2610.26272 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c80205b3aef5 (Metraipolis archive dc_c80205b3aef5, sha256 279c86500a58d73b06cd1b85695d034789d13d6fec3dcd49d3b37c8c57d9d701)
BibTeX
@misc{dcc80205b3aef5,
title = {Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding — arXiv:2610.26272},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.26272},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c80205b3aef5; sha256 279c86500a58d73b06cd1b85695d034789d13d6fec3dcd49d3b37c8c57d9d701},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.26272. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.MA, nuovi lavori del giorno). Categorie arXiv: Emerging Technologies (cs.ET) ; Computational Complexity (cs.CC); Distributed, Parallel, and Cluster Computing (cs.DC); Multiagent Systems (cs.MA). Pagina del lavoro: https://arxiv.org/abs/2610.26272 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-20T14:58:50.776Z dalla pagina https://arxiv.org/list/cs.MA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).