bots IN BRIEF
SERVO 08.2016 19
MORE MOTION COMMOTION
Researchers from the Duke Robotics Group at Duke University in Durham, NC recently presented a paper
about “Robot Motion Planning on a Chip,” in which they
describe how they can speed up motion planning by three
orders of magnitude while using 20 times less power. How?
Rather than using general-purpose CPUs and GPUs, they
instead developed a custom processor that can run
collision checking across an entire 3D grid all at once.
The motion planning is being performed in real time,
in about a millisecond. Typical planning time for a task
might be several hundred milliseconds (or occasionally up
to a second), so the speed increase here is massive.
To understand what’s really going on, take a look at
the figure shown here (from the paper) which illustrates a
probabilistic roadmap, or PRM. A PRM is a graph of
connections between all the points in a 2D or 3D space
that don’t involve going through an obstacle. To motion
plan, all you have to do is put a start position and an end
position into the PRM, and figure out the most efficient
path to follow through the lines of the graph (the “edges”
In practice,
however, you also have
to consider the fact
that you’re dealing with
a physical robot arm, and that
when the arm’s gripper (the bit
you care about) moves from one
place to another, the rest of the
arm (which you don’t care about
as much) also has to move, and
may run into things that aren’t anywhere near the gripper. The area
that a robot arm moves through is called the “swept volume,” and is
shown in the image to the left.
The researchers say one study showed that collision detection
like this “consumed 99 percent of the compute time of a sample-based motion planner,” because it requires making “a geometric
model of the swept volume of each robot movement and [testing]
this model against a geometric model of each obstacle.”
While the researchers acknowledge that “designing specialized
hardware is an unusual step,” they point out that it’s likely
worthwhile because motion planning “is basic to robot movement,
and therefore critical to do quickly and well.”
A swept volume refers to the space
covered by a movement between
two robot positions. According to the
researchers, dominating
computational expense in sample-based motion planning algorithms is
determining whether a swept volume
overlaps with an obstacle.
Motion planning algorithms try to find an optimal path between
two points that avoid obstacles (left). A probabilistic roadmap, or
between them is collision-free (right).
All images courtesy of
Duke Robotics.
