Multi-agent Path Finding (MAPF) is a fascinating problem that asks us to find a coordinated movement plan for a team of cooperating agents. It turns out that one of the major impediments to solving such problems efficiently is symmetry, which manifests when one or more agents have many equivalent paths, all of which are just permutations of one another and all of which are incompatible with the paths of other agents. In January 2019 I was awarded an Amazon Research Awards grant for a related project entitled Symmetry Breaking Constraints for Multi-agent Pathfinding.
In September 2019 I was invited by Amazon to give a talk about my progress at their annual Robotics Symposium. It seems they made the recording of my talk available on Twitch. I share the video here as it might be of interest to others. In the video I give a very high level description of the MAPF problem and some intuitive explanations of the approaches I have worked on to solve this problem optimally. Here’s the bottom line: using something called “Barrier Constraints” my collaborators and I improve state of the art for Optimal MAPF by several orders of magnitude.