Minimizing movement

ABSTRACT

We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects (representing anything from a robot swarm or firefighter team to map labels or network messages) to achieve a global property of the network while minimizing the maximum or average movement. In particular, we consider the goals of achieving connectivity (undirected and directed), achieving connectivity between a given pair of vertices, achieving independence (a dispersion problem), and achieving a perfect matching (with applications to multicasting). This general family of movement problems encompasses an intriguing range of graph and geometric algorithms, with several real-world applications and a surprising range of approximability. In some cases, we obtain tight approximation and inapproximability results using direct techniques (without use of PCP), assuming just that P ≠ NP.

REFERENCES

• 1: Esther M. Arkin , Michael A. Bender , Sándor P. Fekete , Joseph S. B. Mitchell , Martin Skutella, The freeze-tag problem: how to wake up a swarm of robots, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.568-577, January 06-08, 2002, San Francisco, California
• 2: Esther M. Arkin , Michael A. Bender , Dongdong Ge, Improved approximation algorithms for the freeze-tag problem, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777465]
• 3: Jonathan L. Bredin , Erik D. Demaine , MohammadTaghi Hajiaghayi , Daniela Rus, Deploying sensor networks with guaranteed capacity and fault tolerance, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062729]
• 4: Moses Charikar , Chandra Chekuri, Approximation algorithms for directed Steiner problems, Journal of Algorithms, v.33 n.1, p.73-91, Oct. 1999 [doi>10.1006/jagm.1999.1042]
• 5: Johanne Cohen, Broadcasting, multicasting and gossiping in trees under the all-port line model, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.164-171, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277682]
• 6: Johanne Cohen , Pierre Fraigniaud , Jean-Claude König , André Raspaud, Optimized Broadcasting and Multicasting Protocols in Cut-Through Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.788-802, August 1998 [doi>10.1109/71.706050]
• 7: Corke, P., Hrabar, S., Peterson, R., Rus, D., Saripalli, S., and Sukhatme, G. 2004a. Autonomous deployment of a sensor network using an unmanned aerial vehicle. In Proceedings of the International Conference on Robotics and Automation.
• 8: Corke, P., Hrabar, S., Peterson, R., Rus, D., Saripalli, S., and Sukhatme, G. 2004b. Deployment and connectivity repair of a sensor net with a flying robot. In Proceedings of the 9th International Symposium on Experimental Robotics.
• 9: Srinivas Doddi , Madhav V. Marathe , Andy Mirzaian , Bernard M. E. Moret , Binhai Zhu, Map labeling and its generalizations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 05-07, 1997, New Orleans, Louisiana, United States
• 10: Ghodsi, M., Hajiaghayi, M., Mahdian, M., and Mirrokni, V. S. 2002. Length-constrained path-matchings in graphs. Netw. 39, 4, 210--215.
• 11: Sudipto Guha , Samir Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets, Information and Computation, v.150 n.1, p.57-74, April 10, 1999 [doi>10.1006/inco.1998.2754]
• 12: Hsiang, T.-R., Arkin, E. M., Bender, M. A., Fekete, S. P., and Mitchell, J. S. B. 2003. Algorithms for rapidly dispersing robot swarms in unknown environments. In Algorithmic Foundations of Robotics V, J.-D. Boissonnat et al., Eds. Springer Tracts in Advanced Robotics, vol. 7. Springer-Verlag, 77--94.
• 13: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• 14: Jiang, M., Bereg, S., Qin, Z., and Zhu, B. 2004. New bounds on map labeling with circular labels. In Proceedings of the 15th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 3341, 606--617.
• 15: Minghui Jiang , Jianbo Qian , Zhongping Qin , Binhai Zhu , Robert Cimikowski, A simple factor-3 approximation for labeling points with circles, Information Processing Letters, v.87 n.2, p.101-105, 31 July 2003 [doi>10.1016/S0020-0190(03)00256-4]
• 16: Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
• 17: Steven M. LaValle, Planning Algorithms, Cambridge University Press, New York, NY, 2006
• 18: John H. Reif , Hongyan Wang, Social potential fields: a distributed behavioral control for autonomous robots, Proceedings of the workshop on Algorithmic foundations of robotics, p.331-345, May 1995, San Francisco, California, United States
• 19: Schultz, A. C., Parker, L. E., and Schneider, F. E., Eds. 2003. Multi-Robot Systems: From Swarms to Intelligent Automata. Proceedings from the International Workshop on Multi-Robot Systems. Springer.
• 20: Strijk, T., and Wolff, A. 2001. Labeling points with circles. Int. J. Comput. Geom. Appl. 11, 2, 181--195.
• 21: Sztainberg, M. O., Arkin, E. M., Bender, M. A., and Mitchell, J. S. B. 2004. Theoretical and experimental analysis of heuristics for the “freeze-tag” robot awakening problem. IEEE Trans. Robotics Autom. 20, 4, 691--701.
• 22: West, D. B. 2001. Introduction to Graph Theory, 2nd Ed. Prentice Hall, Upper Saddle River.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Euclidean plane, Motion planning, graphs, pebble placement