There’s quite a few quadrupedal robots out there, the most impressive of which might be Boston Dynamics’ Spot. But they have a problem in common: figuring out where to step so that they don’t become stuck or fall over. Luckily, a team of scientists at the University of Oxford, Sabanci University in Istanbul, and the French National Center for Scientific Research have developed a novel algorithm that generates viable guide trajectories for most any environment.

“[W]e present an approach to automatically compute a contact plan on challenging and uneven terrains,” the researchers wrote in a preprint paper on (“Contact Planning for the ANYmal Quadruped Robot using an Acyclic Reachability-Based Planner“). “Navigating through highly uneven and cluttered environments, often with only a small set of potential footholds, is still an open problem.”

The researchers’ approach tackles the challenge in several stages. A model analyzes the environment to identify possible contact surfaces, considering surfaces against which a four-legged robot (the ANYmal, in this case) can push and avoiding contact points too close to edges. Then, that same model creates a “contact reachable” guide path for the robot’s body, such that its limbs make solid contact with each step.

Robot navigation

“If the main body intersects the environment, this implies collision,” the paper’s authors explain, “but if the environment does not intersect with the limb workspace then the robot cannot reach the environment to create contact. Therefore the region between these extremes, in which contact can be created without the body colliding, is considered to meet the reachability condition.”

To reduce computation time, the team tapped a database of randomly generated leg configurations and limb ranges of motion. In the course of path planning, only configurations that result in a stable and non-colliding posture are kept — the rest are discarded until a viable configuration is found.

Furthermore, each sample of leg configuration is scored based on two sets of heuristics. One computes a weighted distance between the sample configuration and the robot’s standard configuration, and the second uses variables like slope steepness to determine which configurations increase controllability and stability.

In tests, the researchers set a digital robot running their framework lose in Gazebo, a simulation environment for autonomous machines. They had it attempt terrains of progressively varying difficulty, including a flat floor, floors with small height variation and obstacles, flat surfaces with large height variation (like stairs), and non-flat surfaces with large height variation (rubble terrain).

The team reports that their guide path planner was “very robust” and that it gave trajectories that avoided collision and unstable configurations. Moreover, they say, it took less than seven seconds to generate a contact plan for approximately 50 steps on any environment.

They do note, however, that the success rate in dynamic simulations is still too low to allow for unsupervised deployment on a real-world robot. They leave this to future work.