Srinivas Akella's Research
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
Digital Microfluidic Systems
Digital microfluidic systems (DMFS) are an emerging class of
lab-on-a-chip systems for biochemical analysis. They are designed to
manipulate individual microdroplets using phenomena such as
electrowetting and dielectrophoresis. These systems can potentially
perform analyses such as DNA polymerase chain reaction (PCR) using
smaller reactant volumes with less energy and at a lower cost. We are
developing a comprehensive approach for array layout design and
automated droplet routing. We have demonstrated (in simulation)
simple algorithms to coordinate hundreds of droplets as they
participate in one or more chemical analyses in parallel. Recently we
have developed algorithms for coordinating droplets using limited
row-column addressing. Joint work with Eric Griffith, Mark
Goldberg , Megha Gupta, and Lingzhi Luo.
- L. Luo and S. Akella, ``Optimal Scheduling for Biochemical Analyses
on Digital Microfluidic Systems,'' IEEE Transactions on Automation Science and Engineering,
Vol. 8, No. 1, pages 216-227, January 2011.
pdf,
bib .
-
J. G. Martin, M. Gupta, Y. Xu, S. Akella, J. Liu, J. S. Dordick, and R. J. Linhardt,
"An Artificial Golgi: Redesigning the Biological Activities of Heparan Sulfate on a Digital Microfluidic Biochip,"
Journal of the American Chemical Society,
Vol. 131, No. 31, 11041-11048, July 2009. pdf
,
bib .
-
L. Luo and S. Akella, "Minimum Resource Characterization of
Biochemical Analyses for Digital Microfluidic Biochip Design,"
Algorithmic Foundations of Robotics VIII (WAFR 2008), Gregory S. Chirikjian, Howie Choset, Marco Morales, and Todd Murphey (editors),
pages 567-581, Springer-Verlag, 2010.
pdf,
bib .
- L. Luo and S. Akella, ``Optimal Scheduling for Biochemical Analyses
on Digital Microfluidic Systems,'' 2007 IEEE/RSJ International
Conference on Intelligent Robots and Systems, pp. 3151-3157, October
2007.
pdf,
bib .
- M. Gupta and S. Akella, ``A Scheduling and Routing Algorithm for
Digital Microfluidic Ring Layouts with Bus-phase Addressing,''
2007 IEEE/RSJ International Conference on Intelligent
Robots and Systems, pp. 3144-3150, October 2007.
pdf,
bib .
- E. Griffith and S. Akella, ``Coordinating Multiple Droplets in Planar
Array Digital Microfluidic Systems,''
International Journal of Robotics Research, Vol. 24,
No. 11, pages 933--949, November
2005. pdf , bib , animations.
- E. J. Griffith, S. Akella, and M. K. Goldberg ``Performance
Characterization of a Reconfigurable Planar Array Digital Microfluidic
System,'' IEEE Transactions on Computer-Aided
Design of Integrated Circuits And Systems, Special issue on Design
Automation Methods and Tools for Microfluidics-Based Biochips,
Vol. 25, No. 2,
pp. 340-352, February 2006. pdf , bib .
-
Eric Griffith and Srinivas Akella, "U. S. Patent No. 7,693,666: Method, System, and Program Product for Controlling Chemical Reactions in a Digital
Microfluidics System" , April 6, 2010. bib .
Multiple Robot Coordination
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
.
- S. Akella and S. Hutchinson, "Coordinating the Motions of
Multiple Robots with Specified Trajectories," 2002
IEEE International Conference on Robotics and Automation, May
2002. abstract and
animations, pdf , bib .
- J. Peng and S. Akella, "Coordinating Multiple Robots with
Kinodynamic Constraints along Specified Paths," Algorithmic
Foundations of Robotics V (WAFR 2002), J.-D. Boissonnat,
J. Burdick, K. Goldberg, and S. Hutchinson (editors), pp. 221-237,
Springer-Verlag, Heidelberg, Germany, 2003.
abstract and animations,
pdf , bib .
- J. Peng and S. Akella, "Coordinating the Motions of Multiple
Robots with Kinodynamic Constraints,'' 2003 IEEE International
Conference on Robotics and Automation , pages 4066--4073, Taipei,
Taiwan, September 2003.
animations, pdf , bib .
- S. Akella and J. Peng, "Time-Scaled Coordination of Multiple
Manipulators,'' 2004 IEEE International Conference on Robotics and
Automation , pages 3337--3344, New Orleans, LA, April 2004.
pdf , bib .
-
J. Peng and S. Akella, ``Coordinating Multiple Double Integrator
Robots on a Roadmap: Convexity and Global Optimality,'' 2005 IEEE
International Conference on Robotics and Automation, Barcelona,
Spain, pp. 2762-2769, April 2005.
pdf ,
bib ,
animations.
- J. Peng and S. Akella, ``Coordinating Multiple Robots with Kinodynamic
Constraints along Specified Paths,''
International Journal of Robotics Research, Vol. 24, No. 4, pp. 295-310, April 2005. pdf (241 KB), bib , animations.
Proximity Queries between Convex Objects: An Interior Point Approach for Implicit Surfaces
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 .
- N. Chakraborty, J. Peng, S. Akella, and J. E. Mitchell, ``Proximity
Queries between Convex Objects: An Interior Point Approach for
Implicit Surfaces,'' IEEE Transactions on Robotics, Vol. 24, No. 1,
pp. 211-220, February 2008. pdf
, bib .
- N. Chakraborty, J. Peng, S. Akella, and J. Mitchell, ``Proximity
Queries between Convex Objects: An Interior Point Approach for
Implicit Surfaces,'' 2006 IEEE International Conference on
Robotics and Automation , pp. 1910-1916, Orlando, FL, May 2006.
pdf ,
bib .
Dynamic Simulation of Multibody Systems with Intermittent Contact
-
N. Chakraborty, S. Berard, S. Akella, and J. C. Trinkle, "A Geometrically-Implicit Time-Stepping Method for Multibody Systems with Intermittent Contact", International Journal of Robotics Research, Vol. 33, No. 3, pages 426–445, March 2014. pdf, bib .
- N. Chakraborty, S. Berard, S. Akella, and J. C. Trinkle,
``An Implicit Time-Stepping Method for Multibody Systems with Intermittent Contact,''
Robotics: Science and Systems 2007,
Atlanta, GA, June 2007.
pdf,
bib .
Recipient of Best Student Paper Award.
Articulated 3-D Structures
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)
- L. Lu and S. Akella, "Folding Cartons with Fixtures: A Motion
Planning Approach," IEEE Transactions on Robotics and
Automation, Vol. 16, No. 4, pp. 346--356, August 2000.
pdf , bib .
- L. Lu and S. Akella, "Folding Cartons with Fixtures: A Motion
Planning Approach," 1999 IEEE International Conference on Robotics
and Automation, Detroit, MI, May 1999.
pdf , bib .
Finalist, Best Paper Award.
- S. Akella, "Packaging of Motorola Two-Way Radios: Efficient
Layouts, Automation, and Defect Reduction," The Beckman Institute,
University of Illinois at Urbana-Champaign, August 1997.
Protein Folding Pathways
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.
- Y. Girdhar, C. Bystroff, S. Akella, and E. Carlson, "Efficient Sampling of Protein Folding Pathways using HMMSTR and Probabilistic Roadmaps," 2005 IEEE Computational Systems Bioinformatics Conference (CSB 2005),
poster, Stanford, CA, August 2005.
Parts Transfer
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.
- S. Akella and M. T. Mason, "Posing polygonal objects in the
plane by pushing," International Journal of Robotics Research,
Vol. 17, No. 1, pp. 70-88, January 1998.
pdf , bib .
- S. Akella and M. T. Mason, "Posing polygonal objects in the plane
by pushing". Proceedings of the 1992 IEEE International Conference
on Robotics and Automation, Nice, France, May 1992.
pdf , bib .
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.
- S. Akella, W. H. Huang, K. M. Lynch, and M. T. Mason, "Parts
Feeding on a Conveyor with a One Joint Robot," Algorithmica
(Special issue on Robotics), Vol. 26, No. 3/4, pp. 313-344,
March/April 2000.
pdf , bib .
1JOC movie (YouTube)
- S. Akella, W. H. Huang, K. M. Lynch, and M. T. Mason, "Planar
Manipulation on a Conveyor with a One Joint Robot". Robotics
Research: The Seventh International Symposium, pp. 265-276,
G. Giralt and G. Hirzinger (editors), Springer, Berlin, 1996.
pdf, bib .
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.
- S. Akella, W. H. Huang, K. M. Lynch, and M. T. Mason,
"Sensorless Parts Orienting with a One-Joint Manipulator," 1997
IEEE International Conference on Robotics and Automation,
pp. 2383-2390, Albuquerque, NM, April 1997.
pdf , bib .
- S. Akella, W. H. Huang, K. M. Lynch, and M. T. Mason,
"Sensorless Parts Feeding with a One Joint Robot," In Algorithms
for Robotic Motion and Manipulation, pp. 229-237, J.-P. Laumond
and M. Overmars (editors), A. K. Peters, Wellesley, Massachusetts,
July 1997.
pdf , bib .
Parts Orienting
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.
- S. Akella and M. T. Mason, "Using Partial Sensor Information
to Orient Parts," International Journal of
Robotics Research, Vol. 18, No. 10, pp. 963--997, October 1999.
pdf, bib .
- S. Akella and M. T. Mason, "Parts Orienting with Partial
Sensor Information," 1998 IEEE International Conference on
Robotics and Automation, Leuven, Belgium, May 1998.
pdf, bib .
- S. Akella and M. T. Mason, "Parts Orienting by
push-aligning". Proceedings of the 1995 IEEE International
Conference on Robotics and Automation, Nagoya, Japan, May 1995.
pdf , bib .
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.
- S. Akella and M. T. Mason, "Orienting Toleranced Polygonal
Parts," International Journal of Robotics Research, Vol. 19,
No. 12, pp. 1147--1170, December 2000.
pdf , bib .
- S. Akella and M. T. Mason, "Parts Orienting with Shape
Uncertainty," 1998 IEEE International Conference on Robotics and
Automation, Leuven, Belgium, May 1998.
pdf, bib .
Finalist, Anton Philips Best Student Paper Award.
Reconfigurable Parts Feeder
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.
Back to top.
Back to Srinivas' home page
Srinivas Akella / sakella at uncc dot edu