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.