Abstract
Content
5. Contact Forces and Hybrid Dynamics
Introduction
Humanoid robots are wonderfully complex machines, with the potential to travel through the same formidable terrains that humans can traverse, and to perform the same tasks that humans can perform. Unfortunately, that complexity and potential results in challenging control problems and computationally difficult planning issues. In this chapter, considered gait planning and locomotion for navigating humanoid robots through complicated and rough terrain. Humanoid robots have the ability to step over or onto obstacles in their path, and to move in an omni-directional manner, allowing the potential for increased versatility and agility when compared with wheeled robots. In this chapter discussed some of the differences that arise when planning for legs instead of wheels, and some of the reductions and approximations that can be used to simplify the planning problem. Considered a safe sequence of footsteps can be chosen in rough terrain, and present planners which can efficiently generate collision-free, stable motions through complicated environments for real humanoid robots.
Figure 1.1 – Humanoid robot
(animation: 21 frames, 7 loops, 450 kBytes)
Humanoid robots must constantly maintain balance using a small base of support which changes with every step the robot takes. Additionally, many different degrees of freedom must coordinate for even the simplest tasks. While whole-body motion planning methods can be applied to generate stable and safe motion[1], when applied to complex tasks and long sequences of motion these approaches become overwhelmed by the complexity of the problem. In this chapter considered gait planning and locomotion, which cause very long and complex paths through the joint space of the robot. For this reason, it is good to divide these large tasks into manageable chunks, and reduce the dimensionality of the problem to provide computationallytracktable problems to tackle. For legged robots, locomotion is a largely cyclical motion, stepping one foot after another. It is possible to take advantage of this repetitious nature of legged locomotion to solve navigation problems efficiently, while still utilizing the abilities that the legs give to the humanoid robot for traversing rough and complicated terrain.
Navigation Planning
Navigation for mobile robots is often a low-dimensional problem. Due to this low dimensionality, algorithms such as A*[2]can be used to provide optimal solutions for wheeled robots and still provide real-time performance. For real-world situations, the D* family of algorithms[3] provide inexpensive replanning to moving robots reacting to new sensor data. To further increase performance, or for planning in higher dimensions (such as including velocities), a coarse–fine or hierarchical approach is used in many systems, in which a coarse global plan is first computed, and a finer-grained planner or controller follows the global path, while adjusting for the dynamics of the vehicle and newly-sensed obstacles. An example of this approach for a cart-like robot is shown in Figure 1.2.
By layering planners and controllers in this way, the low-level control and planners only need to consider the near future, trusting to the higherlevel planners in the hierarchy that the rest of the path will be executable. By shortening the planners’ horizons, the individual planners can perform much quicker. The planners then replan as the robot begins to execute the plan to fill in details along the remaining path.
Figure 1.2 – An example of coarse–fine planning for a mobile robot
Navigation and Legs
Despite the established research into navigation strategies for mobile robots, there are some significant differences between humanoid robots and wheeled robots. Unlike wheeled robots, which can simply turn their wheels to move through the world, for a humanoid to travel from one location to another involves constant coordination of many degrees of freedom to provide balance and support. Another significant difference for legged locomotion is the form of interaction with the environment. Wheeled robots follow a continuous path through the environment, with mostly continuous change in contact with the ground (the exception being wheels leaving or re-contacting the ground). In contrast, while legged robots travel a continuous path through their state space, the contact with the environment changes discretely with every step taken. The dynamics of a legged robot are a hybrid dynamic system, containing discrete regions of continuous dynamics which change whenever a foot touches down or lifts off. It is still possible to directly use navigation planners developed for wheeled robots for humanoid robots[4, 5]. For example, imagine bounding a humanoid robot by a cylinder, and planning a path for that cylinder through the environment so that it avoids all obstacles. This example amounts to steering
the robot through the environment, and while effective and efficient in simple situations, this approach ignores the fact that the robot has legs, and with those legs the ability to step over obstacles, or to climb stairs, or to do the many things which make legged robots interesting.
To use those abilities, the navigation processes must consider them and plan for them. By using a full-body motion planner, is possible to plan for all the degrees of freedom of the robot, ensuring that we utilize all the capabilities available to the robot. However, this can very quickly become computationally intractable when planning long sequences and reasoning about robot dynamics. Additionally, using a full-body motion planning approach to navigate a humanoid robot means that the robot must essentially decide how to walk for every step the robot takes. Biped walking is still a difficult problem and an ongoing area of research. By relying on a motion planner to generate gaits, it becomes much more difficult to take advantage of walking controllers and balance mechanisms as they are developed and improved. There are certainly times when the robot may need to fall back to this kind of low-level planning[1, 2, 6] (imagine a rock-climbing situation, where each motion must be made carefully), but for normal navigation the robot can use an efficient gait utilizing the latest developments in walking and balance algorithms.
Dimensionality Reductions
Because the number of degrees of freedom of humanoid robots is too high to allow full-body motion planning for a large motion sequence, is necessary to reduce the problem to a manageable size, while retaining as much of the abilities of the robot as possible. In order to apply this planning approach is necessary to make an important decision, namely, what are these actions that the robot can take? Are they trajectories, control policies, or something else? This choice of what the actions consist of and how they are chosen has serious consequences for both how difficult the planning problem becomes, as well as how much of the robot’s capabilities are used in the resulting plan. As stated earlier, the full motion planning problem for all the degrees of freedom of a legged robot can quickly become intractable. However, it is possible to reduce this problem to planning in a lower-dimensional subspace in an efficient way by looking at the structure of the problem. After performing planning in this low-dimensional space, we can turn our plan back into a full-body motion for the robot, allowing the robot to move to the goal. In choosing how to reduce our search space, there are several goals for our final action representation:
- Re-use of existing control. A great deal of research has been performed on the subject of balance, walking, and running for legged robots. Ideally, our planning strategies can make use of the controllers that have resulted from that research, rather than requiring the planner to discover how to walk or run from scratch for each situation.
- Planning simplicity. The fewer dimensions in search space, the easier it is for a planner to explore. Simplifying the planning space has a large impact on real-time performance on a robot in real environments. For humanoid robots in challenging, changing environments, quick planning allows for reaction to new sensor data and execution errors before they become problems.
- Capability usage. It is needed to reduce the dimensionality of problem and simplify the actions for planner, another goal is to make sure that it does not sacrifice the unique abilities of legged robots in the process. It is important to find the right balance between utilizing as many capabilities of the robot as possible while at the same time not overwhelming the planner with too many details of the locomotion process.
- Executability. In addition to having enough freedom in the planner to use the full capabilities of the robot, we need to have enough information in the plan to ensure that we are not exceeding the robot’s capabilities. Depending on the details of the robot and its controllers, some dimensions may be safely ignored. However, it is important that we do not reduce our problem to the point where the planned action sequences exceed the abilities of the robot and controller.
To plan for stances for a particular legged system, it is necessary to provide several descriptions of robot capabilities. Each of these capabilities will be based on both the physical limits of the robot as well as the limitations of any underlying gait controllers that the humanoid will use. For a humanoid system the following has to be defined:
- The state space through which the planner will search. This is a projection of the full state of the robot, which will be based around stance configuration.
- The action model which describes the connectivity of our states. In planning for stances, our path will not be continuous through our state space, so we must explicitly define connectivity
- The state-action evaluation function which scores locations in the environment, and the actions the robot can take, providing a description of the types of terrain the robot and its controller can safely traverse. The function also is the objective function, which is need to be minimized, defining the optimal path.
Contact Forces and Hybrid Dynamics
As mentioned earlier, biped locomotion is a system of hybrid dynamics, where the discrete changes in the dynamics model happen upon the touchdown and liftoff of the feet. As the robot travels through its environment, its contact configuration with the terrain changes, and the reaction forces it can generate from those contacts change with each contact configuration. It is possible to classify each of the states of the robot by the support contact configuration, or a stance, the set of contact points between all parts of the robot and the environment. In a particular stance, there is a particular contact constraint being satisfied, but the robot still has freedom to move in the null space of that constraint. For a walking biped, any possible path involves switching back and forth between various single and double support stances, the double support stance being the intersecting region of two adjacent single support stances.
This classification provides a natural way to break up the problem into discrete chunks, in order to build our action set. By planning a path first as a sequence of constrained surfaces through which the motion must pass, it is possible significantly reduce the dimensionality of the search and simplify the checking of environment constraints, without the need to sacrifice the robot’s capabilities. For the walking biped example, every path will be made up of a sequence of double support phases, connected by paths through a single support phase. This breakdown also provides a very natural level of abstraction for behaviors and controllers.
Terrain Evaluation
Due to the fact that humanoid robots have only two legs, they spend a significant amount of time in single support configurations. Even in double support phases, the overall base of support may be small. As a result, the contact of the feet with the terrain takes on paramount importance. The robot must be able to generate required reaction forces to maintain balance as well as to perform its next footstep. More importantly, the contact of the feet with the terrain must not violate any assumptions that the locomotion controller makes about a particular foothold. This requirement can be difficult to satisfy, as it needs an in-depth understanding of the detail of the locomotion control. However, the more capable and robust the locomotion control of the humanoid robot, the less exacting the planning process needs to be to protect the robot from moving to an unsafe location.
Figure 1.3 – Different situation for footstep area
Evaluating the terrain to determine safety and stability is very dependent on both the physical robot used and the control scheme used to balance and locomote, and must be adjusted individually for every robot and controller. Additionally, a truly accurate evaluation of the terrain must consider the entire contact of the foot (or hand) with the ground. Figure 1.3 shows one ambiguous case that arises from analyzing only a small feature of the terrain.
References
1. Kuffner J, Nishiwaki K, Kagami S, Inaba M, Inoue H (2001) Motion planning for humanoid robots under obstacle and dynamic balance constraints. In: proceedings of IEEE international conference on robotics and automation 18.03.2015).
2. Bretl T, Rock S, Latombe JC (2003) Motion planning for a three-limbed climbing robot in vertical natural terrain. In: proceedings of IEEE international conference on robotics and automation, Taipei, Taiwan
3. Stentz A (1995) The focussed D* algorithm for real-time replanning. In: proceedings of international joint conference on artificial intelligence
4. Kuffner J (1998) Goal-directed navigation for animated characters using real-time path planning and control. In: proceedings of CAPTECH: workshop on modelling and motion capture techniques for virtual environments, pp 171–186
5. Chestnutt J, Nishiwaki K, Kuffner J, Kagami S (2007) An adaptive action model for legged navigation planning. In: proceedings of IEEE-RAS international conference on humanoid robots, Pittsburgh, PA
6. Hauser K, Bretl T, Latombe JC (2005) Learning-assisted multi-step planning. In: proceedings of IEEE international conference on robotics and automation, Barcelona, Spain
7. Kensuke Harada, Eiichi Yoshida, Kazuhito Yokoi Motion Planning for Humanoid Robots 305-8568 Tsukuba-shi, Ibaraki, Japan