TY - JOUR

T1 - A foothold selection algorithm for spider robot locomotion in planar tunnel environments

AU - Shapiro, Amir

AU - Rimon, Elon

AU - Shoval, Shraga

PY - 2005/10

Y1 - 2005/10

N2 - In this paper we present an algorithm, called the partitioned cubes gaiting (PCG) algorithm, for planning the foothold positions of spider-like robots in planar tunnels bounded by piecewise linear walls. The paper focuses on three-limb robots, but the algorithm generalizes to robots with a larger number of limbs. The input to the PCG algorithm is a geometric description of the tunnel, 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 configuration space (c-space). Each cube represents a contact independent set of feasible three-limb postures. A graph structure induced by the cubes has the property that its edges represent feasible motion between neighboring sets of three-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 three-two-three gait pattern that moves the robot from start to target using a minimum number of foothold exchanges. In practical environments the algorithm runs in time, which is linear in the number of tunnel walls and polynomial in the degree of cube approximation of contact c-space. Simulations as well as experiments demonstrate the PCG algorithm in tunnel environments.

AB - In this paper we present an algorithm, called the partitioned cubes gaiting (PCG) algorithm, for planning the foothold positions of spider-like robots in planar tunnels bounded by piecewise linear walls. The paper focuses on three-limb robots, but the algorithm generalizes to robots with a larger number of limbs. The input to the PCG algorithm is a geometric description of the tunnel, 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 configuration space (c-space). Each cube represents a contact independent set of feasible three-limb postures. A graph structure induced by the cubes has the property that its edges represent feasible motion between neighboring sets of three-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 three-two-three gait pattern that moves the robot from start to target using a minimum number of foothold exchanges. In practical environments the algorithm runs in time, which is linear in the number of tunnel walls and polynomial in the degree of cube approximation of contact c-space. Simulations as well as experiments demonstrate the PCG algorithm in tunnel environments.

KW - Contact c-space

KW - Gait planning

KW - Multi-legged locomotion planning

UR - http://www.scopus.com/inward/record.url?scp=27144532742&partnerID=8YFLogxK

U2 - 10.1177/0278364905058242

DO - 10.1177/0278364905058242

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:27144532742

SN - 0278-3649

VL - 24

SP - 823

EP - 844

JO - International Journal of Robotics Research

JF - International Journal of Robotics Research

IS - 10

ER -