Search-based Foot Placement for Quadrupedal Traversal of Challenging Terrain

A primary motivation for employing quadrupedal robots is that their morphology allows them to traverse difficult terrain. For example, a mountain goat, by carefully choosing its foot placements, is able to scale steep cliff sides. In contrast, wheeled robots have difficulty traveling over non-level terrain, and bipedal robots face stability challenges on rough terrain, even at low velocities. In order for quadrupeds to perform traversals over rough terrain in a stable manner, robust navigation strategies are needed that allow the robots to take full advantage of their physical capabilities. Foot placement and body pose planning is one of the most challenging problems associated with such navigation. We approach this problem as a combinatoric search over candidate foot placements and body poses. The search returns the sequence of kinematically feasible steps with the lowest cost as determined by their deviation from the terrain-independent nominal steps. Due to the large search domain in this problem and the speed required by real time robots, searching for the true optimal solution is computationally intractable. Therefore, we use a limited-horizon best-first search that quickly finds a near-optimal feasible solution. We show, through a series of tests, that this algorithm is sufficient for traversing challenging terrain, with obstacle heights approaching the leg length of the quadruped.