臺灣博碩士論文加值系統

近年來，攜帶方便、使用試劑樣品量少且精確度高的數位微流體生物晶片(Digital Microfluidic Biochips, DMFBs)備受矚目。紙基數位微流體生物晶片(Paper-Based Digital Microfluidic Biochips, PB-DMFBs)利用含有奈米碳管(Carbon Nanotube, CNT)的墨水在特殊材質的紙上印製形成電極(Electrodes)和控制線(Control Wire)，因此製造成本和所需生產時間遠比傳統的數位微流體晶片少與易於攜帶。但由於紙基微流體生物晶片的所有線路都集中在同一層，使得PB-DMFBs的晶片級合成(Chip-Level Synthesis)成為一個挑戰，而 PB-DMFBs繞線技術尤具挑戰性。此外，當前的PB-DMFBs設計自動化工具必須解決各種設計問題，包括製造成本、可靠性(Reliability)、可測試/診斷性(Testability/ Diagnosability)、容錯性(Fault Tolerance)和安全性(Security)。因此，需要一種更靈活的多目標PB-DMFBs晶片級合成方法。
在本論文中，我們提出了一個基於深度強化學習(Deep Reinforcement Learning)的多目標PB-DMFBs 晶片級合成方法。其中，包括雙深度Q學習網路(Double Deep Q Networks)，DDQN適用於代理選擇動作和動作估計，可以避免潛在的過度樂觀估計問題，並獲取優化的綜合解。藉由調整動作選擇順序和繞線順序，可以獲取製造成本更低的設計方案，並降低繞線複雜度。進一步，我們採行分割方法以有效降低設計複雜度，並增加100%繞線度設計方案的數量。實驗結果顯示，在不使用分割方法的情況下，使用調整電極選擇順序方法可以讓繞線長度平均減少6%、控制端口使用量平均減少10%、100%繞線度解決方案的獲得數量增加203%，CPU時間減少2%。在同時使用分割方法和調整電極選擇順序方法的情況下，100%繞線度解決方案的獲得數量能增加804%，而且CPU時間減少22%。因此，我們所提出的方法對晶片級合成有效且高效，且獲取的最優解比過去研究具有更低的製造成本(控制端口數量更少)，並能為同一生物測定產生多個可使用的解決方案組。

Digital microfluidic biochips (DMFB) have attracted much attention recently due to their portability, high accuracy, and less reagent and sample consumption advantages. Paper-based digital microfluidic biochips (PB-DMFBs) use carbon nanotube ink to print electrodes and control lines on special paper. Hence, the manufacturing cost and production time are far less than traditional digital microfluidic chips. However, since all the circuits of PB-DMFBs are concentrated on the same layer, the chip-level synthesis of PB-DMFBs becomes a challenge. Furthermore, current PB-DMFBs design automation tools must address various design issues, including manufacturing cost, reliability, testability/diagnosability, fault tolerance, and security. Therefore, a more flexible PB-DMFBs chip-level synthesis method is needed.
In this paper, we propose a reinforcement learning-based method for chip-level synthesis of PB-DMFBs. Double Deep Q Networks (DDQN) are suitable for agent selection actions and action estimation, which can avoid potential over-optimistic estimation problems and obtain optimized comprehensive solutions. By adjusting the action selection order and the routing order, design solutions with lower manufacturing costs can be obtained and the routing complexity can be reduced. Further, we adopt the partition method to effectively reduce the design complexity and increase the number of 100% routability design schemes. Experimental results show that our proposed method is not only effective and efficient for chip-level synthesis, but also can generate multiple usable solutions for the same bioassay, and the optimal solution obtained has lower manufacturing cost (less number of control ports) than previous studies, and generate multiple usable solution sets for the same bioassay.

論文審定書i
摘要 ii
Abstract iii
圖目錄 vi
表目錄 ix
第1章 簡介(Introduction) 1
1.1 微流體生物晶片 1
1.2 數位微流體生物晶片 2
1.3 紙基數位微流體生物晶片 2
1.4 研究動機 5
1.5 主要貢獻 8
第2章 相關研究(Related Work) 11
2.1 雙深度Q網路(Double DQN) 11
2.2 考慮液珠控制之PB-DMFBs的合成流程 16
2.3 PB-DMFBs晶片級合成須考慮的限制 19
第3章 問題定義(Problem Definition) 22
3.1 PB-DMFBs晶片級合成的限制和挑戰 22
3.2 PB-DMFB合成問題定義 23
3.3 多目標(Multi-Objective)的PB-DMFB方法 25
3.3.1 可達到的多目標(Multi-Objective) 25
3.3.2 整體方法論中實現各目標之步驟 26
第4章 基於雙深度Q網路的紙基數位微流體生物晶片之晶片級合成方法論 (Multiobjective Double Deep Q-Networks for Chip-Level Synthesis Methodology of Paper-Based Digital Microfluidic Biochips) 29
4.1 環境(Environment)、動作(Action)、狀態(State) 和獎勵(Reward) 29
4.2 雙DQN合成流程 47
4.3 混合動作選擇法(Hybrid Action Selection Method) 54
4.4 迷宮繞線(Maze routing) 60
第5章 實驗成果(Experiment Result) 64
5.1 基礎實驗設置和結果 64
5.2 比較分割方法(Circuit Partition) 67
5.3 比較電極選擇順序(Electrode Order Adjustment) 70
5.4 電極數和使用的控制端口數量比值與100%繞線解數量的關係 71
5.5 線長和使用的控制端口數量之間的權衡(比較是否使用分割和調整電極選擇順序之結果) 72
第6章 結論(Conclusion) 74
參考文獻 75

[1]K. Yang, H. Peretz-Soroka, Y. Liu, and F. Lin, “Novel Developments in Mobile Sensing Based on the Integration of Microfluidic Devices and Smartphones,” Lab on a Chip, vol. 16, no. 6, pp. 943-958, 2016.
[2]M. G. Pollack, A. D. Shenderov, and R. B. Fair, “Electrowetting-Based Actuation of Droplets for Integrated Microfluidics,” Lab Chip, vol. 2, no. 2, pp. 96-101, 2002.
[3]V. Srinivasan, V. K. Pamula, and R. B. Fair, “An Integrated Digital Microfluidic Lab-on-a-Chip for Clinical Diagnostics on Human Physiological Fluids,” Lab on a Chip, vol. 4, no. 4, pp.310-315, 2004.
[4]F. Su, K. Chakrabarty, and R. B. Fair, “Microfluidics-Based Biochips: Technology Issues, Implementation Platforms, and Design-Automation Challenges,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 2, pp. 211-223, 2006.
[5]T.-Y. Ho, J. Zeng and K. Chakrabarty, "Digital Microfluidic Biochips: A Vision for Functional Diversity and more than Moore," IEEE/ACM International Conference on Computer-Aided Design, pp. 578-585, 2010.
[6]T.-Y. Ho, K. Chakrabarty, and P. Pop, "Digital Microfluidic Biochips: Recent Research and Emerging Challenges," IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis I, pp. 335-344, 2011.
[7]H. Ko et al., “Active Digital Microfluidic Paper Chips with Inkjet‐Printed Patterned Electrodes,” Advanced Materials, vol. 26, no. 15, pp. 2335-2340, 2014.
[8]R. Fobel, A. E. Kirby, A. H. Ng, R. R. Farnood, and A. R. Wheeler, “Paper Microfluidics Goes Digital,” Advanced Materials, vol. 26, no. 18, pp. 2838-2843, May, 2014.
[9]N. Ruecha et al., “Paper-Based Digital Microfluidic Chip for Multiple Electrochemical Assay Operated by a Wireless Portable Control System,” Advanced Materials Technologies, vol. 2, no. 3, 1600267, 2017.
[10]G. Tanev and J. Madsen, "A Correct-by-Construction Design and Programming Approach for Open Paper-Based Digital Microfluidics," Symposium on Design, Test, Integration and Packaging of MEMS/MOEMSI, pp. 1-6, 2017.
[11]P. Wang, M. Wang, F. Zhou, G. Yang, L. Qu, and X. Miao, “Development of a Paper-Based, Inexpensive, and Disposable Electrochemical Sensing Platform for Nitrite Detection,” Electrochemistry Communications, vol. 81, pp. 74-78, 2017.
[12]V. Soum et al., “Programmable Contact Printing Using Ballpoint Pens with a Digital Plotter for Patterning Electrodes on Paper,” ACS Omega, vol. 3, no. 12, pp. 16866-16873, 2018.
[13]V. Soum et al., “Affordable Fabrication of Conductive Electrodes and Dielectric Films for a Paper-based Digital Microfluidic Chip,” Micromachines (Basel), vol. 10, no. 2, 109, 2019.
[14]V. Soum, S. Park, A. I. Brilian, O. S. Kwon, and K. Shin, “Programmable Paper-Based Microfluidic Devices for Biomarker Detections,” Micromachines (Basel), vol. 10, no. 8, 516, 2019.
[15]J. A. Berkenbrock, R. Grecco-Machado, and S. Achenbach, “Microfluidic Devices for the Detection of Viruses: Aspects of Emergency Fabrication during the COVID-19 Pandemic and other Outbreaks,” Proceedings of the Royal Society A, vol. 476, no. 2243, 20200398, 2020.
[16]Z. Qin, R. Peng, I. K. Baravik, and X. Liu, “Fighting COVID-19: Integrated Micro-and Nanosystems for Viral Infection Diagnostics,” Matter, vol. 3, no. 3, pp. 628-651, 2020.
[17]M. Tayyab, M. A. Sami, H. Raji, S. Mushnoori, and M. Javanmard, “Potential Microfluidic Devices for COVID-19 Antibody Detection at Point-of-Care (POC): A Review,” IEEE Sensors Journal, vol. 21, no. 4, pp. 4007-4017, 2020.
[18]R. B. Fair et al., “Chemical and Biological Applications of Digital-Microfluidic Devices,” IEEE Design & Test of Computers, vol. 24, no. 1, pp. 10-24, 2007.
[19]T. Zhang et al., “Focusing of Sub-Micrometer Particles in Microfluidic Devices,” Lab on a Chip, vol. 20, no. 1, pp. 35-53, 2020.
[20]V. Narayanamurthy et al., “Advances in Passively Driven Microfluidics and Lab-on-Chip Devices: A Comprehensive Literature Review and Patent Analysis,” RSC Advances, vol. 10, no. 20, pp. 11652-11680, 2020.
[21]Q. Wang, W. He, H. Yao, T.-Y. Ho, and Y. Cai, “SVM-Based Routability-Driven Chip-Level Design for Voltage-Aware Pin-Constrained EWOD Chips,” Symposium on International Symposium on Physical Design, pp. 49-56, 2015.
[22]Q. Wang et al., “Control-Fluidic CoDesign for Paper-Based Digital Microfluidic Biochips,” International Conference on Computer-Aided Design, pp. 1-8, 2016.
[23]W. H. Minhass, P. Pop, and J. Madsen, "System-Level Modeling and Synthesis of Flow-Based Microfluidic Biochips," International conference on Compilers, pp. 225-234, 2011.
[24]J.-D. Li, S.-J. Wang, K. S.-M. Li, and T.-Y. Ho, "Congestion-and Timing-Driven Droplet Routing for Pin-Constrained Paper-Based Microfluidic Biochips," Asia and South Pacific Design Automation Conference, pp. 593-598, 2016.
[25]S. T. Yu and T.-Y. Ho, “Chip-Level Design for Digital Microfluidic Biochips,” International Journal of Automation and Smart Technology, vol. 4, no. 4, pp. 202-207, 2014.
[26]T.-M. Tseng, M. Li, Y. Zhang, T.-Y. Ho, and U. Schlichtmann, "Cloud Columba: Accessible Design Automation Platform for Production and Inspiration," IEEE/ACM International Conference on Computer-Aided Design, pp. 1-6, 2019.
[27]J.-D. Li, S.-J. Wang, K. S.-M. Li, and T.-Y. Ho, “Watermarking for Paper-Based Digital Microfluidic Biochips,” IEEE International Test Conference in Asia, pp. 148-153, 2020.
[28]N.-R. Shih and T.-Y. Ho, “A Multi-Commodity Network Flow Based Routing Algorithm for Paper-Based Digital Microfluidic Biochips,” Asia and South Pacific Design Automation Conference, pp. 73-78, 2021.
[29]J.-D. Li, S.-J. Wang, K. S.-M. Li, and T.-Y. Ho, “Digital Rights Management for Paper-Based Microfluidic Biochips,” IEEE Asian Test Symposium, pp. 179-184, 2018.
[30]Q. Wang et al., “Integrated Control-Fluidic Codesign Methodology for Paper-Based Digital Microfluidic Biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 3, pp. 613-625, 2020.
[31]T.-W. Huang, S.-Y. Yeh, and T.-Y. Ho, “A Network-Flow Based Pin-Count Aware Routing Algorithm for Broadcast-Addressing EWOD Chips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 12, pp. 1786-1799, 2011.
[32]S. S.-Y. Liu, C. Chung-Hung, C. Hung-Ming, and H. Tsung-Yi, “ACER: An Agglomerative Clustering Based Electrode Addressing and Routing Algorithm for Pin-Constrained EWOD Chips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 9, pp. 1316-1327, 2014.
[33]J.-D. Li, S.-J. Wang, K. S.-M. Li, and T.-Y. Ho, "Test and Diagnosis of Paper-Based Microfluidic Biochips," IEEE VLSI Test Symposium, pp. 1-6, 2016.
[34]J.-D. Li, S.-J. Wang, K. S.-M. Li, and T.-Y. Ho, "Design-for-Testability for Paper-Based Digital Microfluidic Biochips," IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, 2017.
[35]J.-D. Li, S.-J. Wang, K. S.-M. Li, and T.-Y. Ho, "Design-for-Reliability and Probability-Based Fault Tolerance for Paper-Based Digital Microfluidic Biochips with Multiple Faults," Asia and South Pacific Design Automation Conference, pp. 62-67, 2022.
[36]J.-D. Li, S.-J. Wang, K. S.-M. Li, and T.-Y. Ho, “Design-for-Reliability and on-the-fly Fault Tolerance Procedure for Paper-Based Digital Microfluidic Biochips with Multiple Faults,” Integration, vol. 89, pp. 185-196, 2023.
[37]R. S. Sutton and A. G. Barto, “Introduction to Reinforcement Learning,” MIT Press, Cambridge, MA, A Bradford Books, 1998.
[38]H. Hasselt, “Double Q-Learning,” Advances in Neural Information Processing Systems, vol. 23, 2010.
[39]V. Mnih et al., “Playing Atari with Deep Reinforcement Learning,” arXiv:1312.5602, 2013.
[40]H. Van Hasselt, A. Guez, and D. Silver, "Deep Reinforcement Learning with Double Q-Learning," the AAAI Conference on Artificial Intelligence, vol. 30, no. 1, 2016.
[41]C.-Y. Chen and J.-L. Huang, "Reinforcement-Learning-Based Test Program Generation for Software-Based Self-Test," IEEE Asian Test Symposium, pp. 73-735, 2019.
[42]K. Rajesh, A. Tirkey, A. Sarkar, and S. Pyne, "Reinforcement Learning Based Droplet Routing Algorithm for Digital Microfluidic Biochips," International Symposium on VLSI Design and Test, pp. 1-6, 2020.
[43]F.-C. Wu, J.-D. Li, K. S.-M. Li, S.-J. Wang, and T.-Y. Ho, "Double DQN for Chip-Level Synthesis of Paper-Based Digital Microfluidic Biochips," Design, Automation & Test in Europe Conference & Exhibition, pp. 350-353, 2021.
[44]C. J. Watkins and P. Dayan, “Q-Learning,” Machine Learning, vol. 8, no. 3, pp. 279-292, 1992.
[45]R. J. Williams, “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning,” Reinforcement Learning, pp. 5-32, 1992.
[46]D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller, "Deterministic Policy Gradient Algorithms," International Conference on Machine Learning, pp. 387-395, 2014.
[47]J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, "Trust Region Policy Optimization," International Conference on Machine Learning, pp. 1889-1897, 2015.
[48]Z. Wang, T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas, "Dueling Network Architectures for Deep Reinforcement Learning," International Conference on Machine Learning, pp. 1995-2003, 2016.
[49]M. G. Bellemare, W. Dabney, and R. Munos, "A Distributional Perspective on Reinforcement Learning," International Conference on Machine Learning, pp. 449-458, 2017.
[50]S. Racanière et al., “Imagination-Augmented Agents for Deep Reinforcement Learning,” Advances in Neural Information Processing Systems, vol. 30, 2017.
[51]J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms,” arXiv:1707.06347, 2017.
[52]D. Silver et al., “Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm,” arXiv:1712.01815, 2017.
[53]D. Ha and J. Schmidhuber, “World Models,” arXiv:1803.10122, 2018.
[54]T. Haarnoja et al., “Soft Actor-Critic Algorithms and Applications,” arXiv:1812.05905, 2018.
[55]C. J. C. H. Watkins, “Learning from Delayed Rewards,” King''s College, Cambridge, 1989.
[56]P.-H. Yuh, C.-L. Yang, and Y.-W. Chang, “BioRoute: A Network-Flow-Based Routing Algorithm for the Synthesis of Digital Microfluidic Biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 11, pp. 1928-1941, 2008.
[57]K. Chakrabarty, “Design Automation and Test Solutions for Digital Microfluidic Biochips,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 57, no. 1, pp. 4-17, 2010.
[58]Y.-C. Lo, B. Li, S. Park, K. Shin, and T.-Y. Ho, “Interference-Free Design Methodology for Paper-Based Digital Microfluidic Biochips,” Asia and South Pacific Design Automation Conference, pp. 79-84, 2021.
[59]M. Abadi et al., “Tensorflow: large-Scale Machine Learning on Heterogeneous Systems,” Software available from tensorflow.org, https://www.tensorflow.org/
[60]G. Brockman et al., “OpenAI Gym,” arXiv:1606.01540, 2016.