Real-time robot-motion planning

New processor can plan an optimal, energy-efficient robot motion path up to 10,000 times faster
June 21, 2016

New computer processor allows for fast, energy-efficient robot motion planning in cluttered environments (credit: Duke Robotics)

Duke University researchers have designed a new computer processor that’s optimized for robot motion planning (for example, for quickly picking up and accurately moving an object in a cluttered environment while evading obstacles). The new processor can plan an optimal motion path up to 10,000 times faster than existing systems while using a small fraction of the required power.

The new processor is fast enough to plan and operate in real time, and power-efficient enough to be used in large-scale manufacturing environments with thousands of robots, according to George Konidaris, assistant professor of computer science and electrical and computer engineering at Duke.

“When you think about a car assembly line, the entire environment is carefully controlled so that the robots can blindly repeat the same movements over and over again,” said Konidaris. “The car parts are in exactly the same place every time, and the robots are contained within cages so that humans don’t wander past.”

But for uncontrolled environments (such as homes), robot motion planning has to be a lot smarter and able to learn in real time. That would save the time and expense of custom-engineering the environment around the robot, said Konidaris, who presented the new work yesterday (June 20) at a conference called Robotics: Science and Systems in Ann Arbor, Mich.

Duke Robotics | Robotic Motion Planning

Collision detection in real time

Most existing approaches for robot motion planning rely on general-purpose CPUs or computationally faster but more power-hungry graphics processors (GPUs). Instead, the Duke team specifically designed a new processor for motion planning.

“While a general-purpose CPU is good at many tasks, it cannot compete with a processor specially designed for just a single task,” said Daniel Sorin, professor of electrical and computer engineering and computer science at Duke.

Konidaris and Sorin’s team designed their new processor to perform collision detection — the most time-consuming aspect of motion planning — requiring thousands of collision checks in parallel. “We streamlined our design and focused our hardware and power budgets on just the specific tasks that matter for motion planning,” Sorin said.

The key was to use an FPGA (field-programmable gate array) integrated circuit, which can be configured by a designer for customized uses.

The robot-motion processor selects the set of voxels swept by the robot arm and this set is used to build specialized circuits in an FPGA integrated circuit to detect collisions and optimize motions in real time during operation (credit: Duke Robotics)

The technology works by breaking down the arm’s operating space into thousands of 3D volumes called voxels (volume pixels). The algorithm then determines whether or not an object is present in one of the voxels contained within pre-programmed motion paths. Thanks to the specially designed hardware, the technology can check thousands of motion paths simultaneously, and then stitch together the shortest motion path possible using the “safe” options remaining.


“The state of the art prior to our work used high-performance, commodity graphics processors that consume 200 to 300 watts,” said Konidaris. “And even then, it was taking hundreds of milliseconds, or even as much as a second, to find a motion plan. We’re at less than a millisecond, and less than 10 watts. Even if we weren’t faster, the power savings alone will add up in factories with thousands, or even millions, of robots.”

Konidaris also notes that the technology opens up new ways to use motion planning. “Previously, planning was done once per movement, because it was so slow,” he said, “but now it is fast enough that it could be used as a component of a more complex planning algorithm, perhaps one that sequences several simpler motions or plans ahead to reason about the movement of several objects.”

The new processor’s speed and power efficiency could create many opportunities for automation. So Konidaris, Sorin and their students have formed a spinoff company, Realtime Robotics, to commercialize the technology. “Real-time motion planning could really be a game-changer for robotics,” said Konidaris.

This research was supported by the Defense Advanced Research Projects Agency and the National Institutes of Health.

Abstract of Robot Motion Planning on a Chip

We describe a process that constructs robot-specific circuitry for motion planning, capable of generating motion plans approximately three orders of magnitude faster than existing methods. Our method is based on building collision detection circuits for a probabilistic roadmap. Collision detection for the roadmap edges is completely parallelized, so that the time to determine which edges are in collision is independent of the number of edges. We demonstrate planning using a 6-degree- of-freedom robot arm in less than 1 millisecond.