Spatio-Temporal Routing

 

The idea behind this project is to route multiple robots to service spatially distributed requests at specified time instants, while optimizing some criterion, for instance the total distance travelled, or the total time of travel. The routing problem is similar to the well known Multiple Traveling Salesman Problem (m-TSP) or the Vehicle Routing Problem (VRP), except that it is temporally constrained, i.e. every request must be serviced at a particular time instant.

The advantage of such a spatio-temporal construction is that a notion of directionality appears in the otherwise NP-hard routing problem, allowing us to apply the framework of assignment problems towards finding solutions, with the resulting reduction in complexity.

The problem of spatio-temporal routing is musically inspired in that it requires a bunch of robots to reach a series of planar positions at specified time instants, much like a musician that uses multiple fingers to play a series of notes on an instrument at specified time instants. As a motivating example, we present the Robot Music Wall.

A Motivating Example: The Robot Music Wall


Consider a two-dimensional magnetic-based surface (wall) with a grid of strings in different pitches that generate sound when plucked, as illustrated in the figure above. Distinct positions on the wall correspond to distinct sound frequencies, i.e. distinct notes of an instrument. Multiple robots with the ability to traverse the wall can reach these positions and pluck at the strings above them. In other words, we have a musically instrumented wall where a robot can effectively “play” a musical note by reaching its corresponding position on the wall and plucking the string above it.

With this set-up, we can interpret any piece of music consisting of a series of notes to be played at specified time instants, as a series of corresponding spatio-temporal requests (timed positions) on the music wall. We call such a series a Score, which contains positions that must be reached at specified time instants. Moreover, we might even require that multiple positions are reached simultaneously, akin to a musician that has to play multiple notes of an instrument simultaneously with different fingers. By routing multiple robots to service such timed positions, we can effectively “play” the piece of music associated with them on the wall.

Velocity Constrained Routing

A realistic approach to the spatio-temporal routing problem would be to introduce, say, a maximum velocity that the robots cannot exceed. Thus, for a given Score and max velocity, we derive results for the minimum number of robots required, as well as find the corresponding routes that the robots must follow.

vcap

Four snapshots of robots playing Fur Elise by Beethoven, under maximum velocity constraintsmin_bots_vs_vcap

Plot of minimum number of robots versus maximum velocity

We conducted hardware experiments to demonstrate the routing problem, shown in the following video:

The Robot Music Wall is also an application for group based leader-follower control.

Connectivity Constrained Routing

Another interesting version of the spatio-temporal routing problem would be to require that range constrained robots be connected at all times, or more formally, the underlying information exchange graph induced by the positions of the robots be connected at all times during the execution of a particular Score. For such a routing problem, we derive the minimum number of robots required, as well as provide an algorithm for finding the corresponding routes that the robots must follow.

Simulation snapshots

Four snapshots of robots playing Fur Elise by Beethoven, under connectivity constraints

min_bots_vs_delta

Plot of the minimum number of robots versus range of robots

Heterogeneous Routing

Heterogeneity is considered an important facet of multi-robot routing. We incorporate heterogeneity in the spatio-temporal routing problem by associating one or more skills with each robots as well as each request. Moreover, we require that in order to service a request, a robot must have at least  one skill in common with the skill set of that request. We characterize the feasibility aspects of such a routing problem, and provide algorithms for finding the minimum number of robots required to service the requests, and for constructing the corresponding routes of the robots.

In order to demonstrate the routing problem, we created a music wall with multiple instruments, where each robot could play one or more instruments, shown below:

het_gui

A simulated GUI of a music wall, with coordinates representing either piano notes, guitar notes or drums

 

 

 

 

 

 

 

 

 

 

 

 

 

gui_snapshots

Two snapshots of robots playing “Can You Feel the Love Tonight”, under the heterogeneous framework

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Investigators:

Related Publications:

S. Chopra and M. Egerstedt. Multi-Robot Routing under Connectivity Constraints. IFAC Workshop on Estimation and Control of Networked Systems, Santa Barbara, CA, Sept. 2012.

S. Chopra and M. Egerstedt. Multi-Robot Routing for Servicing Spatio-Temporal Requests: A Musically Inspired Problem. IFAC Conference on Analysis and Design of Hybrid Systems, Eindhoven, Netherlands, June 2012.

 

Comments are closed.