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

摘要

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.