Critical-Path Repair of Contact Schedules for Wheeled-Legged Robots

Wheeled-legged robots, such as quadrupeds with driven wheels instead of feet, roll efficiently on flat ground and step when the ground breaks up. The hard part is deciding when each leg should lift off and step, and in what order. Current controllers choose this one leg at a time. A leg lifts only when rolling has pushed it to the edge of its reach. That choice ignores what happens to the other three wheels, which must suddenly carry the whole robot. Fixing one leg's reach problem can create a traction or motor-torque problem on another leg. Scheduling researchers know this as the shifting bottleneck: when you shorten the slowest chain of dependent tasks, a different chain becomes the slowest.

We propose to schedule lift-offs the way iterative critical-path schedulers handle task graphs. The robot's next few seconds of stance and swing phases form a small dependency graph. A fast whole-body predictive controller acts as the evaluator. It reports which constraint is binding and on which leg, whether reach, friction, or torque. A repair step moves only the lift-off event on that critical chain, choosing the move that keeps the most timing slack for the events that depend on it. The controller then re-solves and checks where the bottleneck went. Terrain previewed from an elevation map supplies deadlines, the latest moment a wheel can keep rolling before an obstacle. The two-sentence version is this: treat gait timing as a scheduling problem whose bottleneck moves, and let the continuous controller's own constraint violations, not a per-leg reach heuristic, decide which lift-off to move next.

Core Claim

The claim is that most failures and wasted energy in hybrid driving-stepping come from kinetic bottlenecks created by load transfer between legs. A per-leg kinematic signal cannot see these, even one given terrain preview. A schedule repaired by following the controller's binding constraints should cross step-and-stair terrain at higher speed and lower cost of transport, with fewer slips, than reactive or feedforward schedulers. It should do this at a per-cycle compute cost compatible with online use.

What is new is the feedback channel. Prior wheeled-legged schedulers pass information one way. Whole-Body MPC and Online Gait Sequence Generation for Wheeled-Legged Robots triggers each swing from a reactive, exteroception-blind "kinematic leg utility." Automatic Gait Pattern Selection for Legged Robots picks a gait with a classifier trained on offline mixed-integer solutions and only warm-starts the trajectory optimizer. Energy-Efficient Motion Planning for Multi-Modal Hybrid Locomotion fixes a mode sequence by graph search and then optimizes continuously, with no return path. None of them lets an infeasibility found downstream reshape the discrete schedule.

Research Program

The schedule representation borrows from Iterative Dynamic Critical Path Scheduling, which offloads task graphs without fixing start times up front. It repeatedly reassigns the critical-path node to the placement that maximizes that node's "mobility," the gap between its earliest and latest feasible start, and recomputes all dependents after each move. That paper supplies the method.

In our setting a node is a lift-off or touchdown event for one leg. The latest start of a lift-off comes from the terrain preview and the leg's reach limit: the wheel must be airborne before it hits the step face or runs out of workspace. The earliest start comes from support feasibility: the remaining wheels, under the controller's predicted motion, must stay inside their friction cones and torque limits. For event $e$, the mobility is

$$ m_e = \mathrm{LST}_e - \mathrm{EST}_e, $$

where $\mathrm{LST}_e$ is the terrain- and reach-derived deadline and $\mathrm{EST}_e$ is the earliest time the other legs can carry the load. Negative $m_e$ means the schedule is infeasible at that event. Edges in the graph encode support rules, for example that two diagonal legs may not swing together on a stair, and swing-duration bounds.

The continuous evaluator is a single-rigid-body predictive controller with wheel-rolling kinematics. It follows the formulation in the Bjelonic et al. paper above, which reports 71% better state prediction than decomposed control. That makes it a credible source of constraint information.

Each control cycle runs a bounded loop of three steps. The first step solves the predictive controller with the current schedule. It reads the slack and multipliers of the reach, friction, and torque constraints to find the binding event and the leg it belongs to. The second step applies one of three repairs to that event: shift its timing, swap its order with a neighboring leg's event, or lower the commanded speed locally to open slack. It keeps the repair that maximizes the minimum mobility among dependent events. The third step re-solves.

Two known failure modes of iterative refinement shape the design. The first is runtime. Subgraph Extraction-based Feedback-guided Iterative Scheduling for HLS closed the loop with downstream timing tools and gained 28.5% fewer registers, but paid an average 40.8x runtime. That paper constrains us. We cap the number of repairs per cycle, warm-start each solve, and carry the repaired schedule into the next cycle so the loop is anytime. The second is oscillation, where two paths trade critical status back and forth. We borrow the remedy from shifting bottleneck with tabu search: a short tabu memory forbids undoing a repair within a window. We will log oscillation rates with and without it.

Baselines

The naive reference is a hand-tuned state machine. It rolls by default and switches to a fixed trot when the previewed obstacle exceeds a height threshold. Its thresholds are tuned by grid search on the training terrains with the same tuning budget as our method's few hyperparameters (repair cap, tabu window).

The strongest existing method is the reactive leg-utility controller of Whole-Body MPC and Online Gait Sequence Generation for Wheeled-Legged Robots. That paper reports a cost of transport of about 0.1 for pure driving at 2.0 m/s, against about 1.5 for walking, and traversal of 0.20 m steps. We reimplement it on the same predictive controller, dynamics model, and simulator so that only the scheduler differs. Beating it means a higher success rate on step and stair courses taller than 0.20 m at matched commanded speed, or equal success at lower cost of transport, with per-cycle compute under the control period.

We also include a preview-augmented utility baseline that evaluates the same reach utility along the predicted trajectory. This is the most dangerous competitor (see below).

We include the energy-aware nominal-gait selector of Energy-Efficient Omnidirectional Locomotion for Wheeled Quadrupeds. It forecasts power over a 1-second horizon, picks from a gait library, and reports up to 35% energy reduction over fixed gaits. It stands for learned discrete selection, and we retrain it on our robot model with matched simulation samples.

For anytime planning we include Anytime Hybrid Driving-Stepping Locomotion Planning. It uses ARA* and reports a first feasible plan in 32 ms and convergence to within 2% of optimal in 10 seconds. It represents refinement by global heuristic inflation rather than targeted repair, and it will be compared on planning time to a feasible schedule.

Two ablations isolate the key ingredient. The first restricts the repair to see only reach constraints, which removes the kinetic feedback. The second replaces mobility-maximizing repair with random repair of the binding event.

Why not just…?

Why not just give the leg-utility heuristic terrain preview? This is the real threat. If the important bottlenecks are reach deadlines set by obstacles, a predictive utility will match us. The diagnostic is the reach-only ablation. If it performs as well as the full method, the kinetic-feedback claim is false, and the contribution shrinks to scheduling with terrain deadlines. We would report that honestly. We expect the gap to appear mainly with heavy payloads, low-friction patches, and stairs, where lifting one leg overloads a neighbor. We will stratify results by these conditions so a null result is interpretable.

Why not just sample contact schedules and keep the best, using cross-entropy search over lift-off times scored by the same controller? With enough samples this would find good schedules. The question is efficiency. We will give the sampler the same number of controller solves per cycle as our repair loop, and plot success against solves. If sampling matches us at equal solves, targeted repair offers no advantage and we will say so.

Why not just train an end-to-end policy on elevation maps? Learning Robust Autonomous Navigation and Locomotion for Wheeled-Legged Robots reached a cost of transport of 0.16 and 1.68 m/s average speed over 8.3 km. That result is strong evidence that learning works. However, the policy's schedule is implicit, its 3 m map window limits speed, and it gives no handle on hard constraints. We position our method as a model-based scheduler that could supply targets or guard constraints for such a policy, not a replacement. We will compare against a privileged-teacher policy trained in IsaacGym with matched simulation budget, while acknowledging this comparison is the least controlled.

Why not just solve the mixed-integer program? The gait selection paper reports over 5 hours offline for a 4-phase 3D quadruped schedule. We use short offline mixed-integer solves only as an optimality reference on small scenarios.

Proposed Experiments

The main testbed is IsaacGym, following the simulator used by Yang et al., with a wheeled quadruped model. The terrain courses use single steps from 0.10 to 0.30 m, stairs at 0.175 m treads matching the Bjelonic et al. tests, gaps, and mixed courses with friction patches. Payload and commanded speed vary from 0.5 to 3 m/s.

The metrics are success rate, the count of wheel-slip events (friction-cone violations measured in simulation), mechanical cost of transport, and mean traversal speed. We also report run-to-run stability as the coefficient of variation of return, the metric defined by the real-world quadruped offline-RL benchmark. Finally we report scheduler compute per cycle and oscillation frequency.

For the step and stair tasks, there is no reported result on Lacuna for success rates or slip counts of the leg-utility controller. All baselines will therefore be reimplemented and measured on the same courses.

On small two-step scenarios we compare the cost of the repaired schedule to offline mixed-integer optima to measure the optimality gap. A hardware check on a modified small wheeled quadruped is a stretch goal, limited to step-up traversal at increasing speeds.

The decisive checks are three. The full method must beat the preview-augmented utility on the payload and low-friction strata, not just on average. It must beat cross-entropy sampling at equal controller solves. The tabu memory must measurably cut oscillation without hurting success. If the first check fails, we narrow the claim to deadline-aware scheduling. If the second fails, the targeted-repair mechanism is not worth its complexity.