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.
Previous
Next Post »
My photo

Hi, I`m Sostenes, Electrical Technician and PLC`S Programmer.
Everyday I`m exploring the world of Electrical to find better solution for Automation. I believe everyday can become a Electrician with the right learning materials.
My goal with BLOG is to help you learn Electrical.
Related Posts Plugin for WordPress, Blogger...

Label

KITAIFA NEWS KIMATAIFA MICHEZO BURUDANI SIASA TECHNICAL ARTICLES f HAPA KAZI TU. LEKULE TV EDITORIALS ARTICLES DC DIGITAL ROBOTICS SEMICONDUCTORS MAKALA GENERATOR GALLERY AC EXPERIMENTS MANUFACTURING-ENGINEERING MAGAZETI REFERENCE IOT FUNDAMENTAL OF ELECTRICITY ELECTRONICS ELECTRICAL ENGINEER MEASUREMENT VIDEO ZANZIBAR YETU TRANSDUCER & SENSOR MITINDO ARDUINO RENEWABLE ENERGY AUTOMOBILE SYNCHRONOUS GENERATOR ELECTRICAL DISTRIBUTION CABLES DIGITAL ELECTRONICS AUTOMOTIVE PROTECTION SOLAR TEARDOWN DIODE AND CIRCUITS BASIC ELECTRICAL ELECTRONICS MOTOR SWITCHES CIRCUIT BREAKERS MICROCONTROLLER CIRCUITS THEORY PANEL BUILDING ELECTRONICS DEVICES MIRACLES SWITCHGEAR ANALOG MOBILE DEVICES CAMERA TECHNOLOGY GENERATION WEARABLES BATTERIES COMMUNICATION FREE CIRCUITS INDUSTRIAL AUTOMATION SPECIAL MACHINES ELECTRICAL SAFETY ENERGY EFFIDIENCY-BUILDING DRONE NUCLEAR ENERGY CONTROL SYSTEM FILTER`S SMATRPHONE BIOGAS POWER TANZIA BELT CONVEYOR MATERIAL HANDLING RELAY ELECTRICAL INSTRUMENTS PLC`S TRANSFORMER AC CIRCUITS CIRCUIT SCHEMATIC SYMBOLS DDISCRETE SEMICONDUCTOR CIRCUITS WIND POWER C.B DEVICES DC CIRCUITS DIODES AND RECTIFIERS FUSE SPECIAL TRANSFORMER THERMAL POWER PLANT cartoon CELL CHEMISTRY EARTHING SYSTEM ELECTRIC LAMP ENERGY SOURCE FUNDAMENTAL OF ELECTRICITY 2 BIPOLAR JUNCTION TRANSISTOR 555 TIMER CIRCUITS AUTOCAD C PROGRAMMING HYDRO POWER LOGIC GATES OPERATIONAL AMPLIFIER`S SOLID-STATE DEVICE THEORRY DEFECE & MILITARY FLUORESCENT LAMP HOME AUTOMATION INDUSTRIAL ROBOTICS ANDROID COMPUTER ELECTRICAL DRIVES GROUNDING SYSTEM BLUETOOTH CALCULUS REFERENCE DC METERING CIRCUITS DC NETWORK ANALYSIS ELECTRICAL SAFETY TIPS ELECTRICIAN SCHOOL ELECTRON TUBES FUNDAMENTAL OF ELECTRICITY 1 INDUCTION MACHINES INSULATIONS ALGEBRA REFERENCE HMI[Human Interface Machines] INDUCTION MOTOR KARNAUGH MAPPING USEUL EQUIATIONS AND CONVERSION FACTOR ANALOG INTEGRATED CIRCUITS BASIC CONCEPTS AND TEST EQUIPMENTS DIGITAL COMMUNICATION DIGITAL-ANALOG CONVERSION ELECTRICAL SOFTWARE GAS TURBINE ILLUMINATION OHM`S LAW POWER ELECTRONICS THYRISTOR USB AUDIO BOOLEAN ALGEBRA DIGITAL INTEGRATED CIRCUITS FUNDAMENTAL OF ELECTRICITY 3 PHYSICS OF CONDUCTORS AND INSULATORS SPECIAL MOTOR STEAM POWER PLANTS TESTING TRANSMISION LINE C-BISCUIT CAPACITORS COMBINATION LOGIC FUNCTION COMPLEX NUMBERS ELECTRICAL LAWS HMI[HUMANI INTERFACE MACHINES INVERTER LADDER DIAGRAM MULTIVIBRATORS RC AND L/R TIME CONSTANTS SCADA SERIES AND PARALLEL CIRCUITS USING THE SPICE CIRCUIT SIMULATION PROGRAM AMPLIFIERS AND ACTIVE DEVICES BASIC CONCEPTS OF ELECTRICITY CONDUCTOR AND INSULATORS TABLES CONDUITS FITTING AND SUPPORTS CONTROL MOTION ELECTRICAL INSTRUMENTATION SIGNALS ELECTRICAL TOOLS INDUCTORS LiDAR MAGNETISM AND ELECTROMAGNETISM PLYPHASE AC CIRCUITS RECLOSER SAFE LIVING WITH GAS AND LPG SAFETY CLOTHING STEPPER MOTOR SYNCHRONOUS MOTOR AC METRING CIRCUITS APPS & SOFTWARE BASIC AC THEORY BECOME AN ELECTRICIAN BINARY ARITHMETIC BUSHING DIGITAL STORAGE MEMROY ELECTRICIAN JOBS HEAT ENGINES HOME THEATER INPECTIONS LIGHT SABER MOSFET NUMERATION SYSTEM POWER FACTORS REACTANCE AND IMPEDANCE INDUCTIVE RESONANCE SCIENTIFIC NOTATION AND METRIC PREFIXES SULFURIC ACID TROUBLESHOOTING TROUBLESHOOTING-THEORY & PRACTICE 12C BUS APPLE BATTERIES AND POWER SYSTEMS ELECTROMECHANICAL RELAYS ENERGY EFFICIENCY-LIGHT INDUSTRIAL SAFETY EQUIPMENTS MEGGER MXED-FREQUENCY AC SIGNALS PRINCIPLE OF DIGITAL COMPUTING QUESTIONS REACTANCE AND IMPEDANCE-CAPATIVE RECTIFIER AND CONVERTERS SEQUENTIAL CIRCUITS SERRIES-PARALLEL COMBINATION CIRCUITS SHIFT REGISTERS BUILDING SERVICES COMPRESSOR CRANES DC MOTOR DRIVES DIVIDER CIRCUIT AND KIRCHHOFF`S LAW ELECTRICAL DISTRIBUTION EQUIPMENTS 1 ELECTRICAL DISTRIBUTION EQUIPMENTS B ELECTRICAL TOOL KIT ELECTRICIAN JOB DESCRIPTION LAPTOP THERMOCOUPLE TRIGONOMENTRY REFERENCE UART WIRELESS BIOMASS CONTACTOR ELECTRIC ILLUMINATION ELECTRICAL SAFETY TRAINING FILTER DESIGN HARDWARE INDUSTRIAL DRIVES JUNCTION FIELD-EFFECT TRANSISTORS NASA NUCLEAR POWER SCIENCE VALVE WWE oscilloscope 3D TECHNOLOGIES COLOR CODES ELECTRIC TRACTION FEATURED FLEXIBLE ELECTRONICS FLUKE GEARMOTORS INTRODUCTION LASSER MATERIAL PID PUMP SEAL ELECTRICIAN CAREER ELECTRICITY SUPPLY AND DISTRIBUTION MUSIC NEUTRAL PERIODIC TABLES OF THE ELEMENTS POLYPHASE AC CIRCUITS PROJECTS REATORS SATELLITE STAR DELTA VIBRATION WATERPROOF