×

A PTAS for geometric 2-FTP. (English) Zbl 1371.68325

Summary: The Freeze Tag Problem (FTP) is an optimization problem that arises in Swarm Robotics. This problem studies the way of activating a group of inactive robots using only one active robot. In FTP for activating an inactive robot, the active robot should be in the physical proximity of it. The new activated robot can assist in activating other inactive robots. The goal is to find an optimal activating schedule with the minimum time required for activating all robots. In this paper, we investigate \(k\)-FTP which is a generalization of FTP where we have \(k\) initial active robots at first instead of only one active robot. We give an approximation algorithm and a PTAS for 2-FTP \((k=2)\).

MSC:

68W25 Approximation algorithms
68T40 Artificial intelligence for robotics
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ravi, R., Rapid rumor ramification: approximating the minimum broadcast time, (Proceedings of the 35th Annual Symposium on Foundations of Computer Science. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, FOCS (1994)), 202-213
[2] Bar-Noy, A.; Guha, S.; Naor, J.; Schieber, B., Multicasting in heterogeneous networks, (Proceedings of the 30th Annual ACM Symposium on Theory of Computing. Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC (1998)), 448-453 · Zbl 1028.68013
[3] Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047
[4] Arkin, M.; Bender, M. A.; Fekete, S. P.; Mitchell, J. S.B.; Skutella, M., The freeze-tag problem: how to wake up a swarm of robots, Algorithmica, 46, 2, 193-221 (2006) · Zbl 1101.68098
[5] Hammar, M.; Nilsson, B. J.; Persson, M., The online freeze-tag problem, (7th Latin American Symposium. 7th Latin American Symposium, Theoretical Informatics, vol. 3887 (2006)), 569-579 · Zbl 1145.68548
[6] Arkin, E. M.; Bender, M. A.; Ge, D.; He, S.; Mitchell, J. S.B., Improved approximation algorithms for the freeze-tag problem, (Proc. 15th ACM Symposium on Parallel Algorithms and Architectures. Proc. 15th ACM Symposium on Parallel Algorithms and Architectures, California, USA (2003)), 295-303
[7] Sztainberg, M. O.; Arkin, E. M.; Bender, M. A.; Mitchell, J. S.B., Analysis of heuristics for the freeze-tag problem, (Proceeding of the 8th Scandinavian Workshop on Algorithm Theory (2002)), 270-279 · Zbl 1078.68762
[8] Sztainberg, M. O.; Arkin, E. M.; Bender, M. A.; Mitchell, J. S.B., Theoretical and experimental analysis of heuristics for the freeze-tag robot awakening problem, IEEE Trans. Robot. Autom., 20, 4, 691-701 (2004)
[9] Bucantanschi, D.; Hoffmann, B.; Hutson, K. R.; Kretchmar, R. M., A neighborhood search technique for the freeze tag problem, (Extending the Horizons. Extending the Horizons, Advances in Computing, Optimization, and Decision Technologies, vol. 37 (2007)), 97-113 · Zbl 1127.68429
[10] Bucatanschi, D. G., The ant colony system for the freeze-tag problem, (Midstates Conference on Undergraduate Research in Mathematics and Computer Science. Midstates Conference on Undergraduate Research in Mathematics and Computer Science, MCURCSM, Ohio, USA (2004)), 61-69
[11] Zoraida, B. S.E.; Arock, M.; Ronald, B. S.M.; Ponalagusamy, R., DNA algorithm employing temperature gradient for freeze-tag problem in swarm robotics, Trans. Inst. Meas. Control, 34, 2-3, 278-290 (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.