SGER: Optimal Strategies for Moving Droplets in Digital Microfluidic Systems

微流体系统是能够以非常高的精度操作（例如，处理，存储，分类和分析）非常少量的液体（通常远小于一微升）的设备。在过去的十年中，在阀门、泵和通道等组件的小型化以及将它们集成到硅、玻璃或塑料芯片上方面取得了很大进展。这些系统的制造通常使用来自集成电路和微处理器工业的技术。目标是在芯片上创建一个完整的实验室，它可以用于新的生物医学和化学任务，包括基因组学和蛋白质组学研究，病原体检测和国土安全。第一代微流体装置主要使用的设计是传统组件的缩小版，如微阀，微泵和微通道。然而，最近新一代的微流体系统已经被引入。这些所谓的数字微流体系统利用了只能在非常小的范围内使用的效应。电润湿是这样一种效应：当一个电压加在一个液滴附近，液滴在疏水表面上形成一个头，然后这个液滴在这个电压的响应下变形。通过适当的设计，人们可以建立一个系统，使微小的液滴非常迅速和精确地在表面上移动。这种方法的最大优点是，液体的处理是由软件执行的，并且可以根据想要执行的任务随时重新编程。这提供了传统实验室设备甚至第一代微流体所不存在的灵活性。预计这些数字微流控系统可以同时处理数百或数千个液滴，从而实现大规模并行实验。然而，控制如此大量的液滴是非常重要的：在水库、分析点、反应点和垃圾箱之间移动数百或数千个液滴，就像一个停车场，有些车来了，有些车想离开，还有一些车可能想找一个更好的阴凉的地方。我们的目标是找到所有液滴的最佳运动计划，从而产生一个最小化同时执行所有实验所需时间的策略。理论家们已经证明，类似的问题（比如旅行推销员问题）很难得到最优解。因此，我们在这个项目中的任务是(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.