Researchers Develop Advanced Path Planning Approach for Robots

Researchers at the University of Michigan have developed a new path planning approach that speeds up robots across rough terrain. The newly developed algorithm was able to find successful paths three times as often as standard algorithms, and it required far less processing time. 

The research was published in Autonomous Robots. 

Developing The New Algorithm

The algorithm was specifically aimed at robots that use arm-like appendages to maintain balance on rough terrain, such as disaster areas and construction sites. 

Dmitry Berenson is associate professor of electrical and computer engineering and core faculty at the Robotics Institute. 

“In a collapsed building or on very rough terrain, a robot won't always be able to balance itself and move forward with just its feet,” said Berenson. “You need new algorithms to figure out where to put both feet and hands. You need to coordinate all these limbs together to maintain stability, and what that boils down to is a very difficult problem.”

The new research helps robots determine how difficult a terrain is before calculating the best path forward.

Yu-Chi Lin is a recent robotics Ph.D graduate and software engineer at Neuro Inc. 

“First, we used machine learning to train the robot on the different ways it can place its hands and feet to maintain balance and make progress,” said Lin. “Then, when placed in a new, complex environment, the robot can use what it learned to determine how traversable a path is, allowing it to find a path to the goal much faster.”

Despite the new and improved method, it still takes a long time to plan a successful long path while using traditional planning algorithms.

“If we tried to find all the hand and foot locations over a long path, it would take a very long time,” Berenson said.

Divide-and-Conquer

To get around this, the team relied on a “divide-and-conquer” approach. They split the path into tough-to-traverse sections and easier-to-traverse sections. With the former, the robots apply their learning-based method, and with the latter, they use a simpler path planning. 

“That sounds simple, but it's really hard to know how to split up that problem correctly, and which planning method to use for each segment,” Lin said.

For this to happen, the researchers need a geometric model of the entire environment, which they can get by flying a drone that scouts ahead of the robot.

The team created a virtual experiment with a humanoid robot in a corridor of rubble, and the results demonstrated that the team’s method outperformed previous methods in success and total time to plan. This is crucial during disaster scenarios. 

Out of 50 trials, the team’s method reached the goal 84% of the time compared to 26% for the basic path planner. It only took a little over two minutes to plan compared to over three minutes for the basic path planner. 

Besides this, the team also demonstrated how their method can work in the real world with a wheeled robot with a torso and two arms. The base of the robot was placed on a steep ramp, and it used its “hands” to brace itself as an uneven surface moved. The team’s method enabled the robot to plan a path in just over a tenth of a second, compared to just over 3.5 seconds with the basic path planner. 

The team will now look toward incorporating dynamically stable motion, which is similar to the natural movement of humans and animals. This would improve the robot's speed of movement, since it doesn't need to be constantly in balance.