A provisional desired motion trajectory of an object is determined based on a moving plan of the object. Then, it is determined whether a robot leg motion can satisfy a necessary requirement. The requirement is related to a position/posture relationship between the object and the robot, and a determination of whether the requirement can be satisfied is made at a future, predetermined step. A restrictive condition related to robot leg motion is satisfied at each step up to the predetermined number of steps. If the requirement is satisfied, then a desired gait is generated on the basis of the provisional desired motion trajectory. Otherwise, a desired gait is generated on the basis of a desired motion trajectory of the object according to a corrected moving plan.