ABSTRACT Title of dissertation: PLANNING FOR AUTOMATED OPTICAL MICROMANIPULATION OF BIOLOGICAL CELLS Sagar Chowdhury, Doctor of Philosophy, 2013 Dissertation directed by: Professor Satyandra K. Gupta Department of Mechanical Engineering Optical tweezers (OT) can be viewed as a robot that uses a highly focused laser beam for precise manipulation of biological objects and dielectric beads at micro-scale. Using holographic optical tweezers (HOT) multiple optical traps can be created to allow several operations in parallel. Moreover, due to the non-contact nature of manipulation OT can be potentially integrated with other manipulation techniques (e.g. microfluidics, acoustics, magnetics etc.) to ensure its high through- put. However, biological manipulation using OT suffers from two serious draw- backs: (1) slow manipulation due to manual operation and (2) severe effects on cell viability due to direct exposure of laser. This dissertation explores the prob- lem of autonomous OT based cell manipulation in the light of addressing the two aforementioned limitations. Microfluidic devices are well suited for the study of biological objects because of their high throughput. Integrating microfluidics with OT provides precise position control as well as high throughput. An automated, physics-aware, planning approach is developed for fast transport of cells in OT as- sisted microfluidic chambers. The heuristic based planner employs a specific cost function for searching over a novel state-action space representation. The effective- ness of the planning algorithm is demonstrated using both simulation and physical experiments in microfluidic-optical tweezers hybrid manipulation setup. An indirect manipulation approach is developed for preventing cells from high intensity laser. Optically trapped inert microspheres are used for manipulating cells indirectly ei- ther by gripping or pushing. A novel planning and control approach is devised to automate the indirect manipulation of cells. The planning algorithm takes the mo- tion constraints of the gripper or pushing formation into account to minimize the manipulation time. Two different types of cells (Saccharomyces cerevisiae and Dictyostelium discoideum) are manipulated to demonstrate the effectiveness of the indirect manipulation approach. Planning for Automated Optical Micromanipulation of Biological Cells by Sagar Chowdhury Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2013 Advisory Committee: Professor Satyandra K. Gupta, Chair/Advisor Professor Hugh Bruck Professor Jaydev P. Desai Associate Professor Nikhil Chopra Associate Professor Wolfgang Losert (Dean?s representative) EP Copyright by Sagar Chowdhury 2013 Dedication To my wonderful parents and beloved brother ii Acknowledgments First and foremost I would like to thank Dr. Satyandra K. Gupta, my advi- sor and mentor for giving me the opportunity to conduct research under his guid- ance. His boundless energy and attitude of accepting nothing-but-the-best helped me refining my skills to become a better researcher every single day. His wonderful analytical skills and motivational power never let me feel short of energy in dealing with difficult research problems. This dissertation is the result of a collaboration between roboticists and bio- physicists. I would like to express my thanks to Dr. Wolfgang Losert for providing me constant support in conducting challenging experiments with biological cells in Biodynamics Laboratory. His close monitoring in conducting experiments and thoughtful insights helped me refining several methods presented in this dissertation. I would like to thank Dr. Hugh Bruck, Dr. Jaydev P. Desai, and Dr. Nikhil Chopra for serving in my dissertation committee despite of having busy academic and research responsibilities of their own. I would also take this opportunity to thank Dr. John P. Wikswo and Dr. Kevin T. Seale from Vanderbilt University for supplying microfluidic chambers to conduct experiments with optical tweezers. I also want to thank National Science Foundation for supporting my disser- tation research work. Many thanks to the University of Maryland, Department of Mechanical Engineering, and the Institute of Systems Research for providing re- search facilities and administrative support. I would also like to thank Ashis Banerjee for his help and advice when I first iii started working on optical tweezers. I am grateful to him for being prompt in answering all my questions despite of his busy research commitments at MIT. I would also like to thank Atul Thakur for being such a good friend. I will never forget all the nights and days we spend together in Simulation Based System Design Laboratory in designing new algorithms. His constructive criticism always helped me to improve my technical skills. I was lucky to have Petr ?Svec as a collaborator throughout my PhD. I would like to thank him for providing me rigorous training in robot motion planning. I am grateful to him for spending hours and hours in front of white board describing novel algorithms that laid out the foundations for my motion planning skills. I would like to thank former Biophysics Laboratory member Brian Koss for giving me extensive laboratory training on handling sophisticated cell cultures. I would also like to thank another former Biophysics Laboratory member Andrew Pomerance for developing preliminary software to control optical tweezers. I also want to thank current Biophysics Laboratory members - Chenlu Wang, Meghan Driscoll, Can Guven, and Xiaoyu Sun for providing me with cell samples to conduct experiments. I am thankful to my colleagues Krishnanand Kaipa, Carlos Morato, Michael Joseph Kuhlman, Brual Shah, Joshua Langsfeld, Boxuan Zhao, Wei Shang, Luke J. Roberts, Andrew Vogel, and Gregory Krummel in Simulation Based System Design Laboratory (SBSD) and Advanced Manufacturing Laboratory (AML) for their sup- port and words of encouragement. I would like to thank my past colleagues Arvind Ananthanarayanan, Madan Dabbeeru, Timothy Hall, Adam Montjoy, Alexander iv Weissman, Peyman Karimian, and Wojciech Bejgerowski for being great friends. I also want to thank all my dear friends: Saurabh Paul, Subhadeep De, Koushik Pal, Sandip Halder, Rajarshi Roy, Sujal Bista, and many others for making my staying in Maryland a memorable one. I am also thankful to my brother Shaiket Chowdhury, sister-in-law Nandita Majumder, and nephew Saimantik Chowdhury for all the good wishes that helped me focused throughout my PhD. Finally, I would like to extend my deepest gratitude to my parents, Prohmod Ranjan Chowdhury and Ratna Sree Chowdhury for their emotional support and affection throughout my life. v Table of Contents List of Tables ix List of Figures x List of Abbreviations xii 1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Research Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Dissertation scope and Outline . . . . . . . . . . . . . . . . . . . . . . 12 2 Literature Review 14 2.1 Optical Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Optical Tweezers Instrumentation . . . . . . . . . . . . . . . . 18 2.1.2 Laser exposure using direct trapping . . . . . . . . . . . . . . 22 2.1.3 Indirect Manipulation of Cells . . . . . . . . . . . . . . . . . . 24 2.1.4 Comparison with Other Approaches for Manipulating Cells . . 31 2.2 Hybrid manipulation systems . . . . . . . . . . . . . . . . . . . . . . 37 2.3 Robot Motion Planning and Control . . . . . . . . . . . . . . . . . . 40 2.4 Robotic grasping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.5 Pushing based manipulation . . . . . . . . . . . . . . . . . . . . . . . 50 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3 Automated Cell Transport in Optical Tweezers-Assisted Microfluidic Cham- bers 55 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 Simulations of cell motion in microfluidic chamber . . . . . . . . . . . 60 3.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.2 Simulation of cell motion . . . . . . . . . . . . . . . . . . . . . 61 3.2.3 Modeling of collision forces . . . . . . . . . . . . . . . . . . . . 62 3.2.4 Modeling of fluid flow . . . . . . . . . . . . . . . . . . . . . . . 63 3.2.5 Workspace simulator design . . . . . . . . . . . . . . . . . . . 67 3.2.6 Building of the probability table . . . . . . . . . . . . . . . . . 68 3.3 Motion planning for automated transport of cells . . . . . . . . . . . 69 3.3.1 Motion planning problem formulation . . . . . . . . . . . . . . 69 3.3.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3.3 Motion planning approach . . . . . . . . . . . . . . . . . . . . 70 3.3.3.1 State-action space representation for planning . . . . 71 3.3.3.2 Cost function . . . . . . . . . . . . . . . . . . . . . . 72 3.3.3.3 Planning algorithm . . . . . . . . . . . . . . . . . . . 75 3.4 Results and discussions . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.4.1 Experimental setup and methods . . . . . . . . . . . . . . . . 77 vi 3.4.2 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.4.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . 83 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4 Enhancing Range of Transport in Optical Tweezers Assisted Microfluidic Chambers Using Automated Stage Motion 90 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.2 Problem formulation and overview of approach . . . . . . . . . . . . . 95 4.3 Selecting ensemble shape and locations . . . . . . . . . . . . . . . . . 100 4.4 Path planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.4.1 Trap Path Planning . . . . . . . . . . . . . . . . . . . . . . . . 107 4.4.2 Stage Path Planning . . . . . . . . . . . . . . . . . . . . . . . 109 4.4.3 Modeling of Speed Constraints Based on the Trapping Force Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.5 System architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5 Robust Gripper Synthesis for Indirect Manipulation of Cells using Optical Tweezers 118 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.2 Gripper synthesis problem formulation . . . . . . . . . . . . . . . . . 122 5.3 Optimization functions and constraints . . . . . . . . . . . . . . . . . 123 5.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.4.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . 126 5.4.2 Gripper synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.4.3 Gripper performance evaluation . . . . . . . . . . . . . . . . . 130 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 6 Automated Manipulation of Biological Cells Using Gripper Formations Con- trolled By Optical Tweezers 136 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.2 Problem overview and terminology . . . . . . . . . . . . . . . . . . . 140 6.2.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.2.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . 144 6.2.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.2.4 Solution approach . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.3 Path planning for gripper formation . . . . . . . . . . . . . . . . . . . 145 6.3.1 State-action space representation for planning . . . . . . . . . 146 6.3.2 Cost function . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 6.4 Feedback control for gripper formation . . . . . . . . . . . . . . . . . 151 6.5 Results and discussions . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.5.1 Experimental setup and method . . . . . . . . . . . . . . . . . 154 6.5.2 Simulation results of path planning . . . . . . . . . . . . . . . 156 6.5.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . 160 vii 6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 7 Automated Indirect Manipulation of Irregular Shaped Cells With Optical Tweezers for Studying Collective Cell Migration 165 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7.2 Problem overview and terminology . . . . . . . . . . . . . . . . . . . 168 7.2.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . 171 7.2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 7.3 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 7.3.1 Solution approach . . . . . . . . . . . . . . . . . . . . . . . . . 172 7.3.2 State-action space representation . . . . . . . . . . . . . . . . 173 7.3.3 Image processing . . . . . . . . . . . . . . . . . . . . . . . . . 176 7.3.4 Motion goal for gripper formation . . . . . . . . . . . . . . . . 178 7.3.5 Global path planner . . . . . . . . . . . . . . . . . . . . . . . 179 7.3.6 Formation control . . . . . . . . . . . . . . . . . . . . . . . . . 180 7.4 Results and discussions . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.4.1 Cell preparation and experimental setup . . . . . . . . . . . . 181 7.4.2 Experimental results . . . . . . . . . . . . . . . . . . . . . . . 183 7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 8 Conclusions 188 8.1 Intellectual Contributions . . . . . . . . . . . . . . . . . . . . . . . . 188 8.2 Anticipated Benefits . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 8.3 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Bibliography 200 viii List of Tables 2.1 Summary of optical tweezer setups . . . . . . . . . . . . . . . . . . . 34 2.2 Summary of materials, size, and manipulation type . . . . . . . . . . 36 5.1 Performance of the synthesized grippers . . . . . . . . . . . . . . . . . 134 6.1 Rules used by the formation generator g to determine the positions of beads inside the gripper . . . . . . . . . . . . . . . . . . . . . . . . 152 6.2 Performance of designed grippers . . . . . . . . . . . . . . . . . . . . 157 7.1 Experiments of cell viability for direct trapping, direct gripping and indirect gripping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 ix List of Figures 1.1 Scaling of attractive forces with the scaling down in size . . . . . . . 2 1.2 Schematic illustration of optical trapping . . . . . . . . . . . . . . . . 3 1.3 Hybrid manipulation comprising of OT and microfluidics . . . . . . . 5 1.4 Dictyostelium discoideum cells arranged in a pattern . . . . . . . . . 6 1.5 Cell is manipulated by gripper . . . . . . . . . . . . . . . . . . . . . . 8 1.6 Collective migration of suspended Dictyostelium discoideum cells under the influence of cAMP . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Schematic illustration of scanning mirror based optical tweezers system 21 2.2 Schematic illustration of Diffractive optical element (DOE) based op- tical tweezers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Schematic illustration of Diffractive optical element (DOE) based op- tical tweezers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 Schematic illustration of two, six, and four bead arrangements to manipulate cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.5 Schematic illustration of a electromagnetic-microfluidics hybrid cell manipulation system . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 Schematic illustration of a opto-fluidic hybrid cell manipulation system 39 2.7 Schematic illustration of a OT-microfluidic hybrid cell manipulation system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.8 Schematic illustration of a OT-microfluidic hybrid cell sorting system 41 3.1 Sequential cleaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 Measurement of flow vectors . . . . . . . . . . . . . . . . . . . . . . . 64 3.3 Holographic optical tweezers (HOT) cell transport workstation . . . . 68 3.4 Illustration of cost function . . . . . . . . . . . . . . . . . . . . . . . 72 3.5 m? ? coupling cost function . . . . . . . . . . . . . . . . . . . . . . . 73 3.6 Effects of fluid force weight parameter and release threshold param- eter on cell trajectories . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.7 Automated transport of two cells to their respective goals to control cell population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.8 Three-stage probability tree of a cell successfully reaching the exit . . 86 4.1 A schematic overview of a microfluidic device . . . . . . . . . . . . . 92 4.2 A schematic overview of cell manipulation operation . . . . . . . . . . 94 4.3 Illustration of problem formulation . . . . . . . . . . . . . . . . . . . 96 4.4 A schematic illustration of ensemble shapes . . . . . . . . . . . . . . . 101 4.5 Turning around tight corners may require relative repositioning within linear arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.6 A schematic overview of planning approach . . . . . . . . . . . . . . . 104 4.7 Optical tweezers setup with motorized stage . . . . . . . . . . . . . . 106 4.8 Transport of 2 F1m beads to their corresponding goal locations inside the ensemble formation using trap motion . . . . . . . . . . . . . . . 108 x 4.9 Transport of the ensemble from an initial location to a final location using stage motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.10 Distribution of particles to their corresponding microNet locations . . 113 5.1 Direct vs. indirect manipulation using OT . . . . . . . . . . . . . . . 120 5.2 Manipulated object and contact positions of the gripper beads . . . . 124 5.3 Intensity calculation of the laser beam imposed on the gripped object 127 5.4 Holographic Optical Tweezers based cell manipulation system . . . . 128 5.5 Different gripper configurations . . . . . . . . . . . . . . . . . . . . . 130 5.6 Transportation of a yeast cell using the synthesized gripper . . . . . . 132 5.7 Trapping force components . . . . . . . . . . . . . . . . . . . . . . . . 133 6.1 Gripper formations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.3 Workspace with a spherical cell and beads . . . . . . . . . . . . . . . 145 6.4 Manipulation approach . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.5 Gripper formation with all the direction vectors . . . . . . . . . . . . 148 6.6 Cost function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.7 Transport time for G4 and G6 gripper formations . . . . . . . . . . . 153 6.8 Transport time for G2 and G3 gripper formations . . . . . . . . . . . 154 6.9 Indirect transport of a bead using the 3-bead gripper formation . . . 158 6.10 Indirect transport of a bead using the 6-bead gripper formation . . . 159 6.11 Releasing a cell from the gripper . . . . . . . . . . . . . . . . . . . . . 159 7.1 Collective cell migration during chemotaxis . . . . . . . . . . . . . . . 167 7.2 Gripper formation state and cell state . . . . . . . . . . . . . . . . . . 169 7.3 Gripper formation-cell ensemble maneuvers . . . . . . . . . . . . . . . 170 7.4 Solution approach and OT setup . . . . . . . . . . . . . . . . . . . . 173 7.5 Image processing steps . . . . . . . . . . . . . . . . . . . . . . . . . . 177 7.6 Pushing a Dictyostelium cell . . . . . . . . . . . . . . . . . . . . . . 183 7.7 Re-orientation of a Dictyostelium cell . . . . . . . . . . . . . . . . . 184 7.8 Three different manipulation approaches . . . . . . . . . . . . . . . . 186 8.1 Changing in cell motion due to the presence of a bead . . . . . . . . 196 xi List of Abbreviations OT Optical tweezers HOT Holographic optical tweezers AFM Atomic force microscopy PFM Photonic force microscopy AOD Acousto-optic deflector DOE Diffractive optical element DOF Degrees of freedom SLM Spatial light modulator PDMS polydimethylsiloxane GPU Graphics processing unit CPU Central processing unit RBC Red blood cell RPE Representative pattern element CFD Computational fluid dynamics SIPLE Semi implicit method for pressure linked equation PRM Probabilistic roadmap RRT Rapidly exploring randomized tree MDP Markov decision process POMDP Partially observable Markov decision process cAMP Cyclic adenosine monophosphate OpenCV Open source computer vision library PI Proportional integral controller xii Chapter 1 Introduction 1.1 Background One of the biggest challenges in biological researches in micro and nano scale is to understand the change of behavior that occurs with the scaling down in size. The effects of forces that are negligible at macroscopic scale may become dominant in micro and nano scale. For example, gravity plays no longer important role, rather forces like electrostatic, van der Waals etc. become dominant at micro and nano scale [ANBN07]. Figure 1.1 illustrates the effects of scaling in attractive forces between a sphere of radius r with a cylinder of height 8r and radius 4r [ANBN07]. It shows magnetic force dominates over gravitational force as the radius goes below 1 m. The forces like electrostatic and van der Waals that are generally ignored in designing macro-scale manipulators become dominant over gravitational forces as r goes below 10?4 m. Macroscopic techniques that exploit the gravitational forces can no longer be applicable for manipulation of objects in micro and nano scale. This change of be- havior due to the scaling down in size encourages the researchers to come up with new manipulation techniques for the biological objects at micro and nanoscale. AFM (Atomic Force Microscope) [RWG+10], electrophoresis [Vol06], magnetic manipula- tion [SVC+08], optical tweezers (OT) [ADY87], microfluidic techniques [CSW+11], 1 Figure 1.1: Scaling of attractive forces [ANBN07]: For r < 1 m, the magnetic force is sufficient to lift the sphere. Below r = 104 m, the electrostatic force dominates over gravity, and for r < 107 m, the van der Waals force is higher than the weight of the sphere acoustics [DLK+12], use of microfabricated tools [KDG12a, KYY+12, KDG12b, KDG13, KDG11] etc. are some of the well known manipulation techniques at micro and nano scale. Unlike most of the other manipulation techniques OT provides a non-invasive means of manipulation. OT is particularly suitable for precise manip- ulation. It can apply a force in order of pN with an accuracy of the order of aN. Hence, it can provide a position accuracy of the order of angstrom. Targeted cell manipulation is becoming increasingly popular in various cell studies, for example, how cells respond to changes in environment both internally and externally, how do they interact with each other, or how do they undergo complex processes such as differentiation etc. Traditionally the studies listed here are conducted over a large population or ensemble of cells that leave out various 2 insights mainly due to the difference in behavior in individual cell. Targeted analysis over a small population will provide more insight into the system level properties of signaling pathways and their dependence on in individual cell properties, e.g. cellular age, degree of development, cell cycle progression etc. High position and force accuracy make OT suitable for targeted manipulation of cells. Throughput of targeted OT manipulation can be significantly improved by integrating it with other gross manipulation techniques e.g. microfluidics, acoustics, magnetic etc. [MSD03]. Figure 1.2: Schematic illustration of optical trapping: the trapped particle is steered by the laser beam The interaction of a particle with an optical trap is schematically depicted in Figure 1.2. Particles move randomly due to Brownian motion in a fluid medium. A strongly focused laser beam is used to exert optical gradient and scattering forces on a particle, which results in trapping the particle at the focal point of the laser 3 [ADBC86, Ash92]. By controlling the laser beam, the trapped particle can be trans- ported precisely to the desired location without any physical contact. Holographic optical tweezers (HOT) uses a spatial light modulator (SLM) that can split the laser to create multiple traps to facilitate manipulation of multiple particles simultane- ously. Unfortunately, most of the OT manipulation tasks are conducted manually and hence it is slow. Slow manual manipulation makes OT hard to carry out many systematic biological studies that need to be properly timed to exhibit the desired motility. In order to make OT a useful manipulation tool for sophisticated biologi- cal studies real-time and automated planning approaches need to be developed. In the following sections we will discuss OT manipulation in the context of biological studies to identify challenges in developing automated planning algorithms. 1.2 Motivation As discussed in previous section, OT is an emerging tool to manipulate mi- cro and nonoscale biological objects in fluid medium. Although OT is particularly useful for single cell manipulation, throughput can be significantly improved by in- tegrating it with other gross-manipulation techniques e.g. microfluidics. The hybrid manipulation techniques will provide high throughput as well as precise manipula- tion control. An example of such microfluidic device is illustrated in Figure 1.3. This mi- crofluidic device includes around 10, 000 net-like structures to capture cells inside them. However, the number of cells inside the nets cannot be controlled since the manipulation is solely dependent on the fluid flow which subjects to change with 4 Figure 1.3: Hybrid manipulation comprising of OT and microfluidics (Courtesy: Dr. John P. Wikswo and Dr. Kevin T. Seale (Vanderbilt University)) the variation in number of cells at inlet. OT can be integrated with microfluidics to control the equal distribution of cells inside the nets by taking the cells out from crowded nets and placing them in empty nets or to the exits of the chamber. Manual cleaning of large number of nets will require large preparation time for biological experiments that may alter the outcome. The automated approaches need to ac- count for the physics of microfluidic chamber in order to move the cells reliably with the presence of fluid flow. Moreover, the planning environment frequently changes 5 Figure 1.4: Dictyostelium discoideum cells arranged in a pattern: cells are killed due to direct exposure to laser (Image courtesy: Chenlu Wang and Dr. Wolfgang Losert) due to the fluid flow and random Brownian motion of cells in microscale. Plan- ning algorithm needs to have fast replanning capability to cope up with changing environment inside microfluidic chamber. Another big challenge in integrating OT with microfluidics is the workspace size mismatch. OT can operate in a space of 100 F1m ? 100 F1m whereas microfluidic chamber has a dimension in the range of mm ? mm. OT has to be facilitated with long distance transport capability in order to harness the high throughput advantage of microfluidics in a hybrid manipulation setup. The planning strategies have to be developed accordingly to accommodate the long distance transport operation along with fine manipulation using optical trap planning. Cells need to be arranged in a certain pattern and observed for a reasonable 6 time length in order to study the evolving behavior due to their interaction with each other. Cells can also be actively nudged during observation to study the under- lying mechanism behind their collective behavior. OT can be used to trap different cells and arrange them in pattern. However, direct exposure of laser to the cells may inflict photodamage that can affect their physiological behavior. Vegetative Dictyostelium discoideum cells are arranged in a pattern of the alphabet ?A? in Figure 1.4 by directly trapping them with OT. Some of the cells are disintegrated while trapping them due to direct exposure to laser. Rather than trapping directly, cells can be manipulated indirectly using inert microspheres as grippers. Each mi- crosphere can be optically trapped to act as a robotic finger to hold and manipulate the biological cell indirectly. Figure 1.5 illustrates a gripper which is made of six inert silica microspheres directly trapped by multiplexed laser traps to manipulate a Saccharomyces cerevisiae cell indirectly. The arrangement of microspheres is important to ensure robust gripping as well as minimum laser exposure to the cell. A computational synthesis foundation needs to be developed for designing gripper configurations for the cells that will ensure robust gripping as well as minimum laser exposure while transporting them towards certain goal locations. Manual control of multiple laser traps for indirect manipulation of cell us- ing gripper formations is nearly impossible. Hence, there is a need for automated planner that can handle multiple lasers simultaneously. The interactions among multiple lasers for indirect manipulation of cell using the gripper formation makes the planning challenging. The planner also needs to be characterized in terms of manipulation speed, laser power, and the resulting exposure of laser intensity to the 7 Figure 1.5: Saccharomyces cerevisiae cell is manipulated indirectly using the gripper made of inert silica beads directly trapped by laser manipulated cell. Polarized Dictyostelium discoideum cells are used as model organism to study collective migration of cancer cells. Figure 1.6 shows an example of collective migra- tion of polarized Dictyostelium discoideum suspended in water under the influence of chemotaxis cAMP. In order to understand the underlying migration behavior, cells need to be manipulated individually and arranged in some predefined patterns to see different outcomes. However, Dictyostelium discoideum are very sensitive to laser and need to be ensured zero laser exposure in case of OT manipulation. While gripper formations can prevent the cell from a large portion of laser, it cannot elim- inate entire exposure. Hence, manipulating Dictyostelium discoideum cells using gripper formations is not favorable to their viability. A new indirect manipulation approach needs to be developed that ensures zero exposure to the cell. This disser- tation describes the development of computational tools that can exploit the physics 8 Figure 1.6: Collective migration of suspended Dictyostelium discoideum cells un- der the influence of cAMP (Image courtesy: Chenlu Wang and Dr. Wolfgang Losert) of the system to automate the cell manipulation using optical tweezers. 1.3 Research Issues This dissertation identifies three fundamental research issues or challenges in order to perform autonomous manipulation of cells using optical tweezers. Following is the description of the research issues in details. 1. Utilization of physics of the system for effective planning: Microparticles im- 9 mersed in a fluid medium exhibit random stochastic motion due to Brownian motion. Moreover, the presence of external fluid flow in case of microfluidic chamber influences the OT manipulation since particles have a chance to get knocked out of the traps while moving across the fluid streamlines. The plan generated without considering the physics of the system may lead to the path that is risky in terms of successful manipulation or requires more laser power to execute. As mentioned earlier, high laser power will lead to severe pho- todamage to the trapped cell. In case of microfluidic cleaning operation as mentioned in section 1.2, cells need to be released inside the OT workspace so that fluid flow can take them outside the chamber. The release locations need to be carefully selected so that cells have higher probability of reaching the exits of the chamber. This dissertation explores the use of physically ac- curate simulations to estimate the probability of success for the cells to reach one of the exists of the microfluidic chamber with the influence of fluid flow. The estimated probability can be used to enhance the performance of realtime planner. However, the simulations need to be performed at very small time intervals (in the order of microseconds). Hence, offline simulations can be used to generate a probability table at discrete points in the OT workspace. The probability table generated by offline simulations can then be used to increase the effectiveness of the real-time planner. 2. Preventing cells from direct exposure of laser during optical manipulation: Ex- posure to laser due to direct trapping during OT manipulation negatively af- 10 fects physiological activities of cells. Cells can be manipulated indirectly with the gripper formations or pushing formations while preventing them from dan- gerous laser. The gripping or pushing formations can be created by directly trapped inert microspheres. The arrangement of the microspheres inside the formations need to be carefully designed so that cells can be robustly manip- ulated as well as the laser exposure remains to be minimum. The interactions of the laser cones among themselves as well as the microspheres need to be considered to be able to generate effective configurations which is impossible to do manually. Hence, this dissertation develops computational synthesis foun- dations to automatically design the microsphere configurations that facilitates robust manipulation of cell with minimal laser exposure. 3. Concurrent grasping and planning for indirect manipulation of cells: Manip- ulation of cells using gripper or pushing formations requires moving multiple traps simultaneously which is time consuming to perform manually. However, automated manipulation using microsphere formations is challenging for three reasons. Firstly, all the particles which are not directly trapped by laser are constantly moving in the workspace due to Brownian motion. That means the actual position, velocity, and acceleration of any particle are not known in advance. The environment of the OT workspace changes rapidly due to the random motion of the particles. Thus, any planning algorithm needs to have fast replanning capability to handle the dynamic nature of the workspace environment. Secondly, the planning has to deal with noisy images. The po- 11 sitions of the particles inside the formations are difficult to estimate. Thirdly, the trapping power is not uniform all over the workspace and hence, the trap- ping effectiveness is not uniform everywhere. The planner has to provide more time for the microparticles to move to the formation where the trapping power is less. The planning algorithm also needs to account for motion constraints specific to a particular formation in order to reliably manipulate cells. This dissertation investigates the use of feedback policy alongside fast planning algorithm to ensure robust manipulation of cells using gripper or pushing for- mations. The dynamic model of the laser trap can be utilized during planning for better estimation of the positions of microparticles inside the formations. 1.4 Dissertation scope and Outline Currently, optical tweezers is used for various cell manipulation operation rang- ing from transport to stretching. However, this dissertation focuses on challenging operations that are challenging for a human operator. Hence, cell localization, ro- tation, transport, sorting, gripping, pushing, and mechanical probing are termed as cell manipulation. Microfluidics is a widely used cell manipulation tools. Hence, OT assisted microfluidics is demonstrated as an example for hybrid manipulation setup in this dissertation. Similar approaches can be translated to other hybrid setup with Optical tweezers e.g. magnetics, electrophoresis, or acoustics. Automated cell manipulation is demonstrated using two types of cells namely Saccharomyces cerevisiae and Dictyostelium discoideum. Saccharomyces cerevisiae is a Yeast which is a popular model organism for studying eukaryotic cell biology. It can be 12 easily cultivated in the laboratory. The detection of cells is also easy since they can be approximated with spheres. Dictyostelium discoideum is used as an impor- tant model organism for studying cancer cell migration. The dynamically changing shapes during migration poses unique challenge during automated manipulation. Amorphous silica microspheres are chosen as material for designing gripper or pusher formations for indirect manipulation of cells. The rest of the dissertation are organized as follows. The next chapter surveys state-of-the-art literature in the related works in optical manipulation of cells, optical tweezers setups, different hybrid manipulation approaches, robot motion planning under uncertainty, robotic grasping, and robotic pushing based manipulation ap- proaches. Chapter 3 presents the fast real time planning approach for automated manipulation of cell inside OT assisted microfluidic chamber. Chapter 4 extends the automated manipulation approach inside OT assisted microfluidic chamber to enhance the range of transport using automated stage motion. Chapter 5 describes a computational synthesis foundations for designing grippers for indirect manipula- tion of cells. Chapter 6 describes an automated planning approach with a feedback policy for automated indirect manipulation of cells using gripper formations. Chap- ter 7 describes a novel automated pushing based manipulation approach to transport irregular shaped cells from its current location to the goal. Finally Chapter 8 sum- marizes the intellectual contributions of the current work, highlights anticipated benefits of this research in biophysics research community as well as healthcare industry, and outlines for future work. 13 Chapter 2 Literature Review In this chapter1, we survey literature related to the goal and scope we men- tioned in Chapter 1. Our work is multidisciplinary in nature and falls in the inter- section of Biophysics and Robotics. We present the more relevant research papers in this chapter since it is nearly impossible to review all the papers available in literature. Section 2.1 deals with different issues related to optical manipulation including instrumentation, effects of direct exposure laser to cells, and different indirect ma- nipulation approaches to encounter the problem of direct exposure. A chronological study on the development of modern optical tweezers system is presented. Direct exposure to high intensity laser affects the cell viability severely. We survey existing literature that characterizes the damage in cell health due to high intensity laser and different indirect manipulation approaches proposed by various research groups to prevent cell from high intensity laser. Indirect manipulation approaches are not only important for preventing photodamage but also for some indirect measurement of physical properties of cell using optical tweezers. Many representative works take the advantage of high precision of OT in indirect measurement of physical properties of the cell. In section 2.2 we present different hybrid manipulation setups and their poten- tials to improve biological studies. We have mentioned a list of different techniques 1 The work in this chapter is partially derived from the published work in [BCLG11]. 14 available for manipulation of biological studies in chapter 1. Every manipulation techniques have their own niche domain of application where it can be the most effective. By combining two or more such manipulation systems, we can add more capabilities into the same system. That will enable more efficient studies that need to be properly synchronized and need different capabilities that cannot be provided with a single system. Laser traps can be regarded as robots to draw inspiration from robotics in automating the cell manipulation process. We survey existing literature on robot motion planning in section 2.3 that are closely related to our problem. In microscale world, the environment changes randomly due to Brownian motion of particles. Actual position, velocity, and acceleration cannot be known in advance. Hence, we focus mostly into robot motion planning under uncertainty in this section. In section 2.4 we draw inspiration from robotic grasping literature to develop robust gripper for indirect manipulation of cell. People have developed different metrics to characterize the performance of a gripper in grasping an object robustly. Our problem is unique because of size scale we are operating in. In section 2.5, we survey another body of literature in the intersection of indus- trial manufacturing and robotics to derive another mode of indirect manipulation through pushing. Dynamically changing irregular shaped objects cannot be manipu- lated using grippers. We use pushing based techniques to manipulate those objects. Our problem is interesting because of the dynamical shape of the manipulated cell. 15 2.1 Optical Manipulation The idea of optical trapping is based on Newton?s particle principle of light. Newton postulated in 1704 that light consists of tiny masses. This postulate con- tradicts the wave principle proposed by Christian Huygens who believed that light is made up of waves that can vibrate up and down perpendicular to its direction of propagation. Einstein later unified both the principles by describing light as a collection of mass-less particles, photons, which carry momenta proportional to their energy. Any change in the direction of propagation due to reflection or refraction will result in an associated change in momentum of light. As a consequence, the object that causes light to reflect or refract will undergo an equal and opposite mo- mentum change according to the principle of the conservation of momentum. This change in momentum gives rise to a net force acting on the object. However, we do not feel that force from sunlight in our everyday life because of its ultra low intensity. The intensity of sunlight is about 100 W/m2. This intensity provides an optical levitation pressure of about 10?6 Pa, which is negligible compared with the atmospheric pressure (105 Pa approximately). This radiation pressure is much more profound in the space beyond our atmosphere where there is no air resistance. Kepler in 1600 discovered that comet tails always point away from the sun due to the radiation pressure of sunlight. He named the radiation pressure as ?Heavenly Breeze?. Jules Verne first envisioned the concept of using radiation pressure for the propulsion of sailing ships for traveling in space in his science fiction novel ?From the Earth to Moon? which came out in 1865. However, it was not 16 until 2010, we saw this concept came in live when the scientists of JAXA Space Exploration Center sent the first solar sail IKAROS to monitor the atmosphere of our neighboring planet Venus. The optical force on our Earth?s surface is so small that it did not have any application for a long time until the availability of high intensity laser. Using laser with intensity million times higher than sunlight on the Earth surface, it is possible to generate force in the order of pico-newtons that may be sufficient to manipulate objects in the size scale of micro and nano meters. While scientists were arguing about the design of the future gigantic solar sailing ships that could transport cargoes between the Earth and the Mars, some scientists in Bell Laboratory started asking an even simpler question: can we use the powerful lasers to push objects in the microscale? Ashkin and other colleagues showed that it is, indeed, possible leading to the development of the first optical tweezers in 1986 [ADY87]. Since its inception optical tweezers have become a popular tools for the re- searchers in physics and biology. Optical tweezes possesses the unique capability of applying force in the order of pN with a sub-pN resolution. Hence, the it provides tremendous position accuracy in the order of micrometers down to angstrom. These unique capabilities make them suitable for variety of nanomechanical measurements, specially in biological applications. Optical tweezers have been successfully used for various cell, DNA, RNA, and motor protein manipulation. 17 2.1.1 Optical Tweezers Instrumentation The most fundamental parts of an optical tweezers are a custom-built optical microscope with imaging capabilities, a good objective lens, and a trapping laser source. Over the years, optical tweezers have been equipped with sophisticated technologies including sensitive lens, detection system, beam steering mechanism, calibration methods transforming it to a powerful experimental Instrument. Earlier optical tweezers were based on one single laser beam capable of cre- ating a single optical trap and hence can manipulate a single object. Soon people realize the necessity for manipulating multiple objects simultaneously. The simplest but expensive solution is to use multiple laser source each of them is responsible for creating a single trap. Visscher et al. [VGB96] came up with a new optical tweezers system which is capable of creating two optical traps by splitting a laser into two based on polarization. Their optical tweezers system was equipped with polarizing beam splitters to split the laser beam into two and x-y-z telescopes that can independently in X,Y, and Z axes to provide independent relative positioning of the optical traps. However, it has an inherent disadvantage since the optical traps cannot be independently switched on and off. The authors developed a more flexible method of creating multiple optical traps by time sharing of a single laser beam by fast scanning among multiple locations. The laser dwells on a single trap location briefly before moving to the next location. The fast scanning of laser into the traps gives the capability of manipulating multiple objects simultaneously. The time- sharing optical tweezers system is equipped with acousto-optic deflectors (AOD) for 18 fast scanning of laser beam which can be computer controlled. The relative posi- tions of the trap locations, the laser power strength, and the scanning rate can be controlled with computer controlled AODs adding to the greater flexibility of the time sharing optical tweezers. Another method of realizing a optical tweezers system capable of creating multiple optical traps is to use galvanometer scanning mirrors. Balijepalli et al. [BLG06] have developed a scanning mirror based optical tweezers system where AODs are replaced with scanning mirrors. The trapping laser passes through an isolator to protect the laser head from beam reflections, a first telescope for beam expansion and two scanning mirrors for increased scan range and a second telescope before reaching the microscopic objective (see Figure 2.1). The telescope is used to provide required magnification and direct the laser to the objective lens which is essential to maximize trapping force. A piezo-electric actuator is attached to the objective to enable scanning in Z-axis. However, all the multiple traps can only be created at the same X-Y plane at a time instant using this optical tweezers system providing only planar manipulation of multiple objects. The scanning mirrors can also be controlled by computers to provide similar flexibility as AOD based optical tweezers systems. Object detection has become a crucial component of the optical tweezers sys- tems in order to harness the flexibility of computer controlled AOD or scanning mirrors. The users often want to precisely position the optical traps to manip- ulate the desired objects. The positions and orientations of the objects are very important for accurate manipulation of multiple objects. Depending on manual 19 detection of objects may lead to slower and error-prone manipulation. Peng et al. [PBGL06, PBGL07b, PBGL07a, PBGL09] were motivated to solve the problem of manual detection by its potential application in precise and micro and nano assem- bly operations. In micro and nano assembly operations, objects need to be brought together with certain position and orientation in order to make a successful ma- nipulation. The authors have utilized the piezo-electric actuator attached to the objective in order to generate a stack of images in different cross-sections in Z-axis for 3D detection of objects. The image processing has three steps to extract regular shaped objects e.g., spheres. In the first step, the image is segmented to isolate the region of interest mainly to reduce the computational overhead of analyzing whole image. In the following step, a suitable gradient based algorithm e.g., Hough transformation is used to identify the locations in x-y plane. From the stack of im- ages generated offline, a set of signature curves have been generated for the regular shaped objects for known z-locations. The current image is compared online with the library of signature curves to identify the z-location of the objects. They later extend the algorithm by improving the feature extraction technique with modified Hough transform in order to find the position, orientation,and geometric identity of irregular shaped object e.g., nanowires. In order to eliminate the limitation of planar manipulation using scanning based optical tweezers, Dufresne and Grier [DG98] developed an optical tweezers where input laser is split into multiples using a diffractive optical element (DOE) that can create an array of optical traps based on the input pattern (see Figure 2.2). However, it comes with a sacrifice in flexibility since the trap patterns depend on 20 Figure 2.1: Schematic illustration of scanning mirror based optical tweezers system (Image source:[BLG06]) the input microfabricated DOE. To create a new trap patterns, a new DOE needs to be fabricated. Later on, Grier and his colleagues [Gri03, CKG02] revolutionized the optical trapping by introducing computer-addressable DOE named as Spatial Light Modulators (SLMs) made from liquid crystals. The new generation of optical tweezers are popularly named as Holographic optical tweezers (HOT). The authors [DSD+01] developed algorithm for inverse Fourier transform in order to compute phase hologram to create dynamically configurable optical traps. However, real time computation of phase hologram has been a major bottle neck for holographic optical tweezers. That is the reason, the trap update frequency of HOT is much lower as compared to scanner based optical tweezers. Over the year numerous algorithms have been proposed for efficient computation of holograms. Recently, Onda and Arai [OA12] used graphics processing unit (GPU) to accelerate the hologram computation 21 Figure 2.2: Schematic illustration of Diffractive optical element (DOE) based op- tical tweezers (Image source:[DG98]) and managed to improve the update frequency to 250 Hz as compared to 8 Hz using CPU. 2.1.2 Laser exposure using direct trapping Optical tweezers were initially used to directly manipulate cells. However, soon it was observed that direct trapping can lead to considerable photodamage on trapped cells, including the death of cells as noted by Ashkin [ADY87]. The un- derlying mechanism for photodamage has been proposed to be due to the creation of reactive chemical species [SB94, LSBT96], local heating [LSBT96], two-photon absorption [KLBT95, KSL+96] and singlet oxygen through the excitation of a pho- tosensitizer [NCL+99]. Many in depth studies that monitored cell health by a variety of methods 22 Figure 2.3: Schematic illustration of Diffractive optical element (DOE) based op- tical tweezers (Image source:[Gri03]) Figure 2.4: Schematic illustration of two, six, and four bead arrangements to manipulate cells; (a) (adapted from [LLLL08]) is useful for stretching red blood cells, while (b) and (c) (adapted from [KCA+11]) are useful for transporting cells (Note that the figure is not drawn to scale) 23 show optical micromanipulation affects cell health to some extent. Using the cloning efficiency of CHO cells [LVK+96], or the rotation rate of the E.coli flagella motor [NCL+99], it was found that 830 nm and 970 nm laser wavelengths were significantly less harmful to cells, and that the region from 870 nm to 910 nm was particularly harmful. Using the ability to express genes as a measure of cell health, another group found only a weak dependence of cell viability on wavelength (in the range 840 nm to 930 nm), with the total dose of laser light as dominant parameter determining the ability of cells to express genes [MTT+08]. The low light threshold for cell damage is of great concern for the use of optical micromanipulation: using 1064 nm, Ayano showed that cell damage to E.coli was linearly dependent on the total dose received and found that cell division ability was affected at a dose of 0.35 J [AWYY06]. Rasmussen, using the internal pH as a measure of viability, found that the internal pH of both E.coli and Listeria bacteria declined at laser intensities as low as 6 mW [ROS08]. These studies caution that direct cell trapping may not be desirable. 2.1.3 Indirect Manipulation of Cells Sleep et al. [SWSG99] studied the elasticity of red blood cell (RBC) membrane by using two-bead arrangement with optical tweezers. Two aldehyde derivatized polystyrene latex beads, attached to two diametrically opposite ends of the cell, were trapped by optical tweezers. One trap was held stationary while moving the other to induce tension or compression in the cell. The force-extension profile was generated by monitoring the displacement of the bead held in a stationary trap. 24 To reduce the influence of protein cytoskeleton on the force-extension curve for membrane, the red blood cells were prepared by saponlysis, that interacted with the membrane cholesterol to provide permeability of the membrane. Henon et al. [HLRG99] used optical tweezers to measure the shear modulus of RBC. RBCs were treated with hypotonic buffer to create the spherical or near- spherical shapes. Silica beads were added to RBC solutions to allow them to adhere to the cell surface. For the experiment, RBCs having two silica beads in diametrical position were selected from the solution. The beads were moved away from each other by increasing the relative distance between two traps until one of the beads escaped from the trap. By analyzing the final deformed shape and the associated force determined from optical trapping, the shear modulus was measured as 2.5 ? 0.4 ?N/m which was in an order of magnitude lower than those found in other experiments. The authors addressed that discrepancy by arguing that different experiments examined different elasticity regimes. More recently, Li et al. [LLLL08] studied the deformation of the erythrocyte cells by stretching them using optically trapped beads. The force applied through the bead was calibrated by exposing it to a fluid flow of various speeds. At a certain power level, there existed a maximum flow velocity beyond which the laser could not hold the bead indicating the equilibrium state where trapping force was balanced by viscous drag force. The cells were stretched in a similar way as described in [SWSG99]. The geometry of the deformed shape of the cells was measured with the help of image processing which was later used to calculate the transverse strain and lateral strain. The experimental results were compared by using mechanical model 25 of liposomes since erythrocytes have very similar phospholipid bilayers. By compar- ing the experimental and numerical results, the shear stiffness of the phospholipid membrane, a proper shear stiffness was determined to minimize the error between the two. The average estimated shear stiffness agreed with the other published results. Fontes et al. [FFDT+08] recently proposed a new method to measure mechan- ical (apparent membrane viscosity and adhesion force) and electrical (zeta potential, thickness of the double layer of charges) using double optical tweezers. To measure the adhesion membrane viscosity, an optically trapped silica bead was bound to a RBC of a two cell spontaneously formed rouleaux and moved while the other RBC was directly held by another optical trap. For the adhesion force measurement, two silica beads captured by double optical tweezers were used to manipulate RBCs. One bead was kept stationary while the other was moved in diametrically opposite direction. An special chamber with two electrodes were built to measure the elec- trical properties . An external electrical field was applied through the electrodes. The double layer thickness was measured by determining the force that the trapped bead bound to a RBC experienced due to the external electrical field. On the other hand, The zeta potential was measured using the velocity of the bead due to the applied electrical field after it was released from trap. Laurent et al. [LHP+02] measured the viscoelestic properties of alveolar epithe- lial cell and compared the experimental and theoretical measurements using both magnetic twisting cytometry and optical tweezers technique. A silica microbead attached to a cell was trapped and displaced at a low constant speed by moving 26 the trap parallel to the cover slip. The position of the bead, measured by image processing, was used to calculate the displacement of the bead relative to the trap. The geometric parameters, i.e. cell stiffness, bead immersion angle, were determined from the microscopic images during laser trapping. The two techniques used same size beads and the data was analyzed using the same model. However, The authors reported some discrepancy between the two results that occurred mainly due to the difference in experimental conditions. Wei et al. [WZY+08] most recently used microrheometer based on oscillatory optical tweezers to measure both extracellular and intracellular complex shear mod- ulus with the separate measurement of storage and loss modulus components for alveolar epithelial cell. Protein A coated 1.5 ?m silica beads were used as probe for exterior shear modulus experiment whereas internal granule was used as probe for intracellular measurement. To calibrate the system, a trapped bead was forced to oscillate along the x-direction by the application of an oscillatory optical force. Arai et al. [AOF+00] developed a new system for high speed random sepa- ration of microbes using optical radiation pressure and dielectrophoretic force in microfluidic chamber. The system was composed of laser scanning manipulator to trap the target microbe, electrophoretic manipulator to create electric field gradient for separating the other objects from the target, and finally capillary flow in the mi- cro channel to extract the isolated target. To avoid the direct exposure of the target microbe to the laser some new microtools were used which could be trapped by laser to manipulate the microbes indirectly. In a similar work, Arai et al. [AMS+03] used two types of microtools for indirect manipulation of living objects namely natural 27 microtool (e.g., microbe such as bacillus) and artificial microtool (e.g., microbead) for separation of target bioorganism. An inner installation method was developed to install the microtools into the manipulation chamber. The target microbes was then transported using the trapped microtool. In a later work, Arai et al. [AYSF04] used synchronized Laser Micromanipu- lation (SLM) for indirect force measurement of the microbes. SLM facilitated the trajectory control of multiple targets by using single laser. Using SLM two mi- crotools were trapped in a certain distance. When the target microbe was pushed by one of the microtool while keeping the distance among themselves same, the microtool experienced a reaction force which was balanced by the trapping. Mea- suring the displacement of the microtool from the optical trap, the reaction force was determined. Fall et al. [FSJ+04] also developed an optical force measurement system for the calculation of forces in biological object, for instance, E. Coli. The adhesion force between E. Coli and galabiose functionalized beads was measured using polystyrene beads as handles for optical tweezers. An immobilized large bead was brought into contact with E. Coli. A second galabiose functionalized bead, trapped by optical tweezers, was brought close to E. Coli. The large bead was moved away from the trapped bead at a constant speed (0.05 ?m/s) until the bonding collapsed. The maximum displacement of the bead was used to measure the binding force. The microscope was modified to accommodate a probe laser which along with a position detector monitored the position of a bead in the trap. Sun et al. [SHC+01] used irregularly shaped diamond as handles for the con- 28 trolled rotation and translation of biological object. Diamond microparticles are transparent at visible and infrared wavelength of light and biologically inert. The irregular shape of microparticle induced self rotation in optical trap. The rotation speed and direction of diamond microparticle was controlled by moving the objec- tive in the direction of laser propagation. Mesophyl protoplasts were manipulated by tagging them with diamond microparticles. Controlled rotation as well as pure translation were achieved using diamond microparticles. Ferrari et al. [FEC+05] used two different setups to create multiple traps for indirect manipulation of biological objects. One of the setups used AOD (accousto optics deflectors) to achieve deflection of laser fast enough to maintain multiple traps by sequential sharing of the laser beam. However, AOD could only provide planar trapping configuration. The second setup used DOE ( diffractive optical elements) that converts a specified illuminated beam into a beam with desired distribution of amplitude, phase or polarization. 2 ?m RGD coated latex beads were trapped in a circular configuration by using AOD based multi-trapping system. By varying the diameter of the circular pattern the trapped beads were moved close enough to the cell such that RGD allowed the bead to adhere to the cell. The cell was shrunk or stretched by varying the circular pattern to investigate the cell reaction to the mechanical stimuli. The same cell was manipulated using an improved 3D multitraping system based on DOE. Ichikawa et al. [IAY+05, IHE+06] proposed a new method for manipulation of biological objects by instant creating and destroying the microtool. The microtool was formed by local thermal gelation using the laser power. After manipulation the 29 microtool was dissolved by turning off the laser. Kress et al. [KSGR05] investigated the binding mechanism of morphage cell during phagocytosis using fluctuating bead in optical trap as a local probe. By optimizing the numerical aperture of the trap and thereby controlling the trapping position of the bead, a stable 3D position detection was achieved. The trapped bead was moved close to morphage cell. The bead was coated with ligands to trigger the phagocytic binding process. Four different types of ligands were used: Immunoglob- ulin G(IgG), complement, bacterial lipopolysaccharide (LPS), and avidin. The dy- namics of the membrane binding events was monitored using PFM (Photonic force microscopy). Miyata et al. [MRB02] used optical tweezers to study the effect of temperature and opposing force on the gliding speed of Micoplasma mobile. 1.1 ? beads were attached to gliding M. mobile cells and held into optical trap to apply enough force to stall their forward movement. The authors found that the gliding mechanism is composed of at least two steps. One step generates force while the other allows displacement. Taka et al. [THM03] studied the dynamic behavior of swiss 3T3 fibroblast membrane by using an optically trapped polystyrene bead as a probe. A polystyrene bead coated with BSA was captured with optical trap and brought into contact with cell edge. The image was recorded for 1-2 mins. The experiments were conducted at three trap stiffness (0.024, 0.053, and 0.090 pN/nm). The analysis demonstrated that the protrusion and withdrawal of the cell edge occurred at non-uniform veloc- ities and dependent on stiffness. 30 Most recently Pozzo et al. [PFdT+09] used optical tweezers to study the chemotaxis behavior of flagellated microorganism (Lashmania amazonensis) by observing the force response when exposed to a gradient of attractive chemical sub- stance. The propulsion force of the flagellum of L. amazonensis was measured by at- taching a polystyrene bead using optical tweezers. The displacement of polystyrene bead from the optical trap was used to measure the propulsion force. The protozoan responded to the glucose gradient by circular and tumbling motion whereas swam erratically in the absence of any gradient. 2.1.4 Comparison with Other Approaches for Manipulating Cells Cell manipulation is an important steps both for medical experiments and making fundamental advances in biological sciences. Hence different techniques have been developed for manipulating cells over the years. In this section, we compare indirect optical manipulation with other well-known techniques for manipulating cells. Dielectrophoresis involves manipulation of dielectric particles using time-varying electric-fields. This method has been successfully used to manipulate cells [AOM+99, AZ88, WKI+93, NKHM97, DKB99]. Magnetic manipulation involves tagging cells by magnetic particles and then using the time varying magnetic field to move the particles and hence the cells [HJB+03, dVKvDK05, WGB03, LHW04]. Both of these methods place restrictions on the types of cells that can be manipulated by these methods and the environments in which the cells should be manipulated. More- over, it is very difficult to achieve independent placement control over multiple cells 31 concurrently. Recent advances in silicon and polymer based micro-electromechanical systems have been exploited to develop microscale grippers that can hold individual cells and arrays of cells [JIL00, CL05, WUH04, KCL+03, JIP+02]. These methods utilize customized grippers to grasp cell. These grippers are used in conjunction with mechanical micromanipulators to move cells. These grippers are not reconfigurable to allow for changes in the cell shapes. Moreover, only limited field of view is available for imaging while the gripper is holding the cell. Integrating multiple mechanical manipulators together to perform multiple independent operations is challenging due to workspace limitations. Microfluidics, when combined with e.g. electro-osmotic actuation can be a powerful tool to steer a small number of objects. It has been shown to be a useful technology for cell manipulation [WBC03, ACPS05, YLJY06, OZDF08]. However, fluids are incompressible and thus harder to focus than optical traps. Microfluidics also generally requires a closed system for controlled flows and thus makes further manipulation of the sample (e.g. insertion of a micropipette or a chemoattractant) difficult unless integrated with the microfluidics device. Microfluidics is a promising technology for gross motion and can be combined with the optical manipulation techniques for fine motion control. The existing research clearly shows that cells can be manipulated by attaching microspheres to them and optically manipulated the microspheres. We anticipate that an increasing level of autonomy in the field of optical tweezers will enable manipulation of cells using multiple different microspheres without a need for the 32 microspheres to be physically attached to the cells. Such capability will further enhance the field of indirect manipulation of cells using optical tweezers. Moreover, optical tweezers can be combined with gross manipulation techniques e.g. microflu- idics, dielectrophoresis etc. to provide high throughput as well as precise control of manipulation. We have tabulated the different optical tweezer set-ups as well as the type of biological objects, size and type of gripper objects, and the types of manipulation operations being performed, to bring out the common features that can be observed across this research domain. Table 2.1 summarizes the tweezer set-ups, whereas the remaining information is presented in Table 2.2. It may be noted here that we have clustered together all the work published by researchers belonging to the same research group in the same row and used certain abbreviations to represent the tables in a more compact form. NR refers to the fact that the particular data is not reported in the cited paper; PS, Sl, Gl, and Lt stand for polystyrene, silica, glass, and latex respectively, gripper object size refers to the diameter, and the two entries in the objective lens parameters column denote magnification and numerical aperture values respectively. It can be seen from Table 2.1 that Nd:YAG and Nd:YVO4 are the two most popular laser types. The lasers are always operated in the infra-red regime, although, the specific wavelengths may vary from (790-1064) nm. Usually, the laser power is kept quite low (mostly below 300 mW), even though in few cases much higher values are used. Typically, very high magnification (100X) and numerical aperture (1.2-1.4) objective lens are used. Only in few cases, lens having 40, 50 or 63X 33 magnification, and numerical aperture of 1.0 or 0.6 are utilized. Unlike most of the tweezer set-up parameters, lot of variation is observed in case of the gripper object size (shown in Table 2.2). Although in quite a few cases, bead size within the range of (1-2.5)?-m are selected, in certain cases, beads as small as 75 nm in diameter are used, whereas, in other cases, beads as large as 10 ?-m diameter are utilized. Biotin and streptavidin are commonly used as coating materials to facilitate the binding of beads with the biological objects. It may also be noted here that stretching or pulling is the most prevalent form of manipulation as it enables characterization of biomechanical properties and provides information on the underlying mechanisms behind physiological processes. Moreover, rotation is never performed, although some papers on direct optical manipulation of cells have looked into this. Table 2.1: Summary of optical tweezer setups Papers Laser type Laser power Wave length Objective lens pa- rameters [AYA+99, MYK96, NMY+95, THM03] Nd:YAG, Nd: YLF 150 mW, 1 W 1064nm, 1053nm 100X, 1.3 [AYA+99, MYK96, NMY+95, THM03] Nd:YAG, Nd: YLF 150 mW, 1 W 1064nm, 1053nm 100X, 1.3 [BSK+99, BLL+01] Diode laser 200 mW, 500 mW 829 nm, 1064 nm 100X, 1.2 [BGS90, SSSB93, WYL+97, VSB99] Nd:YAG, Nd:YVO4, Nd:YLF NR 1064 nm 100X, 1.3 [BTER+02, MCB+06] Nd:YAG, Ti:Sa 1W 1064 nm 100X, 1.25 [CSS05] NR NR NR NR continued on next page . . . 34 continued from previous page . . . Papers Laser type Laser power Wave length Objective lens pa- rameters [FSS94] Nd:YLF NR 1047nm 63X, 1.4 [KB97, DWLB00, LOS+01, LBT07, MWL+07, WML+07] Nd:YAG 1.5W 835 nm, 1064 nm NR,1.2 [STNS+05] Ti:Sa 200 mW 830 nm NR [AMS+03, IAY+05, IHE+06] Nd:YVO4 4.98 W, 200 mW 1064 nm, 860 nm 100X, 1.3 [LHP+02, HLRG99] Nd:YAG 600 mW 1064 nm 100X, 1.25 [PFdT+09] Nd:YAG NR NR 100X, 1.25 [KMHY97] Nd:YAG 300 mW 1064 nm 100X, 1.3 [DGWW97] Nd:YLF 3W 1047 nm 100X, 1.4 [HBMM02] Nd:YAG 600 mW 1064 nm 100X, 1.3 [JSGF04] NR NR 1064 nm NR [PQSC94] Nd:YAG 100 mW NR 63X, 1.4 [SWSG99] Nd:YLF NR 1047 nm 63X, 1.4 [VBW+98] Nd: YAG NR 1064 nm 100X, 1.3 [RHX+04] Nd:YAG 2.5 W NR 100X, 1.3 [BVHS09] Nd:YVO4 NR 1064 nm 100X, 1.3 [CVJ+05] Nd: YAG NR 1064 nm NR, 1.45 [SL97, SSL98, SHRS02] Nd:YAG 150 mW 830 nm, 1064 nm 100X, 1.3 [WSY+02] Nd:YAG NR NR 100X, 1.35 [WCMF95] NR NR NR 100X, 1.4 [DLP+07, PPM+05, PPM+07] Nd:YAG 1 W 1064 nm 60X,NR [FEC+05] Nd:YAG 15W 1064 nm 100X, 1.3 [FFDT+08] Nd:YAG 60 mW; 30 mW; 15 mW NR 100X, 1.25 continued on next page . . . 35 continued from previous page . . . Papers Laser type Laser power Wave length Objective lens pa- rameters [KYI+01] Nd: YAG NR 1064 nm 40X, 1.0 [LLLL08] Nd: YAG 1.5 W 1064 nm NR [SHC+01] Nd: YVO4 50-500 mW 790 nm 50X, 0.6 [WZY+08] Nd: YVO4 NR 1064 nm 100X, 1.3 Table 2.2: Summary of materials, size, and manipulation type Papers Biological ob- ject Gripper ob- ject Gripper coat- ing Gripper ob- ject size (?m) Manipulation type [AYA+99, MYK96, NMY+95, THM03] ?-Actinin, Swiss 3T3 fibroblasts, Actin, HMM, DNA PS Galsonin, BSA 1 Translation, Stretch- ing, Tying knot [BSK+99, BLL+01] ?-phage DNA Polystyrene Streptavidin 2.5 Stretching [BGS90, SSSB93, WYL+97, VSB99] Kinesin, DNA Sl, PS BSA 0.2-0.6 Tracking [BTER+02, MCB+06] DNA, Ki- nesin Sl Streptavidin 1 Translation, Stretch- ing [CC05] Kinesin Sl NR 1 Keeping bead sta- tionary [CSS05] DNA of type A and type B PS, Au Streptavidin 1 Forming DNA- DNA linkage [FSS94] Actin fila- ment Sl, PS NEM 1 Straightening, Pulling [KB97, DWLB00, LOS+01, LBT07, MWL+07, WML+07] RNA poly- merase, Titin, RBC, P5ab RNA and corre- sponding DNA Carboxylated PS, Sl Streptavidin, T12 antibody, T51 antibody 2 - 3.4 Stretching, Pulling, Relaxing [STNS+05] Cell organelle Lipid granules NR 0.075 Moving [SHC+01] Type 1 Pro- collagen PS Streptavidin, Biotin 2.17 - 6.7 Stretching [AMS+03, IAY+05, IHE+06] Yeast, DNA, Viruses PS NR 3 - 10 Pushing, Indirect transportation continued on next page . . . 36 continued from previous page . . . Papers Biological ob- ject Gripper ob- ject Gripper coat- ing Gripper ob- ject size (?m) Manipulation type [LHP+02, HLRG99] Fibronectin, RBC Carboxylated Sl RGD 2.1 - 5 Application of force [PFdT+09] P. L. amazo- nensis PS NR 9 Translation [KMHY97] Kinesin Lt Kinesin 1 Bead is kept station- ary [DGWW97] Actin Polybeads amino Myosin 1 Stretching [HBMM02] DNA Lt NR 0.2 Stretching [JSGF04] Kinesin Gl Kinesin 0.430 Allow brownian mo- tion creating weak trap [PQSC94] ?phage DNA PS Streptavidin 1 Stretching [SWSG99] RBC mem- brane PS NR 1 Tension [VBW+98] Actin, HMM Lt, Gl NEM myosin 1.1 Stretching [BVHS09] Kip3p(His6- Kip3p- EGFP) PS NertrAvidin 0.528 Friction generation [CVJ+05] Myosin-V, F- Actin PS Myosin-V 1 Moving [SL97, SSL98, SHRS02] ? phage DNA Lt, PS Streptavidin 3.2 Grafting, Stretching [WSY+02] Myosin, G-actin Polybeads- amino Myosin 1 - 3.38 Translation [WCMF95] Myosin-V, Actin Sl Aminoprofyl surface groups 0.3, 0.8 Trapping [DLP+07, PPM+05, PPM+07] Blood cells, T-cells, HL 60 cells Sl Streptavidin 5 Tagging [FEC+05] E. Coli, Eu- karyotic cells Lt, Sl RGD contain- ing peptide 2 Stretching, Shrinking [FFDT+08] RBC Sl NR NR Pulling [KYI+01] DNA Water droplet in oil No coating 10 Translation [LLLL08] T7 RNA polymerase Microspheres Streptavidin, Anti- dioxygenin antibody NR Pulling [WZY+08] Human lung epithelial type 2 cells Sl Protein A 1.5 Oscillating the trapped bead 2.2 Hybrid manipulation systems There is a growing interest of using hybrid system rather than a single ma- nipulation system for some synchronized biological studies that are not possible otherwise. An example of such capability is combining gross manipulation with targeted single cell studies. Sott et al. [SEPG08] show the usefulness of single cell 37 Figure 2.5: Schematic illustration of a electromagnetic-microfluidics hybrid cell manipulation system (Image source: [Lee05]) studies in identifying important physiological phenomena which were traditionally studied over a population of biological studies. Experiments by using gross ma- nipulation can only provide the average response over a population of cells. This does not show whether the result is because all the cells respond in the same way or in a all-or-nothing fashion or in a combination of both. To answer the question, a targeted manipulation capability needs to be added with the gross manipulation system. This section presents the literature focused on hybrid manipulation systems. A hybrid system combining micro-electromagnetic and microfluidics is demon- strated by Lee [Lee05]. The magnetic peaks can be controlled to direct the cell in a predefined path inside a microfluidic channel. A schematic of the hybrid system is shown in Figure 2.5. The author demonstrates its capability by manipulating magnetotactic bacteria and neutral yeast cells tagged with magnetic beads. Schmidt et al. [SYEL07] developed a hybrid optofluidic system to guide the cell transport in a desired direction. A schematic of a optofluidic trapping system is 38 Figure 2.6: Schematic illustration of a opto-fluidic hybrid cell manipulation system (Image source: [SYEL07]) shown in Figure 2.6. The solid optical guide provides scattering optical force to push the cell in the direction. The optical force can act in a long range to provide targeted manipulation. Most of microfluidic devices are built from polydimethylsiloxane (PDMS) which is transparent to laser. That makes it suitable to be combined with opti- cal tweezers. Because of its high precision in manipulation optical tweezers is a popular choice where single cell analysis is a necessary step in biological studies. A schematic of such system is provided in Figure 2.7. Microfluidics provide gross ma- nipulation facility to bring the objects in the workspace where rest of the targeted manipulation is provided by OT. This hybrid system is particularly important to study how individual cells respond to different environment changes in their vicinity. Multiple channels of microfluidics can be used to supply different growth solutions to change the environments in the vicinity [ESL+10]. Umehara et al. [UWIY03] developed a similar system to monitor responses of cells in different environment. Cells are trapped and transported by OT in different compartments of microfluidic 39 Figure 2.7: Schematic illustration of a OT-microfluidic hybrid cell manipulation system (Image source: [SEPG08]) chamber representing different environments. MacDonald et al. [MSD03] use OT-microfluidics hybrid systems to sort rare cells from a large population. OT is used as a complementary device that provides fine manipulation to sort the individual cells in their respective containers, on the other hand, microfluidics provide gross manipulation to bring the population to the workspace of OT. A schematic of a hybrid cell sorting system in shown in Figure 2.8. Wang et al. [WWS10] use robotics technologies to automate the cell sorting in such a hybrid system. 2.3 Robot Motion Planning and Control Planning is an essential part for any autonomous robotic system. There is a huge potential for automated planning and control in the field of micro manipulation 40 Figure 2.8: Schematic illustration of a OT-microfluidic hybrid cell sorting system (Image source: [MSD03]) [BG13]. In most of the autonomous systems planning is used as a high level layer which splits out the desired waypoints for the robot and an underlying control layer is dedicated to ensure that robot is following the path which is known as tracking. Control is a vast research field on its own. This dissertation is only focused on developing novel planning algorithms to facilitate cell manipulation. Hence, the control approaches encountered only in micro-manipulation using optical tweezers are discussed. Robot motion planning problems can be broadly classified into two categories, namely, deterministic planning and planning under uncertainty. In the first category, the motion planning algorithms assume that the sensor data precisely reflect the current state of the world and the motion of the robot is always deterministic. In the second category, these assumptions are not considered and the planning algorithms explicitly deal with sensor and motion uncertainties. Additional complication for robotic motion planning is the inherent latency between the sensor and motion controller, leading to increased reaction time to new sensory information. 41 In both the cases, the underlying state space (also known as a configura- tion space or C-space) is either discretized and then searched using graph search techniques including graph search algorithms [LaV06],decision theoretic approaches [CTS11], or sampled using the sampling-based planning algorithms [LaV06]. The explicit representations of the state space include, e.g., a visibility graph [LP83], road map [LaV06], Voronoi diagram [GL04, LaV06], or lattice-based representa- tions [LaV06]. Some of the most common graph search algorithms include Breadth-first search, Depth-first, Dynamic programming (Dijkstra), and A* [HNR68]. Often time, graph search is equipped with suitable heuristics to direct the search for finding the op- timal solution in minimum time. The heuristic function biases the search to the required direction. The heuristics are generally developed by the user based on the objective of the planning. Graph search algorithms have to be provided with a graph representing the workspace of the robot. The workspace or state space is generally created using on-board or remote sensor information. However, in the real world, sensors cannot provide perfect information in most of the cases due to the latency between sensors and controller, highly stochastic nature of the envi- ronment, etc. Classical graph search algorithms can be proved to be inefficient in dynamic environment where the state space and hence the resulting graph changes rapidly since the planning has to be started from scratch every time the state space is updated. To address the problem of motion planning under uncertainty, Koenig and Likhachev [KL05] used heuristic based search with the reuse of past informa- tion about the environment for fast replanning in unknown terrain. Ferguson et al. 42 [FLS05] modified the same heuristic based search to be able to get a sub-optimal trajectory in a given time interval. Graph search algorithms were frequently used for automated manipulation using optical tweezers. Wu et al. [WTSH10, WSH11] developed a similar A* based approach for automated transport of directly trapped cells using OT. In that approach, the cost function is designed such that smooth paths are computed to ensure reliable transport of cells. Chowdhury et al. [CTW+13] developed A* based path planner with a novel cost function for gripper-based automated indirect manipulation of cells using OT. Decision theoretic approaches have been popular particularly because of their inherent capability to handle both action and sensor uncertainties. Most of problems with uncertainties can be modeled as a Markov decision process which assumes the current state of the robot only depends on its previous state and action. If the uncertainties can be modeled perfectly using the state transition model, decision theoretic approaches can be proved to be much useful since unlike graph search algorithms they do not need to be recomputed every time the graph changes. The solution of a decision theoretic approach is a policy which maps the state into action. For a given state the robot can execute the optimal action from the computed policy. The main criticism of decision theoretic approaches is the dimensional curse. The state space grows exponentially with the increase in dimension. Since, it computes a policy, the cost function (known as value function for decision theoretic approaches) need to be computed all over the state space. Dean et al. [DKKN93] developed an algorithm by combining depth first search and MDP. An initial path is computed 43 using breadth first search and corresponding policy is generated using MDP by creating an envelope of states only along the initial path. As the robot starts executing the plan the planner iteratively update the policy by considering a bigger envelope with more states. Although this reduces the planning time, it provides a sub-optimal solutions since the planner does not consider the whole state space. For instance, if the two consecutive policies define conflicting actions, robot may need to take a much expensive detour to reach the goal. Laroche [Lar00] uses an initial path computed by Dijkstra algorithm and decomposed the path into multiple segments. Each segment is treated as an independent MDP to compute the optimal path in multiple segments. Finally all the paths using multiple MDPs are combined to compute the final path. A discrete version of the infinite horizon MDP was applied to steer flexible bevel-tip needles inside soft tissues in [ALG+05]. Banerjee et al. [BG08, BPLG10] developed a partially observable MDP based planner for automated transport of a particle in an environment with obstacles. They further extended the planner in [BCLG12, BLG09] for automated transport of multiple particles. They introduced a time parameter in the convergence loop to enhance the computational speed and ac- curacy in deriving the safest paths. In order to incorporate the trapping uncertainty into the MDP framework, they have developed a physically accurate simulation ap- proach incorporating all the forces acting on a freely diffusing particle in a fluid medium [BBGL08, BBGL09, BLGG09]. The output of the simulation framework is a trapping probability table at discrete locations of the OT workspace. However, the timestep of the micro-scale simulation has to be small (in the order of microsec- 44 onds). Hence, they run the simulations offline and generate a lookup table which is used for the online planning. Later on, Patro et al. [PDB+12] used GPU to speed up the computation of trapping probability and showed a 356 times speedup over CPU computation performed by Banerjee et al.. Balijepalli et al. [BLG10, Bal11] also showed similar speedup over CPU for nano-scale simulations of freely diffus- ing particles in a fluid medium. Bista et al. [BCGV12, BCGV13] extends the simulation approach for real-time prediction of forces due to interaction of multiple optical traps in a particle ensemble using GPUs. Chowdhury et al. [CSW+11] used the MDP framework to compute path for manipulating particles inside OT-assisted microfluidic chamber under the influence of fluid flow. Sampling based algorithms are particularly useful for planning in higher dimen- sional space since it does not require to explicitly construct configuration space. Two popular sampling based algorithms are Probabilistic roadmap (PRM) and Rapidly Exploring Randomized Tree (RRT). PRM planner [CLH+05] samples the workspace to construct a roadmap which is equivalent to configuration space and uses a graph search algorithm to compute path on the roadmap. The efficiency of the algorithm is lying on the implementation of an efficient collision detection algorithm and a robust sampling algorithm that can find feasible path. Inefficient sampling some- times lead to invalid path in case of narrow spaces. On the other hand, RRT based planner [LaV06] creates the map and the optimal path simultaneously, hence does not require an additional graph search. Missiuro and Roy [MR06] in their Probabilistic Roadmap (PRM) planner made the sampling of the state space biased to specific state space areas by calculating 45 the collision probability for certain sampled states. The Rapidly Exploring Random Tree (RRT) algorithm was modified by representing the extended nodes by a distri- bution of states rather than by a single state [MS07] for planning under uncertainty. Another extension of RRT was presented in [FSL09] in which an anytime algorithm was developed that was able to react to changes of the environment and make ap- propriate re-planning. The nodes were sampled in [GHKR09] according to a suitable probability distribution and thereby an uncertainty roadmap was developed. A sam- pling RRT based algorithm was developed by Ju et al. [JLYS11a, JLYS11b] for automated OT-based transport of cells in 3D. Trapping force is zero at the focal point of the laser. Hence, particles that are less than 1 m can exhibit Brownian motions inside the traps. Sometimes Brownian motions lead the particles escape the trap. Balijepalli et al. [BGGL12] used a feedback controller that can actively control the position and associated laser inten- sity of the trap to increase the lifetime in trapping nanoparticles. The feedback is achieved by a simple proportional controller to control the laser intensity based on the location of nanoparticles from the center of the traps. The closed loop controller actively changes the laser power and position in order to reduce the escaping of the nanoparticles from the trap. With the controller on, they have seen a 26 and 22 times increase in trap lifetime for 100 nm and 350 nm gold particles respectively without any corresponding increase in laser power. Huang et al. [HZM09, HWC+09] used a similar feedback loop based on proportional control law in order to control the Brownian motion of an optically trapped probe. As the probe size goes down to submicrometer or nanometer scale, the diffusion rate due to Brownian forces in- 46 creases with a rapid decline in stabilizing force from the optical trap. Hence, the probes in submicrometer or nanometer scale used for many biological measurements produce noisy data. Although the stabilizing force can be increased by increasing the laser power that might inflict photodamge to the biological samples. The au- thors by using their feedback control were able to decrease the variance of their 1.87 m optically trapped probe?s Brownian motion. Gorman et al. [GBL12] also used feedback control for suppressing Brownian motion of microparticles inside optical trap. Chen et al. [CCWS10, CS11, CS12, CWL13] used a potential field based open loop controller to move a collection of optically trapped cells to a desired region while avoiding collisions with each other as well as freely diffusing objects in the workspace. Li et al. [LWS13] also used a potential field based controller with vision feedback for reliable positioning of cell to the desired location in the workspace with optical tweezers. In another work on manipulation of a swarm of microparticles Chen et al. [CCS11] developed a multi-step approach for assigning goal locations to the individual agent to maintain their formation. A open loop controller is designed to move the microparticles to their assigned goal locations with optical tweezers. Rather than focused on controlling the position of an optical trap, Li and Cheah [LC12] developed a region based controller to automatically transport a cell. The shape and location of the region can be dynamically changed to transport the cell precisely. Wang et al. [WYCS12] developed a controller to automatically move the motorized stage while keeping the optical traps stationary to move a group of cells to their desired locations inside a microfluidic chamber. In a separate work Wang et al. [WCK+11] used optical tweezers to automatically 47 move the cell to the desired direction in order to enhance sorting operation inside a microfluidic chamber. Wu et al. [WSHX13] integrated a proportional-integral (PI) controller with A* based planner to achieve a stable and precise transport of cells. Hu and Sun [HS11] developed a closed loop controller to precise positioning and transport of multiple cells while maintaining a certain pattern. Li et al. [LCHS13] developed closed loop controller based on dynamics of optical trap for simultaneous trapping and manipulation of cells. A summary of the literature review and the main issues related to this section are the following: DS Heuristic based planning approaches [WTSH10] are efficient. However, the cost function needs to be chosen carefully based on the planning scenario and objectives. Correspondingly, the underlying state-action space representation needs to reflect the requirements of a particular planning domain. DS Decision theoretic approaches can incorporate uncertainty into the planning. However, they are computationally expensive and not suitable when there is a need for fast replanning. DS While sampling based algorithms are suitable for planning in high dimensional space, they are not suitable for planning in randomly changing dynamic envi- ronments where the roadmap needs to be constructed again or the planner has to be equipped with a reactive planning component that will take corrective action based on the current scenarios. DS Planning has to be integrated with feedback control in order to reliably trans- 48 port the particles with optical tweezers. 2.4 Robotic grasping In this section, we will present literature on robotic grasping closely related to the problem of automated indirect transport of cells. The overall problem of finding a suitable gripper configuration is closely related to the problem of robotic grasping [Mas01]. One of the basic requirements of robotic grasp is to immobilize the object by preventing its motion due to undesirable external forces, which is characterized by form and force closures. A grasp can be considered as form closured if it immobilizes the object based on frictionless point contact. On the other hand, force closured grasp is able to provide the wrench on the grasped object to balance out any external loads. Hence, the primary distinction between the form and force closures lies in the type of the contact model between the grasped object and the restraining mechanism [Bic00]. Mason [Mas01] divides the robotic grasping into three different issues. The first issue concerns the analysis that determines whether closure applies on an object with a given set of contact points, and possibly other information. Reuleux [Reu76] showed that the minimum contact necessary to achieve the form closure for a rigid body in n dimensional space is n + 1. The second issue concerns the existence that determines whether a set of allowable contacts exists to provide closure on an object. Mishra et al. [MSS87] proved that any object with any kind of rotational symmetry cannot be fully immobilized with only frictionless point contacts. Hence, only a relative form closure [ZD07] can be achieved. The third issue concerns the 49 synthesis that determines a suitable set of contacts to achieve closure for an object with a set of allowable contacts. Grasp synthesis is much more challenging problem compared to the other two. Various grasp synthesis algorithms have been proposed [ZW03, ZD07]. Another stream of research deals with the quality of a grasp by developing different metrics [RSC08]. The synthesis problem is cast as a multi-objective optimization problem in [MDS10] where quality metrics are combined with closure properties. Our problem is challenging due to small size scale involved and the uncertainty in placing the beads at the correct locations. Moreover, we want to minimize the intensity of the laser beam experienced by the gripped object resulting from the placement of the configured gripper silica beads. Finally, we want to transport the whole ensemble that consists of a gripper and gripped object, against the drag force resulting from the resistance of surrounding fluid medium. Thus, we need additional validation of robustness that will specify the maximum speed using which the ensemble can be transported without collapsing the gripper configuration. 2.5 Pushing based manipulation In this section, we will present literature on robotic pushing closely related to the problem of automated indirect transport of cells. Akella and Mason [AM92] generated open-loop feedback plans to push a polyg- onal object using a fence. Balorda and Bazd [BB94] reduced motion uncertainty by pushing an object rather than using expensive fixtures arrangements. Lynch and Mason [LM95, LM96] generated a collision-free path for stable pushing of a heavy 50 object with multiple pusher objects. Abell and Erdmann [AE95] used the idea of stable support to manipulate an object with a known gravitational force and a small uncertainty in its pose. Aiyama et al. [AII93] used pivoting as a method of automated non-prehensile manipulation. Erdmann [Erd98] implemented a planner that generates a plan for non-prehensile orientation of an object using two palms without the use of fingers to wrap it around. Cappalleri et al. [CFM+06] used ran- domized motion planning techniques for planar micromanipulation tasks based on quasi-static models. Rezzoug and Gorce [RG99] dynamically controlled the multi- finger pushing operation by considering optimal force distribution and center of mass acceleration correction. Goldberg [Gol93] generated a sequence of gripping actions in order to manipulate a part in a sensor-less setup. A similar approach was used by [Qia03, BOvdS02] to orient the part in any arbitrary orientation. Moll et al. [MGEF02] used two manipulation primitives: sequencing and rolling for sensor-less orientation of a micro-scaled asymmetric part. Thakur et al. [TCW+12] developed rule-based automated pushing approach for indirectly manipulate a yeast cell with an optically trapped bead. An optically trapped bead is used to push an intermediate bead that is not directly trapped by laser which eventually pushes the cell to the desired location. In summary, Objects can be transported by pushing rather than grasping. Transporting a cell by pushing requires a feedback control in order to retain the beads in a formation. 51 2.6 Summary Optical tweezers is a wonderful instrument for precise manipulation of biolog- ical objects. It is very popular to the biologists because of its non-invasive nature of manipulation. However, the slow speed of optical manipulation of cells, confinement to single-cell studies, and lack of widespread usage in cell biology laboratories and clinics indicate that a more systematic approach to design and control this complex system may be valuable for broader implementation. Currently, optical manipula- tion is limited to a small workspace of 100 F1m ? 100 F1m. The workspace limitation needs to be addressed for comprehensive study on a group of cells using optical tweezers. Another big criticism of optical manipulation is the detrimental effect of laser to the biological objects. Novel manipulation approaches need be developed with tight integration of perception, planning, and control in order to tackle the problem direct exposure of laser to the cell. Hence, we believe that there are many research issues still need be addressed to turn optical tweezers into a promising gen- eralized manipulation technique for objects in micro and nano scale. We list them and briefly discuss how they may help in addressing the current challenges. DS Automation: Operation automation is very important since manual interven- tion and low throughput are major hurdles against wide adaptation of optical tweezers. Although some work has been done on automating transport of col- loidal microspheres [CGD06, BCLG12, BPLG10], significant advances in image processing and planning and control are necessary for developing reliable au- tonomous systems to indirectly manipulate cells. Specifically, automation will 52 tremendously help in re-adjusting trap and gripper positions by compensating for the constant Brownian motion of the cells, planning optimal trajectories to transport the cells to desired locations in the assays, and selecting appropriate trap intensities and speeds to maximize the operation efficiency. DS Hybridization: An alternative to multi-beam tweezer systems for achieving multi-cell manipulation lies in combining optical traps with other forms of manipulation techniques, most notably microfluidic, magnetic, and acoustics. Although many researchers [OPS+03, LLHW07, OCP+07] have already de- veloped hybrid systems to pattern cells or separate them, to the best of our knowledge this has not been done in the context of automated manipulation. We believe that the combination of microfluidic and optical manipulation sys- tems holds the greatest promise in providing high speed of operation and positional accuracy simultaneously. In such systems, the gross motion will be imparted by the fluid flow, whereas the fine and precise positioning of cells at their final locations will be performed by the optical grippers. DS Manipulation without inflicting photodamage: Direct exposure of laser to the cell during optical trapping may inflict photodamge. Although a number of indirect manipulation approaches have been reviewed, none of them is partic- ularly useful for transporting and positioning cell to a desired location. Most of the approaches take advantage of adhesive coating to attach cells with op- tically trapped microparticles to manipulate them indirectly. However, that makes a permanent bonding between cell and microparticle that cannot be de- 53 tached after manipulation. Hence, these approaches are not useful where cells need be studied for a long time interval after manipulation. A gel microbead is proposed in [MFA09] that can be attached or detached from the cell at will by UV illumination. However, that requires a UV illumination setup along with the optical tweezers. Multiple optically trapped microparticles without any coating can be used as robotic fingers to indirectly grip the cell. How- ever,manual control of multiple particles is nearly impossible. Novel planning and control approaches need to be developed to coordinate the motions of multiple optically trapped particles to manipulate cells indirectly. After ma- nipulation, cells can be released from the optical fingers by simply switching off the laser. 54 Chapter 3 Automated Cell Transport in Optical Tweezers-Assisted Microfluidic Chambers In this chapter2 , we present an automated, physics-aware, planning approach for transporting cells in an optical tweezers assisted microfluidic chamber. We use optical tweezers to achieve efficient manipulation of cells with improved precision inside a microfluidic chamber. The particular application of the developed motion planning approach concerns making a uniform distribution of the cells inside mi- croNets of the chamber to study cell signaling. We use computational fluid dynamics to model fluid forces inside the chamber. The resulting fluid forces are incorporated into the widely used Langevin equation to simulate the motion of cells. The devel- oped simulator is used to build a look-up table for determining probabilities of a cell successfully reaching one of the outlets under the influence of the fluid flow from each location inside the chamber. The developed planner generates collision-free paths that exploit the fluid flow inside the chamber to allow robust cell transport while minimizing the required laser power and operational time. In addition, the planner utilizes the offline generated simulation data to decide a suitable location inside the chamber at which to release the cell to be taken by the fluid flow to one of the outlets. The planner is based on the heuristic D* Lite algorithm that employs a specific cost function for searching over a novel state-action space representation. The effectiveness of the planning algorithm is demonstrated using both simulation 2 The work in this chapter is derived from the published work in [CSW+11] and accepted work in [CSW+13] 55 Figure 3.1: A schematic overview of a microfluidic device and sequential cleaning operation. The cells transported to empty microNets are marked as green, the cells released after moving to the edge of the workspace are marked as yellow, and the cells released inside workspace to allow them to move towards the outlets with the influence of fluid flow are marked as red and physical experiments in microfluidic-optical tweezers hybrid manipulation setup. 3.1 Introduction Cell localization, transport, sorting, and characterization are crucial in many emerging medical and biological applications [CDS09]. We will refer to these types of operations as cell manipulation. In medicine, for example, diagnosis, therapy, and drug delivery can be significantly improved by deploying specialized robotics technologies for manipulating cells. The ability to manipulate individual cells and thereby conduct highly discriminating cell and drug interaction studies will enable development of new drugs and possibly new diagnostic procedures that can detect the onset of lethal diseases at very early stages. Microfluidics has emerged as a very promising technology to manipulate cells 56 for high throughput screening [WKC+98], cell signaling analysis [FSH+08] etc. due to its low cost, low power consumption, and ability to handle a large sample pop- ulation simultaneously. However, careful control strategies must be developed to provide fine position control over the cells in some microfluidic chambers (e.g. see Figure 3.1). Another emerging technique which has become very popular over the last two decades in the field of micro-manipulation is optical tweezers (OT) [ADBC86, Ash92]. OT have been shown to be a very effective technique for trans- porting cells with high precision; however, throughput significantly depends on the maximum number of traps that can be created. The advantages of these two manipulation techniques can be exploited by combining them into a single hybrid system. In our hybrid system, we integrated a microfluidic chamber [FSH+08] (see Figure 3.1) into our OT system. The mi- crofluidic chamber contains about 10, 000 microNets [SFCW10] (previously, they have been termed traps, but to avoid confusion with the laser traps, herein we term them MicroNets or nets) that are created intentionally to direct the fluid flow in a certain direction and capture cells in each microNet. However, the number of cells captured in the microNets cannot be controlled by solely regulating the fluid flow. This results in non-uniform distribution of cells inside the chamber which is not de- sirable for certain biological experiments e.g. cell-cell interaction studies [DMK+12] in which each microNet should contain a desired number of cells to get statistically accurate results. The optical tweezers can be useful for providing fine control for moving the excess of cells from crowded microNets to the nets with insufficient number of cells 57 or by releasing the cells in suitable locations to be taken by the fluid flow to one of the outlets of the chamber (we will refer to this operation as cleaning in this chapter). However, the following challenges need to be addressed to utilize OT in providing microfluidics with more efficient and reliable manipulation control. Presence of fluid flow The microfluidic chamber needs to be provided with continuous fluid flow to keep the cells inside the microNets. Hence, OT needs to take the fluid flow into account during the cleaning operation. Moving the optically trapped cells along the streamlines increases the reliability of the operation. This allows using lower laser power to prevent damaging the cells that are transferred into microNets. On the other hand, in order to reliably transfer the cells to one of the outlets of the chamber by the sole use of the fluid flow, they need to be released by the OT at suitable positions. Although fluid flow is laminar inside the chamber, the streamlines get affected by the fluctuation in flow at the inlet, due to the presence of clogged cells at the entry to the chamber, and laser heating. This noise in streamlines need to be characterized to determine suitable release points for the cells. Operating space OT operates in a much smaller workspace (102 ?m ? 60 ?m in our setup) compared to the microfluidic workspace (see Figure 3.1). This re- quires sequential cleaning of microNets. A cleaning operation depicted in Figure 3.1 consists of moving the excess of cells from crowded microNets to empty microNets or released at suitable locations. After cleaning all the microNets, the workspace needs to be shifted by using motor-controlled stage. The cleaning operation contin- ues until all the microNets are cleaned. Sometimes, cells (in case of rare cells) need 58 to be stored in a convanient microNet that can be used to fill empty nets in next cycle rather than releasing them to reach the outlets of the chamber. Fast operation The cleaning operation needs to be very fast to utilize the high throughput advantage of the microfluidic chamber. Using holographic optical tweezers (HOT) [CKG02], multiple traps can be created to allow cleaning of multiple nets in parallel. However, manual handling of multiple traps in parallel is very challenging due to the presence of randomly moving cells in the workspace as well as fluid flow and hence makes the cleaning process less reliable and thus slower. Exposure to high intensity laser for a longer time due to slow manipulation process may cause photo-damage to the cells [NCL+99]. In this chapter, we have developed an automated, physics-aware, simulation- assisted planning approach for transporting cells in an environment with obstacles and the presence of fluid flow that enables fast cleaning of microNets inside a mi- crofluidic chamber using OT. This involves trapping of desired cells inside microNets, transporting them to other microNets or releasing them at suitable locations from which the cells can be taken by the fluid flow to one of the outlets of the chamber. In order to maximize the cleaning efficiency, we utilize offline simulation of cells moving with the influence of fluid flow inside the chamber to generate supporting data represented as flow vectors and probabilities of the cells successfully reaching the outlets of the chamber from all its discrete locations. We then use the generated simulation data in online planning as opposed to using manually constructed rules. The developed planning approach is similar to a physics-aware robot motion planning problem where the traps themselves can be regarded as robots. Our de- 59 veloped approach is independent of microNet arrangements, hence can be applied to a wide variety of microfluidic designs that focus on immobilizing cells inside the chamber and a secondary manipulation tool (e.g. OT) can be integrated to provide better handle on controlling the cell population. 3.2 Simulations of cell motion in microfluidic chamber 3.2.1 Overview Given a cell C located in the state ~x = [x, y]T in a microfluidic chamber under the influence of fluid flow, compute: DS all external forces exerted on the cell C at the state ~x. DS the probability preach and the required time treach for the cell C to successfully reach one of the outlets { ~xl,exit = [xl, yl]T}Nl=1 of the chamber (see Figure 3.1). Here, N is the total number of outlets. We adopt following approach to simulate the cell motion DS We use a commercial CFD package FLUENT (ANSYS, Inc. Version 13.0.0) to model the fluid flow inside the microfluidic chamber [KWLT08]. The quality of the fluid flow vectors are tested using experiments. DS We use a open source collision engine Box2D [box] to model the collision force of cells with other cells and microNets inside the chamber. DS We incorporate all the external forces into Langevin dynamics equation and solve the ordinary differential equation using Verlet integration scheme to get the trajectories of the cells. 60 DS We run the simulations for 100 times introducing a random Gaussian noise to the fluid force vectors to calculate the probability preach and the required time treach for the cell to reach one of the outlets ~xl,exit from every location inside the microfluidic chamber. 3.2.2 Simulation of cell motion A cell can be considered as a particle of a spherical shape. A particle mov- ing in a fluid undergoes the effect of a rapidly fluctuating force due to random collisions with the surrounding liquid molecules, as well as a hydrodynamic drag force [BLG10]. These forces are closely related to each other and are modeled using Langevin?s equation [Wei89] as follows: ?V (t) ?t = ? ? m V (t) + ? m ?(t) (3.1) where V (t) is the velocity of a particle with mass m and radius Ra at time t. This equation assumes a fluid with viscosity ?, which is a function of temperature T . The drag coefficient ? for a spherical particle is given by Stokes? law as 6pi?Ra,where Ra is the radius of the spherical particle. The scaling constant ? = ? 2?kBT in Equation 3.1 is obtained by applying requirements of the fluctuation-dissipation theorem [AT99], where kB is the Boltzman?s constant. The acceleration of the particle at the end of a uniform time step ?t can be written in the finite difference form [PDB+12, BBGL09, BLG10] as shown in Equation 3.2. A(t+ ?t) = ? ? m V (t) + 1 m ? 2?kBT ?t N(0, 1) + Fext m (3.2) 61 Here, the stochastic term in Equation 3.1 is replaced by normal distribution N(0, 1) and the scaling constant ? includes the time step ?t. The external force term Fext allows us to include the collision force and force due to the influence of fluid flow. Once we calculate the acceleration A(t + ?t) at the end of the time step ?t, we can use the velocity form of the second order Verlet integrator [Ver67] to calculate the position (R) and velocity (V ) of the particle at the end of each time [PDB+12, BBGL09, BLG10]. The simulation time step is taken as the closest multiple of 10 smaller than m? as described in [BLG10]. Before modeling the external forces (collision, and fluid force), we test the Brownian motion behavior of a freely diffusing particle by excluding the Fext term from Equation 3.2. We run the simulation for 300 s without the presence of any external force and recorded the positions of the particle along X axis at different time intervals. Then we plot the distribution of change in positions of the particles at those respective intervals. The distribution resembles the Gaussian distribution with zero mean, which agrees with the Brownian motion model. Then we check the standard deviation of the position-change distribution with the increasing time interval. The standard deviation increases gradually with the increase of time interval, which agrees with the Brownian motion physics. The change in the position of the particle along Y axis at different time intervals follows the same distribution as well. 3.2.3 Modeling of collision forces We use the open source collision detection library Box2D [box] to check for a collision of the cell with other suspended cells and static nets. Since the simulation 62 time step is very small, the cell does not move much in a single time step. So we do not need to go through any sophisticated collision force calculations. We use Box2D only for detecting a collision, and if a collision occurred we applied a static force in the normal direction of the collision point. However, checking for collisions for all individual cell-cell pairs and cell-net pairs would be computationally expensive. Therefore, we restrict the collision checking to the vicinity of each individual cell. The collision engine checks for collisions of the cells and nets that lie in 10Ra distance of the interested cell. 3.2.4 Modeling of fluid flow The fluid flow in a microfluidic chamber is laminar since viscosity dominates over inertia in reduced dimension [AB05]. We carried out computational fluid dy- namics (CFD) simulations using a commercial package FLUENT (ANSYS, Inc. Version 13.0.0). We used water (?f = 998.2 kg/m3) as working fluid. Hence, fluid flow fields are Newtonian and incompressible in nature. We used the Design Modeler of ANSYS to create the 2D geometry of the microfluidic chamber. For meshing, we used patch conforming method which is suitable for small features in the geometry. The momentum and continuity equations are solved using the semi implicit method for pressure linked equation (SIMPLE) algorithm. First order upwind scheme is chosen for spatial discretization of momentum. A flat velocity profile is imposed at a uniform flow rate of 1200 nl/min and a constant pressure (P = Patm) boundary condition is imposed at the outlet. FLUENT computes the fluid velocity at every node of the mesh element. 63 Figure 3.2: Measurement of flow vectors: (a) Solution of 0.98 ?m silica beads is pumped into a microfluidic chamber with a constant flow rate, (b) Detecting the beads from a thresholded image, (c) Tracking the beads to generate streamlines, (d) Confining all the trajectories into the representative pattern element (RPE) of the microfluidic chamber, (e) Calculating the velocity vectors from the streamlines over the RPE, (f) Mapping the flow vectors to the workspace of the OT 64 We developed an experimental procedure to qualitatively verify the velocity derived from CFD. We pump 0.98 ?m sized silica beads into the microfluidic cham- ber at a low enough volume rate so that we can track them using a high-speed camera and 40X objective lens. By tracking the positions of the beads we get the streamlines inside the chamber. To measure the velocity vector of the beads in dif- ferent positions of the chamber we record the images to capture the flowing beads (see Figure 3.2a) using a high-speed camera (at a frame rate of 60 fps). Then we de- veloped a MATLAB script (The MathWorks, Inc. Version 7.10.0.499 (R2010a)) to generate the trajectories followed by individual beads based on the particle tracking algorithm described in [CG96]. The MATLAB script applies a thresholding scheme (see Figure 3.2b) to detect the beads, track them in each frame and generates the trajectories by plotting the positions of the beads in subsequent frames (see Fig- ure 3.2c). We used the generated trajectories to calculate the velocity of the beads in different positions inside the chamber. However, due to the small size scale, motion of 0.98 ?m beads is influenced by a significant Brownian motion while following the trajectories. Hence, we need to filter out the noise due to Brownian motion from the trajectories to retain the monotonic behavior of the streamlines. The appearance of the net structures in our microfluidic chamber is repetitive in nature. We define a representative pattern element (RPE) (see Figure 3.2d) which appears repetitively in the whole chamber. Since fluid flow is dominated by the fluid viscosity (laminar flow), the relative positions of RPEs do not have much effect on the flow. Therefore, the streamlines around the RPEs are assumed to be similar regardless of their relative positions inside the chamber. 65 We represent all the trajectories found in Figure 3.2c with respect to the RPE coordinates (see Figure 3.2d). In that way, we have enough trajectories that can be averaged to filter out the Brownian motion and retain the monotonic behavior of the streamlines. We apply fine gridlines over the RPE to take the average of all velocities of the beads in each grid to remove the Brownian motion effect from the velocity vectors (see Figure 3.2e). For our automatic cleaning operation we use 60X objective lens with the uEye camera (IDS, Inc., Cambridge, MA) that has a smaller field of view. By applying the concept of repetitive patterns we map the flow vectors to the workspace of the OT (see Figure 3.2f). The fluid vectors computed experimentally qualitatively match with that com- puted by FLUENT. Due to their laminar nature, the flow of 0.98 ?m beads is caused by only a drag force that can be modeled as Stokes? law given by Equation 3.3. F = ?Vf (3.3) This equation assumes the fluid viscosity ? as a function of temperature T (?= 1.002?10?3 Pa-s and T=293 K for water). The drag coefficient ? for a spherical particle is given by Stokes? law as 6pi?Ra, where Ra is the radius of the spherical particle. The fluid force F causes the beads to flow and Vf is the velocity of the beads. Since we have calculated the force of the fluid at each position in the chamber, we use Equation 3.3 to develop a look-up table for all the forces acting in the corresponding positions. The fluid force acts in the direction of the fluid flow which is computed from the streamlines in Figure 3.2e. The forces at different positions in the chamber are plugged into Fext term in Equation 3.2 for simulation. 66 Although we use a flat inlet velocity profile for our fluid force computation, the fluid flow velocity is affected by flow fluctuation at inlet, clogged cells at the entrance to the chamber, and the evaporation due to exposed laser. Since there is no suitable way to measure these uncertainties, we apply a Gaussian noise to the fluid force at every discrete location to introduce uncertainty. At every location we change the fluid force from FLUENT by perturbing its direction with a random Gaussian with mean 0 and standard deviation 5 degrees. The standard deviation of 5 degrees is determined by running some initial experiments by releasing a cell at certain location of the chamber and recording its final locations. We ran the simulations for similar location with different standard deviation and chose the one that gives similar distribution of final locations. The standard deviation varies with the inlet fluid flow rate. To maintain the monotonic flow of streamlines we did not change the fluid force at every simulation time step ?t rather at every discrete location of the chamber. 3.2.5 Workspace simulator design In each time step ?t, the position, velocity, and acceleration of each cell are advanced in the system. The acceleration of the cell at the next time step t+?t is calculated using Equation 3.2. Next, the position of the cell is updated using the previous velocity and acceleration [PDB+12, BBGL09, BLG10]. Finally, we calculate the velocity of the cell at t+?t using the average acceleration from the current and previous time steps and the previous velocity. Therefore, the velocity Verlet integration generated a list of positions, velocities, and accelerations in each 67 Figure 3.3: Holographic optical tweezers (HOT) cell transport workstation: the image processing unit returns the positions of cells and obstacles in the workspace from the camera and passes them to the motion planner, the planner then computes the collision-free paths and determines the next trap positions for the control unit that activates the trap positions through the spatial light modulator time step. After each time step, the positions of the cells are provided into two force modules (i.e., collision and flow). The force value from the flow force module is perturbed with a random Gaussian noise to model the force fluctuation. Each force module returns a force value depending on the position of the cell. All the force values are then added to F ext to update the external force after each time step. 3.2.6 Building of the probability table In order to build the look-up tables for probability preach of cell to reach one of the outlets ( ~xl,exit) ? and time treach to successfully reach one of the outlets ( ~xl,exit) ?, we discretize the whole chamber into rectangular grids of dimension 0.4 ?m ? 0.4 ?m. We set one of the grid locations as the initial state ~xinit = [xinit, yinit]T of the cell and run the simulation for 100 times to record the final states ~xfinal = [xfinal, yfinal]T and required times treq. We use the final states and required times treq to calculate 68 the probability preach and average time treach for the cell to successfully reach one of the outlets ~xl,exit if the cell is released from that particular state. We continue the simulation for all the grid states to build the look-up table ? and ? for whole chamber. 3.3 Motion planning for automated transport of cells 3.3.1 Motion planning problem formulation Given, (1) the initial states { ~xi,init = [xi, yi]T}ni=1 of n cells to be transported in the OT workspace X ? ? X of the discretized operating space X of the chamber, (2) their candidate goal states { ~xj,goal}mj=1 represented either as one of the chamber outlets ~xl,exit or microNets within X ?, (3) static and dynamic obstacles {?k}lk=1 represented either as microNets or other moving cells, (4) a probability look-up table ? containing probabilities preach of a cell successfully reaching ~xl,exit from each possible discretized location ~x ? X , (5) a time look-up table ? containing the average time treach required for a cell to reach ~xl,exit for each ~x ? X , and (5) a fluid force map ? defining a fluid force vector ? for each ~x ? X , compute: DS collision-free trajectories {?i}ni=1 for n laser traps to transport the cells either to their target microNets or release locations within OT operating space X ?, while following fluid flow streamlines in order to maximize the cleaning reliability as well as operation speed. 3.3.2 Assumptions We made the following assumptions: 69 DS We approximate cells as perfect spheres of radius Ra. DS We assume the optically trapped cells move with the same velocity as the traps. This is ensured by selecting an operating speed using which the beads can be reliably trapped by the laser traps [BBGL09]. 3.3.3 Motion planning approach Since the microfluidic environment is dynamically changing due to fluid flow and Brownian motion of cells, the required trajectories for the cells must be fre- quently replanned. The architecture of the cell transport workstation is shown in Figure 3.3. The imaging unit needs ?tg to process the image sequence and the mo- tion planner needs ?tp to generate collision free trajectories. The total time taken by imaging and motion planner unit (?tg + ?tp) is determined by the control unit update, which is about 66 milliseconds. Hence, we need a fast replanning scheme to be able to compute the trajectory within the planning time interval ?tp. Our motion planner adopts the fast heuristic search algorithm D* Lite [FLS05] to find an efficient trajectory for a single cell from a given initial ~xinit to a goal ~xgoal position. The algorithm functions similarly as a backward version of the A* al- gorithm [HNR68]. It incrementally expands the states from ~xgoal to ~xinit. During computation of a trajectory, all the remaining cells and microNets are considered as obstacles. The heuristic is used to guide the search in order to expand the minimum number of states and thus maximize planning efficiency. During the search, the planner maintains a set of states named as open set ?(~x). It contains the states that are more likely to be expanded next based on their cost in a priority queue. For 70 replanning, the planner reuses the history of the search from previous planning time interval by maintaining the same open set ?(~x) throughout the entire planning hori- zon. When the cost of a node is changed due to the change in OT workspace states X ?, the planner immediately inserts the node into ?(~x) and continues expanding the node with the lowest cost until a new trajectory is evolved. This allows the con- troller to efficiently launch multiple plans corresponding to multiple traps in order to transport multiple cells simultaneously. The algorithm terminates when each cell reaches its goal position ~xgoal. The following sections present the state-action space representation, cost function, and planning algorithm itself. 3.3.3.1 State-action space representation for planning The state space of OT is represented as a 2D rectangular grid since we translate cells only in x? y plane. The discrete state ~xk = [ xkc , ykc ] of a cell C is thus defined as a vector of its position ~xkc at time step k corresponding to a particular grid cell. An action control set U = { ~ukt,1, ~ukt,2, . . . , ~ukt,8, ~ukr} consists of eight linear trans- lation actions ~ukt,i and a single release action ~ukr available for execution at a given time step k. By executing the release action ~ukr , the cell is immediately released from the trap allowing the fluid flow to transport it to one of the goal states ~xj,goal. All linear actions can be represented mathematically as follows. ~ukt ( ?xk, ?yk ) = ? ????xk ?yk ? ??? (3.4) where ?x and ?y are the linear translations along X and Y axis, respectively. When the optical trap executes an action ~ukt at time step k, it transitions from 71 Figure 3.4: Illustration of cost-to-go g(~x?), transition cost t(~x, ~x?), and heuristic h( ~xinit, ~x) ~xk to ~xk+1 using the following equation. ~xk+1 = ? ???? ???? ~xk + ~ukt for the linear actions, ~xj,goal for the release action (3.5) 3.3.3.2 Cost function The planning algorithm iteratively expands the states from the priority queue (open set ?(~x)) with their key values [FLS05] computed as key(~x) = [key1(~x), key2(~x)], = [min(g(~x), rhs(~x)) + h( ~xinit, ~x), min(g(~x), rhs(~x))] (3.6) g(~x) is the optimal cost-to-go from ~x to ~xgoal, h( ~xinit, ~x) is the heuristic cost estimate of the trajectory between ~x and ~xinit, and rhs(~x) is the one-step look-ahead cost 72 Figure 3.5: m? ? coupling cost function: (a) illustration of different components in the cost function: m(~x) is the magnitude of flow vector at state ~x, ?(~x) is the direction of flow vector at state ~x with respect to the direction vector from ~x to ~x?, d(~x, ~x?) is the Euclidean distance between states ~x and ~x?, (b) characteristics of the m? ? coupling cost function which is calculated according to rhs(~x) = ? ????????? ???? ???? 0 if ~x = ~xgoal, min~x??succ(~x))(t(~x, ~x?) +g(~x?)) otherwise (3.7) where succ(~x) denotes a set of possible resulting states after taking an action ~u at state ~x and t(~x, ~x?) denotes the transition cost (see Figure 3.4) of moving from ~x to ~x?. In order to ensure optimality, the heuristic function may not overestimate the true cost to ~xinit. We use the time required for the trap to travel the distance between ~x and ~xinit to calculate h( ~xinit, ~x). The magnitude m(~x) and direction ?(~x) (see Figure 3.5a) of the fluid force vector acting at state ~x are combined with the Euclidean distance between ~x and ~x? to calculate the transition cost t(~x, ~x?) for linear action. The magnitude and direction of flow vectors are coupled and cannot be separated. Hence, t(~x, ~x?) has 73 two components as t(~x, ~x?) = ? ??? ??? w d(~x,~x?) v + (1? w)c(~x) + e for linear actions , r(~x) for release action (3.8) where d(~x, ~x?) is the Euclidean distance (see Figure 3.5a) between ~x, ~x? and c(~x) is the m-? coupling cost defining the contribution of magnitude and direction of flow vectors, and r(~x) is the cost associated with the release action. The edge cost e is set to ? if either ~x or ~x? lies in obstacle. Otherwise, e is set to 0. v is the constant trap speed and w is a user defined fluid force weight parameter (0 ? w ? 1). We define the m-? coupling cost c(~x) using a smooth function stated as follows: c(~x) = 0.5 +m(~x)(?(~x)? 0.5) (3.9) where m(~x) is the normalized magnitude of the contributing flow vector at ~x, and ?(~x) is the normalized angle between the direction vector from ~x to ~x? and the flow vector. The characteristic of c(~x) is illustrated in Figure 3.5b. t(~x, ~x?) is set to ? if ~x lies in an obstacle to prevent it from further expansions. We want the traps to follow high magnitude flow-lines as long as the angle between the direction vector from ~x to ~x? and the flow vector does not exceed a limit. Beyond that limit, following the high magnitude flow-lines may lead into moving the traps across them. This would require higher laser power to execute the plan in order to prevent the cell being knocked out from the trap by the fluid flow. We define the limiting value of ?(~x) to be 0.5 for our algorithm to be conservative. The value of c(~x) decreases with the increase of m(~x), preferring the higher magnitude 74 flow-lines up to the limiting value of ?(~x). Beyond that, the value of c(~x) increases with the increase of m(~x) to suggest the lower magnitude flow-lines. We define the cost associated with release action r(~x) using the following function. r(~x) = ? ???? ???? (1? preach)treach if preach ? prelease,T , ? otherwise (3.10) preach is the probability of the cell to reach ~xl,exit if released at state ~x and treach is the corresponding required time according to ? and ?. prelease,T is a user-defined release threshold parameter that allows the planner to consider only the states that have higher probability to reach ~xl,exit. 3.3.3.3 Planning algorithm The algorithm for computation of trajectories for the desired cells to transport is given as follows: Input: (a.) Finite non-empty state space X . (b.) Obstacle map ? where ?(~x) represents an obstacle state. (c.) Obstacle cost map ? such that, ?(~x) = ? ???? ???? 1 if ~x lies on obstacle, 0 if ~x lies on free space. (d.) Fluid force map ?, where ?(~x) encompasses the magnitude m(~x) and direction ?(~x) of the fluid force vector at state ~x. 75 (e.) Probability look-up table ?, where ?(~x) encompasses the probability preach of the cell to reach one of the outlets ~xl,exit if released at state ~x. (f.) Time look-up table ?, where ?(~x) represents the average time treach of the cell to reach one of the outlets ~xl,exit if released at state ~x. (g.) Initial states Xinit = { ~xi,init}ni=1 ? X of target cells. (h.) Goal states Xgoal = { ~xj,goal}mj=1 ? X of the target cells. (i.) Planning time interval ?tp, goal deviation threshold wth. (j.) User defined fluid force weight parameter w and release threshold parameter prelease,T . Output: Trajectories {?i}ni=1 for the cells to be transported at each planning time in- terval ?tp Steps: (1.) For each target cell go through the following steps: i. Read the obstacle map ? and identify the obstacle states Xobs = { ~xobs,i}mi=1 ? X . ii. For each obstacle state ~xobs,i  Xobs, compute a safety zone by determin- ing the adjacent neighboring state set Neighbor( ~xobs,i) ? X and setting ?(Neighbor( ~xobs,i)) = 1. 76 iii. Using the cost function described in Section 3.3.3.2 expand the successor states succ(~x) with minimum cost from goal state ~xgoal to the initial state ~xinit [FLS05] to calculate the initial trajectory ? . iv. Keep open set ?(~x) (priority queue that stores the states that are most likely to be expanded later in the search) for future expansion during re- planning. (2.) Execute the trajectories. Stop the algorithm if ? Xinit?Xgoal ?? wth, otherwise update the obstacle cost map at every planning time interval ?tp. (3.) If there is any change to the cost in any state due to the change in the workspace environment, insert the affected states into the open set. (4.) Go to Step 1iii to expand nodes from ?(~x) based on priority key (see Equa- tion 3.6) until new trajectories are evolved. 3.4 Results and discussions 3.4.1 Experimental setup and methods A schematic of the microfluidic chamber used in this chapter is shown in Figure 3.1. Cell medium is injected into the chamber through one of the three inlets using a digitally controlled microsyringe pump. The cell medium gets divided into six different channels before entering the rectangular microNet region in order to distribute the cells uniformly. The cells are captured inside different microNets as they flow through the microNet region. The actual dimension of the microNet region is 3.77 mm ? 2.36 mm consisting of 9432 number of nets. The height of the device 77 is 10 ?m to prevent stacking of cells. OT can only operate in a limited space of 74 ?m ? 43 ?m ? 10 ?m that consists of only four microNets. Hence, we have to carry out the cleaning operation in multiple steps to be able to clean the entire chamber. The entire cleaning operation starts from the lower left corner of the rectangular microNet region. We demonstrate the usefulness of the planner using a BioRyx 200 (Arryx, Inc., Chicago, IL) holographic laser tweezer. It consists of a Nikon Eclipse TE 200 in- verted microscope, a Spectra-Physics Nd-YAG laser (wavelength 532 nm), a spatial light modulator (SLM), and proprietary phase mask generation software running on a desktop computer. Nikon Plan Apo 60x/1.4 NA, DIC H oil-immersion objec- tive is used. The maximum rate at which traps can be set is the update rate of the Spatial Light Modulator (SLM), 15 Hz, and the minimum step size is 150 nm. The feedback control is achieved with a second PC equipped with a uEye camera (IDS, Inc., Cambridge, MA) for imaging the cells through transparent microfluidic chamber and running the software for executing the planning algorithm. A digi- tally controlled microfluidic syringe pump (SP230iW Syringe pump manufactured by World Precision Instruments, Inc., Sarasota, FL) is used to inject cells into the microfluidic chamber through the inlets. Cells are identified and located by thresholding the image and then calculating the center of mass of all the remaining blobs (see Figure 3.3). Yeast cells used in this experiment are cultivated from fast growing yeast powder. 0.016 gm of yeast powder is mixed with 3% (w/v) glucose solution. The cells are allowed to grow for an hour. After an hour, the concentration of cells is examined under microscope. 78 The average diameter of cells after an hour is 5-8 ?m. For measuring the fluid flow vectors we use 0.98 ?m diameter silica beads (density of 2000 kg/m3 and refractive index of 1.46, purchased from Bangs Laboratories, Inc., Fishers, IN). Initially Yeast solution is pumped into the chamber with a flow-rate of 0.03 ?l/m. It takes about 20 minutes to fill the chamber with yeast cells trapped inside the microNets. Once the chamber is filled up, we switch the pump inlet from the Yeast solution to water. 3.4.2 Simulation results In this section we demonstrate two novel functionalities of the planner using simulations: (1) Utilizing fluid force map ? to derive collision-free paths based on the user defined fluid force weight parameter w, (2) Using the probability look- up table ? and time look-up table ? based on the user defined release threshold parameter prelease,T to decide suitable release points of corresponding laser traps. The simulation results are obtained on Intel(R) Core(TM)2 Quad processor with 2.83 GHz speed. We scale down the microfluidic chamber for simulation to a region of 195 ?m ? 150 ?m to avoid computation overhead to build the probability look-up table ? and time look-up table ?. The simulation can be run for whole chamber in the similar fashion described in section 3.2.6 to build the entire look-up table. The dimensions of the OT workspace are chosen as 65 ?m ? 50 ?m. We discretize the workspace into 7650 number of grids for planning with grid size 0.4 ?m ? 0.4 ?m. The z dimension of the workspace is ignored since the laser is constrained to move in x?y plane. In each planning time interval ?tp laser can either move only to next neighboring grid or can release the cell to let it move with the influence of 79 Figure 3.6: Variations in cell trajectories as well as release locations based on user defined fluid force weight parameter w and release threshold parameter prelease,T : (a) w = 1; prelease,T = 0.85, (b) w = 1; prelease,T = 0.65, (c) w = 1; prelease,T = 0.5, (d) w = 0.5; prelease,T = 0.85, (e) w = 0.5; prelease,T = 0.65, (f) w = 0.5; prelease,T = 0.5, (g) w = 0; prelease,T = 0.85, (h) w = 0; prelease,T = 0.65, (i) w = 0; prelease,T = 0.5 80 fluid flow. In the workspace, 5 microNets can be accommodated, hence can be cleaned in parallel. The simulation of transporting one cell from each of the 5 microNets to the suitable release location is shown in Figure 3.6. The target cells are labeled as Ti. The goal locations ~xj,goal of all the cells are assigned to the outlets ~xl,exit of the scaled chamber which is outside of the OT workspace. Hence, the planner is forced to release the cell inside the workspace based on prelease,T at the locations denoted by R (see Figure 3.6). The suitable release locations vary with the user defined parameters w and prelease,T . The computation time for calculating 5 trajectories depends on user defined parameters w and prelease,T (see Equations 3.8 and 3.10). Figure 3.6 shows the simulated trajectories for the cells with three different w and prelease,T . Each trap coordinates with the movements of other traps, while generating the trajectories so that two traps do not move to the same location at the same time. The planner generates the shortest path between initial and the goal position with the fluid force weight parameter value w = 1.0 (see Figures 3.6a, b, c). Since the planner does not account for the fluid flow inside the chamber, the shortest path most often prefers the laser to go across the fluid streamlines. Therefore, the transporting cells have higher risks of being knocked out from the traps. Moreover, the laser power needs to be increased in this case in order to hold the cells against the fluid flow while moving across the streamlines which is susceptible to cell damage. The planner prefers high magnitude streamlines that are aligned with the direction of motion of traps with the fluid force weight parameter value w = 0 81 (see Figure 3.6c, d, e). Hence, the planner needs to expand more nodes compared to the shortest path search. The resulting path is longer and needs more time to execute. However, the planner can use minimum laser power to execute the path since the laser follows the fluid streamlines making it suitable to retain cell viability. Moreover, it will reduce the chance of cells being knocked out of the traps by the fluid flow. With the fluid force weight parameter w = 0.5 (see Figure 3.6f, g, h), the plan- ner generates a balanced path that can be shorter compared to the path calculated using w = 0. The planner prefers the shortest distant grids, where the flow vectors have lower magnitude since the laser can still be able to hold the cell. The user sets the parameters based on the fluid flow conditions and sensitivity of the cells being manipulated by the laser beam. With the change of prelease,T , the planner chooses different release points for the cells from respective traps. With a higher prelease,T (e.g. 0.85) all the cells are carried to the edge of the workspace before release (see Figure 3.6a, d, e) because of the fact that there is no other locations in the workspace that have higher probability for the cells to reach ~xl,exit if released from the traps. With the decrease of prelease,T , the planner is able to release the cells much earlier. The release points are also influenced by w (see Figure 3.6e, h) since in addition to reaching probability preach, the planner uses treach (see Equation 3.10) to decide the suitable release points. 82 Figure 3.7: Automated transport of two cells to their respective goals to control cell population: (a) initial scene, (b) target cells T1 and T2 are moving towards their respective goals, (c) target cell T2 is changing direction towards its goal, and (d) target cells reach the respective goal locations 3.4.3 Experimental results In this section, we demonstrate the automated cell transport capability of the OT-microfluidic system with some initial experiments with our physical systems. Due to some physical limitations of our customized setup, we restricted the fluid force weight parameter to w = 1 and threshold parameter to prelease,T = 0.85 for this demonstration, i.e. the planner does not utilize the high magnitude streamlines while transporting the cells. Hence, all the cells are transported to the nearest local exits and released while avoiding collisions with the microNets and other transporting cells inside the workspace. After identifying the cells and microNets using image processing, we select the cells that are in the same optical plane to be transported automatically. The 83 weight w and threshold prelease,T parameters are also provided to the planner. The planner automatically computes collision-free paths to release locations based on the input parameters. The planner transports the cells by creating point traps at every planning time interval ?tp. Since the planner does not generate paths that utilize the fluid flow streamlines, the laser power has to be set to the significant 0.6 watts. However, the laser power at the objective is much smaller due to some losses in the hologram phase calculation. A constant flow of water (0.03 ?l/m) is maintained throughout the experiments. In the designed experiment as illustrated in Figure 3.7, a uniform distribution of a single cell in each microNet has to be maintained. In this figure, the target cells are labeled as Ti, their initial locations are marked using green ???, and their corresponding release locations are marked using red ??? and labeled as Gi, where i represents an index of a target cell. In the experiment, the two cells T1 and T2 need to be removed from the microNet (locations are marked using green ???) in order to achieve the required distribution. The cell T1 is transported automatically to the empty MicroNet location G1, while the other cell T2 is transported to the location G2 and then released. During the transport, the cells avoid other microNets and cells in the workspace. The transport time is shown in the upper left corner of the images in Figure 3.7. The cleaning time of the OT workspace in this experiment is 13 s. After cleaning the microNets, the user can continue in operation at a different location of the microfluidic chamber by manually changing the position of the microfluidic stage. The effectiveness of the developed system can be expressed in terms of the 84 expected transport time for a cell to reach the exit of the chamber, which is a function of its maximum transport speed and probability preach of successfully reaching the exit. In order to measure the successful release rate experimentally, we released the cell for 10 times at a particular region in between two microNets as the planner suggested and let it follow the flow. Each time when the cell went through the chamber without being captured by any other microNet, we marked it as a success, otherwise as a failure. The cell successfully reached the outlet of the chamber 6 times out of 10 test cases. The rate 0.6 of successfully reaching the outlet is lower than prelease,T = 0.85 suggested by the simulator partly because for the simulation we used a scaled down area which is smaller than the actual microfluidic region. If we hold the cell using the optical trap and move it all the way out of the chamber following the fluid flow lines, preach will be as high as 0.9 as opposed to releasing it at a suggested location determined by the planner. However, the transport time will increase due to the limited, maximum velocity of the trap which is in the order of 10-20 times less than the speed of fluid flow. Our simulation and physical experiments suggest that there exist release locations inside the OT workspace that have a higher probability of reaching the exit of the chamber. If there does not exist such locations, the planner suggests to hold the cell all the way out of the chamber. Our approach utilizes a combination of an optical trap and fluid flow for cell transport. There are two options for removing a redundant cell from the chamber. First, the cell can be transported all the way out of the chamber using only an optical trap, making sure the cell does not get stuck inside another microNet. In this case, the transport speed of the cell is limited by the maximum speed of the 85 (a) (b) Figure 3.8: Three-stage probability tree of a cell successfully reaching the exit: (a) an example of a more general scenario with the existence of release positions inside the workspace that have higher probability to reach the cell to one of the exits, (b) an example of a worst case scenario where cell always gets trapped in one of the microNets trap which is 10 to 20 times smaller than the speed of the fluid flow. Second, the cell can be transported using a combination of the fluid flow and the optical trap. In this case, the cell is taken out of its current microNet and then released at a suitable location nearby. The location is selected such that it increases the probability of the cell successfully reaching the exit. If the cell gets captured by one of the microNets downstream, it is trapped and released again at a new suitable location. The probability of the cell successfully reaching the outlet of the chamber increases as the cell gets closer to it. The expected time of the cell reaching the exit can be computed recursively using a probability tree. An example of the tree is shown in Figure 3.8a). The root of the tree represents the current position of the cell. The emanating edges of each node represent two possible outcomes of releasing the cell. The cell either reaches the exit of the chamber or is captured by another 86 microNet inside the chamber. The edges determine probabilities of the two possible outcomes corresponding to the current state of the cell. The computation of the expected time starts from the leaves up to the root of the tree. By climbing the tree up to the root, the expected transport time treach,i for each node i is computed and gradually propagated back to the root. The time treach,i is computed as the average over the two possible outcomes according to treach,i = ptrappedtreach,s + (1 ? ptrapped)treach,m, where ptrapped is the probability of the cell getting trapped in one of the microNets, treach,s is the expected time of successfully transporting the cell in a single attempt to the exit by the sole use of the fluid flow, and treach,m is the expected time of multi-step cell transport that combines the use of the optical trap and the fluid flow. In the worst case (see Figure 3.8b), the cell will be always captured by one of the microNets after it is removed from its current microNet and released from the optical trap to be taken by the fluid flow. Let treach,t be the time required to transport the cell to the exit by the sole use of the optical trap and the total transport length is lchamber. Then, the total time treach,m required to transport the cell to the exit using a combination of the fluid flow and the optical trap is less or equal to treach,t since a fraction of lchamber will be transported with the speed of fluid in the former case. 3.5 Summary Microfluidic devices are becoming widespread tools in cell biology and medicine because of their ability to handle a large volume of cells and non-invasive nature of 87 manipulation. However, the lack of precise position control makes the tools often inconvenient and highly inefficient. The use of OT as a complementary tool en- sures precise position control inside a microfluidic chamber. This chapter describes a fast heuristic based planning approach built on D* Lite algorithm with a novel state-action space representation and a new cost function. That enables efficient and reliable cleaning of multiple nets in parallel inside a microfluidic chamber, while drawing minimum laser power during execution of the cleaning plan. The devel- oped composite cost function incorporates the magnitude and direction of fluid flow vectors in order to compute trajectories that follow the fluid flow. The computed trajectories ensure reliable cell transport since the cells do not need to be trans- ported across the flowlines and need less laser power to execute preventing them from photodamage. Moreover, we utilized our developed physics-based simulator to build a look-up table that contains probabilities of a cell successfully reaching one of the chamber outlets for each discrete location in the chamber. The planner utilized the table to decide suitable release locations for the cells. Manual control of the microscope stage to move the OT workspace to a differ- ent region of the microfluidic chamber slows down the cleaning process. Chapter 4 will focus on planning for synchronized movement of the microscope stage and op- tical traps that will further expedite the automated cleaning. In this chapter, cells are directly trapped to be transported to their nearby unfilled microNets, which may affect their viability. Hence, another future direction of this research is to use optical grippers [BCLG11, KCA+11] made of optically trapped beads to indirectly trap and transport cells to the desired microNets (See Chapters 5 and 6 for details). 88 The planner will need to generate trajectories for the entire ensembles, which will require detailed modeling of trap-trap and multiple trap-cell interactions. 89 Chapter 4 Enhancing Range of Transport in Optical Tweezers Assisted Microfluidic Chambers Using Automated Stage Motion In this chapter 3, we present a planning approach for automated high-speed transport of cells over large distances inside an Optical Tweezers (OT) assisted mi- crofluidic chamber. The transport is performed in three steps that combine the optical trap and motorized stage motions. This includes optical trapping and trans- porting the cells to form a desired cell-ensemble that is suitable for a long distance transport, automatically moving the motorized stage to transport the cell-ensemble over a large distance while avoiding static obstacles, and distributing the cells from the ensemble to the desired locations using OT. The speeds of optical traps and the motorized stage are determined by modeling the motion of the particle under the influence of optical trap. The desired cell-ensemble is automatically determined based on the geometry of the microfluidic chamber. We have developed a greedy heuristic method for optimal selection of the initial and the final location of the cell-ensemble to minimize the overall transport time while satisfying the constraints of the OT workspace. We have discussed the computational complexity of the devel- oped method and compared it with exhaustive combinatorial search. The approach is particularly useful in applications where cells are needed to be rapidly distributed inside a microfluidic chamber. We show the capability of our planning approach using physical experiments. 3 The work in this chapter is derived from the published work in [CATW+13]. 90 4.1 Introduction Microfluidic chambers are emerging as useful devices for conducting research in biology and biophysics [ZA12]. Common applications include cell sorting [Lan12, MSD03], studying cell response under changing environment [ESL+10, UWIY03], stem cell research [ZA12], etc. However, microfluidic chambers lack the capability of precisely placing individual particles at the desired locations. Integration of optical tweezers with microfluidic chambers has provided fine motion control capabilities [CSW+13, WCK+11, WWS10, EGR+04]. Ma et al. [MYP+12] used specially designed dual channel line optical tweezers in Y shaped configuration to separate yeast cells of different sizes within a microfluidic chip. Honarmandi et al. [HLLK11] reported an approach combining microfluidics and optical manipulation to locally apply tensile and compressive force on a single target cell. Erikson et al. [EEN+07] developed an experimental platform to use epi-fluorescence microscopy and optical tweezers in combination with microfluidic system for the analysis of rapid cytological responses occurring in single cells. Optical traps enable simultaneous independent manipulation of multiple par- ticles [BCLG11, KCA+11, CSW+12]. However, typically optical tweezers have very limited workspace due to high magnification needed for optical trapping. For exam- ple, a microfluidic chamber may have dimension of 3,000? 2,000 F1m (see Figure 4.1), but the optical tweezers might be able to work only in 100 ? 100 F1m area (with 40? objective lens). So new techniques are needed to expand the workspace in which optical traps can be utilized. 91 Figure 4.1: A schematic overview of a microfluidic device with microNets [CSW+13] and long distance cell transport operation A typical microscope that is used to realize optical tweezers also has a motion stage driven by electric motors. This stage has large motion ranges in X and Y axes and can move at a very high speed. If a particle is held stationary using an optical trap then the stage motion capability can be used to move the microfluidic chamber and realize relative motion between the particle and the chamber. This capability is easy to realize during manual operation. However, conducting repeated biological experiments requires high level of automation [BPLG10, CTW+12, TCW+12]. The problem addressed in this chapter is motivated by microNet cleaning ap- plication described in Chapter 3. In this application, biological cells are injected into a microfluidic chamber containing physical traps defined as microNets (see Fig- ure 4.1) with the objective of placing exactly one cell in each microNet. Due to 92 the limited control over the flow process, some of the microNets may trap multiple cells, while some other microNets may not trap any cell at all. After the initial cell placement has been completed by the flow, the next step is to redistribute cells by moving them from microNets that contain multiple cells to the empty microNets (not containing any cells). In Chapter 3, we addressed the problem of using opti- cal tweezers for removing extra cells from microNets and getting them out of the microfluidic chamber [CSW+13]. In this chapter, we attempt to redistribute extra cells from overloaded microNets to empty microNets rather than simply removing the extra cells. MicroNets act as obstacles when an ensemble of cells is transported. This type of operation may require long range transport with an obstacle avoidance strategy and is the main motivation behind the problem formulated in this chapter. In this chapter, we present a new technique for realizing precise, concurrent, and automated transport of multiple cells over large distances. First, cells are moved using optical tweezers into a compact ensemble. During this phase multiple cells can be moved independently and concurrently. The state of the workspace determines the optimal location of ensemble formation and its shape. Once the ensemble is created, multiple optical traps can be used to hold cells in the ensemble in place. Now the stage carrying the chamber can be moved to transport the entire ensemble with respect to the optical traps. If during the stage motion, a particle dislodges from the ensemble, then the stage motion can be suspended, and an optical trap can be used to move the particle back into the ensemble. Stage motion can be resumed when the ensemble is complete again. The stage motion should move such that the ensemble does not collide 93 (a) Chamber with the target microNets filled with cells that need to be transported (b) Cells are transported to form an en- semble using optical traps. (c) Cell ensemble is transported to a new location using stage motion. (d) Cells are distributed to the desired mi- croNets. Figure 4.2: A schematic overview of cell manipulation operation 94 with any obstacle in the workspace. Once the ensemble arrives close to the final destinations of cells in the ensemble, the stage motion stops. Now optical traps are used to move all the cells in the ensemble to their final goal locations. Figure 4.2 graphically illustrates this concept. This chapter describes a planning system for combining motorized stage mo- tion with optical trap motion to realize automated transport of ensemble of cells over large distances. We have enhanced our prior work in the area of optical trap motion planning [CSW+13] by combining it with stage motion planning to realize this capability. Using the combination of both stage and optical trap motion, we are able to automatically transport particles at a fast speed in a larger workspace compared to the limit of optical tweezers workspace. 4.2 Problem formulation and overview of approach Let X be the overall workspace of the chamber and ?X be the corresponding discretized state-space. Let V (o) be the workspace of optical tweezers (OT) when it is located at the location o ? X in the overall workspace. The location o is selected such that V (o) ? X . Let ?V (o) be the discretized state-space corresponding to OT workspace V (o) such that ?V (o) ? ?X . A state in ?X or ?V (o) is defined as a location of an ensemble or a particle during trap path planning or a stage location during stage path planning (introduced in Section 4.4). If the motion stage is kept stationary, optical traps can only move particles within the OT workspace (a cell can be considered as a particle of certain shape). We apply appropriate safety margins to ensure that particles can be successfully transported between every pair 95 (a) Dimension of OT workspace with respect to overall workspace. (b) Initial and final locations of particles. (c) Particle transportable by only an optical trap. (d) Matching OT workspaces for transporting particles with a combination of optical motion and stage motion. Figure 4.3: Illustration of problem formulation 96 of locations in the OT workspace. By moving the motion stage with respect to OT, the OT workspace can be located at different regions of the overall workspace. In general, the size of the OT workspace is much smaller than the overall workspace (see Figure 4.3a for an illustration). Let P be the set of particles (assumed to be identical) that need to be trans- ported. Let Si and Sf be the set of initial and final locations of these particles respectively, such that Si, Sf ? X (see Figure 4.3b for an illustration). A particle can be moved from a location s in Si to location s? in Sf using only an optical trap, if there exists a location o for placing OT such that both s and s? belong to V (o) (i.e., s ? V (o) and s? ? V (o)) (see Figure 4.3c for an illustration). In general, we prefer transporting particles using only optical traps because it allows concurrent independent positioning of multiple particles. However, due to having smaller workspace, if an optical trap alone is incapable of transporting particle, then a combination of optical trap and stage motion, i.e., a hybrid strategy is used. The first step is to find locations in Si and Sf that can be handled by optical traps alone. This is done by finding the closest members of each s ? Sf in the set Si. If the closest members are within an OT workspace, then we assign particles at initial locations Si to final locations in Sf using the goal assignment method described in [BCLG12]. All locations that can be handled by only optical traps are removed from Si and Sf . The next step is to find a set of matching OT workspaces V = {(V 1i (o1i ), V 1f (o1f)), (V 2i (o2i ), V 2f (o2f)), . . . , (V ji (oji ), V jf (ojf )), . . .} that will use hybrid transport strategy (see Figure 4.3d for an illustration). V ji (oji ) contains locations Sji (i.e., Sji ? Si). 97 V jf (ojf) contains locations Sjf (i.e., Sjf ? Sf ). Particles from locations in Sji are trans- ported to locations in Sjf using a combination of optical traps and stage motion. V is computed using a greedy heuristic. We start by placing a window of the size of the OT workspace such that the top edge of the window is aligned with the top most location in Sf and left edge of the window is aligned with the left most location in Sf . If this window contains more than N locations, then we select N ?1 closest locations of other particles to the particle location in the top-left corner where, N is the maximum number of particles that can be concurrently transported using motion stage. N is set to 4 in the setup used in this chapter. This step leads to computation of V jf (ojf) and Sjf for a matching pair j. We then find matching V ji (oji ) by placing a window that is closest to V jf (ojf) and contains the same number of locations as in Sjf . If V j i (oji ) does not contain enough locations to match the number of locations in Sjf , we reduce the number of locations from S j f so that its cardinality matches Sji . Once we compute matching V ji (oji ), V jf (ojf), and associated Sji and S j f , locations in S j f and S j i are removed from Sf and Si, respectively. This process is repeated until Sf and Si are empty. The following steps are used to transport particles located at locations in Sji to locations in Sjf (we drop reference to index j to simplify the notation). (i.) Select the shape of the ensemble and its initial and final locations in the overall workspace X . (ii.) Plan paths for each particle at locations in Si into the initial ensemble location. (iii.) Transport particles into the initial ensemble location along the paths computed 98 in the previous step using optical trap motion. (iv.) Compute a path for the ensemble from its initial to the final location. (v.) Transport ensemble along the path generated in the previous step using stage motion. If one or more particles get detached from the ensemble, then stop stage motion. Compute path for the detached particle and bring it back into the ensemble. (vi.) When the ensemble reaches its final destination, stop stage motion. (vii.) Plan paths for the particles from their final ensemble locations to their corre- sponding locations in Sf . (viii.) Transport particles into their final locations using paths computed in the pre- vious step. The goal is to minimize overall transport time T , where T can be defined as the following: minimize ?i,?f T = max(t(ski , sk(?i))) + t(?i, ?f) + max(t(sk(?f), skf)) ski ? Si; skf ? Sf (4.1) Where, t(ski , sk(?i)) is the required time to transport particle k from the initial location ski to its location sk(?i) in the initial ensemble formation, t(sk(?f ), skf) is the time required to transport the particle k from its location sk(?f ) in the final ensemble formation to the final location skf , ?i is the initial ensemble location, ?f is 99 the final ensemble location, Si is the set of particles at initial locations, and Sf is the set of particles at final locations. Section 4.3 describes our approach for selecting ensemble shape and the initial and final ensemble location. Section 4.4 describes our approach for computing paths for optical traps as well as motorized stage. This includes computing paths and identifying maximum allowable speeds. Section 4.5 describes the overall system architecture for executing the computed paths. 4.3 Selecting ensemble shape and locations In order to create and transport ensembles, we need to determine their sizes. The following factors affect the size of an ensemble: (i.) Ensemble should be able to fit within the available empty space. So the size of the ensemble is restricted by the obstacle region. If a large portion of space is occupied by obstacles, then the ensemble has to be small in size. In other words, the ensemble size is governed by the minimum gap available between obstacles in the workspace. (ii.) While the stage moves, the ensemble is held together by optical traps. If optical trapping power is insufficient to hold ensemble together at higher speeds, then the stage needs to move slowly to ensure that the drag forces do not exceed the trapping force. This increases the transport time. So the ensemble size is limited by the total available laser power for the optical tweezers. (iii.) If the number of particles in the ensemble is large, then the probability of 100 (a) (b) Figure 4.4: A schematic illustration of ensemble shapes: (a) convex polygonal arrangement and (b) linear arrangement (a) (b) (c) Figure 4.5: Turning around tight corners may require relative repositioning within linear arrangements accidentally loosing a particle increases. The above described factors determine the optimal ensemble size. In this chap- ter, we limit maximum ensemble size to 4 particles due to the narrow space available between two consecutive microNets to move it around inside the microfluidic cham- bers used in the experimental validation. The next decision to be made in the planning process is about the shape of the ensemble. The following two main shapes are possible: (1) convex compact polygonal arrangement, and (2) linear arrangement. Figure 4.4 shows illustration of these shapes. Linear arrangements can navigate through narrow spaces. However, they require stopping the motion stage and optical trap rearrangements to navigate around tight corners (see Figure 4.5). 101 Particles in linear arrangement are more likely to dislodge from the ensemble due to drag force and Brownian stochastic forces. In this chapter, we only utilize polygon arrangements for 3 and 4 particle ensembles. For 2 particles we use linear arrangement. Once the ensemble shape has been decided, we need to determine the ensemble locations ?i and ?f in the OT workspace. As indicated in the previous section, we select the ensemble locations by minimizing the transport time T . The main steps in our approach for this task are as following: (i.) Let vi be a state of the discretized OT workspace ?Vi(oi) corresponding to Vi(oi). The initial state ?i of the ensemble will lie on this grid (see Figure 4.2b for illustration). (ii.) For every state vi in the grid (i.e., the candidate location of the ensemble), compute the time ti(vi) to complete the ensemble at vi using the Equation 4.2: ti(vi) = max(t(ski , sk(vi))) ski ? Si (4.2) where t(ski , sk(vi)) is the required time to transport the particle k from its initial state ski to the state sk(vi) in the initial ensemble formation state vi; Si is the set of particles at their initial states. (iii.) Let vf be a state in the discretized OT workspace ?Vf (of) corresponding to Vf(of). The final state ?f of the ensemble will lie on this grid (see Figure 4.2d for illustration). 102 (iv.) For every state vf of the grid, compute the time tf (vf) to disassemble the ensemble at vf using Equation 4.3: tf (vf) = max(t(sk(vf), skf)) skf ? Sf (4.3) where t(sk(vf ), skf) is the required time to transport the particle k from its state sk(vf) in the final ensemble formation state vf to its final state skf ; Sf is the set of particles at final states. (v.) Determine the set of boundary states of the state-space ?Vf(of), placed on Vf(of). Let vf (b) be an element of this set. Any path from Vi(oi) to Vf(of) will have to pass through the boundary of ?Vf(of). We use this fact to reduce the computational complexity and we first plan a path from the states in ?Vi(oi) to the boundary states of ?Vf(of). (vi.) Compute a path from every state vi to every state at boundary vf(b). Let t(vi, vf (b)) be the time to transport ensemble from vi to vf(b). (vii.) Compute a path from every boundary state vf(b) to every interior state vf (?). Let t(vf(b), vf (?)) be the time to transport the ensemble from vf(b) to vf (?). (viii.) Select a state ?i from the state-space ?Vi(oi) placed in Vi(oi) and a state ?f from the state-space ?Vf (of) placed in Vf(of) such that following total time T is minimized: T = ti(vi) + t(vi, vf (b)) + t(vf (b), vf(?)) + tf(vf ) (4.4) 103 Figure 4.6: A schematic overview of planning approach where ?i and ?f are selected using dynamic programming. We first compute the optimal time for the ensemble to arrive at every boundary state vf (b). Then, we compute the optimal arrival time for the ensemble at every interior state vf(?). Finally, by accounting for the disassembly time for the ensemble at every interior state, we find the optimal ensemble final state ?f . Tracing the path back, we identify the optimal boundary state, and the optimal ensemble start state ?i. 4.4 Path planning The overall operation envisioned in this chapter (see Figure 4.6) starts with the motorized stage that scans the entire microfluidic chamber and comes back to 104 the initial location. During the operation, the image processing unit identifies the microNets with unacceptable number of particles. The ensemble state selection algorithm (see Sections 4.2 and 4.3) divides the overall task into multiple transport tasks based on the constraints of the OT workspace. The planner is responsible to finish each single transport task. The overall planning is divided into three steps: (a) transporting the individual particle to its desired state in the ensemble using trap path planning, (b) transporting the ensemble towards the final ensemble state using stage path planning, and (c) transporting the individual particle from its state in the final ensemble formation to the final microNet location using trap path planning. Sometimes, the particles may get dislodged from the ensemble while transporting with stage motion. The exception handler identifies the breaking ensemble formation, stops passing the stage positions, and passes the control to the trap path planning to bring the particles back to the formation. After reaching the final ensemble state, the trap path planning is used to move all the particles to the final microNet locations from the final ensemble state. We use discretized OT workspace ?V (o) for trap path planning and discretized overall workspace ?X for stage path planning. A path planning problem can be defined as follows. Given, (1) the initial state vinit = [xi, yi]T of a particle represented by the initial particle location in ?V (o) or ensemble location in ?X , (2) its goal state vgoal = [xg, yg]T represented by the final location of the particle in ?V (o) or ensemble location in ?X , (3) static and dynamic obstacles {?i}li=1 represented either as microNets or other moving particles, compute a collision-free path ? for the laser trap or the stage to transport the particle or the 105 Figure 4.7: Optical tweezers setup with motorized stage ensemble to its goal state vgoal. Due to the dynamically changing environment of the microfluidic chamber under the influence of fluid flow and Brownian motion of particles, the required paths for the particles must be frequently replanned. The planning time ?tp is limited by the controller update rate and image processing time ?tg. The controller frequency of the OT system used for this chapter is 15 Hz that limits the allowable processing time ?tc = 66 ms. The total computation time in combination with ?tg and ?tp must be less than ?tc to maintain continuous operation. We adopt the D* Lite[KL02] based graph search algorithm as described in [CSW+13] for this chapter. The algorithm incrementally expands the states from the goal state vgoal to the initial state vinit in a fashion similar to the backward version of A* algorithm [HNR68]. All the remaining particles and the microNets 106 other than the target particles in the workspace are regarded as obstacles during the computation of the collision-free path ? . A heuristic function is used that guides the search in order to increase the planning efficiency. The planner maintains an open set ? containing the states that are more likely to be expanded next based on their cost during the search throughout the planning horizon. Thus, the planner is able to reuse the history of the search from the previous planning time interval during replanning. If the cost of a state node is changed due to the change in workspace, the planner only updates ? by inserting the state with the changed cost. A new path is computed by expanding the node with the minimum cost from ?. Hence, the planner does not need to focus on the entire search space that decreases the planning time ?tp significantly. This allows the controller to efficiently launch multiple plans corresponding to multiple traps in order to transport multiple particles simultaneously. The algorithm terminates when each particle reaches its goal state vgoal. 4.4.1 Trap Path Planning We define a state of a particle using vt = [xt, yt]T ? ?V (o) where [xt, yt]T denotes the position of a particle at a discrete time step t. We define a control action set Utr = {uttr,1, uttr,2, . . . , uttr,8} that consists of eight linear translation actions uttr,i available for the execution at a given time step t. All linear actions can be represented as follows. uttr ( ?xt, ?yt ) = ? ? ???xt ?yt ? ? ?? (4.5) 107 (a) (b) (c) (d) Figure 4.8: Transport of 2 F1m beads to their corresponding goal locations inside the ensemble formation using trap motion: (a) initial scene, (b) particle ?T4? reaches to its goal location denoted by ?G4?, (c) particle ?T3? reaches its goal at ?G3?, and (d) all the particles reach their respective goal locations in the final scene 108 where ?x and ?y are the linear action lengths along X and Y axis, respectively. For trap motion, the action length is selected to be ?x = ?xtr and ?y = ?ytr. When the optical trap executes an action uttr at the time step t, it transitions from vt to vt+1 using Equation 4.6. vt+1 = vt + uttr (4.6) We use the cost function defined in [CSW+13] for the planner to consider the fluid flow inside the chamber. This allows to reduce the probability of the particles being dislodged from the traps during the transport operation. 4.4.2 Stage Path Planning The microNets in the microfluidic chamber are arranged in a rectangular array (see Figure 4.1). We want to compute a path for stage that has minimum turn to avoid continuous readjustment of the particles inside the ensemble (see Figure 4.2c). Hence, we define a control action set consisting of four linear action for the stage. The control action set for the stage Us = {utN , utS, utE, utW} consists of four linear actions (e.g., north, south, east, and west) that can be represented similarly as in Equation 4.5. The control action length for the stage is selected as ?x = ?xs and ?y = ?ys. The state transition is represented by Equation 4.6. We only consider static microNet obstacles for stage planning with the reasonable assumption that the occasionally moving particles will not be able to break the ensemble formation of multiple particles trapped closely using multiple traps. In the worst case, if the formation breaks by sudden fluctuation in the fluid flow the trap path planning is invoked to move the particles back into the ensemble formation and continue the 109 (a) (b) (c) (d) Figure 4.9: Transport of the ensemble from an initial location to a final location using stage motion: (a) initial scene with the stage position denoted by ?E1?, (b) the stage moves downward to transport the ensemble to a location at ?E2?, (c) the stage moves towards left to transport the ensemble to ?E3?, and (d) the ensemble reaches to its final location at ?Ef? after a sequence of stage motions stage motion. The cost function c(vs) for the stage path planner is designed to minimize the transport time as shown in Equation 4.7. c(vs) = Lvs (4.7) Here, vs ? ?X is the state of the stage, L is the linear displacement resulting from the execution of an action us, and vs is the operating speed of the stage. 110 4.4.3 Modeling of Speed Constraints Based on the Trapping Force Considerations The allowable speeds of the stage and the traps are limited by the correspond- ing controller frequency (see Section 4.5). The dynamics of a particle moving under the actuation of the optical trap can be described by the following Equation 4.8 [HS11]. mx? = Ftr ? Fd (4.8) Here, m is the mass of the particle, x is the position of the optically trapped particle such that x ? X , Ftr is the trapping force which is a function of incident laser power and index of refraction of the suspending medium, and Fd is the viscous drag force which represents the resistance of surrounding fluid medium. The inertia force mx? can be neglected for low Reynold?s number[HS11]. Ftr can be modeled as a spring force for trapping a spherical particle lying within a distance less than or equal to its radius from the focal point (see Equation 4.9). Ftr = ktr(xf ? x), ||xf ? x|| < r0 (4.9) Here, ktr is the trap stiffness and xf ? X is the position of the laser focus. r0 can be estimated as the radius r of the particle. Ftr is the maximum at r0 = r. We compute the stiffness of the trap using ray-tracing approach described in [BCGV12]. Viscous drag force Fd can be calculated using Stoke?s law as given by Equation 4.10. Fd = 6pi?rvtr (4.10) 111 Here, ? is the dynamic viscosity of the surrounding medium and vtr is the optical trap speed. The maximum trap speed can be determined corresponding to maximum Ftr from Equation 4.8. For a spherical particle of 2 F1m diameter trapped in an aqueous medium with a trap stiffness of 1.5 ? 10?5 N/m corresponding to 20 mW laser power at the objective lens, the maximum trap speed can be calculated as 795 F1m/s. However, the allowable trap speed is dependent on the controller update frequency. For optical trap planner, the trap speed is limited by the SLM update frequency (see Section 4.5). In our calibrated holographic optical tweezers system, the SLM update rate is 15 Hz. Hence, the maximum allowable trap speed is limited to 15 F1m/s corresponding to ||xf ? x|| = 1 F1m. In case of multiple laser traps, the laser power is significantly reduced due to the formation of stray laser by SLM. Hence, the maximum allowable trap speed is further reduced to around 7 F1m/s for our system. On the other hand, in case of stage motion the trap position remains fixed. The transport is executed by the movement of stage which has a resolution of 40 nm (much lower than r0) and the controller frequency is 6 MHz. Hence, we can safely operate the stage at 795 F1m/s without losing the particles from traps. 4.5 System architecture A schematic of the microfluidic chamber used in this chapter is shown in Figure 4.1. A digitally controlled microfluidic syringe pump (SP230iW syringe pump manufactured by World Precision Instruments, Inc., Sarasota, FL) is used to inject particles into the chamber through one of its three inlets. The particle solution gets divided into six different channels before entering the rectangular microNet 112 (a) (b) (c) (d) Figure 4.10: Distribution of particles to their corresponding microNet locations: (a)initial scene with the particles arranged at their final ensemble formation, (b) particle ?T4? reaches to its microNet location denoted by ?G4?, (c) particle ?T3? reaches its microNet location at ?G3?, and (d) all the particles get distributed to their final microNet locations in the final scene region in order to uniformly distribute the particles. The particles are captured inside different microNets as they flow through the microNet region. The actual dimension of the microNet region is 3.77 mm ? 2.36 mm and consists of 9432 nets. The height of the device is 10 F1m to prevent stacking of the particles. OT can only operate in a limited space of 56 F1m ? 37 F1m ? 10 F1m that consists of only four microNets. Hence, we have to utilize motorized stage to carry out long distance particle transport. The cleaning operation starts from the lower left corner of the rectangular microNet region (see Figure 4.1). We demonstrate the usefulness of the developed planner using BioRyx 200 113 (Arryx, Inc., Chicago, IL) holographic laser tweezer as shown in Figure 4.7. The BioRyx 200 consists of a Nikon Eclipse TE 200 inverted microscope, a Spectra- Physics Nd-YAG laser (emitting green light of wavelength of 532 nm with 2 watts at the source), a spatial light modulator (SLM), and proprietary phase mask gen- eration software running on a desktop PC. Nikon Plan Apo 60x/1.4 NA, DIC H oil-immersion objective is used for laser magnification. The maximum rate at which traps can be set is limited by the update rate of the SLM, which in our case is 15 Hz. The sample holder is placed on a Proscan H107 motorized stage which can move the sample in X ? Y with respect to the microscope objective. The stage is equipped with a Proscan H29XYZ controller which can be connected to a PC using a RS 232 serial port connector. The controller can move the stage with the resolution of 40 nm. The stage is capable of moving in a 112 mm ? 70 mm rectangular area. The controller frequency is 6 MHz. 4.6 Results We performed 20 simulation runs to test the computational complexity of our greedy heuristic approach in determining the initial ?i and final state ?f of the ensemble. We discretized both the initial and final OT workspace with a 100 ? 100 grids. We chose N = 4 to determine the matching OT workspaces for our simulation runs. The simulation was conducted on an Intel(R)Core(TM)i7-2600 CPU. The clock speed is 3.4 GHz with a RAM of 8 GB. We implemented the planning algorithm in MATLAB. Our greedy heuristic method is able to determine the optimal states for initial and final ensemble formations that minimize the overall transport time 23 114 times faster on an average compared to the time taken by exhaustive combinatorial search. We demonstrate three different features of our planning approach with physical experiments. We use 10 mW laser power at the objective lens for the experiment. Laser power higher than 10 mW produces bubbles inside microfludic chamber that destabilize the fluid flow. We use a constant trap speed of 5 F1m/s and stage speed of 200 F1m/s through out the experiment. Hence stage motion provides 40 times faster transport operation compared to the trap motion. Figure 4.8 shows the trap motion to transport the microparticles to the initial ensemble location. The trap path planning unit computes four collision free paths corresponding to four microparticles for transporting them to the locations in the initial cell-ensemble. During the transport the planner continuously replan the paths to avoid other microparticles dynamically moving around. The target particles are denoted by ?T? and corresponding goal locations in the ensemble formation are denoted by ?G?. The paths of the particles are shown by white dotted lines in the figure. The total time taken by the traps is shown upper right corner of the figure. The particles successfully reach their respective goal locations in about 7 s. (corresponding to the associated number in Figure 4.8). Figure 4.9 demonstrates a sequence of automated stage motions to transport an ensemble from its initial to its final location. Stage locations are denoted by ?E? in the figure. The direction of the stage motion is shown using white ??? in the figure. The stage exhibits a zigzag motion due to the action set selection as described in Section 4.4.2. The stage successfully transports the ensemble to its 115 final location denoted by ?Ef? with a high speed of 200 F1m/s. Figure 4.10 shows the transport of 4 microparticles from the locations in the final cell-ensemble to the corresponding microNet locations with trap motions. The particles inside the ensemble are denoted by ?T? and final microNet locations are denoted by ?G?. The total time taken by the traps to transport the particles is shown in upper right corner of the figure. The trap path planning is able to compute collision-free paths for the particles in a scene with randomly moving microparticles. All the particles successfully get distributed to their respective microNet locations in about 7 s. It shows the advantage of the trap motion over the stage motion. The trap motion provides total control over the transport by handling all the dynamic and static obstacles in the scene. 4.7 Summary Microfluidics has gained acceptance as a medium-scale manipulation technique to transport biological objects over larger distances. In order to increase the preci- sion of manipulation, they need to be integrated with other devices such as optical tweezers. However, the limitation of a small workspace makes OT unsuitable for long distance transport operations. In this chapter, we have utilized a motorized stage for fast shifting of OT workspace to facilitate controlled transport of cells over large distances inside a microfluidic chamber. We have developed an automated manipulation approach that combines the operation of the optical trap and the stage. Our developed planner automatically computes collision-free paths to transport the cells using optical trap 116 motions to suitable locations to form a cell-ensemble, computes a suitable path to transport the cell-ensemble to a final ensemble location using the stage, and finally computes collision-free paths to disassemble the cell-ensemble by distributing the cells to their final goal locations. We have developed a greedy heuristic approach for efficient computation of initial and final cell-ensemble locations that will minimize the overall transport time. We have modeled the cell motion within the trap to determine the maximum allowable speeds for the optical trap and the stage. We have demonstrated the usefulness of the approach using our OT-assisted microfluidic chamber setup by transporting 2 F1m particles over a large distance. In the experiments, the shape of the ensemble was determined based on the available space inside the microfluidic chamber. This allowed us to transport the ensemble without any rearrangement of the particles. The developed approach for fast cell transport is suitable for conducting bio- logical experiments that need to be properly timed to exhibit desired motility. In future, the planner can be improved for concurrent movement of optical trap and stage that will enable us to transport different ensemble configurations in narrow spaces. 117 Chapter 5 Robust Gripper Synthesis for Indirect Manipulation of Cells using Optical Tweezers This chapter4 presents a robust gripper synthesis technique for indirect manip- ulation of cells using optical tweezers. Optical Tweezers (OT) are used for highly accurate manipulations of cells. However, the direct exposure of cells to focused laser beam may cause significant damage to their structures. In order to ameliorate this problem, we generate multiple optical traps to grab and move 3D ensembles of inert particles such as silica microspheres to act as a reconfigurable gripper for a manipulated cell. The relative positions of the microspheres are important in order for the gripper to be robust against external environmental forces and the exposure of high intensity laser on the cell was minimized. In this chapter, we present results of different gripper configurations, experimentally tested using our OT setup, that provide robust gripping as well as minimize laser intensity experienced by the cell. In order to construct the configurations, we developed a preliminary computational approach for gripper arrangement modeling and synthesis. The overall synthesis problem is cast as a multi-objective optimization problem that is solved in order to get a Pareto front of non-dominated solutions. 5.1 Introduction Cell manipulation (cell localization, transportation, sorting, characterization etc.) is crucial in many emerging medical and biological applications. The ability 4 The work in this chapter is derived from the published work in [CSW+12]. 118 to efficient and accurate manipulation of individual cells will enable researchers to conduct basic research at the cellular scale. Optical Tweezers (OT) that can grasp and move microscale and nanoscale biological objects using focused light provide a highly accurate and minimally invasive method of micro and nano-manipulation. A strongly focused laser beam is used to exert an optical gradient and scattering forces on an object, which results in creating a stable trap [Ash92] near the focal point. Objects are transported in workspace by moving the laser beam and are released from the trap by simply switching off the laser (see Figure 5.1). Due to the non- contact nature, OT is successfully used in various types of manipulations [SB94] of biological objects, e.g., for orienting, stretching, moving, etc. Holographic Optical Tweezers (HOT) is able to generate a large number of traps allowing simultaneous manipulation of multiple objects in three dimensions. However, due to the extreme focus of the laser beam to a small region, consid- erable photodamage can be inflicted on trapped cells, possibly causing death of the cells as noted by Ashkin [ADY87]. The underlying mechanism of photodamage has been proposed to be due to the creation of reactive chemical species [SB94], local heating [LSBT96], two-photon absorption [KLBT95] and singlet oxygen through the excitation of a photosensitizer [NCL+99]. Rasmussen, using the internal pH as a measure of viability, found that the internal pH of both E. coli and Listeria bacteria declined at laser intensities as low as 6 mW [ROS08]. Using the rotation rate of the E. coli flagella motor [NCL+99], it was found that 830 nm and 970 nm laser wavelengths were significantly less harmful to cells, and that the region from 870 nm to 910 nm was particularly harmful. 119 (a) (b) (c) (d) Figure 5.1: Direct vs. indirect manipulation using OT: (a) solution of Dictyostelium discoideum cell and inert silica microspheres, (b) the cell A is trapped directly, while the cell B is trapped indirectly using a synthesized gripper (t = 0 s), (c) the cells are being transported to their goal locations (t = 12 s), and (d) the cells are released at the goal locations; the cell A that was directly trapped is dead, while the indirectly manipulated cell B is still alive (t = 15 s) 120 Cell damage can be reduced by using less laser power which results in less intensity experienced by the trapped cells. Although, the trap stability of OT can be enhanced by utilizing feedback control [HZM09, WOHT08], this still would not be sufficient for robust manipulation of many sensitive cells. Hence, rather than reducing the damage exerted by optical manipulation on cells by minimizing the intensity of the laser beam (which would weaken manipulation capabilities of OT) or optimizing laser wavelength (which would require intensive calibration due to the need to have a different optimal wavelength for each cell line), in our approach, we indirectly trap [BCLG11] and manipulate cells using grippers composed from inert microspheres (i.e., silica beads; see Figure 5.1). We utilize HOT device which is capable of generating multiple, independently movable focused optical traps for 3D positioning of silica beads around a biological object. HOT utilizes Gaussian beam that has a maximum intensity at the focal point. The intensity drops exponentially with the increase of distance from the focal point. Thus, by placing the inert beads into safe distances from the manipulated cell, the cell can avoid the maximum intensity of the laser, while still being robustly held by the ensemble of beads. In this chapter, we present three synthesized gripper configurations that were tested experimentally using our HOT setup. The configurations provide robust gripping as well as impose the least possible intensity of the laser beam on the manipulated cell. We developed a preliminary computational approach for gripper arrangement modeling and synthesis. The overall synthesis problem is cast as a multi-objective optimization problem that is solved in order to get a Pareto front 121 of non-dominated solutions. The robustness of the gripper is characterized by the maximum velocity using which the ensemble can be moved in XY plane without effecting the stability of cell transfer. To the best of our knowledge, this is the first successful demonstration of a gripper that is able to reliably transport another object using HOT. 5.2 Gripper synthesis problem formulation We model the biological object that needs to be manipulated as a sphere to resemble the shape of a single yeast cell. Although cells are deformable in nature, we do not want to squeeze them with the gripper. That is why the cell is modeled as a rigid object so that the gripper objects are always placed at a safe distance. The gripper consists of six spherical silica beads of the same size as the cell to be indirectly manipulated. With more than six beads, the gripper might get unstable due to weaker traps (the laser beam needs to be split for creating multiple traps). The contact between a silica bead and the manipulated sphere is modeled as a point contact without friction. Friction is not a dominating force in microscale and thus can be neglected. Even if a small friction force exists, that can only improve gripping. Each bead has three degrees of freedom (DOFs) so that it can be positioned in any location around the object. We are only interested in eliminating undesirable translational motions of the gripped object. Hence, the object can rotate inside the gripper. Therefore, we are looking to achieve 3D relative form closure for the manipulated object by suitable placement of the gripper beads [ZD07]. Every position of a point lying in 3D space can be represented by its spherical 122 coordinates defined as the radial distance r, azimuthal angle ?, and polar angle ?. Hence, a gripper configuration can be defined as G = [r1, ?1, ?1, r2, ?2, ?2, r3, ?3, ?3, r4, ?4, ?4, r5, ?5, ?5, r6, ?6, ?6] . Each triplet in the gripper configuration represents the actual position of a silica bead in Cartesian coordinates defined as Pi = [ri cos ?i sin?i, ri sin ?i sin ?i, ri cos?i]. Here, the radial distance ri is the distance of the point Pi from the centroid of the object. The overall synthesis problem is to determine the best gripper configuration Gopt that will provide robust gripping based on friction- less contacts, as well as minimize the intensity of the laser beam experienced by the object to be manipulated. 5.3 Optimization functions and constraints Since we are modeling frictionless point contacts between a gripper and the manipulated object, we have to satisfy the form closure properties. Moreover, we want to ensure the best quality of the resulting gripper in terms of its stability and the intensity of the laser beam imposed on the object. Let Ci be a contact point on the object and Ni be the inward normal vector defined at Ci (see Figure 5.2), then the contact wrench at Ci is defined by Equation 5.1 gi = ? ??? Ni Ni ? Ri ? ??? (5.1) Here, Ri is the position vector for Ci in the global coordinate system. The wrench has 6 components for an object in 3D. By placing the origin to the center of the sphere (X ?, Y ?, and Z ? as shown in Figure 5.2), the wrench space can be 123 Figure 5.2: Manipulated object and contact positions of the gripper beads reduced to 3. Since we consider only the translational motion, we ignore the torque component in the wrench. All the wrenches can be combined to get grasp matrix G = {g1, g2, g3, . . . , g6} ? <3?6 of an 6-point gripper. As stated in [Mas01], a grasp can achieve form closure if the grasp matrix positively span all over the wrench space. The statement comes with the following theorems: DS A set of vectors {vi} positively spans the entire space (rB + rC) , 1 otherwise. Here, ?~ri (see Figure 6.5) is the unit direction vector towards the cell C from the gripper bead Bi and dBi,C is the distance between them. The momentum is transferred to the cell only when the beads are in contact to the cell. Hence, ?? is set to 0 when cell and bead are not in contact. We imposed some constraints on the action u when executing different types of maneuvers depending on the formation type to satisfy its motion constraints. For G4 and G6 gripper formations, the velocities of all the traps are constrained to be the same as given by Equation 6.5 ~vi k = ~vj k : ?i, j,where i, j = 1, 2, 3, . . . , n (6.5) In case of G2 and G3 gripper formations, the speed of all the traps is con- strained to be the same (see Equation 6.6). The trap motions are constrained only 147 Figure 6.5: Gripper formation with all the direction vectors parallel to the desired direction of the cell C in case of translate maneuver to pre- vent the formation from falling apart (see Equation 6.7). Similarly, the traps are restricted to move only towards the tangential direction of the cell in case of rotate maneuver (see Equation 6.8). |~vik| = |~vjk| : ?i, j,where i, j = 1, 2, 3, . . . , n (6.6) ~vi k . ? ~dg = 1 (6.7) ~vi k . ? ~ri = 0 (6.8) Here, ?~dg (see Figure 6.5) is the unit direction vector from the cell towards the desired waypoint that can be derived from the orientation of the gripper formation (see Equation 6.9). ? ~dg = [cos?, sin?]T (6.9) 148 When the gripper formation takes an action ~uk at time step k, it transitions from ~Sk to ~Sk+1 using Equations 6.10 and 6.11. ~Xk+1 = ~Xk + ?~Xk4t (6.10) ~?k+1 = ?k + ??k4t (6.11) Here, 4t is the time spent between two subsequent time steps. 6.3.2 Cost function The planner iteratively expands the nodes of candidate paths in the state- space from the initial state ~Si to the goal state ~Sg according to the cost function f(~S). f(~S) = g(~S) + h(~S) (6.12) Here, f is the total cost estimation of a path starting from ~Si to ~Sg through the state ~S, g(~S) is the optimal cost-to-come from ~Si to ~S, and h(~S) is the heuristic cost estimate from ~S to ~Sg. The formation is transported with a constant speed and thus we use the transport time as the cost estimate. The cost of a newly encountered state ~S ? is computed as follows: f(~S ?) = g(~S) + l(~S, ~u) + h(~S ?) (6.13) Here, l(~S, ~u) is the transition cost from the state ~S to ~S ?. We use a general transition cost function c(~S) to calculate the transition l(~S, ~u) and heuristic h(~S) costs as described by Equation 6.14: c(~S) = ? ???? ???? L v + ?? ? if n < 4, L v otherwise, (6.14) 149 where v and ? are the constant linear and angular speeds of the trap ensemble, respectively. In order to calculate l(~S, ~u), L and ?? are taken as the linear and angular displacements resulting from the execution of an action ~u (see Figure 6.6). For the calculation of h(~S), we take the Euclidean distance between the states ~S and ~Sg as the linear displacement L, and the total angular displacement required to move from ~S to ~Sg as ??. During the transport along a given direction, some of the beads in the formation exert a pushing force (actuator beads) on the cell, whereas other beads prevent the cell from drifting out of the ensemble. For the gripper formations G4 and G6, there are enough actuator beads to be able to push the cell in any direction. Hence, they do not need to be rotated to change the transport direction of the formations, while they need to be rotated for gripper formations G2 and G3 to be able to orient the actuator beads along the transport direction. Therefore, we do not consider the rotation for n ? 4 in Equation 6.14. In this dissertation, we will use the controllable degrees of freedom and the total degrees of freedom to characterize whether a gripper ensemble is holonomic or nonholonomic systems [NF72]. In robotics, a system is considered holonomic if the controllable degrees of freedom are equal to the total degrees of freedom. On the other hand, a system is considered nonholonomic if the controllable degrees of freedom are less than the total degrees of freedom. In our case, we are manipulating cells in a plane with the gripper formations. Hence, the total number of degrees of freedom for the gripper ensemble is three (two for position and one for orientation). In case of G4 and G6, gripper ensemble can be translated in arbitrary directions and rotated. Hence, the number of total degrees of freedom for G4 and G6 is equal to 150 Figure 6.6: Cost function for n < 4 the controllable degrees of freedom. However, in case of G2 and G3, grippers cannot translate in arbitrary direction because moving in certain direction may result in the cell coming out of the formation. The resulting cost function can then be divided into two classes: holonomic cost function forG4 andG6 and nonholonomic cost function forG2 andG3. Holonomic cost functions do not account for changes in orientations and are only based on trans- lations. Nonholonomic cost functions account for both translations and rotations. 6.4 Feedback control for gripper formation The maximum operating speed of a particular gripper formation to transport a cell to a given goal location needs to be determined. With the increase in the speed, the formation tends to break down gradually due to Brownian motion and 151 Table 6.1: Rules used by the formation generator g to determine the positions of beads inside the gripper Formation type Bead positions G2 ~XB,1 = ~Xc ? ~D1 ? ~D2; ~XB,2 = ~Xc ? ~D1 + ~D2 G3 ~XB,1 = ~Xc ? ~D1 ? ~D2; ~XB,2 = ~Xc ? ~D1 + ~D2; ~XB,2 = ~Xc ? ~D1 + ~D3 G4 ~XB,i = ~Xc + d[cos(pi/4 + ipi/2), sin(pi/4 + ipi/2)]T G6 ~XB,j = ~Xc + d[cos(pi/6 + jpi/3), sin(pi/6 + jpi/3)]T ~D1 = ?(rB + rC)2 ? d2/4[cos?, sin?]T ; ~D2 = d/2[sin?,?cos?]T , ~D3 = ? 3d/2[sin?,?cos?]T , i = 1, 2, . . . , 4; j = 1, 2, . . . , 6 drag force. Hence, we need a feedback controller that retains gripper beads in the formation if they get deviated for more than the maximum specified distance. In each planning interval, the planner executes one of the three maneuvers: translate, rotate, and retain (see Figure 6.4). The positions of the gripper beads expressed using the formation tuple fn, that is computed using inverse kinematics, are shown in Table 6.1. not rotate in order to reach a particular waypoint. Hence, they need only two maneuvers to follow a path. In each planning time interval, the next trap positions are selected using the following algorithm: Formation control algorithm: (see Figure 6.4) Input: A finite nonempty maneuver library, formation tuple fn, waypoint library ?, bead deviation threshold lth, waypoint deviation threshold wth, and time step t. Output: The next positions of the traps {Ti}ni=1. Steps: (i.) If t = 0, select the first waypoint Wp from the library ?, where p = 1. (ii.) If ? ~Xc ? ~Wp ?? wth, set p = p+ 1. (iii.) Measure the positions of beads { ~ZB,i : ~ZB,i ? <2, i = 1, 2, . . . , n}. If ? 152 Figure 6.7: Transport time required for G4 and G6 gripper formations to follow trajectories in various obstacle fields computed using two different cost functions ~XB,i t?1 ? ~ZB,i ?? lth go to step v. (iv.) Select the retain maneuver. Use the formation generator g to calculate { ~XB,i}ni=1 based on the formation state ~x (see Table 6.1). Set Ti = ~XB,i, ? Ti ? T and return T . (v.) Based on the waypoint ~Wp and the formation state ~x, calculate the desired action ~u. If the action requires both rotate and translate maneuvers, first select the rotate maneuver. Calculate the desired formation state ~x and the corresponding { ~XB,i}ni=1 using the rules in Table 6.1. Set Ti = ~XB,i, ? Ti ? T and return T . 153 Figure 6.8: Transport time required for G2 and G3 gripper formations to follow trajectories in various obstacle fields computed using two different cost functions 6.5 Results and discussions 6.5.1 Experimental setup and method We demonstrate the effectiveness of the planner using a BioRyx 200 (Arryx, Inc., Chicago, IL) holographic laser tweezer platform. The platform consists of a Nikon Eclipse TE 200 inverted microscope, a Spectra-Physics Nd-YAG laser (wave- length of 532 nm), a spatial light modulator (SLM), and a proprietary phase mask generation software running on a desktop computer. The objective used is the oil- immersion Nikon Plan Apo 60x/1.4 NA, DIC H. The maximum rate at which traps can be set is the update rate of the Spatial Light Modulator (SLM), 15 Hz, and the minimum step size of 150 nm. The feedback control is achieved with a second PC equipped with a uEye camera (IDS, Inc., Cambridge, MA) for imaging the cells and 154 beads in the workspace. We use 5.0 F1m diameter silica beads (with the density of 2000 kg/m3 and a refractive index of 1.46 purchased from Bangs Laboratories, Inc., Fishers, IN) as the gripper beads. Yeast cells used in this experiment are cultivated from a fast growing yeast powder. 0.016 mg of yeast powder is mixed with 3% (w/v) glucose solution. The cells are allowed to grow for an hour. After an hour, the concentration of cells is examined under a microscope. The average diameter of the cells after an hour is 5-8 F1m. Beads and cells are identified by thresholding the image and calculating the center of mass of all the remaining blobs (see Figure 6.4). The measurement noise in the particle positions is suppressed through the use of Kalman filtering. The objects at microscale undergo Brownian motion. In order to construct the covariance matrix for the Kalman filter, we hold the object (a bead or cell) using a laser trap and log the measured positions for 1000 time steps. The actual position of the object is determined from the position of the trap since the object gets hopped into the focal point of the laser. The update rate of SLM is about 66 ms. Since the Brownian motion of the object is suppressed by the optical trap, the covariance of the measured positions can be regarded as a metric for the measurement noise. We have calculated the measurement noise covariance matrix from the recorded positions and used Kalman filter to estimate the actual positions. 155 6.5.2 Simulation results of path planning In this section, we present a comparison of the required average transport time for two classes of gripper formations executing two different paths computed using holonomic and nonholonomic cost functions as presented in Equation 6.14 in scenes with different obstacle densities. We use 10 different levels of obstacle densities to generate the scenes. For each obstacle density level, we create 20 different scenes by randomly distributing the obstacles. For each scene, we randomly choose 100 different initial Si and goal states Sg to compute trajectories. The trajectories are computed using two different cost functions as shown in Equation 6.14. We record the transport time required by each formation type for execution of trajectories computed using the two cost functions. The transport time is averaged over 2000 test cases for each obstacle density. The gripper formations are transported with the maximum constant linear velocity of 10 F1m/s and maximum angular velocity of 0.25 rad/sec. Figure 6.7 shows the box plots of transport time of G4 and G6 gripper for- mations executing paths computed using two different cost functions in scenes with different obstacle densities. The average transport time (indicated using 2 sign) gradually increases with the increase of obstacles in the scene for both cost func- tions. This increase is not significant for holonomic cost function since the planner does not consider the time for rotation which is a dominant component in calcula- tion of the total transport time. The transport time required for execution of a path computed using the holonomic cost function is less than that of the nonholonomic 156 Table 6.2: Performance of designed grippers Gripper type Properties Transport speed F1m/s 7 8.5 10 G2 Laser power (w) 0.2 0.3 0.5Intensity (w/F1m2) 6.03e-7 9.05e-7 1.51e-6 G3 Laser power (w) 0.4 0.5 0.8Intensity (w/F1m2) 8.02e-7 1.00e-6 1.60e-6 G4 Laser power (w) 0.6 0.8 1.2Intensity (w/F1m2) 9.06e-7 1.21e-6 1.81e-6 G6 Laser power (w) 1.0 1.5 2.0Intensity (w/F1m2) 1.00e-6 1.50e-7 2.00e-6 cost function. The nonholonomic cost function leads to computation of a path that has less number of turns since it explicitly takes the angular transport time into account. It thus does not necessarily need to be the shortest path between Si and Sg in terms of Euclidean distance in the position space. On the other hand, the holonomic cost function leads to computation of the shortest path in the position space, not taking the orientation of the gripper into account. The G4 and G6 gripper formations do not need to rotate to change the direction of their transport. Hence, the shortest path computed using the holonomic cost function requires the least transport time for G4 and G6 gripper formations. On the contrary, the actual transport time of G2 and G3 gripper formations following a path computed using the nonholonomic cost function is less than that of the holonomic cost function (see the plot in Figure 6.8). The formations need to rotate to change the direction of their transport. Hence, it is preferable to choose a path that has less number of turns, rather than choosing the shortest path in the position space to minimize the total transport time as well as to maintain stability. 157 (a) (b) (c) (d) (e) (f) Figure 6.9: Indirect transport of a bead using the 3-bead gripper formation: (a) gripper in the initial state Si, (b) the gripper applies the rotate maneuver to align itself towards the waypoint W1, (c) the gripper applies the translate maneuver to reach the first waypoint W1, and (d) the gripper applies the rotate maneuver to align itself towards W2, (e) the gripper applies the translate maneuver to reach W2, and (f) the gripper reaches the final goal G with the use of rotate and translate maneuvers respectively 158 (a) (b) (c) (d) Figure 6.10: Indirect transport of a bead using the 6-bead gripper formation: (a) the gripper in the initial state Si, (b) the gripper applies the translate maneuver to reach the first waypoint W1, (c) the gripper applies the translate maneuver to reach the second waypoint W2, and (d) the gripper reaches the final goal G by applying the translate maneuver (a) (b) Figure 6.11: Releasing a cell from the gripper: (a) the cell is transported to the goal G using the gripper formation, and (b) the cell is released from the formation by transporting the beads away from the cell 159 6.5.3 Experimental results We demonstrate the effectiveness of the planner in transporting a yeast cell with different types of gripper formations (see Section 6.4) towards a specified se- quence of waypoints by running experiments on our OT setup. The waypoints are generated by the A* based path planning algorithm presented in Section 6.3. The waypoints are denoted as W and the initial and final location of the gripper is de- noted as Si and G, respectively. Each formation successfully follows the waypoints, while transporting the gripped cell. Figure 6.9 shows the selection of different ma- neuvers by G3 to follow three waypoints including the goal G in a challenging scene with obstacles. In these experiments, the complexity of the obstacle scene is limited by the allowable dimension of our OT workspace as well as the size of the gripper formation. The formations with two and three beads use the same set of maneuvers to follow similar waypoints. The formation G3 is more stable than its G2 counterpart because the extra bead prevents the gripped object from drifting out of the gripper. The planner has to invoke the retain maneuver intermittently to keep the cell inside the gripper formation. Figure 6.10 shows a target cell being transported with G6 through three way- points using the retain and translate maneuvers. Due to the larger size of the formation, we can only demonstrate automated transport of the cell in a space with a single obstacle. Hence, G6 formation is not suitable for a relatively cluttered en- vironment. It does not require the rotate maneuver since it does not need to rotate 160 itself to change the direction of transport. As soon as some of the gripper beads get deviated from their desired locations beyond the user defined bead deviation threshold lth (see section 6.4), the gripper uses the retain maneuver to keep the traps stationary for a specified time interval so that the beads can get back to their original formation. The formation G4 utilizes the same set of maneuvers to transport the gripped bead. Both of the beads in G2 act as actuators (see Figure 6.1a). Hence, there is a risk that the cell will get deviated from its desired location inside the gripper when moving along a curved path. This formation is suitable for transporting the cell in a relatively cluttered environment since it requires low clearance space for navigation due to its smaller diameter. The formation G3 (see Figure 6.1b) has one extra bead which always holds the cell inside the gripper. Both G2 and G3 need to stop and then rotate to change their direction of motion. The formation gets destabilized in case of a drastic change in the direction of transport since it has only one bead to restrict the cell from drifting out of the formation. The formations G4 and G6 (see Figure 6.1c and Figure 6.1d) are much more robust to destabilization for transporting along a curved path since they do not need to rotate to change the direction of their motion. Hence, the required transport time will also be less compared to the transport time of G2 and G3. However, G4 is more prone to get destabilized when moving along a diagonal direction since it can utilize only one actuator bead. Figure 6.11 shows how the cell is released from the gripper formation after it reaches the desired destination. The gripper beads are transported by moving 161 the traps away from the cell to safe locations. Once the gripper beads move away from the cell, they are released from the corresponding traps by switching off the laser. We did not observe any tendency for the gripper beads to stick to cells due to surface tension in our experiments involving yeast cells and silica beads. Hence, simply moving the beads away from the cell was adequate to release the cell. We also observed that once beads were not trapped, Brownian motion alone was adequate to keep the beads and the cells apart from each other. For manipulating sticky cells, gripper beads may need to be functionalized with appropriate coatings to reduce the adhesion to the cell. A formation with a higher number of beads, although more stable, requires higher laser power and hence causes the target cell to be exposed to more intense laser beam compared to a formation with fewer number of beads. Moreover, it re- quires larger clearance space in the workspace for safe navigation. We have analyzed the performance of each gripper formations in terms of the minimum laser power required to transport a cell at a given speed without the formation falling apart. We also measured the corresponding average laser intensity experienced by the cell using the method described in [CSW+12, KCA+11]. We record the minimum laser power required and corresponding average laser intensity experienced by the cell for a particular transport speed setting. For each setting we run 10 experiments to be statistically accurate. The results of the analysis are summarized in Table 6.2. Depending on the sensitivity of a cell to the laser (in terms of allowable average laser intensity) and required transport speed, an appropriate gripper can be chosen based in Table 6.2. 162 To provide a direct comparison between G3 and G6, we have experimentally determined the maximum allowable speeds of the traps during rotation without the formation getting destabilized. We determined the maximum speed for G3 as 3.3 F1m/s. Transport speeds higher than the allowable limit will position the traps closer to the cell, which results in trapping the cell before the gripper beads can move towards them even at higher laser power. To navigate through a path with the curvature of 90 degrees, G3 will require approximately 4 s more time than G6. However, G3 will use about 40% of the laser power used by G6. Moreover, the formation can be utilized in denser obstacle field compared to G6. The formation G6 can be useful for highly targeted experiments with less sensitive cells in a small population where reliability of transport is more important. 6.6 Summary In this chapter, we have presented an approach for automated, indirect trans- port of cells using planar gripper formations consisting of 2, 3, 4, and 6 beads. We used A* based path planning algorithm to generate collision-free paths for the formations. We designed a cost function for the developed planner to be able to find executable paths that minimize the transport time. We have also developed a feedback controller for the gripper to select and execute appropriate maneuvers when following the path. The maneuvers are used for determining the required trap positions for the formation and maintaining its stability. The main contributions of this chapter include the following: (i.) We present an approach for automated indirect manipulation, including ro- 163 tation and linear displacement, of biological cells using planar gripper forma- tions. (ii.) We present a global path planner based on the A* algorithm [HNR68] to auto- matically transport cells using cell-based gripper formations along collision-free paths. (iii.) We demonstrate experimental results of the developed automated indirect cell transport and path planning. (iv.) We present detailed experimental evaluation results of gripper formations in terms of their stability, transport speed, and required laser power. In future, dynamical interactions between a cell and gripper beads can be considered to develop a model predictive control for robust transport of cells. The gripper formations reported in this chapter are tested only for transporting spherical cells. In general, cells can be of arbitrary shapes. Gripper formations can be synthe- sized to transport cells of irregular shapes as introduced in Chapter 5 for spherical cells. 164 Chapter 7 Automated Indirect Manipulation of Irregular Shaped Cells With Optical Tweezers for Studying Collective Cell Migration This chapter7, presents a planning approach for automated indirect manipu- lation of irregular shaped cells in order to study collective cell migration. Study- ing collective migration of cells is currently of considerable interest in biology and medicine leading to possibility of novel diagnosis and treatments, for example, in cancer research. We propose optical tweezers as a useful tool for dynamically po- sitioning of cells in certain geometrical patterns to allow new discoveries on how cell-signaling influences their collective behaviors. Some cells are highly sensitive to direct laser exposure, which may influence their behavior or even cause photodam- age. In addition, manual manipulation of cells is time consuming making it hard to carry out systematic studies that are properly timed to exhibit the desired motil- ity. We have developed an automated planning approach for precise, collision-free, indirect manipulation of cells with irregular, dynamically changing shapes using Op- tical Tweezers (OT). We use a triangular triplet formation for indirect pushing of a cell. This particular formation has the advantage of preventing laser exposure on the cell and is highly stable and thus suitable for automated indirect manipulation. We have carried out an experimental study to demonstrate the effect of indirect pushing using the triplet formation on cell-viability. We find that the triplet for- mation does not influence the boundary protrusions of Dictyostelium discoideum 7 The work in this chapter is partially derived from the published work in [CTW+13]. 165 cells and generation of blebs in contrast to direct trapping or gripping approaches. We have evaluated the effectiveness of our manipulation approach using physical experiments. 7.1 Introduction Collective cell migration [IF09] plays a prominent role in various highly reg- ulated processes and physiological conditions during animal development such as embryogenesis, wound healing, or cancer. Gaining insights into the behavior of the cell migration may help in effective diagnosis and therapy for cancer treatment. Dictyostelium discoideum cells [AF09] are used as model organisms for studying cell-signaling and collective migration. When polarized, they migrate using protru- sions. The protrusions start at the front of the cells and then propagate along their boundaries at speeds of tens of micrometers per minute [DFL11]. In order to study how the cells behave collectively, they need to be positioned in certain geometri- cal patterns. Figure 7.1 shows the collective migration of polarized Dictyostelium cells towards the highest concentration gradient of the chemoattractant cAMP. Cells formed chain by extending the protrusions towards the trailing end of the leading cell. Now, in order to understand how the cells can track the concentration gradient, a new sets of experiments can be designed, for example, cells can be constantly re- arranged in a stack with their leading and trailing protrusion ends being flipped and observe how they behave under the new scenarios. This requires an automated tool for fast and precise, simultaneous micromanipulation of the cells. Various tools for micromanipulation of cells have been developed (e.g., microfluidics, electrophoresis, 166 Figure 7.1: Collective cell migration during chemotaxis (Courtesy: Chenlu Wang and Dr. Wolfgang Losert): (a) cells migrate towards the highest concentration of the chemoattractant cAMP, and (b) cells form chains by tracking the back of other cells magnetic manipulation, AFM, acoustic tweezers, and Optical Tweezers) [CPPM08]. Optical Tweezers (OT) has recently become a popular tool [BCLG11] that uses a highly focused laser beam exerting gradient and scattering forces to stably trap a particle at the focal point [Ash92]. However, direct manipulation by a laser beam can cause significant photodamage to the cells. In order to reduce the laser exposure, several approaches have been proposed, namely (1) the use of a laser beam with lesser intensity, (2) the use of feedback control during manipulation to increase the trap effectiveness [HZM09], (3) the use of optimum laser wavelength [NCL+99], and (4) indirect manipulation using grippers made of silica beads (we term it as direct gripping in this chapter) [CTW+12], functionalized microbeads [AEM+07], or microtools [AOIM09], or pushing using 2- bead chains [TCW+12]. Indirect gripping of a cell (i.e., the cell is partially exposed to a laser beam) even with lower laser power is not suitable for sensitive cells such as 167 Dictyostelium. Similarly, using optimal laser wavelength may influence the behavior of the cell, and in general has to be specifically tuned for a particular type and size of the cell. Pushing using 2-bead chains is highly unstable, slowing down the manipulation process. In this chapter, we use triangular pushing triplet formations consisting of an intermediate bead that is not directly trapped, and is positioned between two optically trapped beads and a target cell (see Figure 7.2a). The formation has the advantage of preventing laser exposure to the cell and is highly stable which makes it particularly suitable for automation. We have carried out an experimental study to demonstrate the effect of indirect pushing using the triplet formation on cell- viability. We specifically compare it with direct trapping and gripping approaches. Since cells constantly change, divide, and migrate, many biological experi- ments are constrained by the available time to set up cells in a desired configura- tion. Manual manipulation of optically trapped beads to push the intermediate bead and thereby the cell towards its desired pose may be time consuming, and at times even infeasible when pushing more than one cell is needed. We have developed an automated manipulation approach for dynamic positioning of an irregular shaped cell using triangular triplet formations. The developed approach is able to handle dynamically changing shape of the cell. 7.2 Problem overview and terminology We used the following terminology throughout the chapter. Gripper Formation is defined as ?n = {{~PB,i, ~PI}, |~PB,i, ~PI ? R2, i = 1, 2, . . . , n}, 168 (a) (b) Figure 7.2: Gripper formation state and cell state: (a) two bead gripper formation, and (b)cell state with irregular shaped contour that consists of n active beads, where each bead Bi has a position PB,i in the local coordinate system (X ?, Y ?) of the formation. The origin of the formation is defined by PI that represents a position of the intermediate bead I in the global coordinate system (X, Y ). The intermediate bead is not directly trapped by the laser during the manipulation of the cell. Figure 7.2a shows an example of ?2 where two active beads are separated by a distance d. During the manipulation operation, {Bi}ni=1 are held with their corresponding optical traps Ti, i = 1, 2, . . . , n by setting the status of the laser beam ? to 1. The intermediate bead is not trapped and thus indirectly manipulated by the laser. Gripper Formation State is defined as ~x? = [~PI , ?I ]T , ~PI ? R2 is the position (identical to the position of I) and ?I is the orientation of the formation in (X, Y ) (see Figure 7.2a). Cell State is defined as ~x? = [~PC , ?C ]T in which ~PC ? R2 is the position, ?C is the orientation of the cell C which is the angular difference between X-Y and 169 Figure 7.3: Gripper formation-cell ensemble maneuvers: (a) re-orient rre, (b) go-back rgo, and (c) push rp the local coordinate system X ??-Y ??. ~x? is determined from the bounding box of cell computed from contour information ? (see Figure 7.2b). Obstacles is defined as {?i|~P?,i ? R2, i = 1, 2, . . . , m}, where ~P?,i represents the position of an obstacle ?i in (X, Y ). The set of obstacles includes all the cells and beads in the workspace besides the beads that are not part of ?n and the cell C being manipulated. Gripper Formation Maneuver We define a maneuver setM = {mr, mt, mre} that consists of rotate mr, translate mt, and re-arrange mre maneuvers used by ac- tive beads {Bi}ni=1 to transport the intermediate bead I that eventually pushes the target cell C. mr rotates the formation by a constant angle ??I , mt causes a linear translation for a constant constant distance ?d = [?xI , ?yI ]T (?xI and ?yI are the translations in X and Y directions respectively), while mre arranges back the active beads in the formation if I is displaced from ?n. Ensemble Maneuver We define a similar maneuver set N = {nre, np, ngo} that consists of re-orient nre, push np, and go-back ngo used by ?n to push the 170 target cell C (see Figure 7.3. Only nre and np are used to manipulate the cell and we call them primary maneuvers. ngo is only invoked during switching between the primary maneuvers since the motion goal ~x?,g = [~PI,g, ?I,g]T of ?n also needs to be changed. It will allow the formation enough space to turn before moving towards the new motion goal without affecting the cell state. In case of ngo we have to trap the intermediate bead since the gripper formation cannot execute backup action (see Equation 7.4) by setting the corresponding laser status to be 1. That does not affect the cell viability since ngo leads the gripper formation away from the cell. 7.2.1 Problem formulation Given, (i.) a continuous, bounded, non-empty state space X ? R2 ? S1 in which each state ~x consists of position in (X, Y ) and orientation about the Z axis, (ii.) the current state ~x?,i = [~PC,i, ?C,i]T and the goal state ~x?,g = [~PC,g, ?C,g]T of the cell, (iii.) the current state ~x?,i of the gripper formation ?n, (iv.) an obstacle map ? such that ?(~x) = 1 if ~x ? Xobs ? X , otherwise ?(~x) = 0, and (v.) the goal region XG represented as a permitted distance range (rmin, rmax) of the cell C from it?s state ~x?,g. Compute, 171 (i.) a collision-free global path ?? between ~x?,i and ~x?,g, where Xfree = X \Xobs, (ii.) a motion goal ~x?,g = [~PI,g, ?I,g]T for the gripper formation ?n based on the desired state ~x?,d of the cell and its current state ~x?,i, (iii.) a feasible path ?? between ~x?,u and ~x?,g for the gripper formation ?n, and (iv.) a complete feedback control to select formation maneuversMd to determine the trap positions Ti and corresponding status of the laser ? for the formation ?n so that it can reliably follow the path ?? . 7.2.2 Assumptions We approximate both the gripper beads and the intermediate bead as perfect spheres of radius r. The beads trapped by laser are assumed to move with the same velocity as the traps. This is ensured by choosing an operating speed using which the beads can be reliably trapped by the laser traps [CTW+12]. 7.3 Approach 7.3.1 Solution approach The outline of the technical approach used in this chapter can be divided into four high level tasks namely (see Figure 7.4): (1) Development of an image based feature recognition and tracking system to estimate contours of cells and positions of beads, (2) Development of a global path planner based on A* algorithm that computes the desired waypoints for the cell based on its desired initial state ~x?,i and goal state ~x?,g, (3) Development of an algorithm to determine motion goal ~x?,g for the gripper formation based upon ~x?,i and ~x?,g, and (4) Development of a formation 172 Figure 7.4: Solution approach and OT setup control algorithm that determines desired maneuverMd and the corresponding trap positions Ti for the gripper formation to reliably follow the desired state ~x?,d. 7.3.2 State-action space representation We discretize the continuous state space X ? R2 ? S1 into a finite discrete space Xd ? X . ~xk? and ~xk? ? Xd are the cell state and formation state at time step k respectively. The state space is a 3D grid with each grid cell representing a state of the formation ?n or the cell C. A control action uk is represented by a vector of velocities of individual traps and corresponding status of the laser at a given time step k (see Equation 7.1). 173 ~uk = [[~v1k, ?1], [~v2k, ?2], . . . , [ ~vn+1k, ?n+1]] (7.1) Here ~vik represents the velocity of ith trap at time step k and n is the total number of gripper beads. (n+1)th trap corresponds to the intermediate bead I. It gets activated by setting the status ?n+1 of (n+1)th laser trap to be 1 whenever required based on the selected ensemble maneuver Nd. The dynamics of formation ?n is described by Equations 7.2 and 7.3 ? ~P kI = n? i=1 max(0, ~vik?~ri)?~ri (7.2) ??kI = n? i=1 ( ~vi k 2r ? r?i ) ?contact (7.3) ?contact = ? ???? ???? 0 if dBi,I > 2r, 1 otherwise. Here, ?~ri (see Figure 7.2a) is the unit direction vector towards the intermediate bead from the active bead Bi and dBi,I is the distance between them. The momentum is transferred to the intermediate bead only when it is in contact with the gripper beads. Hence, ??I is set to 0 when there is no contact. The speed of all traps are constrained to be same (see Equation 7.4). The trap motions are constrained only parallel to the desired direction of the intermediate bead in case of formation maneuver nt to prevent the formation from falling apart (see Equation 7.5). Similarly, the traps are restricted to move only towards the tangential direction of the intermediate bead in case of nr (see Equation 7.6). 174 |~vik| = |~vjk|?i, j,where i, j = 1, 2, 3, . . . , n (7.4) ~vi k ? ? ~dI,g = 0 (7.5) ~vi k . ? ~ri = 0 (7.6) Here, ?~dI,g = [c?I , s?I ]T (see Figure 7.2a) is the unit direction vector from the current position ~PI,u towards the desired waypoint of ?n that is derived from it?s orientation ?I . When ?n takes an action ~uk at time step k, it transitions from ~xk? to ~xk+1? using Equation 7.7. ~xk+1? = ~x k ? + ?~x k ?4t (7.7) Here, 4t is the time spent between two subsequent time steps. As the inter- mediate bead I comes in contact with the cell the momentum will be transferred to the cell C. We assume that ?n can only cause either pure rotation or pure transla- tion to the cell. That is ensured by careful selection of it?s motion goal ~x?,g. The dynamics of the cell C is described using Equations 7.8 and 7.9 ? ~P kC = (max(? ?~P kI , ?~dI,C?, 0) ?~dI,C)?contact (7.8) ??kC = ( ? ~P kI |dC,I | ? ? ~dI,C)?contact (7.9) ?contact = ? ??? ??? 1 if in contact, 0 otherwise. 175 Here ?dI,C is the unit vector from ?n towards the cell and |dC,I | is the perpen- dicular distance from ~PC to the velocity vector of the gripper formation. The cell transition to time step k + 1 is given by Equation 7.10 ~xk+1? = ~x k ? + ?~xk?4t (7.10) 7.3.3 Image processing In OT setup, beads and cells are identified by processing gray-scale video (see Figure 7.5a) stream captured by a CCD camera. We used Open Source Computer Vision library (OpenCV) to detect the beads and the contour of the cells. We applied Hough transform to the input gray-scale image to identify spherical gripper beads (see Figure 7.5b). The center of the identified gripper beads are calculated before replacing them with the background (see Figure 7.5c) to isolate them from the image. We applied Canny Edge Detector [Can86] on the image containing only cell to detect the fine edges of the cell (see Figure 7.5d). We dilated the canny image to make the edges more prominent and decrease the linear gaps between them (see Figure 7.5e). The resulting image contains some disconnected black pixels inside the cell boundary. To remove the disconnected black pixels we filled all the reachable black pixels with white pixels using a flood filling algorithm (see Figure 7.5f). The while image after flood filling contains the black patches left after dilation. We took a complimentary of the image that turns the black pixels inside the cell into white (see Figure 7.5g) while makes the rest of the image black. We got a well-defined boundary of the cell by adding the dilated image with the complementary image (see Figure 7.5h). We refined all the noises by retaining the boundary with the largest 176 (a) (b) (c) (d) (e) (f) (g) (h) (i) Figure 7.5: Image processing steps: (a) input image, (b) Hough transformation to identify the beads, (c) replacing beads with background of the image to isolate the bead information, (d) identify edges using Canny Edge Detector, (e) dilate the image, (f) flood fill the image, (g) complement of the image, (h) addition of dilated image and complement image to detect the boundary, and (i) identify the contour of the image 177 area since the cell represents most of the images. Finally, we determined the contour points ? of the boundary to identify the detailed shape of the cell (see Figure 7.5i). We computed the oriented bounding box and calculate it?s side lengths dl and dw (see Figure 7.2b). The side lengths are used to compute the state ~x? of the cell. Before starting the planning, the planner records the contour points for 100 frames. Subtracting the contour points ?i?1 of (i-1)?th frame from ?i of i?th frame gives the direction of protrusion where i = 1, 2, 3, . . . , 100. The protrusion direction provides the knowledge about the leading and trailing edge of the cell that can be used by the user to select the goal state ~x?,g of the cell. 7.3.4 Motion goal for gripper formation The planner takes the current and desired state of the cell as inputs to select the desired maneuver Nd for the formation ?n. Based on the desired maneuver Nd the planner computes the next motion goal ~x?,g for ?n. Let us assume the current and next desired states for the cell are ~x?,i = [~PC,i, ?C,i]T and ~x?,d = [~PC,d, ?C,d]T respectively. The planner first reorient the cell such that ? ?dC,X??, ?dC,d? = 1 (see Figure 7.3) by calling ensemble maneuver nre to align its axis perpendicular to the desired state direction. Here, ?dC,X?? is the unit vector defining the axis of the cell C and ?dC,d is the direction vector from C towards the desired state ~x?,d. Then it switches to np to translate the cell to the desired location. Finally it again switches back to np to re-orient the cell to the desired orientation. Before switching to the np from nre or vice-versa, it has to invoke ngo maneuver to move the gripper formation in a safe location. We have to change the motion goal to switch the ensemble 178 maneuver. ?n has to move away from the cell to provide itself enough space to move to the new motion goal ~x?,g without affecting the cell orientation. We define a reference position ~PI?,g as shown in Equation 7.11 to define the motion goal position for ?n. ~PI?,g = ? ????? ??? ????????? ~PC,i + c?C,i/4[dl,?dw] if ??C is positive, ~PC,i + c?C,i/4[?dl,?dw] if negative ~PC,i + c?C,i/4[0,?dw] if 0 (7.11) Here ??C = ?C,d??C,i. We now compute the nearest contour point from the contour data ? of the cell to compute the motion goal position ~PI,g. The orientation ??,g is set to the desired orientation of the cell. For ngo maneuver we project the cell state to a new state as shown in Equation 7.12 ~x?,g = [~PC,i + 4rc?C,i[0,?dw], ??,u]T (7.12) The desired maneuver Nd is computed using Algorithm 1. 7.3.5 Global path planner We use the A* based global path planner for computing the intermediate states for both ?n and C that iteratively expands nodes from the initial state ~xi to goal state ~xg using a cost function f(~x). We use a similar cost function as described in [CTW+12] that takes transport time for both re-orientation and translation into account to compute the collision-free path with minimum time. 179 Input: Ensemble maneuver library N , planning time tp, previously executed maneuver Np, current state of gripper ~x?,i, current state ~x?,i and desired state ~x?,d of the cell, a user defined threshold difference between current and desired orientation of cell ?C,th, a binary variable go-back-reach that indicates whether the motion goal for go-back maneuver is reached or not . Output: Desired maneuver Nd for the gripper formation-cell ensemble. 1: Compute ??C = ?C,i - ?C,d. 2: Compute ?dC,I = ~PC,i - ~PI,i 3: Compute align = ? ?dC,X??, ?dC,d? (see Figure 7.3) 4: if ? ??C ? 4r then 6: set Nd ? np 7: else 8: set Nd ? ngo 9: end if 10: else 11: if tp = 0 ? Np = nre ? (Np = ngo && go-back-reach = TRUE) ? ? ?dC,I ?? 4r then 12: set Nd ? nre 13: else 14: set Nd ? ngo 15: end if 16: end if 17: return Nd. Algorithm 1: Gripper-cellmanueverselection(): Compute the desired ma- neuver for the gripper formation ?n to determine it?s the motion goal. 7.3.6 Formation control In this section we describe a feed-back policy to determine the trap positions Ti in order to transport the cell towards the desired state x?,d. The trap positions are determined by the choice of ensemble maneuver Nd. We use the global path planner to compute the desired next state ~x?,d of the formation based on its motion goal state ~x?,g computed in section 7.3.4. Based on ~x?,d the required formation maneuver Md is selected as shown in Algorithm 2. mt transports the formation linearly, mr changes the orientation of the formation, and mre keeps the traps stationary to allow 180 the active beads to move into the formation [CTW+12]. The desired trap positions associated with the active beads Bi in our triple formation ?2 can be determined from the desired formation state ~x?,d as shown in Equation 7.13 T1 = ~PI ?D1 ?D2 T2 = ~PI ?D1 +D2 T3 = ~PI (7.13) Here, D1 = ? 4r2 ? d24 [c?I,d, s?I,d]T and D2 = d2 [s?I,d,?c?I,d ]T . The algorithm for selecting the desired trap positions Ti is shown in Algorithm 2 7.4 Results and discussions 7.4.1 Cell preparation and experimental setup AX3 D. discoideum were grown in HL-5 media at the concentration below 4? 106 cells/mL at 21DT, starved at the concentration of 1? 107 cell/mL in develop buffer (5 mM Na2HPO4, pH 6.2, 2 mM MgSO4, and 0.2 mM CaCl2) with pulses of 80 ?M of cAMP every 6 minutes for 5 hours, shaking at 140 rpm [SLB+10]. Cell pellets were gathered by centrifuging at 500 g in 1 mL micro-centrifuge tube and aspirating the supernatant. Cell pellets were washed twice with DI water afterwards for washing out ions containing in the develop buffer. 1?105 cells were added into a chamber (0.8 cm2 surface area) that containing 400 ?L DI water and were allowed to settle down for 15 minutes. 10 ?L of silica beads (5 ?m) solution (0.01% solid, from Microsil) were added into the same chamber and were allowed to settle down for 10 mins. Cells and silica beads remained suspending in DI water during manipulation experiments because of the electronic repulsion between cover-glass surface (negative 181 Input: Planning time tp, current state of gripper ~x?,i, current state ~x?,i and desired state ~x?,d of the cell, a binary variable go-back-reach, goal region XG, a user defined threshold difference between current and desired orientation of gripper formation ?I,th, formation deviation threshold lth . Output: trap positions Ti along with corresponding laser status ?i . 1: Initialize tp ? 0. 2: while ? ~PC,d ? ~PC,i ?