Duke’s Robotics Team Expedites Real-Time Motion Planning by a Factor of 10000

Researchers at Duke University have dramatically improved motion planning of robots in complicated environments.

Motion Planning in Robotics Applications

Robots are manufactured for a wide variety of applications. In some of these applications, such as the assembly line of a factory, the robot operates in a known and static environment. Since the objects around the robot are known and fixed, we can program the robot to move around without colliding with anything.
On the other hand, there are applications in which the environment changes over time. A search-and-rescue robot, for example, normally does not face a fixed and known environment. In these applications, the robot needs motion planning to avoid collision with the objects in the environment.
According to Daniel Sorin, Professor of Electrical and Computer Engineering and computer science at Duke, until now, robots have always been either limited to a predefined set of movements or burdened by the massive path-finding computations. A robot needs to consider all of the possible movements and determine if a movement leads to a collision with its environment. This is a computationally time-consuming process even for today’s powerful processors.

The Challenges of Motion Planning

Motion planning is not a new problem and a tremendous amount of research is being done to find algorithms which prevent robots from having collisions. However, these algorithms are too heavy to be employed in real-time applications.
Typically, with a power-hungry Graphics Processing Unit (GPU), hundreds of milliseconds are required to do the motion planning in a complicated environment. Moreover, the power consumption of these designs is so high that makes them impractical even in many industrial applications.
Motion planning is one of the main obstacles that prevents robots from being available in our daily life. According to George Konidaris, Assistant Professor of Computer Science and Electrical and Computer Engineering at Duke University, motion planning is not a 3D problem. If a robotic arm has 7 joints, the motion planning will be a 7-dimentional problem. This is due to the fact that the robot must find a sequence of joint positions for each joint in its arm.

New Hardware for the Task

Due to the power and speed limitations of the previous designs, Sorin’s team decided to search for a practical solution to the problem of path finding. The result is a circuit which is specially designed to perform the motion-planning algorithm. It is so specialized in purpose that it does nothing else but motion planning.
The new chip, which speeds up motion planning by almost 10000 times and reduces the power by 15 times, has been tested on a robotic arm. Future applications of this research include autonomous cars, industrial applications, and more.
According to Murray, a PhD student involved in this project, the new design has attracted a lot of attention from industrial and commercial groups including Honda, Dyson, DoraBot, and Mitsubishi.
In the rest of this article, we will briefly review the recent techniques adopted by the robotics team at the Duke University.

Motion Planning by a Probabilistic Roadmap

A Probabilistic Roadmap (PRM) is one of the most widely-used solutions to the problem of motion planning. Let's go over an example process.
The following image shows an example of constructing a PRM which helps the robot to find its path from position q0 to position G:

Figure (1) Sampling the collision-free space around the robot to choose a safe path. Image courtesy of Duke University (PDF).

In order to find a solution, the space that does not overlap with the obstacles is sampled. These samples are shown by nodes in the image.
If a straight movement from one node to another one does not lead to a collision, we may decide to connect those two nodes. Such a connection (called "edge") shows that a straight movement between these two nodes is allowed and collision-free.
Next, we need to find a path from q0 to G using the lines (or edges) of the achieved graph. Collision detection (determining whether a connection between two nodes leads to a collision or not) is the most time-consuming part of the PRM method. Almost 99% of the calculations in motion planning are usually related to the collision detection.
As shown in Figure (2), when a robot moves, its path of movement can be considered as a swept volume.

Figure (2) The path of movement can be considered as a swept volume. Image courtesy of Duke University (PDF).

Collision detection examines this swept volume, along with the obstacles, to achieve a model which predicts collisions.
Unlike some previous designs, which rely simply on employing the many-core nature a GPU, Duke’s robotics utilizes two techniques to speed up motion planning: pre-computation and parallelism. Combined, these techniques are capable of speeding up motion planning by a factor of 10000. By pre-computation, we mean that a heavy part of the calculations is done only once, at the design stage. Using the results of the pre-computation stage, some circuitry is designed which employs the parallelism technique to further speed up the process.

Pre-Computation Along with Parallelism

A large general PRM considers both permanent obstacles in the environment and the robot's structure. A specific application instead uses a pruned version of this PRM. Therefore, we need the initial PRM to be large enough so that it is highly probable to contain solutions for various motion planning problems.
Next, the space around the robot is discretized into small elements of volume called voxels. A 15-bit binary number is assigned to each voxel. Each edge of the PRM, which corresponds to a particular swept volume, is examined and all of the voxels overlapping with this particular edge are listed.
Then, an optimized circuit (which is related to the examined edge) is designed. This circuit accepts the 15-bit code for the voxels and outputs a true value for the overlapping voxels.

A visualization of voxels around the area a robotic arm can operate in. Image courtesy of Duke University.

The above calculations are all performed once at the time of initial design.
In other words, we examine the fixed environment and the robot's structure before the robot starts to solve a problem.
We define a large number of small movements (i.e., edges of the general PRM above), say 1024. We define them for the robot in a way that a particular sub-set of these movements will be a solution to a problem from the set of our practical motion planning problems.
Then, we examine all of these 1024 movements and list the voxels that overlap with each movement.
Based on our findings so far, we develop a circuit for each movement (edge) which accepts the code of a voxel and tells us if an overlap exists. Since we build such collision detection circuit (CDC) for every possible movement, the CDCs are capable of operating simultaneously.
Therefore, we have 1024 CDCs which can simultaneously accept a voxel and mark all of the movements which overlap with that particular voxel. Again, all of these actions are done in the design stage— before the robot starts to solve a problem. This significantly reduces the computational burden of the robot in runtime.

At Runtime

The pre-computations simplify the runtime dramatically. At runtime, we only need to scan the environment and send the binary code of the voxels that are occupied by the obstacles to the CDCs.
The voxels are sent one at a time and all of the edges are examined simultaneously for that particular voxel. If a collision is detected, the corresponding edge (movement) is eliminated from the general PRM. In this way, all of the movements that lead to a collision are eliminated and the robot can find its path from the pruned PRM.
The above techniques are discussed in greater detail at the 2016 Robotics; Science and Systems conference at the University of Michigan.
The video below shows a robotic arm with amazing results of the new motion planning techniques. Note that without the new methods, the following video would have looked like a succession of small movements and pauses of several hundred milliseconds, whereas the new design reduces the pause time to nearly 1 millisecond.

Video courtesy of EurekAlert.

Konidaris and his team have started a spin-off company, Realtime Robotics, to help commercialize the new technology. This commercialization could help accelerate this technology's development—meaning we could see real-time motion planning robotics in application sooner than previously thought.