The proliferation of robots in public spaces necessitates a deeper understanding of how these robots can interact with those they share the space with. In this paper, we present findings from video analysis of publicly deployed cleaning robots in a transit space—a major commercial airport, using their navigational “troubles” as a tool to document what robots currently lack in interactional competence. We demonstrate that these robots, while technically proficient, can disrupt the social order of a space due to their inability to understand core aspects of human movement: mutual adjustment to others, the significance of understanding social groups, and the purpose of different locations. In discussion we argue for exploring a new design space of movement: socially-aware movement. By developing strong concepts that treat movement as an interactional and collaborative accomplishment, we can create systems that better integrate into the everyday rhythms of public life.