Moving robots efficiently using the combinatorics of CAT(0) cubical\n complexes

Abstract

Given a reconfigurable system X, such as a robot moving on a grid or a set of\nparticles traversing a graph without colliding, the possible positions of X\nnaturally form a cubical complex S(X). When S(X) is a CAT(0) space, we can\nexplicitly construct the shortest path between any two points, for any of the\nfour most natural metrics: distance, time, number of moves, and number of steps\nof simultaneous moves.\n CAT(0) cubical complexes are in correspondence with posets with inconsistent\npairs (PIPs), so we can prove that a state complex S(X) is CAT(0) by\nidentifying the corresponding PIP. We illustrate this very general strategy\nwith one known and one new example: Abrams and Ghrist's positive robotic arm on\na square grid, and the robotic arm in a strip. We then use the PIP as a\ncombinatorial "remote control" to move these robots efficiently from one\nposition to another.\n