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

1. Problem Statement

The paper addresses the challenge of locomotion planning for legged robots climbing vertical or steep surfaces using ropes. While ropes allow access to otherwise inaccessible areas, they introduce significant complexity in planning and control due to:

• Underactuation: Rope tension is unilateral (ropes can pull but not push), and gravity limits lateral motion.
• Mixed-Integer Nature: The problem requires simultaneously selecting discrete contact locations (where to land) and optimizing continuous control inputs (rope tensions, leg forces, jump timing).
• Environmental Constraints: The robot must navigate complex, uneven terrain (e.g., rock walls with overhangs, cracks, and obstacles) while adhering to physical hardware limits (actuation bounds, friction cones).

Existing methods either rely on contact-implicit relaxations (computationally heavy) or explicit parameterization (exponential complexity with contact candidates). This paper proposes a solution specifically for rope-assisted jumping robots that balances computational efficiency with dynamic feasibility.

2. Methodology

The authors propose a Bi-Level Optimization Framework that decouples the discrete decision-making (contact scheduling) from the continuous trajectory optimization.

A. Robot Platform (ALPINE)

The framework is validated on the ALPINE robot, a novel platform featuring:

• Two Ropes: Attached to fixed anchors, independently wound/unwound by hoist motors.
• Prismatic Leg: Initiates jumps by pushing the robot away from the wall.
• Landing Legs: Passive torsional springs to dissipate kinetic energy.
• Rear Propeller: Corrects tracking errors in the direction normal to the rope plane during flight.
• Model: A reduced-order 3-DOF model is used for planning, assuming ropes remain taut and mass is concentrated at the Center of Mass (CoM), eliminating holonomic constraints via generalized coordinates ($\psi, l_1, l_2$).

B. Cost Map Generation

A terrain cost map is generated from a height map (point cloud) to guide patch selection:

• Filters: Slope (first-order derivatives), Roughness (second-order derivatives), and Depth (penalizing regions deep inside the anchor vertical).
• Patch Division: The environment is divided into discrete patches. Each patch has a quality score based on a linear combination of the filters.

C. The Bi-Level Optimization Scheme

The core algorithm consists of an outer loop and an inner loop:

1. Outer Loop: Contact Scheduling (Cross-Entropy Method - CEM)

• Goal: Determine the number of jumps ($n$) and the sequence of landing patches ($\pi$).
• Approach: Uses a gradient-free, black-box Cross-Entropy Method to handle discrete integer variables.
• Process:
  • Samples candidate solutions (jump counts and patch IDs) from a categorical probability distribution.
  • Evaluates candidates based on a cost function $F(D)$.
  • Updates the probability distribution based on "elite" (best-performing) samples to converge toward optimal sequences.
• Cost Function: Combines the average terrain cost of selected patches and the outcome of the inner loop (energy consumption + convergence penalty).

2. Inner Loop: Trajectory Optimization (Nonlinear Programming)

• Goal: Compute dynamically feasible jumping trajectories and optimize the exact landing coordinates within the selected patches.
• Approach: Formulated as a Nonlinear Optimal Control Problem (OCP) transcribed into a Non-Linear Program (NLP).
• Variables:
  • States: Generalized coordinates ($\psi, l_1, l_2$) and their velocities.
  • Controls: Rope forces ($f_{rl}, f_{rr}$) and leg impulse ($f_{leg}$).
  • Decision Variables: Jump duration ($t_f$) and landing position within the patch.
• Constraints:
  • Dynamics: Reduced-order robot dynamics.
  • Collision: Ensures the robot does not intersect the wall mesh (using a signed distance function).
  • Actuation: Unilateral rope forces, leg thrust limits, and friction cone constraints.
  • Landing: Enforces landing within the selected patch and consistency with the terrain mesh.
• Objective: Minimize rope force smoothing, hoist work (energy), and the terrain cost at the landing point.

3. Key Contributions

1. Bi-Level Framework: A novel architecture combining CEM for discrete contact planning and gradient-based NLP for continuous motion planning, specifically tailored for underactuated rope-assisted systems.
2. Simultaneous Optimization: The ability to optimize landing locations within a patch and jump trajectories simultaneously, rather than fixing contacts a priori.
3. Terrain Awareness: Integration of a morphological cost map (slope, roughness, depth) to guide the robot toward safe, flat landing zones while avoiding obstacles.
4. Validation on ALPINE: Successful demonstration on a complex, underactuated robot platform with realistic dynamics and constraints.

4. Experimental Results

The framework was tested in three simulation scenarios using the ALPINE robot in Gazebo with an MPC controller:

• Use Case 1 (Hemispheric Obstacle): The robot had to navigate around a large hemispherical obstacle. The planner successfully determined that a single jump was infeasible and generated a multi-jump sequence (3 jumps) to bypass the obstacle, converging after 4 CEM iterations.
• Use Case 2 (Multi-Bulge Terrain): The robot navigated a downward path with complex obstacles. Despite gravity aiding the motion, the obstacle pattern required at least 3 jumps. The total sequence duration was 9.45s.
• Use Case 3 (Rocky Wall with MPC): A high-fidelity simulation on a textured rock wall. The planner generated a 20m trajectory requiring multiple jumps. The system used re-optimization after each landing (using the actual landing state as the new initial condition) to correct for tracking errors. The MPC controller successfully tracked the optimized trajectories, rejecting disturbances via the propeller and rope actuation.

Performance:

• The CEM solver effectively explored the search space, avoiding local minima through a regularization mechanism (minimum probability for all classes).
• Parallelization of the CEM outer loop significantly reduced execution time.
• The system successfully handled the trade-off between energy consumption and constraint satisfaction (e.g., using longer jump durations to accommodate limited rope actuation).

5. Significance and Future Work

• Significance: This work bridges the gap between discrete contact planning and continuous motion control for rope-assisted robots. It demonstrates that complex, underactuated climbing tasks can be solved autonomously by treating contact selection as a probabilistic search problem guided by dynamic feasibility.
• Limitations: The current model does not account for cable penetration into obstacles or the depletion of the pneumatic gas supply for the leg actuator.
• Future Work: The authors plan to incorporate cable-obstacle interaction models, add fitness terms for energy resource depletion, and validate the framework on physical hardware.

In conclusion, the paper presents a robust, computationally efficient planning pipeline that enables legged robots to autonomously navigate challenging vertical terrains by intelligently combining rope assistance with dynamic jumping capabilities.