ates from the desired trajectory. But if
it veers too far off, nonlinear terms can
take over and the robot may crash. But
now, using Parrilo’s tools, Tedrake can
generate “proofs of stability” for these
nonlinear terms that in essence define
an envelope within which the robot will
converge back to its nominal trajectory.
“Proving stability in this way is important for the techniques to be accepted in
many applications,” he says.
“This opens up a rigorous way of
thinking of nonlinear systems in ways
not possible a few years ago,” Tedrake
says. “It used to be you had to be very innovative and creative to come up with a
proof of stability for nonlinear systems.”
Now, he says, his results are more reliable and rigorous, and he can more easily devise and evaluate alternate flight
paths and control systems.
Like Harrison, Tedrake hails an efficiency breakthrough in Parrilo’s methods. Instead of laboriously verifying the
stability of thousands of isolated trajectories, he can now work with just a few
“regions of stability,” he says.
Parrilo’s work is noteworthy for the
specific techniques and algorithms he
has developed, but, at a higher level,
it is impressive for its reach, says John
Doyle, a professor of control and dy-
namical systems at the California In-
stitute of Technology. Doyle points
out that researchers have labored for
decades to understand and control
complex nonlinear systems, such as
those that run computers, manage net-
works, and guide airplanes. Many use-
ful tools—such as formal verification
of software and hardware—and disci-
plines—such as robust control—have
emerged from this work. But, Doyle
says, there has not been a “unified ap-
proach” to the problem of anticipat-
ing and preventing unintended conse-
quences in systems that are “dynamic,
nonlinear, distributed and complex.”
Now, Parrilo has made a giant step
toward developing just such a unified
approach, Doyle says. “What Pablo said
was, ‘Here is a systematic way to pursue
these problems and, oh, by the way, a lot
of these tricks that you guys have come
up with over 30 years—in a whole bunch
of fields that we didn’t see as related—
are all special cases of this strategy.’
What he did is connect the dots.”
Parrilo enables one to “automate
the search for proofs,” Doyle says. He
Pablo Parrilo
has constructed
a bridge between
theoretical math
and engineering
that extends the
frontiers of chip
design, robotics,
biology, and
economics.
explains it this way: “You have a set of
bad behaviors that you don’t want the
system to have, and you have a model
of the system. You want to prove that
the two sets don’t intersect. Pablo rec-
ognized that there was a sort of univer-
sal way to attack this set non-intersec-
tion problem.”
As for the breadth of Parrilo’s think-
ing, Doyle says, “The mathematicians
think of Pablo as one of their own, and
so do the engineers.”
Further Reading
Boyd, S. and Vandenberghe, L.
Convex Optimization, Cambridge University
Press, Cambridge, U.K, 2004.
Dekker, S.
Structured Semidefinite Programs and
Semialgebraic Geometry Methods in
Robustness and Optimization (Ph.D.
dissertation), California Institute of
Technology, Pasadena, CA, May 2000.
Parrilo, P.A.
Semidefinite programming relaxations for
semialgebraic problems, Mathematical
Programming Ser. B 96, 2, 2003.
Parrilo, P.A.
Sum of squares optimization in the analysis
and synthesis of control systems, 2006
American Control Conference, Minneapolis,
Mn, June 14–16 2006.
Parrilo, P.A. and Sturmfels, B.
Minimizing polynomial functions, Cornell
University Library, March 26, 2001, http://
arxiv.org/abs/math.OC/0103170.
Gary Anthes is a technology writer and editor based in
Arlington, VA.
© 2011 ACM 0001-0782/11/0100 $10.00
Education
Hispanics
and STEM
federal and state government
agencies have taken steps to
help more hispanic students
be trained in the science,
technology, engineering, and
mathematics (Stem) fields
in the U. S., but hispanic
students remain severely
underrepresented among Stem
master’s and doctoral degree
recipients. Now, a report from
the Center for Urban education,
Tapping HSI-STEM Funds to
Improve Latina and Latino Access
to STEM Professions, offers
suggestions about improving
hispanics’ Stem participation,
and notes that financial issues
often play an important role.
“It is clear that every
computer scientist, scientist,
and engineer has a role to
play in diversifying the Stem
fields and that the time to do
it is now,” says alicia Dowd,
associate professor of higher
education at the University
of Southern California and
codirector of the Center for
Urban education.
the report alerts Stem
administrators and faculty at
hispanic-Serving Institutions
(hSIs) that substantial funds
will be available over the next
decade to support hispanic
Stem students, and provides
recommendations for how to
best use those funds.
hSIs can improve the
number of hispanic students
earning Stem degrees by
helping them balance their
reliance on loans and earnings
with grants and scholarships,
the report notes. It recommends
that when applying for hSI-
Stem funds, hSIs should
increase support for intensive
junior- and senior-year
Stem research experiences
and propose programs
that incorporate research
opportunities into the core
curriculum rather than into
special programs that may not
be accessible to working adults.
the report suggests that
colleges, particularly those with
large hispanic populations,
should inform students about
their full range of financial-aid
options. It also urges colleges to
recognize that many hispanic
undergraduates are supporting
themselves and are more likely
to work than their peers.