Abstract: According to the characteristics of humanoid robot, the complex motion planning for humanoid robot can be divided into global path planning, local motion planning and task planning. Depending on the time consumed during process of the planning, online and offline are considered as the two ways of controlling the global path planning. The performances of different searching algorithms in the Cfree space are present and analyzed and features that planning algorithms should have are proposed. Planning online is achieved through the feedback information of environment gained by vision sensors and different features on motion planning between mobile robot and humanoid robot are present. The local motion planning can be divided into three methods composed of based on model, non model and intelligent control and tasks planning existed recently are proposed. Finally, challenges of complex motion planning for humanoid robot are present.
INTRODUCTION
Comparing with wheeled mobile robots and multi-legged mobile robot, humanoid robots have better characteristics vary in adapting to the complex and non-construct ground and flexibility in the control of motions. Meanwhile, higher requirements and more complex researches are proposed for the motion planning because of the complex structure, mathematical models and dynamic environment of the humanoid robot. Therefore, the research of motion planning, analysis and evaluation are more important. There are three aspects of content for the researches of complex motions included of global path planning, local motion planning and task planning (Kuffner et al., 2003). Global path planning is the planning of discrete footprint sequence under global environment. Local motion planning is defined as the planning of motion for robot itself, which can be express as the motion trajectories planning of every degree of freedom of the robot. Task planning represents to plan for tasks, such as snatching an object, opening the door and cooperating with human beings some simple tasks. It is integrated with global path planning and local motion planning. As the limitation of research, task planning is not the major research for the humanoid robot recently. This study mainly introduced some typical algorithms of motion and local motion planning, analysis and evaluation of applications on humanoid robot are present.
GLOBAL PATH PLANNING
Mathematical expression of global path planning: No matter what kind of motion planning belongs to the robot and which kind of planning algorithm is adopted, the following steps should be followed:
| • | Build the circumstance model, which is the corresponding model abstracted from real world where the robot is |
| • | Search the path without any collisions, which means finding the path searching algorithm matched the condition in a model space |
The problem of global path planning for mobile robot can be described formally
as the inference engine (LaValle, 2006):
To define the problem of planning, a sequence of behaviors control u1,u2,...,uk is considered and a status sequence can be exported by this sequence:
If xk+1∈xgoal and {x1,x2,...,xk+1}∩xobst = ø, the sequence u1,u2,...,uk can be a solution for the problem of planning. The object of the global path planning for humanoid robot is to find a group of sequences of behaviors control which are conformed to certain rules.
Off-line planning
Planning based on geometric construction within Cfree space:
This method general includes of two stages: the first stage is to construct
a relationship map of Cfree space and the second stage is to find
an optimal path under some criteria (least distance, least time consumed and
et al.). Where the construction of map is more important and Dijkstra
and A* algorithms are used as the searching algorithms. Oommen
et al. (1987) planed the Cfree space with visual map.
The complexity of the time is O(n2lgn) or O(n2), where n represents the sum
of vertexes of obstacles. Many technologies from computational geometry are
introduced into the global path planning. Choset and Burdick
(1995) had done research on motion planning based on sensors using Generalized
Voronoi Graph (GVG). Meanwhile, the grid decomposition is a very popular method
used in the motion planning (Parsons and Canny, 1990).
The so called grids are the simple zones which are decomposed from working space
of robot. A visible connected graph is constructed by these grids or invisible
connected graph are founded during the searching and a path from the beginning
to end grid is searched in the graph. A tangent graph is constructed in the
Cfree based on polygonal obstacle model and substituting the obstacles
in arbitrary shape with approximate polygons. Liu and Arimoto
(1994) constructed the tangent graph by the method of connected with moving
line and scanning line. The moving line algorithm is used to detect all the
common tangents between the vertexes of the obstacle and the scanning line algorithm
is adopted to test whether there is a cross point between the known common tangent
and obstacle. If it exits, eliminate this common tangent and the tangent graph
is constructed by the remained common tangents. The worst time complexity for
constructing the tangent graph is O([M+R]N+M2 lgM), where N denotes the vertexes
of the obstacle, M represents the number of convex curve constructed by the
vertexes and R is the scroll number of open convex curve.
When the degree of freedom of the robot is less than four, the method of Voronoi graph is very well in the performance of real time. The method of construction of Cfree is better in the performance of completeness. The path planned by the methods of Voronoi graph and grid decomposition is reasonable than the methods of visible graph and tangent graph. The optimality of the method of grid decomposition is best than other algorithms.
On-line planning: The sensors of the robot are used to feedback the environment information and the robot can forecast the movement of obstacle to plan the motion on-line. The forecast is under the local environment and the results of the forecast are used to update the local environment information and then find a mapping of global target zone in the edge of local environment by a certain algorithm. The mapping that found is used as the target zone in local environment and then foot trajectory planning is under this local environment. After one period (the robot may not walk to the local target zone at this moment), new information from the sensor is arrived and repeat the above steps until the robot reach the global target zone. The common sensor for the robot usually is vision sensor. Piao et al. (2008a) present a novel image segmentation algorithm of improving the quality of color images for humanoid robot soccer game. The color space is adopted as HSI and an enhanced fuzzy K means clustering method was designed. Philipp et al. (2005) implemented this method mentioned earlier on the robot ASIMO and achieved good experimental results. Cupec et al. (2005) studied the loop iteration between the biped walking and visible observation, they developed a single vision system, which can deal with the wider visual margin in the environment within obstacles. Analysis for scene is achieved after every step of walking and the location of the obstacle is determined by the distance between the visible edges relative to foot reference frame. The edge detection of the obstacle is present by analyzing the scenes on line. Kanehiro et al. (2005) presented a method, which can generate the 3D model environment of humanoid robot by stereo vision (three cameras). Through this model, a feasible path can be found and planned on line in the moveable space. The motion planning is achieved by a pose generator for whole body on line. It can update the height of waist and pose of the upper body according to the size of the moveable space. Cai et al.(2008) proposed a novel scan matching algorithm called Combined Probabilistic Scan Matching (CPSM) for grid based FastSLAM in which Rao-Blackwellized Particle Filters (RBPF) was combined with Probabilistic Scan Matching (PSM). Novel autonomous navigation system for an indoor mobile robot based on monocular vision was presented (Li et al., 2008). A hybrid environment map was built with Rao-Blackwellized particle filters, where the number of resampling steps was determined adaptively for significantly reducing the particle depletion problem and the Evolution Strategies (ES) were introduced for avoiding particle impoverishment.
Characteristics of humanoid robot comparing to the mobile robot: Researches on global path planning and obstacle avoidance for mobile robots have been carried out to a relatively advanced stage. As the environment of the autonomous mobile robot is low dimension, usually, its guidance to find a satisfied path without collision in the two dimension environment can be successful. Part of the methods can be applied in the global path planning of humanoid robot, but these methods exclude the robots out of the obstacles. Comparing to the mobile robots, biped robot can step over some obstacles and step on the obstacle to walk on it. The characteristics of global path planning for humanoid robot can be described as bellow:
Dimensions of environmental model: The global path planning for humanoid robot is under the three dimensions environment and it can avoid the obstacle, step on and step over the obstacle. Therefore, it is more complex for humanoid robot to planning the motions.
Discreteness of the foot planning: From the trajectory of motion, the path for the mobile robot is continuous and smooth, while the path for humanoid robot is a projection set of discrete foot.
High complexity of planning: Jean (2001) proved that the complexity of planning is exponential relationship with the degree of freedom of robot and is polynomial relationship with the scale of obstacle in the environment. It is a dimension curse problem when the degree of freedom of robot increases, especially for the humanoid robot which has dozens of degree of freedom.
Complex dynamic and kinematic model and harsh conditions of the stability constraints: The dynamic and kinematic model for mobile robot is usually very simple and its complex planning is just the motion planning and the dynamic constraints of robot are not considered. However, because during the walking of humanoid robot, the holding foot is shitting from each other frequently and it is very complex to make the robot to keep stable.
For the characteristics mentioned above, the deterministic algorithm is not proper for solving the problems of humanoid robot (LaValle, 2006). Researchers adopted method based on random sampling in the planning space to improve the executing efficiency of the algorithm instead of completeness. Kavraki and Latombe (1994) proposed a serial of rapid motion planning algorithms in the pose space, which can be called Probability Road Mark (PRM) algorithm. Its main idea is to express the free space Cfree by random road mark map and then search a feasible path for robot in the map. It is a multiple search algorithm. But PRM has the flaw of completeness when dealing with the narrow passage. The scientist La Valla in UIUC presents a Rapid Random Tree (RRT) algorithm (LaValla, 2006), it is a rapid single incremental search algorithm and many researchers had improved it later.
LOCAL MOTION PLANNING
Local motion planning is the motion planning for robot itself. Because the humanoid robot can do kinds of motions just like human being, local motion planning is just suitable for humanoid robot. It also can be defined as trajectories planning for the angles from the whole body of robot. According to the different control methods of robot, local motion planning can be divided into control based on model, non-model and intelligent control.
Control based on model: Control based on model is the method that bold simplification for biped robot model is present according to the known physical model. It consists of inverted pendulum model, Central Pattern Generator (CPG) model and passive walking model.
Inverted pendulum model: Approximation is an effective method in dealing with complex system. For abstracting the nature of biped moving, approximating for humanoid robot with 30 degree of freedom is achieved. Supposing the whole mass of the robot is on the location of center of mass, the legs of robot being massless and only movements on up and down direction being considered, the robot can be simply to an inverted pendulum model. Combining the sensory system and the control system enabled the biped robot, Meltran II, to walk over ground of unknown profile successfully. Hofmann et al. (2009) used a simplified, inverted-pendulum model to generate compatible Center of Mass (CM) and ZMP trajectories at runtime and then employed Jacobian relations to transform CM velocities into corresponding joint velocities. Czarnetzki et al. (2009) described the generation of walking patterns based on a simple inverted pendulum model, using a sophisticated preview controller to generate motions, resulting in a desired future ZMP movement and the ability to compensate small disturbances or unforeseen forces.
CPG model: As for other devices, many studies have employed a CPG to generate rhythmic movements. In those studies, the CPG controller and the robot interacted with each other and were eventually entrained into a limit-cycle attractor. Nakamura et al. (2007) proposed a reinforcement learning method called the CPG actor-critic method. This method introduced a new architecture to the actor and its training is roughly based on a stochastic policy gradient algorithm presented recently. Or (2010) present a new hybrid CPG_ZMP control system for the walking of a realistically simulated flexible spine humanoid robot. Experimental results showed that using this control method, the robot is able to adapt its spine motions in real-time to allow stable walking.
Passive walking model: Using the method of passive dynamics, the joints of the robot have no actuators, only the dynamics characteristic alternated between robot and environment can realize the walking, which is defined as passive walking. Collins et al. (2001) developed the first passive walking biped robot which had knees. Recently, passive dynamic walking models have proven to be a useful template for the exploration of nonlinear gait dynamics. These models consist of an inverted double pendulum system that captures the dynamics of the swing and stance phase of gait. Aoyama et al. (2009) addressed a three-dimensional biped dynamic walking control based on Passive Dynamic Autonomous Control (PDAC) and apply its control framework to an experimental robot multi-locomotion robot. Owaki et al. (2009) discussed the common stabilization mechanism underlying Passive Dynamic Walking (PDW) and Passive Dynamic Running (PDR), focusing on the feedback structures in analytical Poincar'e maps and an implicit two-delay feedback structure, which can be seen as a certain type of two-delay input digital feedback control developed as an artificial control structure in the field of control theory, is an inherent stabilization mechanism in PDR appearing from the model with elastic elements and two-period and four period PDW appearing from with stiff legs.
Control based on non-model: The control policy based on non-model should consider the constraints of moving, which consists of stability and energy.
Constraint for stability: To realize the stable gait for biped robot, many researchers present different stability criterions for suiting the different models. For example, Center of Pressure (COP), Zero Moment Point (ZMP), Foot Rotation Indicator (FRI) and et al. where the ZMP present by Vukobratovic et al. (1990) was one of the most widely applied for the stability criterion of robot. Goswami (1999) introduced the notion of Foot Rotation Indicator (FRI), also known as imaginary ZMP (iZMP). The FRI is physically identical to the ZMP and both points coincide as long as ZMP/FRI remains inside the supporting area. Most humanoid robots are equipped with force-torque-sensors at the feet of the robot. Therefore the center of pressure criterion results directly from evaluating those sensors. The Center of Pressure (COP) is defined as the point on the ground where the resultant of the ground reaction forces acts (Goswami, 1999). Farrell et al. (2007) investigated the energetic effects of adding springs at the passive ankles of a planar five-link, four actuator walking biped robot, using FRI as the criterion of stable constraint. Zhong et al. (2008a) realized the dynamic stable standing up and falling down motions of humanoid robot with the constraint of ZMP.
Energy constraint: In addition to the stability of robot, energy consumed is considered a constraint for controlling the gait of robot by some researchers. Zheng and Sias (1988) modeled the collision proceeding of transition period between single supporting period and double supporting period for biped robot in detail. Relation function between changing from the angle of joints before and after collision and impacting force is found. The smooth landing of robot SD-2 is achieved by the controlling linear angular velocity of joints and nonlinear locations.
Intelligent control: It is no doubt that importing the intelligent control algorithm correctly will improve the algorithm of complex motion planning in suitability and robustness. In view of the power capability of self learning, self adaption and fault tolerance from traditional intelligent control algorithms, such as fuzz logic, genetic algorithm and neural network. These algorithms will be introduced in controlling of every model of robot.
Neural network: The neural network has the power ability of parallel computing and nonlinear mapping. It has been applied into the controlling of biped walking, static and dynamic balance and suiting in different terrains. Miller (1994) used an NN-based on-line learning technique, to tackle dynamic balance of a two-legged robot. Juang (2002) developed an algorithm for intelligent locomotion control on different sloping surfaces. Three neural networks with back propagation training were utilized.
Fuzzy algorithm: In the controlling of biped robot walking, keeping the robot stable all the time is difficult. To solve this problem, one way is build an accurate dynamic biped robot model and the other way is to build a simple model and then control it using the adaptable control, intelligent control algorithms. Jha et al. (2005) solved the problem of gait of going upstairs by two Fuzzy Logic Controller (FLC). One is used for computing the angle of joints during the double feet supporting period and the other is used for define the proper variation of angle of joints during the single supporting period. But nobody consider the balance of left and right during the moving of robot. Choil et al. (2006) proposed a method of controlling the pose of robot using fuzzy algorithm and getting the ZMP trajectory of feet of robot by force sensors.
Genetic algorithm: A GA is a model of an evolution process of animal species and the parameter is basically updated by selecting individuals with higher fitness, where the fitness is determined by interactions with the environment during all lifetime of each individual. To determine these parameters, many studies have employed a Genetic Algorithm (GA). Nagasaka (2001) studied the local increment of PD control in adjusting the biped robot gaits through GA. Capi et al. (2003) developed a method based on genetic algorithm to generate a human-like motion. Humanoid robot gait was generated using two different cost functions: minimum Consumed Energy (CE) and minimum Torque Change (TC). Since, the GA generally requires longer time in the process of evolution, if the problem of evolution speed is not solved, it is only just suitable in off-line planning for humanoid robot.
Reinforcement Learning (RL): Reinforcement learning is suitable for learning the biped walking because of its characteristics. It conforms to the process of learning of human beings. The infant always learn to walk by attempting kinds of different gaits, which is the process of trial and error. RL tries to model the learning mechanism of individual animals and the parameter is basically updated for each interaction with the environment. Zhou and Hong (2006) designed a reinforcement learning approach for robots in the motion of pursuit. Nakamura et al. (2007) proposed a new RL architecture called the CPG-actor-critic model and its RL scheme based on the natural policy-gradient method, which allows a biped robot to walk stably, even on a variety of ground conditions. Mao et al. (2007) first learns the desired gait for the robot’s walking on a flat floor. Then a fuzzy advantage learning method is used to control it to walk on uneven floor.
Hybrid evolutionary algorithm: In order to incorporate the expert knowledge into the reinforcement learning, a Fuzzy RL (FRL) agent with the neural-fuzzy architecture is a naturally good choice. Zhou and Meng (2003) proposed a general fuzzy-reinforcement learning (FRL) method, which can be used as controlling the balance of biped robot. This method is based on fuzzy-neural network and different expert knowledge and experience based on information can be dissolved into the agents of FRL to initialize the action network, evaluate network or evaluate the feedback model to accelerate its learning. Neural-fuzzy networks are used to replace the neuron-like adaptive elements in the RL architecture. Therefore, the expert knowledge can be directly built into the FRL agent as a starting con6guration so as to speed up its learning. Jha et al. (2005) developed a genetic-fuzzy system for stable gait generation of a biped robot ascending the staircase. Jingdong et al. (2007) present an efficient method motion planning based on evolutionary algorithm and achieved the experiments on penalty kick and goal keep motion held in FIRA. Fan et al. (2007) introduced a training method for biped robot walking using the (fuzzy neural network) FNN. The constraint is composed of ZMP and COM (center of mass). The cost function comes from the criterion of least energy consumed (composed of the average of power, power variance and the average torque consumption). A kind of stable self-learning fuzzy neural networks control system based on genetic algorithm was proposed by Piao et al. (2008b). The system was composed of two parts: A fuzzy neural networks controller which used GA to search optimal fuzzy rules and membership function; A supervisor which used gradient learning algorithm to train the network weights. Vundavilli and Pratihar (2009) present two controlling methods in motion of moving up and down slops, one method is using GA-NN (genetic algorithm neural network) and the other is GA-FLC (genetic algorithm fuzzy logic controller). The weights of NN and rules of FLC are optimized by GA off-line and then controlling the robot in moving up and down slops using the trained NN or FLC is achieved on-line.
Other methods: Parametric excitation walking is one of methods that realize a passive dynamic like walking on the level ground. Banno et al. (2009) proposed an optimization method for the reference trajectory of parametric excitation walking. They confine the reference trajectory to the quadratic spline curve and take the parameter of spline curve as decision variables and discretize the search space and adopt a local search method usually used in combinational optimization problems. A method based on parametric control and the enhancing technique was presented (Qiubo et al., 2009). The piece-wise constant value was used to approach the optimal solution of optimal control problem and experiment of falling motion for humanoid robot was achieved. In order to obtain the inverse kinematics model, Souto et al. (2009) present as contribution the use of the extended Kalman filter as optimizer in two different situations of the leg motion: unconstrained case, for the swing leg(s) and constrained case, for the leg(s) in contact with the ground. Qiubo et al. (2009) designed a humanoid robot based on embedded vision system and motion planning for penalty kick was carried out by the method of motion control combined with selective joints control.
TASK PLANNING
Recent rapid advancement of humanoid robot research on mechanism and control has brought great improvements in ability of their executable tasks. Not only entertainment or demonstration, they are now expected to perform a variety of tasks to assist or replace humans in environments hardly accessible to humans. Zhong et al. (2008b) implemented a method in controlling the whole joints of robot, which was composed of tasks control and selective joints control. It had taken advantaged of remote control and autonomous control. One task could be divided into several subtasks and task control pattern was adopted for the simple tasks while joint control pattern was achieved for the complex tasks. Yoshida et al. (2005) provided a method of humanoid motion planning for dynamic tasks based on two-stage approach. At the first stage the kinematic and geometric motion planner generates the trajectory for both humanoid body and carried object. Then in the second stage the dynamic walking pattern generator outputs appropriate dynamically stable walking motion that allows the robot to carry the object from the trajectory given from motion planner. Ramachandran and Gupta (2009) introduced a novel reinforcement learning algorithm called Smoothed Sarsa that learns a good policy for these delivery tasks by delaying the backup reinforcement step until the uncertainty in the state estimate improves. The state space is modeled by a Dynamic Bayesian Network and updated using a Region-based Particle Filter. Muhlig et al. (2009) investigated the topic of imitation learning of motor skills. The focus lies on providing a humanoid robot with the ability to learn new bimanual tasks through the observation of object trajectories, allows the robot to learn the important elements of an observed movement task by application of probabilistic encoding with Gaussian Mixture Models, Experiments performed with the humanoid robot ASIMO show that the proposed system is suitable for transferring information from a human demonstrator to the robot.
CONCLUSION
As a hybrid system composed of variable topology multi-degree of freedom, the complex motion planning of humanoid robot is considerable complexity. The complex motion planning can be divided into global path planning, local motion planning and task planning, applications of which are introduced and discussed in the paper. Recently, researches on humanoid robot are basically focused on the global path planning and local motion planning independently. Constraints of self-motion are considered during the global path planning and the result of global path planning is just used as an input of local motion. Although, good results from experiments are achieved using this method, the planning result is not guaranteed to be optimal in theory. Therefore, evaluation system of complex motion planning for humanoid is required. Task planning may be the direction of research in the humanoid robot. however, there are lots of researches to do.
The further development of research for humanoid robot complex motion planning will raise new issues and challenges in the unstructured environment modeling, intelligent search, complex dynamic systems modeling and intelligent control and other areas of the basic theory.
ACKNOWLEDGMENT
This project is supported by National High Technology Research and Development Program of China (863 Program) with grant No. 2007AA041603.