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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1), 1–18 (2006)
Armstrong, R.D., Jin, Z.: Solving linear bottleneck assignment problems via strong spanning trees. Oper. Res. Lett. 12(3), 179–180 (1992)
Burkard, R.E., Cela, E.: Linear Assignment Problems and Extensions. Springer, Berlin (1999)
Carlsson, J., Ge, D., Subramaniam, A., Wu, A., Ye, Y.: Solving min-max multi-depot vehicle routing problem. Lectures on Global Optimization. Fields Institute Communications, vol. 55, pp. 31-46 (2009)
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, DTIC Document (1976)
Cook, W., Rohe, A.: Computing minimum-weight perfect matchings. INFORMS J. Comput. 11(2), 138–148 (1999)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1(1), 269–271 (1959)
Eksioglu, B., Vural, A.V., Reisman, A.: The vehicle routing problem: a taxonomic review. Comput. Ind. Eng. 57(4), 1472–1483 (2009)
Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: 17th Annual Symposium on Foundations of Computer Science, pp. 216–227. IEEE (1976)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM (JACM) 34(3), 596–615 (1987)
Hierholzer, C., Wiener, C.: Über die möglichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren. Mathematische Annalen 6(1), 30–32 (1873)
Kolmogorov, V., Blossom, V.: A new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. 1(1), 43–67 (2009)
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)
Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Courier Dover Publications (1976)
Nagy, G., Salhi, S.D.: Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. Eur. J. Oper. Res. 162(1), 126–141 (2005)
Ren, C.: Solving min-max vehicle routing problem. J. Softw. (1796217X) 6(9) (2011)
Xu, Z., Rodrigues, B.: A 3/2-approximation algorithm for multiple depot multiple traveling salesman problem. In: Algorithm Theory-SWAT 2010, pp. 127–138. Springer, Berlin (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Turpin, M., Michael, N., Kumar, V. (2015). An Approximation Algorithm for Time Optimal Multi-Robot Routing. In: Akin, H., Amato, N., Isler, V., van der Stappen, A. (eds) Algorithmic Foundations of Robotics XI. Springer Tracts in Advanced Robotics, vol 107. Springer, Cham. https://doi.org/10.1007/978-3-319-16595-0_36
Download citation
DOI: https://doi.org/10.1007/978-3-319-16595-0_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16594-3
Online ISBN: 978-3-319-16595-0
eBook Packages: EngineeringEngineering (R0)