F*: Synchronous, and Collision-Aware Multi-Cell Routing on DEP Biochips for Efficient Cell Transportation

Abstract

Efficient cell transportation is crucial for automating lab-on-chip systems. CMOS-based dielectrophoresis (DEP) biochips provide low-voltage, programmable control over individual cells, making them suitable for large-scale applications. However, when using large electrode arrays such as 128×128, traditional one-by-one routing approaches encounter major limitations, including frequent collisions, inter-cell interference, and a sharp increase in cell transportation time. This work proposes F* (Forbidden Dictionary enhanced A*), a scalable multi-cell routing algorithm that synchronizes cell movements and resolves conflicts through a global forbidden dictionary. The algorithm supports variable-sized cells and considers constraints such as contamination regions and exclusive target assignments. Experimental results on a 128×128 DEP chip with 90 rectangular cells, ranging from 1×1 to 5×5, demonstrate that F* completes routing in 4 minutes and 34 seconds, compared to 1 hour, 37 minutes, and 14 seconds using conventional one-by-one A* routing. This corresponds to a 95.3 percent reduction in both cell transportation time and control pattern count. The proposed method enables efficient, large-scale DEP operations and paves the way for high-throughput and fully automated biochip platforms in biomedical applications.

Lin-Hung Lai

Visiting Student Researcher @ Stanford University

My research interests include distributed robotics, mobile computing and programmable matter.