In (Temporal) Multi-Agent Path Finding (TMAPF) multiple agents must reach their respective destinations over time in a changing environment without colliding. The temporal extension models dynamic real-world scenarios such as warehouse logistics, autonomous vehicle routing, and robotic navigation in environments with time-varying constraints.

Problem Definition

<aside> 💡

Definition. $\textsf{Temporally Disjoint Paths}$ and $\textsf{Temporally Disjoint Walks}$

Input: A temporal graph $\mathcal{G}=(V,E,\lambda)$ and a multiset of source–sink pairs $S=\{(s_1, t_1), \ldots, (s_k, t_k)\}\subseteq V\times V$.

Goal: Route each agent from $s_i$ to $t_i$ via a temporal journey such that no two agents:

• occupy the same vertex at the same time (vertex conflict), and/or
• traverse the same edge at the same time (edge conflict).

This models a temporal movement, where each agent can use at most one edge per time step and must not revisit vertices.

</aside>

Two Problem Variants

Two key variants introduced by Klobas et al. (2023) are:

• Temporally Disjoint Paths (TDP): Each agent follows a time-respecting path, and no two agents share a vertex at the same time. Paths are vertex-simple (no repeated nodes).
• Temporally Disjoint Walks (TDW): Agents may revisit vertices, but still must avoid simultaneous occupancy of any vertex.

Both problems aim to compute temporally feasible plans for all agents, with minimal or no interference.

Background and Classical (Static) Foundations

The (non-temporal) Disjoint Paths problem is a classic NP-complete problem and a cornerstone of algorithmic graph theory (https://archive.org/details/pathsflowsvlsila0000unse).

The (non-temporal) Multi-Agent Path Finding (MAPF) is the problem of deciding whether a set of vertex pairs (source-sink pairs) in a graph can be connected by pairwise vertex disjoint paths. It is solvable in polynomial time for constant $k$, and FPT when parameterized by the number of paths=number of source-sink pairs. On directed graphs, finding $2$ disjoint paths is already NP-hard, but on directed acyclic graphs the problem is solvable in polynomial time for a constant number of paths=pairs. MAPF can be seen as a generalization of pebble motion problems, which was shown to be NP-hard by Goldreich (2011) and Yu and LaValle (2013).

Refer to the following resources for more information on the non-temporal MAPF problem:

• A wiki on MAPF with Introductions, News, and Publications: https://mapf.info/
• Wikipedia page: https://en.wikipedia.org/wiki/Multi-agent_pathfinding
• Some surveys: https://www.researchgate.net/publication/336611576_Multi-Agent_Path_Finding_-_An_Overview https://doi.org/10.48550/arXiv.1906.08291

MAPF on temporal graphs generalizes this setting by relaxing and temporalizing the disjointness condition: agents may share nodes but only at different times.

History on Temporal MAPF

Literature on Temporal MAPF

Overview of Computational Complexity

Temporal MAPF (as all temporal path-based problems) introduces new algorithmic challenges due to the asymmetric and non-transitive nature of temporal reachability.

• List: All
• List: Comparison of Paths and Walks

For an overview of techniques used to show the specific results, refer to the corresponding papers [1] and [2].

Applications