DNA algorithm employing temperature gradient for Freeze-Tag Problem in swarm robotics

Abstract

The biological deoxyribonucleic acid (DNA) strand is found to be a promising computing unit. An attempt has been made to solve Freeze-Tag Problem (FTP) using DNA. In this paper, the thermodynamic properties of DNA have been utilized along with other biochemical operations to obtain the optimal awakening schedule. Actual distance values are represented using the thermodynamic properties of DNA. The proposed method also finds the minimum spanning tree (MST) of the FTP to obtain the optimal awakening schedule. All possible Euler cycles of the different spanning trees of the problem are first generated. From this generated Euler cycle, the MST is obtained, which is the optimal awakening schedule to the problem. Moreover, the proposed approach can be adopted to solve many real-life applications like broadcasting and scheduling problems, with necessary modifications. In this work, an instance with seven robots is solved using DNA computing.

Keywords

DNA computing Euler cycle Freeze-Tag Problem spanning tree swarm robotics temperature gradient

Get full access to this article

View all access options for this article.

References

Adleman

1994: Molecular computation of solutions to combinatorial problems. Science 266, 1021–9.

Amos

2005: Theoretical and experimental DNA computation. Natural Computing Series. Springer-Verlag, 85–7.

Arkin

E.M.

Bender

M.A.

Fekete

S.P.

Mitchell

J.S.B.

Skutella

2002: The Freeze-Tag Problem: how to wake up a swarm of robots. Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, 568–77.

Arkin

E.M.

Bender

M.A.

Mitchell

J.S.B.

2003: Improved approximation algorithms for the Freeze-Tag Problem. Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 295–303.

Hammar

Nilsson

B.J.

Persson

2006: On line Freeze Tag problem. LNCS 3887. Springer-Verlag, 569–79.

Han

Zhu

2006: DNA computing model for the minimum spanning tree problem. Proceedings of the Eighth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC). IEEE.

Han

Zhu

Pan

2008: DNA solution based on sequence alignment to the Minimum Spanning Tree Problem. International Journal of Bioinformatics Research and Applications 4, 188–200.

Hoffman

2004: Genetic algorithms applied to the Freeze Tag Problem. MCURCSM, Granville, OH, 51–60.

Ibrahim

Tsuboi

Ono

Khalid

2004: Direct-proportional length-based DNA computing for shortest path problem. International Journal of Computer Science and Applications 1, 46–60.

10.

Lee

J.Y.

Shin

S.Y.

Park

T.H.

Zhang

B.T.

2004: Solving Traveling Salesman Problem with DNA molecules encoding numerical values. Biosystems 78, 39–47.

11.

MC 2009: Molecular Computing. Available at: http://ls11-www.cs.uni-dortmund.de/molcomp/downloads/ (accessed 20 June, 2009).

12.

Narayanan

Zorbalas

1998: DNA algorithms for computing shortest paths. Proceedings of Genetic Programming, 718–723.

13.

OPC 2009: Oligonucleotide Properties Calculator. Available at: http://www.unc.edu/∼cail/biotool/oligo/ (accessed 23 June, 2009).

14.

Sztainberg

M.O.

Arkin

E.M.

Bender

M.A.

Mitchell

J.S.B.

2002: Analysis of heuristics for the Freeze-Tag Problem. Proceedings of the Scandinavian Workshop on Algorithms, LNCS. Volume 2368. Springer-Verlag, 270–9.

15.

Yamamoto

Kameda

Matsuura

Shiba

Kawazoe

Ahochi

2002a: A separation method for DNA computing based on concentration control. New Generation Computing 20, 251–62.

16.

Yamamoto

Kameda

Matsuura

Shiba

Kawazoe

Ahochi

2002b: Local search by concentration-controlled DNA computing. International Journal of Computational Intelligence and Applications 2, 447–55.