# Offline Time-Independent Multi-Agent Path Planning

arXiv: https://arxiv.org/abs/2105.07132 · HTML: https://mlsanity.com/paper/2105.07132/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2021.

## Built on by (most cited first, 5 of 5)

- [Learning Team-Based Navigation: A Review of Deep Reinforcement Learning Techniques for Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.05893/) (2023)
- [Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution](https://mlsanity.com/paper/2401.00315/) (2023)
- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [Fault-Tolerant Offline Multi-Agent Path Planning](https://mlsanity.com/paper/2211.13908/) (2022)
- [Multi-Agent Pathfinding Under Team-Connected Communication Constraint via Adaptive Path Expansion and Dynamic Leading](https://mlsanity.com/paper/2501.02770/) (2025)

## Abstract (arXiv)

This paper studies a novel planning problem for multiple agents that cannot share holding resources, named OTIMAPP (Offline Time-Independent Multi-Agent Path Planning). Given a graph and a set of start-goal pairs, the problem consists in assigning a path to each agent such that every agent eventually reaches their goal without blocking each other, regardless of how the agents are being scheduled at runtime. The motivation stems from the nature of distributed environments that agents take actions fully asynchronous and have no knowledge about those exact timings of other actors. We present solution conditions, computational complexity, solvers, and robotic applications.