Legged robot locomotion planning

	Topic	Paper page
	A locomotion planning software system	Motion planning for a six-legged lunar robot
	Transition sampling, contact modeling.	Non-gaited locomotion planning

Details

By carefully choosing where to step, humans and animals can overcome steep, rocky, and broken terrain where no wheeled vehicle can travel. Impressively, experienced human rock climbers can climb terrain with slopes beyond 90° vertical without any mechanical aid, only friction between the rock and their hands and feet. Legged robots can potentially traverse such difficult terrain as well. Such capabilities must be exploited for use in search and rescue situations, interplanetary exploration, or off-road transportation. Furthermore, recent developments in humanoid robotics have inspired the desire to create “general-purpose” household robots. However, activities that humans consider mundane, such as navigating outdoor terrain of a garden or park, maneuvering into the seat of a car, or crawling under furniture to reach an electrical socket, require executing sophisticated and coordinated motions.

In each of these situations, the robot should be able to autonomously plan the motions of its joints, subject to certain physical constraints, such that a desired high-level motion task is achieved (e.g., go to point X, or touch object Y). My research addresses this general problem of motion planning for legged robots, focusing primarily on planning for uneven and steep terrain. The main objective is to devise an all-purpose motion planner for robots of arbitrary morphology to traverse terrain of varying difficulty.

This problem is difficult for a number of reasons.

• First, the robot has a high dimensional configuration space (the experimental platforms range from 18 to 42 dimensions). This makes it difficult to reason about the shape of the configuration space and constraints.
• Second, each discrete set of contacts gives rise to different constraints that need to be met by the robot's motion. These constraints mean the robot must move among lower dimensional submanifolds of the configuration space.
• A third aspect that is especially difficult when planning for humanoid robots is that the constraints are extremely constraining in certain dimensions, but not others. For example, when walking as a biped, the body can barely move before stability is lost, but the arms can move vitually anywhere without violating any constraints. This means exploration-based planners may introduce unnatural motions in the arms. However, we cannot remove those degrees of freedom in rough terrain, where the arms are needed to support the robot.

Contact-before-motion approach

This approach explicitly reasons about contacts before trying to produce the motion, and was first demonstrated on climbing robots by Tim Bretl. A similar approach was used in early work in manipulation planning (Alami and Laumond). I extended this work to fully 3D robots in 3D terrain. During this time I have contributed methods for configuration sampling, learning feasibility models to speed up planning, modeling contacts in 3D, and incorporating torque limit constraints. This method has been applied to the LEMUR robot, the HRP-2 in rocky terrain, and the ATHLETE lunar robot in rocky terrain.

The basic algorithm for contact-before motion planning maintains a tree T of configurations reachable from the start, connected by edges of feasible paths. Each configuration has a set of contacts, known as its stance. The algorithm repeats the following operation until the goal is reached

1. Pick a configuration q at a stance s that is known to be reachable.
2. Transition sampling. Sample a configuration q' that transitions to another stance s'. This configuration must satisfy the constraints of both s and s'.
3. Single-step planning. Plan a motion that connects q to q', using the constraints and dynamics of stance s.

The algorithm places an importance on stance transitions. The existence of a feasible transition configuration is a necessary condition on the existence of a feasible path. Furthermore, because transition configurations must meet the constraints of two stances, they are more constrained than configurations in a single stance. Since planning a path takes more computation than finding a configuration, it makes sense to focus on finding a transition before even attempting a path.

The algorithm also uses the fact that while maintaining a fixed set of contacts, motion is restricted to a submanifold of the configuration space. Therefore, single-step planning can be done in a configuration space of a fixed dimension. This allows the use of probabilistic roadmap (PRM) methods, which have been shown to work well for high dimensional configuration spaces with good "visibility" properties. Since PRMs have been shown to plan single-step motions for legged robots quickly, it can be inferred that the configuration space at a fixed set of contacts do have good visibility.

The algorithm does not specify how to select which configuration to pick, or stance to transition to. When adding a contact, there can either be very few choices (like in rock climbing) or infinitely many (when walking on flat ground). In the latter case, the success and efficiency of the algorithm greatly depend on how the contact choices are made.