The complexity of collision-free motion planning on graphs

The problem of multiple occupancy in a space is captured by the topology of its configuration spaces. The problem of navigation within a space is tied to its topological complexity, a numerical invariant introduced by Farber to measure the constraints in motion planning imposed by the shape of the ambient space. Combining these ideas, one is led to the study of the topological complexity of configuration spaces as a measure of the difficulty of collision-free motion planning. Thinking of autonomous vehicles and automated factories, it is natural to take the workspace to be a graph, and the complexity in this setting was described by Farber in 2005 in a conjecture with surprising and counterintuitive consequences. After a gentle introduction to some ideas around topological complexity, configuration spaces, and graph braid groups, I will describe a recent proof of this conjecture.