  We study online Multi-Agent Path Finding (MAPF), where new agents are
constantly revealed over time and all agents must find collision-free paths to
their given goal locations. We generalize existing complexity results of
(offline) MAPF to online MAPF. We classify online MAPF algorithms into
different categories based on (1) controllability (the set of agents that they
can plan paths for at each time) and (2) rationality (the quality of paths they
plan) and study the relationships between them. We perform a competitive
analysis for each category of online MAPF algorithms with respect to
commonly-used objective functions. We show that a naive algorithm that routes
newly-revealed agents one at a time in sequence achieves a competitive ratio
that is asymptotically bounded from both below and above by the number of
agents with respect to flowtime and makespan. We then show a counter-intuitive
result that, if rerouting of previously-revealed agents is not allowed, any
rational online MAPF algorithms, including ones that plan optimal paths for all
newly-revealed agents, have the same asymptotic competitive ratio as the naive
algorithm, even on 2D 4-neighbor grids. We also derive constant lower bounds on
the competitive ratio of any rational online MAPF algorithms that allow
rerouting. The results thus provide theoretical insights into the effectiveness
of using MAPF algorithms in an online setting for the first time.
