Bi-Level Optimization for Contact and Motion Planning in Rope-Assisted Legged Robots

The gist: This work presents a planning pipeline framework for locomotion in rope-assisted robots climbing vertical surfaces by formulating it as a bi-level optimization scheme that addresses selecting feasible terrain regions while optimizing control inputs and landing location <ref:2604.26910#pg2>.

How it works

The proposed framework is formulated as a bi-level optimization scheme that addresses a mixed-integer problem, which involves selecting feasible terrain regions for landing while simultaneously optimizing the control inputs, namely rope tensions and leg forces, and landing location <ref:2604.26910#pg2>. The outer level of the optimization is solved using the Cross-Entropy Method, while the inner level relies on gradient-based nonlinear optimization to compute dynamically feasible motions <ref:2604.26910#pg2>.

The problem of simultaneous contact and motion planning is formulated as a bi-level nested optimization, involving both discrete and continuous decision variables <ref:2604.26910#pg2>. The outer loop consists of a black-box optimizer that handles contact scheduling (number of jumps) and patch selection by dividing the environment into discrete patches <ref:2604.26910#pg2>. The inner loop consists of a gradient-based optimization that attempts to provide a feasible jumping trajectory and contact placements within the selected patches <ref:2604.26910#pg2>.

Bi-level Optimization Scheme

The bi-level optimization problem solved at each iteration has the following form: min D F(D) = f(D0), f(D1),..., f(DI−1) s.t. ni ≥ 1, ∀ i ∈ I, πi ∈ ΠID, ∀ i ∈ I <ref:2604.26910#pg4>. The objective is to minimize the cost function F(D) by selecting the optimal number of jumps and a set of patch IDs from the catalog ΠID <ref:2604.26910#pg4>. The cost f(Di) is formed by summing two terms: f1(Di) = wac X j∈πi c¯t,j. (8)

The first term is the sum of the average terrain costs c¯t,j associated with the selected patch j <ref:2604.26910#pg4>. This enables us to rule out bad rock features like cracks, asperities, holes, etc., favoring locally flat surfaces <ref:2604.26910#pg4>. The second term results from the resolution of multiple non-linear Optimal Control Problem (OCP) parameterized with the set of integer variables Di selected by the outer optimization <ref:2604.26910#pg4>. In particular, f2(Di) is composed of the cumulative consumed energy ce (with weights we) to jump between the selected patches <ref:2604.26910#pg4>.

Inner Loop Optimization Details

The inner loop performs nonlinear trajectory optimization to compute a set of trajectories corresponding to the number of jumps selected by the outer optimization, while respecting under-actuation, hardware, and rope constraints, and simultaneously determining the optimal placement of landing contacts within the selected patches <ref:2604.26910#pg6>. The robot’s motion planning is formulated as a nonlinear OCP transcribed into a finite-dimensional Non Linear Program (NLP) where the rope forces are discretized along the horizon in N knots equally spaced by dt = tf /N time intervals <ref:2604.26910#pg6>.

The state variables are defined as xk = ψk l1,k l2,k ψ˙ k ˙l1,k ˙l2,kT ∈ R (6) and the dynamics are expressed in input-affine form x˙ k = f(xk) + g(xk)uk <ref:2604.26910#pg6>. The control inputs include both the rope forces and the leg impulse uk = frl,k, frr,k,fleg,k ∈ R 5 <ref:2604.26910#pg6>. The objective function J is defined as a sum of three terms: J = ws X i∈(r,l) "NX−1 k=0 (fri,k − fri,k−1) 2 + whw NX−1 k=0 fri,k˙li,kTs + wlcl(p(xN)) <ref:2604.26910#pg7>.

Outer Loop Optimization Details

The outer loop of our bi-level optimization framework adopts the CEM due to its ability to handle integer variables and arbitrary, non-differentiable cost functions, and to converge toward a probability distribution whose mass is concentrated in regions of near-optimal solutions <ref:2604.26910#pg8>. At every iteration, it generates a sample of population members, i.e., number of jumps and patch IDs, (Alg. 1.4) and evaluates their cost (Alg. 1.5) <ref:2604.26910#pg8>. Given a percentage of the best performing candidates, the probability of each category r is updated as the arithmetic mean of the times it was selected by the elites <ref:2604.26910#pg8>.

Validation and Results

The efficacy of the proposed planning strategy is tested on multiple terrains and in dynamic simulations involving the ALPINE robot, presented in [4] <ref:2604.26910#pg2>. The experiments were run on a Notebook computer equipped with a 20-core Intel Core 7 CPU that can reach up to 4.9 GHz clock time. Use Case 3 involves simulating the robot with a Model Predictive Control (MPC) controller in a high-fidelity Gazebo environment to track the optimized multi-jump sequence. The simulation computes the full constrained robot dynamics using the ODE physics engine [17]. The resulting behaviors are provided in the supplementary video.

Conclusion

We presented a motion and contact planner based on bilevel optimization to navigate complex terrain environments, such as mountainous regions. The outer optimization layer relies on the CEM, while the inner loop formulates an OCP to autonomously compute contact schedules, contact locations, and motion trajectories from a given terrain representation. The planner is coupled with an MPC-based controller and validated in simulation using the ALPINE robot. Although demonstrated on this specific platform, the framework readily generalizes to other robotic systems by adapting the dynamic model used in the inner-loop optimization. The current limitations of the framework include the treatment of cables, whose potential penetration into obstacles is not yet considered, as well as the absence of a fitness term accounting for the depletion level of the gas bottle supplying the pneumatic piston that actuates the leg. The authors plan to consider these aspects in future works, together with experiments performed on the real hardware.

--- Page 1 ---

Bi-Level Optimization for Contact and Motion Planning in Rope-Assisted Legged Robots Ruben Malacarne, Ioannis Tsikelis, Enrico Mingo Hoffman, and Michele Focchi <ref:2604.26910#pg2> Abstract— This paper presents a planning pipeline framework for locomotion in rope-assisted robots climbing vertical surfaces <ref:2604.26910#pg2>. The proposed framework is formulated as a bi-level optimization scheme that addresses a mixed-integer problem: selecting feasible terrain regions for landing while simultaneously optimizing the control inputs, namely rope tensions and leg forces, and landing location <ref:2604.26910#pg2>. The outer level of the optimization is solved using the Cross-Entropy Method, while the inner level relies on gradient-based nonlinear optimization to compute dynamically feasible motions <ref:2604.26910#pg2>. The approach is validated on a novel climbing robot platform, ALPINE, across a variety of challenging terrain configurations <ref:2604.26910#pg2>.

I. INTRODUCTION AND RELATED WORKS Robotic systems operating in mountainous environments face several challenges arising from the harshness of these settings, including severe climatic conditions and highly variable morphology [1, 2] <ref:2604.26910#pg2>. Climbing robots, in particular, have been employed to navigate uneven terrain, with some systems adopting alternative locomotion strategies, such as ropes, to ascend extremely steep or vertical surfaces [3, 4, 5] <ref:2604.26910#pg2>.

1. Bold Header: Enhanced Locomotion Planning for Underactuated Systems

This improvement allows AI systems to plan sequences of jumping motions for climbing robots assisted by ropes, explicitly accounting for both the physical limitations of the hardware and constraints imposed by the environment. This capability enables robots to execute complex maneuvers on vertical surfaces where underactuation is a primary challenge.

2. Bold Header: Bi-level Optimization for Simultaneous Contact and Motion Planning

The system can solve the problem of simultaneous contact and motion planning as a bi-level nested optimization, in both discrete and continuous decision variables. This allows the outer loop to handle contact scheduling (number of jumps) and patch selection while the inner loop computes a feasible jumping trajectory and contact placements within the selected patches.

3. Bold Header: Efficient Discrete Search via Cross-Entropy Method

The AI can utilize a gradientfree Cross Entropy Method (CEM) method to handle integer variables, such as patch selection and the number of jumps. This provides a computationally efficient way to explore discrete decisions by modeling the optimal solution as a parameterized probability distribution, allowing it to select the minimal sequence of intermediate jumps and landing patches based on cost.

4. Bold Header: Terrain-Aware Cost Mapping for Robust Landing Selection

The system incorporates a comprehensive cost map derived from an acquired terrain height map using filters like the slope filter (wsl) and roughness filter (wsd). This ensures that the inner loop optimization determines the optimal placement of landing contacts within the selected patches by minimizing a function that includes both terrain cost and energy consumption.

5. Bold Header: Real-Time Trajectory Optimization via Nonlinear OCP

The system can solve the inner loop using a nonlinear Optimal Control Problem (OCP) transcribed into a finite-dimensional Non Linear Program (NLP). This enables the computation of physically consistent motions by optimizing states and controls, such as rope forces and leg impulse, subject to dynamic constraints like those in Equation (10d).

6. Bold Header: Dynamic Constraint Handling for Collision Avoidance

The motion planning incorporates state constraints to prevent collision with the wall mesh for the whole jump duration. Furthermore, it encourages clearance by adding a constraint like n T c p(xN/2) ≥ h, ensuring the robot maintains a safe distance from obstacles during flight.

7. Bold Header: Adaptive Control Integration via Model Predictive Control (MPC)

The final system can be coupled with an MPC-based controller that tracks the optimized multi-jump sequence in a high-fidelity simulation. This allows for dynamic adjustments, as the controller re-optimizes each jump after landing, providing the initial leg impulse, the pattern of the rope forces, and the jump duration for each jump.

This paper presents a planning pipeline framework for locomotion in rope-assisted robots climbing vertical surfaces. The proposed framework is formulated as a bi-level optimization scheme that addresses a mixed-integer problem: selecting feasible terrain regions for landing while simultaneously optimizing the control inputs, namely rope tensions and leg forces, and landing location. The outer level of the optimization is solved using the Cross-Entropy Method, while the inner level relies on gradient-based nonlinear optimization to compute dynamically feasible motions. The approach is validated on a novel climbing robot platform, ALPINE, across a variety of challenging terrain configurations.