Faster Detection Collision Algorithm Could Enable Robots to Perform Better in Tasks that Require Assistance

Electrical engineers from the University of California San Diego have created a faster collision detection algorithm that employs machine learning to help robots keep away from moving objects and move through complex, quickly changing environments in real time.

The algorithm, called “Fastron,” runs up to 8 times faster compared to current collision detection algorithms.

A team of engineers, headed by Michael Yip, a professor of electrical and computer engineering and member of UC San Diego’s Contextual Robotics Institute, will exhibit the new algorithm at the first annual Conference on Robot Learning, being held from November 13 to 15 at Google headquarters in Mountain View, California. The meeting brings the top machine learning researchers to an invitation-only event. During the 3-day conference, Yip’s team will give one of the long talks.

The team predicts that Fastron will be largely useful for robots that work in human environments where they should be able to fluidly work with moving object and people. One such application they are looking at in particular is robot-assisted surgeries employing the da Vinci Surgical System, where a robotic arm would autonomously carry out assistive jobs (suction, irrigation or pulling tissue back) without disturbing the surgeon-controlled arms or the patient’s organs.

“This algorithm could help a robot assistant cooperate in surgery in a safe way,” Yip said.

The team also predicts that Fastron can be employed for robots that operate at home for assisted living applications, and for computer graphics for movie and gaming industry, where collision checking is usually a bottleneck for most algorithms.

A problem with current collision detection algorithms is that they are extremely computation-heavy. They spend more time specifying all the points in a particular space—the specific 3D geometries of the robot and obstacles—and carrying out collision checks on each single point in order to determine whether two bodies are meeting at any given time. When obstacles are moving, the computation gets even more demanding.

In the Advanced Robotics and Controls Lab (ARClab) at UC San Diego, Yip and his team developed a minimalistic method to collision detection in order to lighten the computational load. The outcome was Fastron, an algorithm that makes use of machine learning strategies, which are conventionally used to categorize objects, to categorize collisions versus non-collisions in dynamic environments. “We actually don’t need to know all the specific geometries and points. All we need to know is whether the robot’s current position is in collision or not,” stated Nikhil Das, an electrical engineering Ph.D. student in Yip’s group and the study’s first author.

The Fastron algorithm

The name Fastron is derived from combining Fast and Perceptron, a machine learning approach for performing classification. A significant feature of Fastron is that it very quickly updates its classification boundaries to accommodate for moving scenes, something that has been generally difficult for the machine learning community to do.

The active learning strategy of Fastron works by using a feedback loop. It begins by developing a model of the robot’s configuration space (C-space), which is the space displaying all possible positions the robot can achieve. Fastron uses only a sparse set of points, comprising of a few so-called collision points and collision-free points, to model the C-space. Then, the algorithm defines a classification boundary between both the collision and collision-free points—this boundary is basically a rough outline of where the abstract obstacles are present in the C-space. The classification boundary changes when obstacles move. Instead of carrying out collision checks on each point in the C-space, as is performed with other algorithms, Fastron intelligently chooses and checks near the boundaries. After it categorizes the collisions and non-collisions, the algorithm updates its classifier and after that continues the cycle.

Since Fastron’s models are very simplistic, the researchers fixed its collision checks to be more conservative. Because only a few points represent the whole space, Das explained, it is not always sure what’s taking place in the space between two points, so the team created the algorithm to predict a collision in that space. “We leaned toward making a risk-averse model and essentially padded the workspace obstacles,” Das stated. This ensures that the robot can be adjusted to be more conservative in delicate environments like surgery, or for robots that operate at home for assisted living.

So far, the team has displayed the algorithm in computer simulations on robots and obstacles in simulation. Going forward, the team is working to further enhance the accuracy and speed of Fastron. Its aim is to apply Fastron in homecare robot setting and a robotic surgery.