Abstract
Humanoid robots posses the unique ability to cross obstacles by stepping over or upon them. However, conventional 2D methods for robot navigation fail to exploit this ability and thus design trajectories only by circumventing obstacles. Recently, global algorithms have been presented that take into account this feature of humanoids. However, due to high computational complexity, most of them are very time consuming. In this paper, we present a novel approach to footstep planning in obstacle cluttered environments that employs a human-like strategy to terrain traversal. Design methodology for obstacle stepping over motion designed for use with this algorithm is also presented. The paper puts forth simulation results of footstep planning as well as experimental results for the stepping over trajectory designed for use with hardware execution of the footstep plan.
Introduction
Giving legs to a robot instead of wheels attributes a lot more to it than just resemblance with a human being. Unlike ordinary mobile robots, humanoids have the unique ability to cross obstacles by stepping over or upon them. This ability is left unexploited if the algorithms used for ordinary mobile robot navigation among obstacles are employed for humanoids too.
Various approaches have been adopted in order to address this problem in the past. McGhee et al. [16] developed a method that divides the terrain into ‘permissible’ and ‘impermissible’ stepping positions. Keeping in view the direction in which the ultimate goal position is located, the robot selects the next foothold from amongst the permissible ones in the immediately reachable footholds while taking care of postural stability constraints. While this method targeted a general application to legged robotics, Yagi et al. [21] presented another one that deals specifically with humanoid robots. Depending upon the distance with the obstacle nearest to the robot in the direction of motion (presumably the direction in which the goal position is located) the robot adjusts the length of its steps until it reaches the obstacle. Now, if the obstacle is small in size, it is overcome by stepping over or upon it whereas if it is too tall to be overcome in this way, the robot starts sidestepping until it moves clear of the obstacle. Obviously, whether to sidestep left or right is also a pre-programmed decision. These and other such localized reactive approaches have the tendency to lead the robot into a local loop or a deadlock in which case the robot would have to be backtracked in order to follow an alternate path.
Kuffner et al. [12] argued that since such reactive algorithms failed to consider complexities occurring in the path at a later stage before opting to take it, they ended up stuck in local loops and deadlocks. In order to tackle this problem they presented a sampling based footstep planning algorithm that takes into account global positioning of obstacles in the environment. This technique has been tested on H6 [12], H7 [13], Asimo Honda [3] and HRP-2 [10] humanoid robots with some improvements. The algorithm selects a discrete set of predefined stepping locations in the robot's immediate vicinity while balancing on one leg only. Also predefined are intermediate postures that the robot assumes while moving its feet between any two of these stepping locations. Selecting a set of these possible stepping locations that lead to an equal number of descendants, a tree is spread out from the initial footstep position. Now, after pruning from the tree those branches that do not end up with a step in the destination area, a two-leveled polygon-polygon collision search is conducted in order to identify trajectories that result in collision with the obstacles in the environment. Once these are discarded too, a greedy search is conducted in order to hunt out the best among the paths generated. This strategy cannot distinguish between the paths without obstacles and with some obstacles that can be stepped over due to which the robot always needs to execute high stepping profiles resulting in larger overall energy consumption. In addition, because of generation of a large search tree of possible stepping locations, greedy search has to be applied instead of an exhaustive one. On the other hand, a human in such a situation would start by searching for an obstacle-free path directly connecting initial and goal locations. If found, it would simply be adopted. Whereas some options would be considered once an obstacle-free direct path is not found. Again, an obstacle can be dodged from the right, or dodged from the left, or is crossed by stepping over.
Our algorithm starts by checking if it is possible for the robot to go directly from the initial to the final location. If so, such a path is adopted. If not, trajectories are formed in order to dodge the hindering obstacle from the right and the left. In addition, keeping in view the dimensional constraints, obstacles are classified into three types. The smallest ones that can be stepped over: type-1. For these an additional trajectory considering stepping over is also formed. The larger ones that cannot be stepped over but the robot can pass right next to them: type-2. And the largest ones that might collide with the robot's arms (sticking out wider than its feet) if the robot passes right next to them: type-3. The robot keeps a larger distance from obstacles of type-3 as compared to those of type-2 in order to avoid collision. In this way, the algorithm starts by considering the shortest path and then expands its alternates on either side spreading out considering the obstacle type and proximity. In addition, by identifying obstacles once encountered, it avoids getting stuck into the local loops and deadlocks. It is noticeable here that branches formed from every node in the search tree can be a maximum of 3, and for several straight line segments each node leads to only one child. This reduces the branching factor making a smallest possible search tree which in turn enables us to apply the exhaustive search for seeking the best possible path. It can immediately be noticed that this search, though exhaustive, is computationally very cheap.
This paper explains our proposed method in detail. In section 2 we examine some related research. Section 3 introduces the concept of human-like footstep planning and highlights salient differences with the existing approaches. The footstep planner is explained in detail in section 4. Section 5 describes stepping over motions designed for physical execution of the footstep plan while conclusion and future work ideas are stated in section 6.
Related Research
Kuffner's algorithm for footstep planning among obstacles for biped robots [12], [14] is a global motion planning strategy based on using game theory for finding alternate paths in an obstacle cluttered environment by considering a discrete set of heuristically chosen statically stable footstep locations for a humanoid robot and identifying the better path via cost heuristic implementation using greedy search. The assumptions made by the algorithm are:
The environment floor is flat and cluttered with non-moving obstacles of known position and height, A discrete set of feasible, statically-stable footstep placement positions and associated stepping trajectories are pre-computed, Only the floor surface is currently allowed for foot placement (not obstacle surfaces).
A static stability analysis is carried out for the stepping motion of the humanoid robot as a result of which a continuous region is identified where the robot can place its lifted foot (while balanced on one leg) without losing stability. Since it is computationally extensive to check every single point in this region for a footstep placement possibility in every step, a discrete set of ‘feasible’ footstep locations is heuristically identified in this region.
Standing balanced on one foot, the robot would alternatively consider placing its foot at each of these locations and from each stepping possibility more nodes are generated in a similar manner. Foot transition from each location to the next is carried out via heuristically identified statically stable intermediate postures Q right and Q left (for standing balanced on right and left foot respectively) in order to limit the number of possible transition trajectories considered in every step. This is followed by better path identification through greedy search by employing a heuristic cost function which attempts to approximate an exhaustive search while applying a greedy one since exhaustive search itself would be very time consumptive given the large search tree of possible stepping locations that the algorithm generates [12], [14].
The algorithm was simulated on a model of H6 humanoid robot [12], [14]. Considering 15 discrete footstep placement options in each step in a room with 20 obstacles, it formed search trees of 6,700 and 830,000 nodes in [12] and [14] respectively. Best path was traced out using greedy [12] and A* [14] search strategies with total processing time of 12 s on 800 MHz Pentium-II and 4 s on 1.6 GHz Pentium-IV running Linux respectively.
The main drawback of this algorithm is high computational complexity because of generation of a large search tree of possible stepping locations which reflects in terms of time consumption. Moreover, a closer look reveals that since this algorithm is not reactive in nature, it does not distinguish between steps taken to cross over obstacles and those taken ordinarily. Since the same intermediate postures as in ordinary steps (Q right and Q left ) have to provide the robot with trajectories capable of stepping over obstacles too, they involve lifting of the foot to a high position as if stepping over obstacles in every step. This, inevitably, is quite consumptive in terms of energy and would make the stepping profiles quite unlike human walk if obstacles of reasonable height are considered. In addition, when it comes to searching for the best path amongst those traced out by the algorithm, an exhaustive search cannot be applied because of the large tree of possible stepping locations generated [12], [14]. A greedy search, however, might not hunt out the best solution under many circumstances [4]. In order to tackle some of these problems, a tiered planning strategy has been introduced that splits the planner into high, middle and low level layers in order to traverse different terrain types [2].
Since steps in game theory based footstep planning strategy are spawned without paying heed to presence or absence of obstacles in the environment, stepping over is merely a result of obstacles fortunately found lying between present and next footstep locations without causing a collision during the stepping trajectory. Our algorithm, however, being reactive in nature, designs stepping trajectories conscious of relative obstacle placement. This emphasizes the need for stepping over trajectories that are designed to be collision free given certain relative placement with respect to the obstacle. Some work has been reported on stepping over trajectories that tend to be reactive. Guan et al. [6] attempt to design statically stable trajectories based upon obstacle dimensions provided that the obstacle lies directly perpendicular to the robot since the analysis is limited to sagittal plane. However, stepping over trajectories often involve postures in which CoM of the robot is located very close to the boundary of the support polygon. Given the fact that no matter how slowly we execute the motion, there will always be some dynamic forces other than gravitation practically, trajectories designed assuring static stability only bear a direct risk of instability. Further, stabilizers used with robots like the HRP-2 [10] sometimes slightly modify the stepping trajectory due to which obstacle dimensions possible to be overcome could be altered from their original design. In order to tackle some of these issues, Verrelst et al. [19] use a preview control based dynamic pattern generator to design stepping over trajectories. The method attempts to optimize step length and waist height for the kinematical design of the motion by starting with minimum possible values and increasing piecewise. For foot trajectories also, intermediate control points are selected in order to minimize foot lift. However, after all the designing, most part of the motion has to be heuristically modified by inserting extra data points to control the swing of the foot and speed conditions at touchdown. For online usage, to compensate for the absence of manual alteration possibility, an online collision free adapter is stated to be required. Also, due to slight model inaccuracies or perturbations, the stabilizer of the robot modifies some part of the trajectory and it is not immediately clear as to how kinematic change made in such manner can be dealt with online to avoid collision with the obstacle. Further, collision checking methodology employed in the design seems to resemble that used by the sampling based footstep planner [12], [14] which tends to slow the planner down due to computational complexity. As we shall discuss in this paper, it might not be that important to have a different stepping over trajectory for every obstacle. In addition, though using dynamics to enhance stepping over trajectory is certainly a plus, it is only the motion being dynamically balanced that is a necessary requirement.
Human-Like Approach
One of the fundamental rationales behind development of humanoid robots is their suitability for navigation in human environments due to these being custom designed for biped walkers. Nevertheless, resemblance in terms of construction alone does not guarantee a superior locomotive ability in obstacle cluttered terrains unless coupled with a path planner that thinks like a human.
As humans we know that, unlike localized reactive navigation strategies, paths adopted by us to traverse obstacle cluttered terrains are planned taking into account global position of obstacles in the environment. Also, humans do not conduct navigation planning by random spreading of footstep placement possibilities throughout the terrain while ignoring the relative position of obstacles in the environment and later evaluating which of these would result in collision as is done by the game theory based approaches. Quite differently, humans start by first searching for the path directly connecting the start and destination points. If found available, this path is simply taken without considering alternate routes. On the other hand, if the direct path is found unavailable due to presence of an obstacle, paths are considered to dodge it as well as step over it with the better one of these being adopted.
This is precisely the approach we seek to adopt. In our method the planner starts by looking for presence of obstacles in the path directly connecting the initial and goal locations. If available, this path is taken without heed to alternate possibilities. If unavailable, paths are generated from the right and the left of the nearest obstacle hindering the direct passage. In addition, if the obstacle is ‘small’ enough, a path is also planned by stepping over it. If while planning these alternate steps another obstacle is found hindering an alternate path, paths from right, left and over this obstacle are also analyzed in a similar fashion. In this way the graph starts from the simplest path and moves on to the more complex ones. Being human-like, the method itself is of reactive nature; however, it takes into account global positioning of obstacles in the environment.
Comparison with Visibility Graph
At a casual glance the algorithm might seem to resemble the well known Visibility Graph approach [15] for mobile robot motion planning. However, apart from one obvious difference of planning paths by stepping over obstacles, more fundamental differences of approach reveal themselves upon a keener analysis.
A visibility graph comprises the initial and goal locations and the vertices of all obstacles as nodes in the graph. Contrary to this, our algorithm may not, and in most cases, does not include the vertices of all the obstacles present in the environment into the graph. This is because planning to overcome obstacles not hindering the path of the robot in order to reach the destination intended is unlike the human approach. As explained in the previous subsection, our algorithm expands the graph from simpler to more complex paths. The graph complexity is increased only whenever an obstacle in the environment is found hindering the robot's path towards the destination. Of course, while planning a path to overcome such an obstacle, if another obstacle comes in the way, paths are generated to overcome it as well in a similar fashion and only in such case do its vertices become a part of the graph. In this way, obstacles in the environment not hindering the robot's way are not taken into consideration while expanding the graph.
Another salient difference comes to light when considering graph generation with the same obstacles for two different initial and goal locations. In case of visibility graph approach, the part of the graph formed by linking the obstacle vertices will remain the same in both cases. The only difference would be nodes representing initial and goal positions connected to every node directly connectable to them. However, in case of human-like path planning, nearly the entire graph might change. One reason being that since our intension is to dodge obstacles from right and left, the nodes marking the edges of the near side (and likewise the far side) of an obstacle are not generally interconnected in the graph since this does not represent a meaningful path while moving in this direction. So if the line of motion in case of one set of initial and goal locations is perpendicular to the other, this would result in connections previously absent from the graph even if the same obstacle is dodged in both cases. This is because the sides attributed to as near and far sides in one case (along which paths do not exist in the graph) might become right and left in the other (which would represent meaningful paths).
Thus neither the resulting graph nor the way this graph is formed is similar to the visibility graph. In addition, due to the human-like approach towards trajectory generation, the graph formation is efficient and the graph itself is much smaller, taking into account only the obstacles necessarily hindering the robot's way.
Planner Design and Simulation
Kinematics and Stability Constraints
For initial simulation work, our algorithm inherits assumptions (i) and (iii) from the sampling based method described in section 2. Also, as in assumption (ii), we also employ a static stability based criteria for stepping motions in the simulation phase. Incorporation of dynamic stability constraints for practical implementation is discussed in the next section.
Selection of footstep locations for ordinary walking is done according to the intended direction of motion. Right or left foot respectively is used to take the first step depending upon whether the destination is located to the right or left of the robot's current position. For ordinary steps a half-sitting posture is used. Maximum possible step length (1.9 cm approximately for HRP-2) is used in each step. Final step when reaching the destination is shortened to step exactly within the destination area. Backward steps are not considered while planning since stepping backwards is one of the very situations that a footstep planner is primarily meant to avoid.
Thus, kinematically reachable area in the forward direction only (highlighted in Fig. 1) is used for stepping.
Stepping region for normal half sitting posture.
As is illustrated in Fig. 1, even stretching the foot to its maximum is not sufficient enough to create space between current and next step positions. In other words, this posture for normal stepping cannot be used to step over obstacles as well. Thus for stepping over obstacles the knees of the robot are bent further and the body is lowered in order to increase the possible step-length. In this way a space of 11.9 cm is created between current and next stepping locations in which the obstacle could be located while it is stepped over (illustrated in Fig. 2). The trajectory of foot used is similar to that employed for our earlier work on Saika-3 humanoid robot [1]. The height of HRP-2's ankle joint is approximately 11 cm. Obstacles of height 10 cm and depth 11 cm are thus considered possible to be stepped over for the sake of this simulation work. It is to be borne in mind that here the dimensional constraints are determined neither while accounting for dynamic stability of the robot nor are limiting in terms of obstacle height possible to be overcome by HRP-2. Discussion on dynamic stability and some other practical issues will follow in the next section.
Creating space between current and next stepping locations by lowering the upper body.
Obstacle types
In human environments, obstacles are of a variety of shapes and sizes. Our algorithm requires identification of a box-like boundary around each obstacle such that the obstacle of arbitrary shape is entirely contained inside it. This box-like boundary must be a four cornered shape when viewed from the top but there is no restriction on it being a rectangle or a parallelogram as long as it is a four cornered shape in top view. However, stepping over is only attempted in case the width and height of the boundary that binds the obstacle satisfy the constraints described in section 4.1. Our algorithm at this stage considers the entire area inside this boundary, in which the obstacle of arbitrary shape is contained, as an obstacle. These obstacles are classified into three types:
Type-1:
Height 0.1 m Can be crossed by stepping over if depth 0.11 m.
Type-2:
0.1 m<Height < 0.46 m Cannot be crossed by stepping over and cannot collide with the robot's arms.
Type-3:
Height 0.46 m Cannot be crossed by stepping over and while dodging we have to make sure the robot's arms do not collide with it.
Collision Detection
Extending lines from the current body-corners of the robot to the to-be body-corner locations at the goal position, a gallery is formed. Using two of these boundary-lines and more drawn between corresponding current and destined points, we form a mesh. If any of these line segments is found intersecting a side of an obstacle (marked by a line between two of its neighbouring corners), we say that a collision has been detected. Then, based upon distance from intersection point and angles made from the current position, near and far sides and left and right corners of the obstacle are identified respectively.
The collision detection strategy can be understood more easily using Fig. 4. Using the angle of the intended line of motion, an imaginary set of initial footstep locations is generated at the current position which indicates the initial position of the robot after it will orientate itself towards the destination. In this direction of motion, another set of imaginary footstep locations is generated at the destination point, which marks the locations at which the robot will place its feet upon reaching the destination. Joining the outer boundaries of these initial and final imaginary footstep locations, a gallery is formed. Inside this gallery, a mesh of equidistant line segments joining corresponding points at the initial and final locations is generated. Each of these lines is checked for intersection with each of the walls of all obstacles in the environment (which are also marked by line segments when looked at from the top). If an intersection is found, a collision is said to have been detected and the robot seeks to form trajectories in order to overcome this obstacle in the path. This type of collision detection is performed not only between the starting point and the ultimate destination, but between every two points which mark the initial and final locations of every intermediate path the robot considers traversing.
Mesh of lines drawn for collision checking
From Fig. 4 it can also be seen that a part of the mesh of lines extends beyond the outer boundary of the footholds (drawn in blue). These are drawn by joining the outer ends of the arms of the robot (which stick out wider than its feet) at initial and goal locations. Only if an obstacle of type-3 is found to be colliding with a line in this outer part of the mesh (between the feet and the arms), a collision is said to have been detected.
For the results presented in this paper, we form the collision checking mesh with 31 lines with a distance of less than 2 cm between every two neighbouring line segments.
To dodge an obstacle from a side we choose pivot points near the obstacle corners as shown in Fig. 5.
Choosing pivots to dodge an obstacle from right
The distance ‘d’ along the extended side is chosen such that no part of the robot's body collides with the obstacle as the robot stands in double support phase with its body centre at the pivot point. For instance in case of type-1 and type-2 obstacles, this distance is equal to half the length of the diagonal of the rectangular support polygon formed when the robot stands in the double support state. This is because the outer most edges of the feet are the points closest to the obstacle with which there might be a chance of collision. ‘d’ can thus be different for each obstacle type but not for obstacles of one group. It is obviously greater for obstacles of type-3 since there is a possibility of collision with the robot's upper body.
To step over an obstacle, the robot balances itself on both legs one step short of the closest step-location near the obstacle. Next, based on rightward or leftward tilt of the obstacle with respect to the robot's line of motion, it places forward left or right foot respectively and balances itself on it. The robot then takes a step forward with its non-supporting leg, making sure that the extended foot lands with its back-side parallel to the obstacle's away-side. Fig. 6 displays possible trajectories generated to overcome an obstacle of type-1.
Overcoming an obstacle of type-1
Each obstacle in the surroundings is allotted an identification number. The planner keeps a history of the obstacles it has overcome in a path as it plans footsteps. Whenever an obstacle occurs twice, it indicates a local loop or deadlock since attempting to overcome it again is bound to bring the planner back to the same position again and again. Such a trajectory is immediately abandoned and pruned from the search tree.
One such situation where the robot encounters a local loop and deadlocks while trying to dodge the obstacle labelled ‘1’ from both right and left sides is shown in Fig. 7. For instance, when trying to dodge the obstacle labelled ‘1’ in Fig. 7 from the right, the robot chooses pivot points to pass from its right side as elaborated upon in section 4.4. However, this path is obstructed by another obstacle on the robot's right. To dodge this newly encountered obstacle, once again the robot forms trajectories from its right and left. The one attempted to pass from left finds the obstacle labelled ‘1’ in the way again. Since this obstacle is present in the history as one that has already been attempted to be dodged, the trajectory for dodging the newly encountered obstacle from the left is discarded as a situation where a deadlock is encountered. The trajectory formed to dodge it from the right, however, finds another obstacle (indicated as a type-3 obstacle in Fig. 7). Attempting to dodge this type-3 obstacle from the left results in a deadlock just as in the previous case whereas the one attempted from its right encounters yet another obstacle. This process is repeated twice more until, in an effort to dodge from the right the obstacle to the left of the obstacle labelled ‘1', the obstacle labelled ‘1’ is encountered again. This trajectory, therefore, is also abandoned and a local loop is said to have been encountered.
Avoiding local loops and deadlocks while crossing obstacle ‘1’ of type-1
A similar situation occurs while trying to dodge the obstacle labelled ‘1’ in Fig. 7 from its left side. Thus the only trajectory possible to overcome this obstacle which is free of local loops and deadlocks is the one formed by stepping over. As we can see, the planner only plans the successful trajectory, avoiding getting stuck in local loops and deadlocks.
A heuristic cost based on the order of complexity of each stepping motion is given at Table 1. These costs are assigned to foot placements as they are planned. The total cost of a path is the sum of costs of the footsteps that it contains.
Heuristic costs assigned to different step types
Heuristic costs assigned to different step types
If, in order to proceed towards a pivot point while dodging an obstacle from its side, another obstacle is encountered along the way, alternate paths based upon the obstacle type are formed. All these alternate paths converge at the same pivot point, meaning that they will all have similar descendants. Thus, the number of these intermediate alternate paths is multiplied by the number of descendent paths and added to the total number of possible alternate paths. Thus, evaluating the cost of each intermediate path and keeping only the best during alternate path generation reduces the number of paths to only useful ones.
Search for Best Path
Due to the significantly simpler graph produced containing only the meaningful paths, we are able to apply a depth first exhaustive search for identifying the best path instead of the greedy or A* approximations. As simulation results demonstrate, despite the application of the exhaustive search, the algorithm works very significantly faster as compared to other approaches reviewed in section 2.
Simulation Results
Figs. 8 and 9 show results of a simulation of HRP-2 planning footsteps in a room with 20 obstacles. We see that a graph of only 485 nodes is formed consisting of 12 paths all reaching the destination. The whole process takes only 509 ms using a mesh of 31 lines (for collision detection) on a 2.4 GHz Pentium DUO (2 GB RAM) running Windows Vista. A comparison with previous techniques reviewed in section 2 shows reduction in the number of nodes as well as in processing time even though the algorithm employs exhaustive search for hunting out best path which guarantees optimality of the chosen path among those traced out by the algorithm.
Various paths for reaching the destination
Best path determined using depth first exhaustive search
Some more simulation results are given in Figs. 10 and 11. We see that the fastest result is obtained in Fig. 10. This corresponds to the lowest number of nodes as well as paths in the graph which also reduces the time taken in search for best path. Fig. 11 shows the trajectories formed around the obstacle of type-3 (drawn with red). It is readily observed that the robot keeps a greater distance with this obstacle than with obstacles of other types.
Result 2: Nodes formed 336, paths 11, time taken 444 ms
Result 3: Nodes formed 372, paths 14, time taken 551 ms
The Problem
Locomotion in obstacle cluttered environments can be understood as a series of two main types of motions. One being pattern generation for point to point movement (walking and turning) while the other is stepping over obstacles. Linking these two types of motions into appropriate sequences keeping in view obstacle proximity is the task of a footstep planner. Successful practical executability of this motion plan is subject to availability of successful physical trajectories corresponding to both these types of motions planned.
Much work in the past has been concentrated on the pattern generation part and several approaches for producing dynamic locomotive sequences can be found in humanoid robotics literature [7]–[9] which, with simple addition of some motion sequences, can be employed for point to point movement in reactive footstep planning as well. It is the later, i.e. stepping over obstacles, that presents a greater challenge from the point of view of dynamically stable motion generation.
Few works in this line can also be cited. Guan et al. [6] attempt to produce optimized stepping over trajectories for obstacles of various dimensions but employ only a static stability criterion. Real life motions, however, always have dynamics involved no matter how slow they may be. Thus, when practically executing the trajectory, the obstacle size has to be significantly reduced heuristically from the theoretically expected dimensions. To overcome this problem and also to possibly lengthen the robot's stride while stepping over, Verrelst et al. [19] design dynamic stepping over trajectories using preview control based pattern generation with additional ingredients for suitable waist and leg motion design. Dynamics do help elongate the stride while stepping over. However, despite extensive collision checking and dynamic planning, on account of model inaccuracies, perturbations and changes in the motion induced by the stabilizer of the robot, a major part of the trajectory still requires manual modification by addition of extra data points to achieve desired leg swing and speed profile. This raises questions about suitability of online application of such stepping over motions where manual modifications to the motion would not be possible.
Stepping Over Motion Design Strategy
As has been demonstrated in the previous section, it can be sufficient to use only a few trajectories for stepping over rather than employing a different one for each obstacle. From a footstep planner's point of view, using a large number of trajectories is not necessarily helpful in terms of computational complexity and time efficiency. In compatibility, our strategy here is to design only a few trajectories but making sure that these are dynamically stable originally. For practical concerns, we incorporate changes made to the trajectory by the stabilizer during physical application into the obstacle size possible to be overcome using it. At this stage, dynamics are not used to enhance the stride of the robot; however, treating dynamic stability as an essential practical constraint, a ZMP based stability criterion is employed while designing the trajectory.
Keeping in view compatibility with our algorithm for footstep planning, we need a stepping over trajectory which would be employed for all obstacles fitting within allowable obstacle dimensions. Practical constraints suggest that the trajectory has to be dynamically stable (even if dynamics are not used to enhance the step size). To assist in development of such trajectories we design a Stepping Over Toolbox that is capable of generating certain motions automatically:
WeightShift: Generates trajectory for weight shifting from one foot to another and places CoM at desired location at the destination foot. MoveLeg: Moves the leg while keeping the foot orientation unaltered. MoveJointsWhole: Used for simultaneous motion of various joints with mutually aligned velocity profiles. BodyHeight: Used to raise/lower the upper body.
The complete design methodology is illustrated in Fig. 12. The user can input an intuitive sequence of motions using the features exported by the Stepping Over Toolbox described above. Function call for each segment of motion in this intuitive trajectory also includes maximum velocity permissible for that segment. The toolbox uses maximum value of velocity to design the central one third of each motion preceded by increasing and followed by decreasing velocity segments. Dynamics of the motion are evaluated in every iteration and ZMP is determined using the dynamics computed in preceding two iterations. In every iteration, thus, the dynamic balance and kinematical/dynamic limitations on movement of joints are checked and error is generated if either is found not satisfying respective bounds. The user can then modify the input intuitive trajectory segments’ maximum velocity or the trajectory itself in order to remedy the error. The trajectory can be viewed and analyzed using Impact Motion Generation software developed at our laboratory [18].
Design strategy for the stepping over motion
A graphical analysis is carried out to identify the area untouched by the lower limbs of the robot while executing the trajectory which helps determine the maximum obstacle dimensions scalable using the designed motion. Usually this analysis requires identification of lower limb postures with inward-most tilt in the state when the feet are placed on either side of the obstacle while stepping over. Within this space a box-shaped area is identified which represents the obstacle of maximum dimensions capable of being stepped over. Similarly we identify the distance of this obstacle from the robot's rear foot which represents the required initial proximity of the robot for successfully stepping over an obstacle satisfying the dimensional constraints.
During physical execution of the trajectory, several plugins affect the motion of the robot simultaneously. These also include the stabilizer of the robot. To examine the trajectory in these conditions, it is simulated using the Auditor software accompanying the HRP-2 humanoid robot with the stabilizer and other plugins in operation followed by hardware execution. As discussed earlier, stepping over trajectories usually involve postures with CoM located close to the boundary of the support polygon. Consequently, at times the trajectory is slightly modified by the stabilizer of the robot. These modifications as well as the effect of vibrations result in slight alteration of maximum obstacle size scalable by using the designed trajectory. This is measured during hardware execution by using an obstacle made of polystyrene of the size originally determined through the graphical analysis and checking for even slight physical contact. Size of the obstacle is gradually reduced until the robot is able to overcome it without any contact during physical execution. This incorporates the reduction in obstacle size due to the effect of the stabilizer as well as the vibrations produced. In future the effect of the stabilizer could be attempted to be catered for during the Auditor simulation phase.
The stepping over trajectory generated is shown in Fig. 13. The intuitive design of the trajectory is simple. While stepping over, the body is lowered from the normal half sitting posture in order to elongate the step size. Foot trajectory during lift and extension is along straight lines. Forward and backward extension of arms is used in order to assist in increasing the stability margin in the sagittal plane especially for postures in which a leg is extended forwards or backwards in single support state.
The stepping over motion. Obstacle depth: 5cm, height: 13 cm, initial distance from obstacle: 13 mm
With body height of 57 cm, obstacles of height 15 cm and depth 5 cm were deemed possible to be overcome using the originally designed trajectory. However, in practical execution, due to modification induced by the stabilizer of the robot, the obstacle height is reduced to 13 cm. The initial distance between the obstacle and the robot is 13 mm.
In practical footstep planning it is the robot that has to walk up to the obstacle in order to step over it which might result in certain errors of position and orientation in obstacle proximity with respect to the robot. To emulate such a scenario we also conducted experiments in which the robot walked 1 m towards the obstacle and executed stepping over successfully. The walking trajectory generated using online pattern generator resulted in an overshoot of 1.9 cm which had to be incorporated approximately for the experiment.
Our algorithm successfully demonstrates a novel global reactive footstep planning strategy with a human-like approach. Incremental graph expansion from simpler to more complex paths ensures formation of a simpler and more useful graph as compared to that formed by approaches such as the visibility graph. The trajectory generated is more energy-efficient since the robot does not have to lift its foot to a high location in every step as in case of sampling based approaches. The algorithm is considerably fast and reduces computational complexity by minimizing the number of alternate steps considered after planning each step. However, basing the cost of each step on energy or time optimization criteria instead of just the complexity level of the stepping motion can further improve the performance of the algorithm. In compatibility with the algorithm we have designed a trajectory for stepping over obstacles. The motion is dynamically stable and also incorporates alterations introduced by the stabilizer during physical execution to determine the permissible obstacle dimensions for stepping over. Future work avenues include hardware implementation of the complete footstep planner.