Date: Tue, 7 Oct 1997 18:57:33 -0700 (PDT)
   From: "Christopher J. Phoenix" 
   Cc: The MEMS Lists Manager , [email protected],
           Bruce Donald 

   At 10:53 PM 10/6/97 -0700, Karl F Bohringer wrote:
   >Hi Christopher,
   >
   >we have been working on sorting strategies with smart surfaces for some
   >time now.  Check out our '96 and '97 ICRA papers, or the January-March
   >issue of "IEEE Computer Science and Engineering", there we show some
   >strategies on how to separate parts (without sensor feedback) based on
   >part size.  This is also explained in our web site at
   >http://www.cs.cornell.edu/home/karl/MicroManipulation

   I've seen some sorting stuff that sounds similar, but I'll check it
   out.

The most complete reference for our stuff is the following papers;
available from Karl's webpage (above) or from
http://www.cs.dartmouth.edu/~brd/:

\item[] {\em Programmable Vector Fields for Distributed Manipulation,
with Applications to MEMS Actuator Arrays and Vibratory Parts
Feeders,} ( K.-F.~B\"ohringer B. R. Donald and N.~C.~MacDonald), (
International Journal of Robotics Research, 1997). Accepted; to
appear.

\item[] ``Computational Methods for the Design and Control of MEMS
Micromanipulator Arrays,'' ( K.-F.~B\"ohringer, B.R. Donald,
N.~MacDonald, G.~Kovacs, and J.~Suh), {\em IEEE Computational Science
and Engineering}, Vol.~4, No.~1.  Special Issue on Computational MEMS,
pp.~17--29. Jan-March 1997.

\item[] {\em Sensorless Manipulation Algorithms Using a Vibrating
Surface}, ( K.-F.~B\"ohringer, B.R. Donald, V.~Bhatt, and K.~Goldberg)
(Submitted to {\em Algorithmica}, Special Issue on Algorithmic
Foundations of Robotics, 1996).

   But I'm not so much interested in sorting, as in avoidance of emergent
   properties like traffic jams.  The application is nanotech-based, with
   trillions of one-micron parts over several square meters of area.  The parts
   are all the same size, and would be moved by smart "cilia" robot arms that
   can sense the part type and move in an arbitrary direction.  I'm trying to
   figure out communication and computation requirements to move the parts from
   place to place on the surface.  The parts are actually containers that get
   filled and drained at various special points on the surface.  But product A
   may need to be shipped from (0, 0) to (100000, 100000), while B has to go
   from (0, 1000000) to (100000, 0).

Chris,

I think the algorithm by M. Erdmann and T. Lozano-Perez would work for
exactly this problem. It appeared in Algorithmica around 1986 or 1987,
and the precise reference is on Mike Erdmann's webpage
([email protected]).  The title is "On Multiple Moving Objects."

Best wishes,

Bruce Randall Donald                US Mail:
113 Sudikoff Laboratory             Dept. of Computer Science
Phone: 603/646-3173                 Dartmouth College
Fax:   603/646-1672                 6211 Sudikoff Laboratory
email: [email protected]         Hanover, NH 03755-3510

Lab: 004 Sudikoff; 603/646-1210
WWW: http://www.cs.dartmouth.edu/~brd/