1 Introduction

The recent, rapid innovations and improvements in microfabrication technology have resulted in an ever-growing complexity of available MEMS devices, mandating the use of automated, algorithmic methods for their design and control. This paper surveys our progress towards algorithmic MEMS, by taking on the challenge of design and control of massively-parallel micro actuator arrays. Our goal is to implement task-level, sensorless manipulation strategies with arrays of microfabricated actuators. The theory of programmable force fields ^[1] [19] arguably represents the first systematic attack on massively-parallel, distributed manipulation based on geometric and physical reasoning. Applications such as parts-feeding can be formulated in terms of the force fields required. Hence, programmable force fields act as an abstraction barrier between applications requiring array micromanipulation and their implementation with MEMS devices. Such abstraction barriers permit hierarchical design, and allow application designs with greater independence from underlying device technology.

Figure 1: Sensorless parts orienting using force vector fields The part reaches unique orientation after two subsequent squeezes. There exist such orienting strategies for all polygonal parts. See www.cs.dartmouth.edu/~brd/demo/MicroManipulation for an animated simulation.

We are interested in the algorithmic content of MEMS control strategies. This paper surveys our work on showing how to quantify it, by analyzing the complexity of (1) computing a manipulation plan, (2) the generated plans (i.e., force field sequences) and (3) the individual fields. We survey our results on obtaining upper and lower complexity bounds on plans and fields, and in finding trade-offs between these different kinds of complexity.