Mines computer scientists developing new algorithms to improve robot motion planning

When you and I need to get something out of the refrigerator, we don’t think twice about how we’re going to do it. But for a robot, it’s not so simple as reaching in and grabbing the ketchup. What if the last person to use the ketchup put it back on the wrong shelf? Or what if it got pushed to the back of the fridge behind a bunch of other things?

Today’s robots often rely on algorithms that allow them to perform well within a controlled space. But when the robot encounters an obstacle that deviates from what it’s been programmed to expect, it can struggle to problem solve in a timely manner.

Neil Dantam, associate professor of computer science, and Mines graduate Sihui Li are working to solve this challenge through the development of new algorithms to help robots understand when to stop trying to complete a task that’s not working and find an alternative solution. Here, Dantam answers a few questions about his group’s work and how better robot motion planning can impact the future of robotic technology across sectors.

Q: What is robot motion planning and how do the complexities of real-world environments complicate this process for robots?

Neil Dantam: Robot motion planning is a fundamental set of algorithms for robots – it’s finding the trajectory for a robot arm to go from where it’s starting out to the position where you want it to be, without running into anything, so it can grasp an object. 

If you look at the environment around you, you see a three-dimensional space. Now, look at your arm—you have your shoulder, your elbow and your wrist—and many robot arms are structured in a very similar way. You can also see that there are three axes in which you can move your shoulder, one in which you can move your elbow and three axes in which you can move your wrist—you can move your wrist up and down and left to right and you can rotate your forearm. If you add those up, there are seven dimensions in which you are moving a robot arm.

The challenge comes from the difficulty of operating in this seven-dimensional space of joint positions and the inability of traditional computer science search algorithms to find plans in that high dimensional space.

Q: So, what does it mean if a robot can’t find a motion plan?

Dantam: It can mean a few different things. Does it mean you can’t find a plan because no plan exists? Say you want to get something out of the back of your fridge, but there’s no way to reach around all the stuff you have in front. Or is it because you just didn’t spend long enough thinking about how to reach around everything? Maybe you just needed more time to find the plan. Or maybe the algorithm is such that you don’t have enough computational resources and you will run out of memory. All these things can prevent you from finding a plan. And in the case of classical sampling-based motion planning algorithms, they would not stop looking unless you imposed  aparticular timeout.

Sihui’s work addresses exactly what it means when we say we can’t find a plan. Her work lets us prove this case of “no plan exists.” Given we spend enough time—and have the computational resources—then we can say definitively either no plan exists or yes, there is a plan and here it is.

Q: Why does that distinction matter when it comes to robot motion planning?

Dantam: The classic sampling-based algorithms exclusively address cases where plans exist. That makes sense if you think my only problem is moving the robot from Point A to Point B, but that’s never the only problem. You’re moving the robot from Point A to Point B for some larger task. In a factory, you have a sequence of motions to take—maybe you want the robot to assemble a car door. It’s got to do a combination of things, and there may be some dependencies between steps—you may need to move certain things out of the way to reach other things.

So, it’s not just a single motion-planning problem but multiple, and some motions may not be feasible until you do something else first. That’s why we care about the case where no plan exists, because when we can’t do something, we need to figure out some alternative.

What we’ve done is taken these classical sampling algorithms and added a combination of machine learning and computational geometry. The high-level idea is that the learning we’re doing is describing the connections in this seven-dimensional space of robot joints.

Q: How could these new algorithms impact the future of robotic technology?

Dantam: If we have a way of finding when a particular step is not possible, we can get back to an earlier question I had in my work, which is called “task and motion planning.” Task and motion planning isn’t just about finding the motion from Point A to Point B but thinking about that within the larger task the robot is doing. That’s important for higher-level, more autonomous tasks that you would want a robot to do. 

With industrial robots, you often pre-program specific steps. But if you drop a robot in a less structured or unstructured environment like my kitchen, you may have a task that the robot does not do a million times or even 100 times but maybe just once.

That’s the kind of scenario we’re thinking about—domestic services, things like custom manufacturing. You’re not going to do the typical industrial robot programming to make a single thing one time. But if you’re able to say, “This is what I want at the end. Now, robot, you figure out all the steps to do that,” that’s the idea. That’s what has previously not been feasible but what we’re making progress toward.