A receding-horizon multi-contact motion planner for legged robots in challenging environments

AI summary

Overview

Research area: Robotics — multi-contact motion planning for legged robots (contact-before-motion planning, whole-body trajectory generation, constrained optimisation).

Technical level: Advanced. The paper relies on dual quaternion algebra, vector-field inequalities, quadratic programming, and Bayesian statistical comparison against a baseline planner.

Scope: The paper introduces and statistically evaluates a receding-horizon, multi-contact motion planner (RHCP) with a vector-field-inequality posture generator, demonstrated on the Corin hexapod in scenarios such as chimney climbing, narrow passages, and gap crossing.

What This Paper Is About

Legged robots that must perform acyclic motions — such as climbing a chimney, squeezing through a very narrow passage, or crossing a large gap — cannot rely on a fixed walking gait; they must explicitly decide where and in what order to place and remove each contact. Existing multi-contact planners are usually global: they compute one complete plan from start to goal before moving, which is slow to recompute and cannot easily react to new sensor information, and some of them assume that safe whole-body trajectories between stances exist without verifying it. This paper builds a receding-horizon (local, replan-as-you-go) multi-contact planner that keeps the generality and safety guarantees of global contact-before-motion methods while planning stances, transition configurations, and whole-body trajectories simultaneously.

Key Contributions

1. A receding-horizon tree-search planning framework that rapidly re-plans in response to new information, rather than repeating a costly global planning operation.
2. A quadratic-program-based posture generator using vector-field inequalities that generates the stance, transition configuration, and whole-body trajectory simultaneously — removing the need for post-processing or multi-stage pipelines — and that is more resistant to local minima in the potential field than other potential-field-based approaches.
3. A guarantee that kinematically feasible whole-body trajectories between stances exist before those stances are added to the search tree, verifying assumptions made in prior work (references [7] and [8]).
4. A rigorous Bayesian statistical comparison against the state of the art (CVBFP [7]) across multiple simulation scenarios, quantifying trade-offs between planning speed and motion quality, and demonstrating the framework on the Corin hexapod, including scenarios where some or all contacts are on vertical surfaces.
5. The work extends a previous TAROS 2025 paper (reference [5]) that covered only the posture generator; this paper presents the complete framework (search process plus posture generator) and new experiments and data analysis.

Main Findings

• Short horizons are faster than the state of the art in every scenario tested: With short planning horizons (e.g., one step ahead), the planner was between 45% and 98% faster on average than the state-of-the-art, depending on the scenario.
• Speed at short horizons costs motion efficiency: The same short-horizon plans required between 5% fewer and 700% more stance changes on average than the state-of-the-art.
• Longer horizons trade speed for quality: With longer planning horizons (e.g., four steps ahead), average planning times ranged from 73% faster to 400% slower than the state-of-the-art, but produced higher quality plans — between 8% more and 47% fewer stance changes than the state-of-the-art.
• One scenario behaved differently: Chimney Walking was the only scenario in which longer planning horizons did not extend the average planning times.
• Posture generator speed: The quadratic-program-based posture generator returns nodes more quickly than those of existing algorithms.
• Robustness to local minima: The method is more resistant to local minima problems than other potential-field-based approaches.
• Compounding of search effort: The maximum number of posture generator calls per cycle is given by a sum over the horizon of the number of contact patches times contact areas raised to each generation depth, so the call count grows polynomially with the number of contact patches or contact areas and exponentially with the horizon depth parameter (kappa_max).
• No completeness guarantee: Because RHCP generates only one child node per contact patch–area pair for a given parent node, it cannot guarantee completeness — some feasible motion plans may be missed because alternative contact locations between the same patch and area are not considered.
• Retreat behaviour: If no valid, non-duplicate children exist, the robot retreats to its previous state, and that root node is cached so it is not revisited; if retreat is requested from the initial state, planning is reported as failed and no route is returned.

Methodology in Plain English

The planner works in a loop rather than in one big computation.

A guide path sets direction. The user (or an autonomous routine) supplies a sequence of waypoint configurations, and a potential field is built from them that encourages the robot to move toward the goal while staying near the path. For each contact patch, the field is built from distances to the nearest guide-path line segment, a plane at the segment's end, and the remaining path distance to the final waypoint.

The tree is grown one generation at a time. The robot's current state becomes the root node. For every contact patch–contact area pair, a posture generator is asked for a child node: one contact is moved to the location on the contact area that best minimises the potential field, while all other contacts of the parent stance are kept. The posture generator uses vector-field inequalities to convert geometric constraints (collision avoidance, balance, keeping contacts) into linear constraints on the robot's joint velocities, then solves a quadratic program.

Bad nodes are pruned. A node is invalid if no feasible configuration or linking trajectory can be found — meaning the requested contact cannot be safely broken. A node is a duplicate if its stance is too similar to one already in the cycle cache or root cache, where "too similar" means every contact has a counterpart on the same patch–area pair within a user-defined distance threshold. The whole-body trajectory is checked before the node is added.

The horizon is then executed. Once the search reaches the chosen horizon depth, the node in the final generation that best minimises the potential field is identified, a backward search finds which first-generation node it descends from, and the robot executes that one step. The process repeats with the new state as the root, until the goal is reached.

Evaluation. The authors ran simulation experiments on the Corin hexapod across several challenging scenarios, including ones where some or all contacts are on vertical surfaces, and compared performance to CVBFP using Bayesian data analysis.

Why This Matters

Impact on research: The work reframes multi-contact locomotion planning as a receding-horizon problem that keeps contact-before-motion generality, and it removes a known weakness in prior contact planners — the unverified assumption that a safe whole-body trajectory exists between consecutive stances. It also gives the user a single tuning knob (the horizon depth) to trade planning time against plan quality, and provides statistically rigorous benchmarking with Bayesian methods rather than anecdotal comparisons.

Real-world applications:

• Industrial inspection and maintenance — robots climbing inside chimneys, ducts, or confined vessels where footholds are on vertical surfaces and a fixed gait is unusable.
• Search and rescue in rubble or collapsed structures — crossing gaps and navigating very narrow passages with sparse, irregular footholds.
• Construction and infrastructure surveying — traversing scaffolding, girders, or other structures where precise contact placement matters more than walking speed.
• Nuclear or hazardous-environment operations — where the robot must replan continuously as sensors reveal more of an unmapped or changing environment.

Industry relevance: Because the framework replans in one horizon cycle rather than repeating a global planning operation, it is well suited to robots operating with incomplete maps or streaming sensor data. The simultaneous planning of stance, transition configuration, and whole-body trajectory also simplifies the software stack — no post-processing stage or complex multi-stage pipeline — which lowers integration cost for commercial legged platforms.

Future Directions

• Addressing the completeness gap: Since RHCP considers only one contact location per patch–area pair per parent node, exploring whether additional candidate placements can be included without losing the speed advantage is an open question.
• Reducing the exponential growth in search effort: The maximum number of posture generator calls grows exponentially with horizon depth, so scaling to deeper horizons or more contacts remains a challenge.
• Explaining and exploiting the Chimney Walking anomaly: This was the only scenario where longer horizons did not increase average planning time, and the paper notes new experiments and analysis produced insights into planner behaviour that could be investigated further.
• Extending beyond simulation to physical hardware: The evaluation reported here uses simulation experiments with the Corin hexapod; deployment on real robots with noisy state estimation, contact sensing, and unmapped terrain is a natural next step. (The paper's detailed future work is presented in its concluding section.)

Target Audience

Researchers and graduate students in legged robotics, motion planning, and whole-body control; engineers building contact-planning or posture-generation stacks for hexapods, quadrupeds, and humanoids operating in unstructured or confined environments; and readers interested in applying vector-field inequalities and dual quaternion algebra to constrained optimisation problems in robotics. Readers without a background in constrained optimisation and geometric robot modelling will find the derivations demanding, though the algorithm overview and experimental comparison are accessible.

Authors’ abstract

We present a novel receding-horizon multi-contact motion planner for legged robots in challenging scenarios, able to plan motions such as chimney climbing, navigating very narrow passages or crossing large gaps. Our approach adds new capabilities to the state of the art, including the ability to reactively re-plan in response to new information, and planning contact locations and whole-body trajectories simultaneously, simplifying the implementation and removing the need for post-processing or complex multi-stage approaches. Our method is more resistant to local minima problems than other potential field based approaches, and our quadratic-program-based posture generator returns nodes more quickly than those of existing algorithms. Rigorous statistical analysis shows that, with short planning horizons (e.g., one step ahead), our planner is faster than the state-of-the-art across all scenarios tested (between 45% and 98% faster on average, depending on the scenario), while planning less efficient motions (requiring 5% fewer to 700% more stance changes on average). In all but one scenario (Chimney Walking), longer planning horizons (e.g., four steps ahead) extended the average planning times (between 73% faster and 400% slower than the state-of-the-art) but resulted in higher quality motion plans (between 8% more and 47% fewer stance changes than the state-of-the-art).