Multi-robot routing for servicing spatio-temporal requests: A musically inspired problem

In this paper, we consider the problem of routing multiple robots to service spatially distributed requests at specified time instants. As a motivating example, we present the Robot Music Wall, a musically instrumented surface where planar positions correspond to distinct notes of an instrument. Multiple robots with the ability to traverse the wall can effectively “play” a piece of music by reaching positions on the wall that correspond to the musical notes in the piece, at specified time instants. We show that the multi-robot routing problem for servicing such spatio-temporal requests can be formulated as a pure assignment problem with the resulting reduction in complexity. Moreover, we derive the minimum number of robots required to service such requests.