PCG: A foothold selection algorithm for spider robot locomotion in 2D tunnels

This paper presents an algorithm, called PCG, for planning the foothold positions of spider-like robots in planar tunnels bounded by piece-wise linear walls. The paper focuses on 3-limb robots, but the algorithm generalizes to robots with a higher number of limbs. The input to the PCG algorithm is a description of a tunnel having an arbitrary piece-wise linear geometry, a lower bound on the amount of friction at the contacts, as well as start and target foothold positions. Using efficient convex programming techniques, the algorithm approximates the possible foothold positions as a collection of cubes in contact c-space. A graph structure induced by the cubes has the property that its edges represent feasible motion between neighboring sets of 3-limb postures. This motion is realized by lifting one limb while the other two limbs brace the robot against the tunnel walls. A shortest-path search along the graph yields a 3-2-3 gait pattern that moves the robot from start to target using a minimum number of foothold exchanges. Simulation results demonstrate the PCG algorithm in a tunnel environment.