This paper considers the problem of human evacuation assistance. We discuss how this kind of task differs from the more prevalent search and rescue tasks, and the resulting implications for the design of assistive evacuation systems. We describe the implementation and evaluation of an algorithm for deploying audio navigational cues throughout an office building with a team of mobile robots. A review of evacuation dynamics methods is presented and particular methods are applied on-line during deployment. We use a pedestrian simulation and a simple model of audio–evacuee interaction to show the effects of beacon deployment; the results indicate that even a small number of beacons can significantly decrease the mean and variance of egress time and distance. We also advance uses for human motion-based measures of environment complexity for general mobile robotics.