Shortest coordinated motions for square robots

Abstract We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations (feasible in the sense that the two squares are interior disjoint), find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. In this paper we present an adaptation of the tools developed for the case of disks to the case of squares. We show that in certain aspects the case of squares is more complicated, requiring additional and more involved arguments over the case of disks.