An Approximation Algorithm for Time Optimal Multi-Robot Routing - Robotics Institute Carnegie Mellon University

An Approximation Algorithm for Time Optimal Multi-Robot Routing

M. Turpin, Nathan Michael, and V. Kumar
Workshop Paper, 11th International Workshop on the Algorithmic Foundations of Robotics (WAFR '14), pp. 627 - 640, August, 2014

Abstract

This paper presents a polynomial time approximation algorithm for Multi-Robot Routing. The Multi-Robot Routing problem seeks to plan paths for a team of robots to visit a large number of interchangeable goal locations as quickly as possible. As a result of providing a constant factor bound on the suboptimality of the total distance any robot travels, the total completion time, or makespan, for robots to visit every goal vertex using this plan is no more than 5 times the optimal completion time. This result is significant because it provides a rigorous guarantee on time optimality, important in applications in which teams of robots carry out time-critical missions. These applications include autonomous exploration, surveillance, first response, and search and rescue.

BibTeX

@workshop{Turpin-2014-17172,
author = {M. Turpin and Nathan Michael and V. Kumar},
title = {An Approximation Algorithm for Time Optimal Multi-Robot Routing},
booktitle = {Proceedings of 11th International Workshop on the Algorithmic Foundations of Robotics (WAFR '14)},
year = {2014},
month = {August},
pages = {627 - 640},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.