Droplet Routing in Digital Microfluidic Biochip using Agglomerative Hierarchical Clustering Jayanti Das1,† , Indrajit Pan1,*,† and Hafizur Rahaman2,† 1 RCC Institute of Information Technology, Kolkata, 700015, India 2 Indian Institute of Engineering Science and Technology, Shibpur, 711103, India Abstract Digital microfluidic biochip (DMFB) has established its potential in different applications like lab-on-chip device to perform pathological analysis and sample testing, air contamination detection, drug discovery and many others related to this. Droplet routing in DMFB is an essential operation. Optimization of different droplet routing aspects are fine tuned to enhance the performance of DMFB. Existing researches have used different traditional optimization techniques to optimize the performance of droplet routing. Use of machine learning mechanism is very less. Early-stage research indicates a wide scope for applying machine learning mechanism in DMFB domain. A clustering-based droplet routing mechanism based on the approach of agglomerative hierarchical clustering (AHC) has been used in this work which finds cluster of electrodes to form a path between source to target. Experimental studies on different test benches show a potential result for the approach in compare to existing research reports. Keywords agglomerative hierarchical clustering, digital microfluidic biochip, droplet routing, fluidic constraints,, optimiza- tion 1. Introduction DMFB is an upgradation over continuous fluid flow-based biochip. Digital microfluidic biochip has introduced microfluidic operations along two-dimensional micro-array of electrodes. It can operate on miniaturized samples. Sample size or volume in DMFB lies in the range of nanoliter or picoliter. Since the chips can operate with such a small volume of samples, it is also known as lab-on-chip device. Electro wetting of di-electric (EWOD) mechanism is used here to control the movement of droplets across microfluidic biochip. Droplets can move along horizontal or vertical direction across two-dimensional micro-array but no diagonal movements are allowed there [1]. Droplets can be controlled by EWOD in such a manner that it can travel from a specific electrode location to another electrode location, where the former electrode is termed as source and the latter is termed as target. Two different droplets can start routing from two different source locations and they can be routed towards a same target electrode where they can mix to perform a bio-chemical reaction. Different samples are thus mixed with specific reagents to perform chemical reactions and end results can be tested for a purpose. Thus, the biochip helps to simulate different bioassay protocols on the chips. Simulation of bioassay protocols helps bio-chemists to use DMFB extensively top perform different trials during their bio-chemical experimentations [2]. Applications of DMFB includes pathological experimentations, air contamination detection, smoke detection, drug discovery and many more. Figure 1 represents a schematic view of DMFB [3]. Schematic view shows that the arrangement is like a parallel glass plate, where two-dimensional micro-array is fabricated on bottom glass plate, and top glass plate is connected with ground. There is a hydrophobic filler medium in-between. Every unit cell of microarray is a separate electrode. A unit cell needs to be addressed distinctly to get electrical actuation. EWOD mechanism suggests that when a The 2024 Sixth Doctoral Symposium on Intelligence Enabled Research (DoSIER 2024), November 28–29, 2024, Jalpaiguri, India * Corresponding author. † These authors contributed equally. " jayanti.das@rcciit.org.in (J. Das); indrajit.pan@rcciit.org.in (I. Pan); rahaman_h@it.iiests.ac.in (H. Rahaman)  0009-0008-2516-7874 (J. Das); 0000-0003-4140-6683 (I. Pan); 0000-0001-9012-5437 (H. Rahaman) © 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings Figure 1: Schematic view of DMFB. Figure 2: Actuation sequence during droplet movement. droplet moves from one cell to another then destination cell is charged with high voltage and electrode underneath of droplet is charged with a ground voltage. This facilitates the droplet to move from low charged electrode to active electrode. Reference to figure 2, a droplet is intending to move from source location 1 to 2. Droplet can move once cell at a time using EWOD. Cell 1 is kept at ground voltage and cell 2 is charged with high voltage, as a result the droplet shifts from 1 to 2 [4]. Droplet movement in DMFB is guided by some fluidic constraints. These fluidic constraints suggest that no two different droplets should be allowed to come at adjacent cells at any particular time or even any two droplets shouldn’t cross adjacent locations at two consecutive time instants. Always a one cell gap is maintained around any droplet which called critical region (figure 3). Droplet routing performance across DMFB needs different types of performance optimization. The aspects of this optimization involve [1]; 1. Minimization of total electrode usage with respect to any bioassay 2. Minimization of total turnaround time and average turnaround time Different optimization algorithms are reported in the literature to address the above issues. However, Figure 3: Critical region of droplet D. use of machine learning based methods are being reported recently and the machine learning domain is mostly unexplored in this aspect. Current work proposes a clustering approach based on agglomerative hierarchical clustering (AHC). It attempts to form cluster of electrodes which can form a routing path for any given droplet between a source – target pair. Bioassays designed by bio-chemists suggest a protocol where a droplet is represented in terms of source-target pair. AHC approach selects most potential electrodes into a single cluster for a given source-target pair and hierarchical clustering helps to track a sequence. A droplet can follow its route according to the sequence identified in the cluster of electrodes to travel from source to target. A bioassay protocol combines multiple define droplets with different combination of source-target pairs. All these droplets are routed together. AHC mechanism considers parallel movement following the fluidic constraints stated above and choose suitable electrodes in individual clusters for every droplet. Droplets here are identified with a separate yet parallel and non-conflicting set of clusters of electrodes so that all of them can travel in parallel without interfering each other. Proposed AHC method has been tested on different standard test benches and experimental findings have been compared with a recently published article. Experimental results are promising. Rest of the article contains a brief literature survey in the following section 2 followed by a discussion on proposed method in section 3. Experimental analysis is discussed in section 4 which is followed by a conclusion in section 5. 2. Literature Survey Article [1] discussed droplet routing scheme in DMFB bypassing contamination zones. A preferred routing region has been identified by using shortest path routing scheme. Then the authors proposed a minimal cost circulation (MCC) algorithm for efficient wash-droplet routing. Droplet routing issue is divided into several smaller problems so that the contaminations between the smaller problems are also identified using a look-ahead prediction approach. Then, the MCC method helps to decrease the execution time and requirement of cells. Article [2] provides an approach that addresses the issues of cross-contamination on biochips with pin constraints. Before placement, this algorithm reduces cross-contamination. Authors provide a wash droplet scheduling and routing method to deal with just one more control pin and no additional assay completion time is needed. It also reduces chip volume and the number of electrodes those are used during the routing time. Additionally, it minimized the number of electrodes needed for routing. Another work demonstrated in [3] manages a cross-contamination-avoidance droplet-routing and optimization technique for DMFB. This approach combines washing procedures into useful droplet- routing phases and targets discontinuous droplet paths. Work has reduced the time taken by droplets to be transported by coordinating the routing of wash droplets with functional droplet-routing stages and carefully modifying the arrival orders of both types of droplets at cross-contamination sites. Additionally, an optimization technique to reduce the quantity of wash operations required in between consecutive routing phases has been proposed. This approach has been evaluated using two real-world bioassay applications. The article [5] has proposed first integrated large functional wash droplet routing. Large wash droplet has more capacity to clean. Functional routing and wash droplet routing are performed concurrently to solve cross-contamination problem. It finds the washing channels through horizontal searching. Authors in [6] propose a new algorithm for droplet routing that controls the situation of live-lock and deadlock. They also provide techniques to enable non-reconfigurable modules, including integrated heaters and detectors, and to enhance the effectiveness of wash droplet routing during routing-based synthesis. Article [4] introduced a droplet routing technique depending on adaptive weighted PSO model to find faulty electrodes and removes residue at the same time. It can effectively bypass inactive electrodes and manage significant flow through electrodes that are contaminated. As a result, it facilitates the identification of problematic areas and the removal of bio-residues from utilized electrodes. The proposed approach is based on an adaptive weighted particle swarm optimization method, in which complementary coefficients are used to build the guiding equation. Two complimentary coefficients are linked to the positive and negative inertia of weights, respectively. Additionally, it has the ability to identify fault locations. Article [7] has focused on an efficient, innovative, sophisticated dual faults detection method. This algorithm detects the number of faults which are frequently occurring in DMFB along with particular types of their categories. It introduces two methods, Internal Electrode Traversal (IET) involves the selection of internal cells for testing within a microfluidic biochip. The test droplets are tested by moving them in certain movement patterns from the source to the sink. Boundary electrodes are tested in the method of Boundary Electrode Traversal (BET). In this method, every node and edge along the border line are tested that is left uncovered during internal cell traversal. The test droplet travels through the boundary electrodes anticlockwise. If a defect is found, this method can identify the faulty location by testing a droplet using backtracking method, otherwise it computes the traversal time for faultless biochip. Authors of [8] proposed a unified contamination-aware routing strategy to decrease the execution time of a bioassay and successfully remove contaminations. They are given a top-down strategy to create potential routing paths, and after that, they build a shortest-path model to choose the best routing paths across all sub-problems. Lastly, for all sub-problems, contaminant removal using washing droplets with washing capability was taken into consideration. Article [9] has introduced a serial-parallel conversion test technique to optimize the routing path in parallel by many droplets of DMFB. A combined method using both priority strategy and genetic algorithms is developed to enhance the optimization of parallel test paths on the biochip. This approach aims to mitigate the randomness inherent in using a single intelligent algorithm for test path optimization. Next, an adaptive approach is introduced to dynamically adjust the number of test tasks, enhancing the effectiveness of distributing test tasks evenly and optimizing parallel testing on the digital microfluidic biochip. Authors in [10] introduce new optimized routing techniques using the deep-reinforcement learning for DMFB. This approach is separated into two phases. All droplets are routed from source to target through a distributed Ape-X DQN algorithm. Deadlocks and route collisions are resolved in the subsequent phase of the algorithm. It uses temporary stalling and detouring of certain droplets. Proposed novel algorithm was curated by combining the DQN approach with the double Q-learning technique. The algorithm also acts in two phases which involves acting followed by learning. Initially it finds all-possible routes of source-target pairs through the actors of this method and then review the policy of using deep neural network. Finally, the knowledge is reposited in a replay buffer. Then, the learner derives the experiences and manipulate routing pathways. Article [11] is based on managing both known and unknown errors using deep-reinforcement learning for DMFB. The primary goal of reinforcement learning is problem solving through the use of intelligent agents that aims to maximize the overall rewards under a specific environment. It suggests and evaluates an algorithm capable of handling various types of errors, which might increase the dependability and effectiveness of biochips. This technique helped to find the most likely and efficient routing path while also helping to unknown faults that occurred throughout the routing process. A droplet routing scheme which uses an indirect encoding mechanism through an evolutionary algorithm and an enhanced Dijkstra-based decoding technique to reduce the arrival time of the droplets has been proposed in [12]. This proposed algorithm considers indirect representation, which is a easy procedure for population initialization. In the decoding technique, the Dijkstra algorithm is extended with a problem-specific cost function to identify a path for each droplet within limited time requirement. Various techniques are introduced to avoid unwanted mixing in both 2D and 3D DMFBs for considering fluidic constraints. Recent studies of some different approaches addressing factors associated with droplet routing in digital microfluidic biochip shows that the scopes and prospect related to droplet routing in DMFB is wide yet the application of machine learning methods and approaches are minimal. Hence, it is quite important to focus on some techniques that can alleviate the process of introducing machine learning based solutions in the domains of DMFB droplet routing. 3. Agglomerative Hierarchical Clustering (AHC) for Droplet Routing AHC is a familiar clustering approach for problems where solutions can be represented in a tree like structure. Microarray of electrodes in DMFB is a two-dimensional patterned array of unit electrodes. Electrodes are connected with each other in sequence, either row-wise or column-wise. Droplet routing path is a combination and sequential arrangement of electrodes. Hence the path and its options can be represented in a level wise tree like organization. Fluidic constraints of droplet routing have been simply considered here to represent parallel routing of droplet and formation of hierarchical cluster following the principle of agglomerative clustering. Let us consider the figure 4 as a sample workflow example. Figure 4 (a) represents two nets. Net 1 is represented by S1 – T1 pair and net 2 is represented by S2 – T2 pair. Figure 4 (a) is [6 × 6] two-dimensional micro-array of electrodes taken as an example and unit cells are marked with yellow are blocked electrodes which can’t be used during routing. Net 1 is having source location (S1) at electrode 1 and target location (T1) at electrode 27. Similarly net 2 is having source (S2) at 4 and target (T2) at 20. Agglomerative hierarchical clusters for both the nets are formed simultaneously and parallelly as shown in figure 4 (b) while maintaining all fluidic constraints and avoiding blocked electrodes marked in yellow. This proposed method is demonstrated with a flowchart in figure 5 and corresponding algorithm is formally represented after the figure. Algorithm 1: Agglomerative Hierarchical Clustering (AHC) for droplet routing in digital microfluidic biochip Input: Source location denotes S, target location denotes T and blockage location denotes in B in state space (DMFB dimensions m x n). Let number of nets (N) = x (considering 2-pin nets) in state space. Step 1: Initialize the position of source (𝑆𝑖 ), target (𝑇𝑖 ) and blockage (𝐵𝑖 ) location of each net. (a) (b) Figure 4: (a) Sample input (b) AHC formation for net 1 and net 2 Step 2: Find out the bounded/ critical region between Si-Ti pair of each net. Step 3: First visit all source locations of each net. Applying Agglomerative Hierarchical Clustering to find the all possible paths from 𝑆𝑖 - 𝑇𝑖 . This Figure 5: Flowchart of Agglomerative Hierarchical Clustering for droplet routing in DMFB formation will only be confined within bounded-region of 𝑆𝑖 - 𝑇𝑖 . Step 4: for (each net i = 1 to x) do (Finding route for each Ni) if 𝑆𝑖 <𝑇𝑖 , then Find next possible location from current location for all 𝑆𝑖 . (If current location is right on the state space, then select immediate left and down location from current location and if current location is left position on state space, then select immediate right and down location from current location) if (𝑆𝑖 +R != 𝐵𝑖 ) and (𝑆𝑖 +D!= 𝐵𝑖 ) (where 𝑆𝑖 +R and 𝑆𝑖 +D denotes right and down location of 𝑆𝑖 respectively.) then check fluidic constraints with all pairs of 𝑆𝑖 - 𝑇𝑖 . Calculate latest Arrival turnaround time (𝐴𝑇𝑚𝑎𝑥 ) Repeat Step 4. end if end if end for Step 5: Exit 4. Experimental Results Table 1 Experimental results of Proposed AHC on Test bench-suite 1 and comparative with [10] LAT AAT TEU Test Name Test Bench Nets Blockage % [10] AHC [10] AHC [10] AHC Test1 12x12_1 12 5.6 32 28 5.04 4.62 62 57 Test2 12x12_2 12 6.2 33 28 9.85 8.88 62 58 Test3 12x12_3 12 7.6 35 30 9.35 8.01 57 52 Test4 12x12_4 12 7.6 26 22 5.3 3.8 59 54 Test5 16x16_1 16 6.6 32 28 9.54 8.28 96 82 Test6 16x16_2 16 5.5 34 28 9.65 8.35 95 82 Test7 16x16_3 16 10.5 37 30 16.33 9.88 94 80 Test8 16x16_4 16 10.2 36 32 9.25 8.2 95 80 Test9 16x16_5 16 15.2 35 32 8.67 8.03 92 102 Test10 16x16_6 16 15.2 38 32 9.21 8.01 92 115 Test11 24x24_1 24 11.1 43 32 9.52 8.52 214 183 Test12 24x24_2 24 10.1 50 29 17.45 12.65 219 182 Test13 24x24_3 24 15.5 48 31 19.67 17.2 220 177 Test14 24x24_4 24 15.8 49 36 12.65 10.11 218 179 Test15 24x24_5 24 20.7 53 38 18.33 15.32 210 172 Proposed method has been implemented using python 3.13.0 on a Ubuntu Linux OS, version 20.0. Test bench-suite 1 [13] was rigorously used to generate the test result and compare the same with the most recent result available in [10]. Table 1 presents the detailed records of experimentation. Details of test bench-suite is given in the left of the table which includes some details like test name, test bench details, total number of nets present, percentage of blockage present. Experimentation was mainly focused on three factors, 1. Latest arrival time (LAT): Maximum time required to complete the whole process as per specifica- tion of test bench 2. Average arrival time (AAT): Average of arrival times for all individual nets under a specific test bench 3. Total electrodes usage (TEU): Total number of unique electrodes used to complete the droplet routing process under each test bench. Comparative analysis is given graphically figure 6 where the performance improved of the proposed method is evident. 5. Conclusion Experimental finding of proposed AHC method for droplet routing in DMFB has shown potential to apply it further for other aspects associated with droplet routing. This concept can be further tuned to address fault aware droplet movement and optimize the electrode actuation pin so that minimum number of pins can be devised to control the electrode actuation during electro-wetting of di-electric. (a) (b) (c) Figure 6: Comparison between proposed method and the work in [10]; (a) (LAT) Latest arrival time (b) (AAT) Average arrival time (c) (TEU) Total electrode usage Further extension of this work can address cross-contamination avoidance in-between two consecutive bio-assay operations on the same DMFB board. Declaration on Generative AI The author(s) have not employed any Generative AI tools. References [1] T. W. Huang, C. H. Lin, T. Y. Ho, A contamination aware droplet routing algorithm for the synthesis of digital microfluidic biochips, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 29 (2010) 1682–1695. doi:10.1109/TCAD.2010.2062770. [2] C. C. Y. Lin, Y. W. Chang, Cross-contamination aware design methodology for pin-constrained digital microfluidic biochips, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30 (2011) 817–828. doi:10.1109/TCAD.2011.2108010. [3] Y. Zhao, K. Chakrabarty, Cross-contamination avoidance for droplet routing in digital microfluidic biochips, in: Proceedings of the 2009 Design, Automation Test in Europe Conference Exhibition, France, 2009, pp. 1290–1295. doi:10.1109/DATE.2009.5090864. [4] S. Mukherjee, I. Pan, T. Samanta, A particle swarm optimization method for fault localization and residue removal in digital microfluidic biochips, Applied Soft Computing 85 (2019) 105839. doi:10.1016/j.asoc.2019.105839. [5] H. Yao, Q. Wang, Y. Shen, T.-Y. Ho, Y. Cai, Integrated functional and washing routing optimization for cross-contamination removal in digital microfluidic biochips, IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems 35 (2016) 1283–1296. doi:10.1109/TCAD.2015. 2504397. [6] S. Windh, C. Phung, D. Grissom, P. Pop, P. Brisk, Performance improvements and congestion reduction for routing-based synthesis for digital microfluidic biochips, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36 (2017) 41–54. doi:10.1109/TCAD. 2016.2557726. [7] A. Saha, M. Majumder, An efficient technique for double faults detection and their locations identification in digital microfluidic biochip, International Journal of Automation and Smart Technology 9 (2019) 65–75. [8] Z. Huang, X. Bai, T. Lan, X. Li, G. Lin, Unified contamination-aware routing method considering realistic washing capacity constraint in digital microfluidic biochips, IEEE Access 8 (2020) 192867– 192879. doi:10.1109/ACCESS.2020.3032675. [9] X. Huang, C. Xu, L. Zhang, C. Hu, W. Mo, Parallel testing optimization method of digital microfluidic biochip, Measurement 194 (2022) 111018. doi:10.1016/j.measurement.2022.111018. [10] B. Saha, B. Das, M. Majumder, A deep-reinforcement learning approach for optimizing homoge- neous droplet routing in digital microfluidic biochips, Nanotechnology and Precision Engineering 6 (2023) 023001.1–023001.12. doi:10.1063/10.0017350. [11] T. Kawakami, C. Shiro, H. Nishikawa, X. Kong, H. Tomiyama, S. Yamashita, A deep reinforcement learning approach to droplet routing for erroneous digital microfluidic biochips, Sensors 23 (2023) 8924. doi:10.3390/s23218924. [12] C. Jiang, R.-Q. Yang, B. Yuan, An evolutionary algorithm with indirect representation for droplet routing in digital microfluidic biochips, Engineering Applications of Artificial Intelligence 115 (2022) 105305. doi:10.1016/j.engappai.2022.105305. [13] F. Su, K. Chakrabarty, Benchmarks for digital microfluidic biochips and synthesis, Department of Electrical and Computer Engineering, Duke University, Durham, NC, 2006.