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:

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.

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.

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 Systemsconference 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.

Read more at: allaboutcircuits.com