SGER: Optimal Strategies for Moving Droplets in Digital Microfluidic Systems

微流控系统是能够以非常高的精度处理(例如，处理、存储、分类和分析)非常少量的液体(通常远小于1微升)的设备。在过去的十年里，在将阀门、泵和通道等部件微型化并将其集成到硅片、玻璃或塑料芯片上方面取得了很大进展。这些系统的制造通常使用源自集成电路和微处理器行业的技术。其目标是创建一个完整的芯片实验室，特别是可以用于新的生物医学和化学任务，包括基因组学和蛋白质组学研究、病原体检测和国土安全。第一代微流控设备主要使用的设计是传统组件的缩小版本，如微阀、微泵和微通道。然而，最近又引入了新一代微流控系统。这些所谓的数字微流控系统利用了只有在非常小的范围内才能获得的效果。电润湿就是这样一种效应：当在疏水表面上形成珠子的液滴附近施加电压时，该液滴就会因此而变形。通过适当的设计，人们可以建立能够非常快速和精确地在表面上移动微小液滴的系统。这种方法的最大优点是，液体的处理由软件执行，并可随时重新编程，具体取决于您想要执行的任务。这提供了传统实验室设备甚至第一代微流体所不具备的灵活性。预计这些数字微流体系统可以同时处理数百或数千个液滴，从而实现大规模并行实验。然而，控制如此大量的液滴绝非易事：在水库、分析地点、反应地点和垃圾箱之间移动数百或数千个液滴可以比作停车场，一些汽车到达这里，另一些人想离开，还有一些人可能想找一个更好的、阴暗的地方。我们的目标是为所有液滴找到最优的运动计划，从而产生一种最大限度地减少同时执行所有实验所需的时间的策略。理论家已经证明，类似的问题(如旅行商问题)很难以最优方式解决。因此，我们在这个项目中的任务是(A)发展对问题的良好的理论理解，(B)推导方法和计算机软件来自动生成最优解，以及(C)如果b部分被证明太难，那么找到接近最优但更容易计算的近似。最终结果应该是这样一个系统，它将数字微流控系统的描述加上所有液滴的所有开始和目标状态作为输入，并生成一个计划作为输出，在(接近)最佳时间内将所有液滴从开始移动到目标。

Microfluidic systems are devices that can manipulate (e.g., handle, store, sort, and analyze) very small amounts of liquids (often much less than a microliter) with very high accuracy. Over the past decade, much progress has been achieved in miniaturizing components such as valves, pumps, and channels, and integrating them onto silicon, glass, or plastic chips. The anufacture of these systems often uses techniques derived from the integrated circuit and microprocessor industry. The goal is to create a complete lab on a chip, which could be employed in particular for novel biomedical and chemical tasks, including genomics and proteomics research, pathogen detection, and homeland security.The first generation of microfluidic devices has mostly used designs that are downscaled versions of conventional components, such as micro valves, micro pumps, and micro channels. However, recently a new generation of microfluidic systems has been introduced. These so-called digital microfluidic systemsexploit effects that are only available at very small scales. Electrowetting is such an effect: when a voltage is applied near a droplet that forms a bead on a hydrophobic surface then this droplet deforms in response to this voltage. By appropriate design, one can build systems that can move tiny droplets very rapidly and precisely across a surface. The big advantage of this approach is that the handling of liquid is performed by software and re-programmable at any time, depending on the task one wants to perform. This provides a level of flexibility that does not exist in traditional lab equipment or even first generation microfluidics.It is expected that these digital microfluidic systems could handle hundreds or thousands of droplets simultaneously, resulting in massively parallel performance of experiments. However, controlling such a large number the droplets is highly non-trivial: moving hundreds or thousands of droplets between reservoirs, analysis sites, reaction sites, and waste bins could be compared to a parking lot where some cars arrive, others want to leave, and yet others maybe want to find a better, shady spot. Our goal is to find the optimal motion plan for all droplets, resulting in a strategy that minimizes the time it takes to perform all experiments simultaneously. Theorists have shown that similar problems (such as the traveling salesman problem) are very difficult to solve optimally. Thus, our task in this project are to (a) develop a good theoretical understanding of the problem, (b) derive methods and computer software to automatically generate optimal solutions, and (c) if part b proves to be too hard, then find approximations that are close to optimal but easier to compute. The end result should be a system that takes as input a description of a digital microfluidic system plus all the start and goal states of all droplets, and generates as output a plan that moves all droplets from start to goal in (near) optimal time.