PaperlayerView exact revision on arXiv

Source-linked AI summary

Cross-entropy optimization with prioritized constraints

Francisco Roldan Sanchez, Pau de las Heras Molins, David Fridovich-Keil, Georgios Bakirtzis

arXiv:2610.01319v1cs.RO

TL;DR

When constraints conflict, weighted penalties can trade higher-priority requirements against lower-priority improvements. TierCEM incorporates explicit priority ordering into CEM candidate selection; across navigation and pushing settings, changing that ordering changes which constraint is relaxed.

  • Problem

    Scalarized constraint penalties make priorities depend on numerical weights, so task or lower-priority improvements can compensate for higher-priority violations.

    Source: §1 · pp. 1–2

  • Method

    TierCEM filters sampled candidates from highest- to lowest-priority constraint and ranks candidates by the blocking constraint if a tier empties the set.

    Source: §1 · p. 2, §3.1 · p. 5

  • Results

    Across 2D navigation and learned-world-model pushing, reversing the constraint ordering changes which constraint is violated under conflict.

    Source: §1 · p. 2, §6 · p. 13

  • Takeaways & Limitations

    In 2D navigation, prioritizing task progress lets TierCEM relax lower-priority constraints where CCE stalls while preserving spatial constraints.

    Source: §4.3 · p. 8

    The reported stalling mechanism depends on dynamics that admit a stationary constraint-satisfying solution.

    Source: §4.3 · p. 8

Abstract

from arXiv · show

When constraints conflict, an optimizer must determine which requirements to preserve and which to relax. On the one hand, a priority ordering specifies which requirements take precedence. On the other hand, penalty-based formulations encode their relative importance through numerical weights. Depending on these weights, a solution can improve its weighted score while violating intended priorities. We introduce TierCEM, a variant of the cross-entropy method that incorporates strict constraint priorities directly into elite selection without requiring per-constraint importance weights. TierCEM works by sequentially filtering sampled candidates, from highest- to lowest-priority constraint. If and when a constraint eliminates all remaining candidates, TierCEM returns to the last nonempty set and selects elites with the smallest violations of that blocking constraint, recursively preserving satisfaction of all higher-priority constraints. We evaluate TierCEM on 2D navigation and contact-rich pushing tasks in proprioceptive and learned world-model settings. Experiments show that reversing the constraint ordering changes which constraints are violated under conflict. Prioritizing progress toward the task objective also enables TierCEM to relax lower-priority constraints when they would otherwise prevent further progress.

1. Introduction

Weighted scalar scores can trade higher-priority constraints against lower-priority penalties, making intended precedence sensitive to weight calibration. TierCEM instead filters CEM candidates in priority order and relaxes a blocking constraint while preserving higher-priority requirements.

1. Introduction

  • Scalarized penalties can let objective gains or lower-priority improvements compensate for higher-priority violations, making constraint satisfaction sensitive to numerical weight calibration.The weights must reflect both the prescribed ordering and the scales and attainable values of competing terms.Source: §1 · pp. 1–2
  • TierCEM filters candidates from highest- to lowest-priority constraint and, when a filter empties the set, selects least-violating candidates from the preceding nonempty set.This integrates ordered relaxation into CEM elite selection without per-constraint importance weights.Source: §1 · p. 2, Figure 1 · p. 3
  • In 2D navigation and learned-model pushing, reversing the constraint order changes which constraint is violated under conflict.The pushing setting uses a frozen latent-space world model and learned decoder heads to predict constraint violations.Source: §1 · p. 2

2. Related work

Related work includes constrained sampling-based optimization, lexicographic constraint handling, and planning with learned predictive models. TierCEM brings ordered priorities into CEM's candidate retention and distribution updates.

2. Related work

  • Prior constrained CEM separates feasibility from task reward, while Liu et al. (2020) rank infeasible candidates by accumulated constraint cost; TierCEM instead uses ordered individual constraints to govern fallback.The distinction is how priorities shape fallback and the resulting distribution update, not whether an infeasibility fallback exists.Source: §2 · p. 3
  • Lexicographic optimization, hierarchical quadratic programming, and traffic-rule Rulebooks encode precedence without weighted trade-offs (Quan et al., 2025; Lee et al., 2023; Censi et al., 2019).Jia & How (2026) combine dynamic barriers with lexicographic selection for trajectories from pretrained generative robot policies.Source: §2 · p. 3
  • TierCEM applies priority ordering to the finite candidate set in each CEM update, determining which candidates are retained and how the sampling distribution changes.Source: §2 · p. 4
  • Learned-model planning already uses CEM for reward-based and safety-aware planning; TierCEM targets cases where no predicted candidate satisfies every ordered constraint.Its learned-model experiments use a frozen world model and learned constraint heads for candidate evaluation.Source: §2 · p. 4

3. Tiered cross-entropy method

TierCEM applies ordered constraint filters to candidate sets used in CEM updates. When a filter empties the set, it ranks candidates from the preceding nonempty set by the blocking constraint while retaining higher-priority feasibility.

3. Tiered cross-entropy method

  • TierCEM filters candidates through an ordered sequence of constraints to determine which samples update CEM's distribution, independent of candidate representation.Source: §3 · p. 4

3.1. Priority-relaxation cascade

  • Each constraint has a margin m_n, with positive values indicating satisfaction and nonpositive values indicating violation; the constraints are ordered by priority.The candidate set is finite, and selection follows that ordering.Source: §3.1 · p. 4
  • If the first empty tier is n*, TierCEM returns to the preceding nonempty set and ranks candidates by the blocking constraint, preserving satisfaction of all higher-priority constraints.The blocking tier is the highest-priority constraint that cannot be satisfied together with all higher-priority constraints; if all constraints can be satisfied, the final tier is used.Source: §3.1 · pp. 4–6
  • When every filter retains candidates, TierCEM ranks the final set by the lowest-priority constraint's margin; selected elites then refit the Gaussian sampling distribution.Sampling, filtering, ranking, and refitting repeat for a fixed iteration budget, and the best final-iteration elite is returned.Source: §3.1 · p. 6
  • The cascade provides candidates for ranking even when no sampled trajectory satisfies every constraint, without comparing violation magnitudes across constraints or calibrating penalty weights.Source: §3.1 · p. 6

4. Mechanism analysis under exact margins

The exact-margin studies test how TierCEM handles conflicting constraints in navigation and contact-rich pushing. Across both settings, reversing the prescribed ordering changes which constraint is relaxed.

4.1. States, dynamics, and constraints

  • The trajectory optimizer predicts states from action sequences, and each constraint margin evaluates the resulting state-action trajectory.Source: §4.1 · p. 6

4.2. Baselines

  • The baselines include shared-weight and separately weighted scalarized CEM, plus CCE, which switches from violation-based selection to task performance once enough feasible policies are found.Source: §4.2 · p. 7

4.3. Priority-controlled relaxation in 2D navigation

  • When task progress is lower priority, TierCEM can preserve both spatial constraints by stalling; prioritizing progress forces a constraint to relax.Source: §4.3 · pp. 7–8, Figure 2 · p. 8
  • TierCEM and hierarchical scalarized CEM reach the goal while preserving the higher-priority spatial constraint in all 40 episodes; TierCEM specifies priorities by filter order rather than tuned weights.Source: §4.3 · p. 8, Table 1 · p. 8

4.4. Contact-rich manipulation with exact margins

  • In Push-T, reversing the ordering reverses the violation pattern with similar task performance; obstacle priority nearly eliminates obstacle violations, while lane priority substantially reduces lane violations.Source: §4.4 · p. 9, Table 2 · p. 10
  • As the Push-T goal moves farther away with planner settings fixed, CCE’s final position error increases, while TierCEM continues by relaxing its designated lower-priority constraint.Source: §4.4 · p. 9, Table 3 · p. 10

4. Mechanism analysis under exact margins

5. Planning with learned world-model predictions

TierCEM retains its priority-ordered behavior in Push-T when task progress and constraint margins are inferred from learned visual latents. Reversing the order changes which constraint absorbs violations, while the learned-model results also expose sensitivity to model errors and penalty weights.

5. Planning with learned world-model predictions

  • Under imperfect learned models, margin-prediction errors can cause conservative behavior, while dynamics mismatch can result in constraint violations.TierCEM remains effective when constraints are jointly satisfiable.Source: §5 · p. 10
  • Learned violation-probability margins separate violating from non-violating obstacle and lane latents, while the goal-distance regressor has a 6.2 px mean absolute error.The experiment tests priority-relaxation behavior when candidate trajectories, task progress, and margins are inferred from predicted visual latents rather than exact simulator states.Source: §5 · pp. 10–11
  • With task ≻ obstacle ≻ lane, TierCEM relaxes the lane; with task ≻ lane ≻ obstacle, it crosses the obstacle while staying within the lane boundary.In both configurations, the higher-priority constraint remains better satisfied while the incompatible lower-priority constraint absorbs the violation.Source: §5 · p. 11
  • For task ≻ obstacle ≻ lane, lowering λL from 0.1 to 0.02 with λO fixed at 0.5 increases lane violations and decreases obstacle violations; TierCEM obtains lower violations of both for that priority configuration.The hierarchical scalarized CEM’s weights do not transfer across task variants: the best configuration for a non-conflictive Push-T variant differs.Source: §5 · pp. 11–12

6. Conclusion

The conclusion presents TierCEM as an explicit priority-ordered approach to resolving conflicting constraints, including when task progress is prioritized. The base configuration is recorded in Table 5, with planner and cascade parameters specified by Algorithm 1.

6. Conclusion

  • When constraints conflict, TierCEM encodes their priorities as an explicit lexicographic order and relaxes the lower-priority constraint; reversing the order changes which constraint is relaxed.Prioritizing task progress can retain task completion when constraints conflict, and the method also functions with learned constraint specifications in contact-rich trajectory optimization, subject to learned-model accuracy.Source: §6 · p. 13

A. Setup and baseline details

  • Table 5 records the base configuration, with planner and cascade parameters specified by Algorithm 1.Source: Table 5 · p. 16

B. Geometry robustness

The geometry experiments show that changing the constraint order changes which requirement is sacrificed, and the reported robustness and baseline comparisons examine this behavior across settings. Hyperparameter search identifies a configuration that reaches the goal in all evaluated seeds without high-priority violations.

B. Geometry robustness

  • Across the four geometry configurations, task_obstacle_lane sacrifices the lane while keeping the obstacle clear, whereas task_lane_obstacle sacrifices the obstacle while keeping the lane clear.Plain CEM violates at least one constraint, while task_last stalls with both geometry constraints preserved; the geometry study includes an off-diagonal disk, overlapping disks, and a narrower lane.Source: Table 6 · p. 17, Figure 5 · p. 18

C. TierCEM hyperparameter search

  • Both experiments reach the goal in all evaluated seeds with zero high-priority violations at variance 1.00, 1200 samples, 24 elites, horizon 8, 10 iterations, and commit length 4.The hyperparameter search varies one parameter at a time over seeds 0–4.Source: C. TierCEM hyperparameter search · p. 19, Table 7 · p. 19

D. Baselines grid search

  • The soft-constraint baseline clips the disk at every λ from 0.05 to 2 while violating the lane; at λ = 5, disk clipping stops but reach falls to 2/20.In the mechanism-analysis comparison, CCE stalls in a safe state, while a hierarchical scalarized CEM with a tuned 25:1 ratio protects the higher-priority tier at the illustrated seed; its ratio must be tuned per environment.Source: Table 8 · p. 20, Figure 6 · p. 21
  • Table 9 pairs each hierarchical-scalarization weight setting with both task orderings, assigning the first weight to the highest-priority constraint in each configuration.The table reports reach, high- and lower-priority violations, and average steps across 20 random seeds.Source: Table 9 · p. 20

E. TierCEM under inertial bodies

For inertial bodies, stopping distance relative to the obstacle gap determines whether the planner can stop and sacrifice the lane or instead passes through the obstacle. The pure hierarchy’s safe-state escape behavior depends on a kinematic, position-controlled body.

E. TierCEM under inertial bodies

  • A pure hierarchy may never empty a tier when a no-move action holds a safe state; this controllability assumption applies to kinematic, velocity-controlled bodies, not momentum-bearing bodies controlled by acceleration.Source: E. TierCEM under inertial bodies · p. 22
  • The kinematic baseline is a single integrator with position state and velocity commands; the inertial body instead has position and velocity state and acceleration actions.The kinematic velocity command is clamped element-wise to [−Amax, Amax].Source: E. TierCEM under inertial bodies · p. 22
  • When stopping distance E(s) is at most the gap, the inertial body can stop before the disk and arc around it, sacrificing the lane; when E(s) exceeds the gap, it cannot stop in time and goes through the obstacle.The stopping distance is E(s) = s^2/(2Amax), with Amax = 1.2; Figure 7 likewise reports lane sacrifice for the inertial body unless the gap is too narrow for the initial speed.Source: E. TierCEM under inertial bodies · p. 22, Figure 7 · p. 23, Table 10 · p. 23

F. Imperfect constraint signals

Imperfect constraint signals produce distinct failure modes: margin prediction errors cause over-conservative behavior, while dynamics mismatch creates false confidence and repeated violations. The appendix also describes the learned margin classifier and its training setup.

F. Imperfect constraint signals

  • To isolate constraint-signal quality, the study replaces the lane boundary with a squared workspace boundary in a second environment, defining six scenarios including conventional CEM, exact noise-free oracle margins, and MLP-predicted margins.Source: F. Imperfect constraint signals · p. 23
  • Margin errors cause over-conservative behavior, whereas dynamics mismatch creates false confidence and repeated violations of both constraints.The figure also shows the mismatched model planning a safe arc while execution clips the obstacle and sometimes crosses the workspace boundary.Source: Figure 8 · p. 24, F. Imperfect constraint signals · p. 24

G. MLP margin predictor details and hyperparameters

  • The deployed shared-backbone classifier has one binary output for each competing constraint, and its exact signed margins are positive in safe states.A predicted transition is labeled unsafe if the end-effector violates a constraint at any environment state during the action horizon; training uses six autoregressive DINO-WM steps.Source: G. MLP margin predictor details and… · p. 25
  • The classifier uses a 384 →256 →64 →2 architecture with LayerNorm, GELU, and dropout, producing obstacle and lane-boundary violation probabilities from frozen DINO-WM latents.It contains 115,778 trainable parameters; the DINO-WM remains frozen.Source: G. MLP margin predictor details and… · p. 25
  • The classifier is trained with unweighted binary cross-entropy and AdamW, selecting the checkpoint with the lowest validation loss.Training runs for up to 200 epochs and stops after 25 epochs without sufficient validation improvement.Source: G. MLP margin predictor details and… · p. 25

H. Task-progress MLP hyperparameters

The appendix specifies a task-progress MLP and examines a Push-T variant where obstacle and workspace constraints can both be satisfied. In that non-conflict setting, reversing their priority is not expected to change behavior.

H. Task-progress MLP hyperparameters

  • The task-progress regressor maps 384-dimensional frozen DINO-WM latents through 32- and 32-unit hidden layers to one linear output, with 13,537 trainable parameters.Hidden layers use LayerNorm, GELU, and dropout with probability 0.5.Source: H. Task-progress MLP hyperparameters · p. 28
  • The regressor is trained with AdamW to minimize mean squared error in standardized target space, using the lowest-validation-MSE checkpoint.Training stops after 20 consecutive epochs without validation improvement of at least 10^-6.Source: H. Task-progress MLP hyperparameters · p. 28

I. Behavior when constraints are jointly satisfiable

  • When obstacle and workspace constraints can both be satisfied during task success, reversing their priority is not expected to change behavior.This variant uses an expert-dataset goal and omits the task-progress margin; it probes sequential filtering outside the conflict setting.Source: §I · p. 29
  • The joint-satisfiability comparison averages 100 episodes over seeds 1–5 and uses negative terminal-latent-to-goal-latent MSE as the task reward.This criterion matches the trajectory-selection criterion used by DINO-WM and keeps the comparison focused on priority ordering.Source: §I · p. 29

I.1. Number of TierCEM iterations sweep

The iteration sweep shows a TierCEM operating point below scalarized baselines on both violation axes, with a selectable trade-off between violations and task accuracy. In the jointly satisfiable variant, reversing priorities has little effect, and an exploratory cascade includes an optional third predicate.

I.1. Number of TierCEM iterations sweep

  • Workspace-boundary violations fall monotonically from 41.0% to 20.9% as cascade iterations increase, at the expense of task accuracy.The number of cascade iterations can be selected to choose an operating point without changing the priority order.Source: §I.1 · p. 30
  • The normal and reversed priority columns are nearly identical across cascade iteration counts because the obstacle and workspace constraints do not conflict in this variant.Here TierCEM enforces both constraints rather than choosing which one to relax.Source: §I.1 · p. 30
  • At 30 TierCEM iterations, forbidden-zone violations are 9.6% and workspace-boundary violations are 20.9%, below every scalarized point on both axes at 26.7 px position error.Figure 11 presents the aggregate trade-off and ordering-plane comparison.Source: §I.1 · p. 30, Figure 11 · p. 31

I.2. Optional third tier

  • An exploratory OOD ≻ obstacle ≻ workspace-boundary cascade accepts a heterogeneous third predicate; OOD detection is disabled in the reported quantitative results.The appendix reports its effect in Table 17 but does not treat OOD detection as a contribution.Source: §I.2 · p. 31, Table 17 · p. 32
Loading 2610.01319v1…