My current research focuses on algorithms for coordinating the
collision-free motions of multiple robots. By designing algorithms
that consider the complex dynamics of industrial robots, I can
coordinate the motions of robots in automotive workcells. In a related
effort, I am developing algorithms for coordinating microdroplets in
lab-on-a-chip digital microfluidics systems so they can perform
biochemical analyses. I am also developing algorithms for robotics
systems that can automatically fold objects for packaging
applications, as well for identifying protein folding pathways.
I am also interested in developing robotic systems that can automatically perform manipulation tasks. By designing efficient algorithms and planners that use the underlying task mechanics and geometry to generate solutions automatically, I have developed robots that are mechanically simple, yet very flexible. To demonstrate this approach, I have implemented robotic systems to feed and fold objects for flexible assembly and packaging. Since these systems do not require specialized effectors or sensors, they can be implemented quickly and inexpensively to shorten the time to market of new products and to reduce manufacturing costs.
Digital Microfluidic Systems
Multiple Robot Coordination
Proximity Queries
Articulated 3-D Structures
Protein Folding
Parts Feeding
When multiple robots execute tasks in a shared workspace, automatic
planners to ensure that the robots do not collide with each other
become essential. Optimized coordination of multiple robots can result
in tremendous time, energy, and cost savings. I have developed mixed
integer programming formulations to minimize task execution time and
coordinate collision-free robot motions, given individual robot
trajectories (or paths) that avoid collisions with stationary
obstacles. We have explored a progression of problems, particularly
for the case when the robots have dynamics constraints. This work is
directly relevant to the design and virtual prototyping of automotive
painting and welding workcells, and the coordination of wafer
transport robots in semiconductor fabs. This is joint work with Jufeng Peng
and Seth Hutchinson
.
We develop an interior point approach to exact distance computation
between convex objects represented as intersections of implicit
surfaces. Exact distance computation algorithms are particularly
important for applications involving objects that make contact, such
as in multibody dynamic simulations and haptic interactions. In
contrast to geometric approaches developed for polyhedral objects, we
formulate the distance computation problem as a convex optimization
problem; this optimization formulation has been previously described
for polyhedral objects. Example implicit surfaces include planes
(polyhedra), quadrics, and generalizations of quadrics including
superquadrics and hyperquadrics, as well as intersections of these
surfaces.
We use an interior point method to solve the optimization problem and
demonstrate that for general convex objects represented as
implicit surfaces, interior point approaches are globally convergent,
and fast in practice. Further, they provide polynomial-time
guarantees for implicit surface objects when the implicit surfaces
have self-concordant barrier functions. We use a primal-dual interior
point algorithm that solves the KKT conditions obtained from the
convex programming formulation. For the case of polyhedra and
quadrics, we establish a theoretical time complexity of O(n^{1.5}),
where n is the number of constraints.
We present
implementation results for example implicit surface objects and
demonstrate that distance computation rates of about 1 kHz can be
achieved.
Joint work with Nilanjan Chakraborty, Jufeng Peng, John Mitchell .
Manipulating articulated 3-D structures is challenging since the shape
of the object changes as it is manipulated and the number of degrees
of freedom of the object can exceed those of the manipulating robot. I
am developing techniques for the manipulation and motion planning of
"pop-up" 3-D structures. This work is motivated by the task of folding
cartons from blanks to package products such as telephones and two-way
radios, which is typically performed by human operators or with fixed
automation. Liang Lu and I developed a flexible method to fold
cardboard cartons from blanks by using interchangeable fixtures to
enable rapid product changeovers. We developed a motion planning
algorithm that generates all folding sequences for a carton by
modeling it as a robot manipulator with revolute joints and branching
links. A fixture constrains the carton motion to paths consisting of
line segments in its configuration space, and these paths are
generated by the motion planner. To illustrate the method, we
selected a folding sequence for an example carton, designed a fixture,
and demonstrated folding of the carton from blanks with an AdeptOne
robot. Carton folding movie (YouTube)
Since the 3D folded shape of a protein determines its function,
knowing the folding pathways can aid understanding of misfolding
diseases (e.g., Alzheimer's disease) and guide drug design. We are
building
on sampling-based motion planning methods, which have been recently
used
to identify feasible folding pathways for proteins with known
structure by modeling proteins as articulated robots.
Our focus is on generating
sample configurations using a hidden Markov model of protein
structures from the Protein Data Bank.
By using energy-minimized protein configurations derived from those
present in nature, we believe we can obtain biologically plausible
configurations and sample the configuration space more efficiently. We
have preliminary folding pathway results for short
proteins. Joint work with Chris Bystroff , Yogesh Girdhar, and Ted
Carlson.
A parts transfer system must automatically identify actions to move
parts from initial to goal configurations. I explored the use of
graspless pushing operations, which can be used by robots to feed parts for
assembly or by mobile robots to move furniture. I proved that
any polygonal part can be moved from any known position
and orientation to any other position and orientation in the
obstacle-free plane by a sensorless sequence of pushes. I developed a
linear programming formulation and implemented a polynomial-time
planner to automatically generate sequences of pushes to perform such
parts transfer. I demonstrated these plans using a Puma 560 robot.
A fundamental question is: How many degrees of freedom does a robot
require to manipulate a part with three planar degrees of freedom? We
developed a one-joint-over-conveyor (IJOC) system that uses the
pushing motions of a single joint effector positioned over a conveyor
belt and the conveyor drift to perform parts transfer. We showed that
it is possible to manipulate all three degrees of freedom of any
polygon to move it from any known initial configuration
upstream of the effector to a specific goal configuration. I developed
a nonlinear programming formulation to automatically generate plans
for this 1JOC system and demonstrated these plans on a conveyor with
an Adept 550 robot.
Sensorless 1JOC: We modified the 1JOC system to perform
sensorless parts transfer on a conveyor. This system can perform
a sequence of operations to bring all initially unknown positions and
orientations of the part (upstream of the effector) to the same goal
position and orientation without using sensors.
A parts orienting system must identify a sequence of actions
to bring a randomly oriented part to a goal orientation for
assembly. Since sensorless systems can orient parts (e.g. sensorless
1JOC), characterizing the advantages of using sensors is important. To
quantify the significant cycle time reduction when inexpensive sensors
that provide partial information on orientation, such as photosensors
to measure part width, are combined with actions, I proved bounds on
the lengths of sensor-based plans. I also showed that a single
sensor-based plan can orient and recognize different parts.
Toleranced parts: Since parts manufactured to tolerances have
to be reliably oriented, I characterized the effect of part shape
uncertainty on the orienting process. For the class of convex polygonal
parts, I defined a shape tolerance model that permits the center of
mass and the vertices to lie anywhere in disks centered at their
nominal positions. I demonstrated that the variational class of parts
defined by the tolerance model can be reliably oriented by both
sensor-based and sensorless plans despite the resulting
nondeterminism.
Jointly with Sebastien Blind, Chris McCullough, and Jean Ponce , I developed a reconfigurable parts orienting device that is modular and composed of simple electromechanical elements. This device, the "Pachinko machine," automatically catches and orients dropped parts of known shape using a grid of actuated pins on a vertical plate. We use a configuration space representation of the part and nest geometry to compute stable part configurations in the nests, their capture regions, and orienting plans.
Pachinko machine movie (YouTube)