text: Humanoid robots dynamically navigate an environment by interacting with it via contact wrenches exerted at intermittent contact poses. Therefore, it is important to consider dynamics when planning a contact sequence. Traditional contact planning approaches assume a quasi-static balance criterion to reduce the computational challenges of selecting a contact sequence over a rough terrain. This however limits the applicability of the approach when dynamic motions are required, such as when walking down a steep slope or crossing a wide gap. Recent methods overcome this limitation with the help of efficient mixed integer convex programming solvers capable of synthesizing dynamic contact sequences. Nevertheless, its exponential-time complexity limits its applicability to short time horizon contact sequences within small environments. In this paper, we go beyond current approaches by learning a prediction of the dynamic evolution of the robot centroidal momenta, which can then be used for quickly generating dynamically robust contact sequences for robots with arms and legs using a search-based contact planner. We demonstrate the efficiency and quality of the results of the proposed approach in a set of dynamically challenging scenarios.
  @cite_30: The rapid development of the theory of robust estimation (Huber, 1973) has created a need for computational procedures to produce robust estimates. We will review a number of different computational approaches for robust linear regression but focus on one—iteratively reweighted least-squares (IRLS). The weight functions that we discuss are a part of a semi-portable subroutine library called ROSEPACK (RObust Statistical Estimation PACKage) that has been developed by the authors and Virginia Klema at the Computer Research Center of the National Bureau of Economic Research, Inc. in Cambridge, Mass. with the support of the National Science Foundation. This library (Klema, 1976) makes it relatively simple to implement an IRLS regression package.
  @cite_35: We present an algorithm for planning goal-directed footstep navigation strategies for biped robots through obstacle-filled environ- ments and uneven ground. Planning footsteps is more general than most existing navigation methods designed for wheeled robots, since the op- tions of stepping over or upon obstacles are available. Given a height map of the terrain and a discrete set of possible footstep motions, the planner uses an A* search to generate a sequence of footstep locations to reach a given goal state. The planner evaluates footstep locations for viability using a collection of heuristic metrics designed to encode the relative safety, effort required, and overall motion complexity. We show preliminary results of the planner over several simulated terrains, as well as a simplified, online version of the algorithm running on the H7 hu- manoid robot. In the latter case, a stereo vision system is used to sense obstacles in the immediate environment and identify a target goal loca- tion, which is used to update the current optimal footstep sequence to the goal from the robot's present location.
  @cite_18: This paper presents a method of computing efficient and natural-looking motions for humanoid robots walking on varied terrain. It uses a small set of high-quality motion primitives (such as a fixed gait on flat ground) that have been generated offline. But rather than restrict motion to these primitives, it uses them to derive a sampling strategy for a probabilistic, sample-based planner. Results in simulation on several different terrains demonstrate a reduction in planning time and a marked increase in motion quality.
  @cite_26: We propose a humanoid robot navigation planning framework that reuses previous experience to decrease planning time. The framework is intended for navigating complex unstructured environments using both palm and foot contacts. In a complex environment, discrete-search-based contact space planners trade-off between high branching factor and action flexibility. Although approaches such as weighted A∗, ARA∗ and ANA∗ could speed up the search by compromising on optimality, they can be very slow when the heuristic is inaccurate. In the proposed framework, an experience-retrieval module is added in parallel to ANA∗. This module collects previously-generated motion plans and clusters them based on contact pose similarity to form a motion plan library. To retrieve an appropriate plan from the library for a given environment, the framework uses a distance between the contact poses in the plan and environment surfaces. Candidate plans are then modified with local trajectory optimization until a plan fitting the query environment is found. Our experiments show that the proposed framework outperforms planning-from-scratch in success rate in unstructured environments by at least 28 and can navigate difficult environments such as rubble and narrow corridors.
  @cite_22: This paper presents improvements in contact-before-motion planning for humanoid robots that enables to find a path in very constrained environments. Starting from our previous work, the main novelties are to use a rough trajectory to drive the search and as a criterion to find new contacts and generate the best nodes first. This way only few nodes are effectively explored, speeding up the planning process. We experience the algorithm on the humanoid HRP-2 in a complex scenario.
  @cite_7: We present a novel method to solve the problem of planning footsteps for a humanoid robot according to an arbitrary set of tasks. In this method, we consider the sequence of footsteps required to solve a task as a virtual kinematic chain that augments the state of the humanoid robot. We introduce this representation to formulate the footsteps planning as an iterative constrainted optimization problem where the footsteps are accounted for as additional degrees of freedom helping the robot in achieving its tasks. We demonstrate the efficiency and the generality of the method through three task scenarios for the humanoid robot HRP-2.
  @cite_21: We present a new method for planning footstep placements for a robot walking on uneven terrain with obstacles, using a mixed-integer quadratically-constrained quadratic program (MIQCQP). Our approach is unique in that it handles obstacle avoidance, kinematic reachability, and rotation of footstep placements, which typically have required non-convex constraints, in a single mixed-integer optimization that can be efficiently solved to its global optimum. Reachability is enforced through a convex inner approximation of the reachable space for the robot's feet. Rotation of the footsteps is handled by a piecewise linear approximation of sine and cosine, designed to ensure that the approximation never overestimates the robot's reachability. Obstacle avoidance is ensured by decomposing the environment into convex regions of obstacle-free configuration space and assigning each footstep to one such safe region. We demonstrate this technique in simple 2D and 3D environments and with real environments sensed by a humanoid robot. We also discuss computational performance of the algorithm, which is currently capable of planning short sequences of a few steps in under one second or longer sequences of 10–30 footsteps in tens of seconds to minutes on common laptop computer hardware. Our implementation is available within the Drake MATLAB toolbox [1].
  @cite_1: We present a contact planner for complex legged locomotion tasks: standing up, climbing stairs using a handrail, crossing rubble, and getting out of a car. The need for such a planner was shown at the DARPA Robotics Challenge, where such behaviors could not be demonstrated (except for egress). Current planners suffer from their prohibitive algorithmic complexity because they deploy a tree of robot configurations projected in contact with the environment. We tackle this issue by introducing a reduction property: the reachability condition. This condition defines a geometric approximation of the contact manifold, which is of low dimension, presents a Cartesian topology, and can be efficiently sampled and explored. The hard contact planning problem can then be decomposed into two subproblems: first, we plan a path for the root without considering the whole-body configuration, using a sampling-based algorithm; then, we generate a discrete sequence of whole-body configurations in static equilibrium along this path, using a deterministic contact-selection algorithm. The reduction breaks the algorithm complexity encountered in previous works, resulting in the first interactive implementation of a contact planner (open source). While no contact planner has yet been proposed with theoretical completeness, we empirically show the interest of our framework: in a few seconds, with high success rates, we generate complex contact plans for various scenarios and two robots: HRP-2 and HyQ. These plans are validated in dynamic simulations or on the real HRP-2 robot.
  @cite_24: Efficient footstep planning for humanoid navigation through cluttered environments is still a challenging problem. Many obstacles create local minima in the search space, forcing heuristic planners such as A* to expand large areas. The goal of this work is to efficiently compute long, feasible footstep paths. For navigation, finding the optimal path initially is often not needed as it can be improved while walking. Thus, we propose anytime search-based planning using the anytime repairing A* (ARA*) and randomized A* (R*) planners. This allows to obtain efficient paths with provable suboptimality within short planning times. Opposed to completely randomized methods such as rapidly-exploring random trees (RRTs), these planners create paths that are goal-directed and guaranteed to be no more than a certain factor longer than the optimal solution. We thoroughly evaluated the planners in various scenarios using different heuristics. ARA* with the 2D Dijkstra heuristic yields fast and efficient solutions but its potential inadmissibility results in non-optimal paths for some scenarios. R*, on the other hand borrows ideas from RRTs, yields fast solutions, and is less dependent on a well-designed heuristic function. This allows it to avoid local minima and reduces the number of expanded states.
  @cite_0: This paper presents the contact-consistent elastic strips (CES) framework, a motion planning approach capable of producing complex multi-contact whole-body humanoid behaviors in dynamic environments. Planning multi-contact motions for humanoid robots is known to be non-trivial since it involves aspects of autonomous balancing, obstacle avoidance, ensuring global connectivity of the workspace and concurrent consideration of the kinematic and dynamic constraints. Previous works at motion planning for humanoid systems tend to focus on joint space planning and deal with obstacle avoidance and contact-point searching as the separated problems. CES framework, however, simultaneously considers all these requirements and constraints in task space while planning a valid sequence of contact-points and corresponding motions. This resulted in considerable improvements to efficiency and significantly reduced planning time. With the use of CES framework, complex multi-contact locomotion behaviors and real-time adjustments to the robot motions in 3D unstructured environments is possible. Several simulations are demonstrated to evaluate and verify the performance of CES framework.
  @cite_15: We present an algorithm for planning safe navigation strategies for biped robots moving in obstacle-cluttered environments. From a discrete set of plausible statically-stable, single-step motions, a forward dynamic programming approach is used to compute a sequence of feasible footstep locations. In contrast to existing navigation strategies for mobile robots, our method is a global method that takes into account the unique ability of legged robots such as bipedal humanoids to traverse obstacles by stepping over them. Heuristics designed to minimize the number and complexity of the step motions are used to encode cost functions used for searching a footstep transition graph. We show preliminary results of an experimental implementation of the algorithm using a model of the H6 humanoid navigating on an office floor littered with obstacles.
  @cite_12: Despite the stable walking capabilities of modern biped humanoid robots, their ability to autonomously and safely navigate obstacle-filled, unpredictable environments has so far been limited. We present an approach to autonomous humanoid walking that combines vision-based sensing with a footstep planner, allowing the robot to navigate toward a desired goal position while avoiding obstacles. An environment map including the robot, goal, and obstacle locations is built in real-time from vision. The footstep planner then computes an optimal sequence of footstep locations within a time-limited planning horizon. Footstep plans are reused and only partially recomputed as the environment changes during the walking sequence. In our experiments, combining real-time vision with plan reuse has allowed a Honda ASIMO humanoid robot to autonomously traverse dynamic environments containing unpredictably moving obstacles
summary: Footstep planning for humanoid robot has been studied extensively @cite_15 @cite_35 @cite_12 @cite_30 @cite_24 @cite_7 @cite_21 . In these works, the planner plans a footstep sequence to avoid obstacles on the ground and remain inside the specified contact regions on a flat or piecewise-flat ground. To increase the likelihood of success, they incorporate an approximation of robot balance and kinematic reachability into the contact transition model, and do not explicitly perform balance check online. There are also works addressing contact planning in unstructured environment using both palm and foot contacts @cite_22 @cite_18 @cite_1 @cite_26 @cite_0 . However, these approaches assumes quasi-static motions, and drops solutions involving dynamic motions.