Two major approaches exist for devising gait control for a legged machine: (1) finding a sequence of leg and body movements of a robot on the basis of kinematic and possibly dynamic considerations assuming all foot placements are valid and (2) selecting leg and body movements first on the basis of feasibility of foot placements (because the underlying terrain might render impossible certain foot placements) and then accepting those that also satisfy kinematic and possibly dynamic constraints. Consider now the problem of a legged robot pursuing a quarry. With the first approach, the robot will be limited to operating over a relatively flat terrain; over such a terrain, it might be able to synthesize a sequence of precomputed straight-line and turning gaits in order to match as closely as possible to the trajectory of the quarry. If the terrain is uneven, however, the robot will have no recourse but to take the second approach, even though it is computationally more demanding. The work done so far in the second approach is limited either by the constraint that the overall direction of ambulation of the robot is known in advance or by the constraint that the foot placements are limited to the points of a grid superim-