A new arXiv preprint takes up exact-arrival multi-agent path finding (MAPF), a version where each agent's departure and arrival are pinned in both location and time. The authors study this on ranked directed acyclic graphs coupled by vertex conflicts, meaning agents cannot occupy the same vertex at the same time.
Rather than treating it as a centralized planning problem, they pose it as a distributed output task: every cell in the machine must emit its own bit. This framing turns the path-finding question into one about what a cellular machine can compute under local constraints.
The paper's central claim is that bidirectionality is necessary in such cellular machines. In other words, allowing movement in both directions along edges is not just convenient but required for exact-arrival MAPF. The abstract does not include proof details, but the result points to a fundamental trade-off between directed graph structure and time-exact coordination.