Cross-entropy optimization with prioritized constraints
This preprint introduces TierCEM, a variant of the cross-entropy method that enforces an ordered sequence of constraints during elite selection, removing the need for per-constraint penalty weights. In exact and learned world-model Push-T tests, reversing the priority order switched which constraint was violated, and putting task progress first let lower-priority constraints relax so progress continued. For robot planners facing conflicting safety and task requirements, this offers a more explicit and tunable-free way to specify which rules yield first.
Can a cross-entropy method incorporate strict lexicographic constraint priorities directly into elite selection, without scalar weights, so that conflicting constraints are relaxed in the prescribed order?
When multiple constraints conflict, penalty-weighted objectives turn priorities into numerical trade-offs, so a higher-priority constraint can be sacrificed to improve lower-priority or task scores. Existing constrained sampling planners either treat constraints jointly or use feasibility-first selection without deciding which single constraint should be relaxed.
Prior work used scalarized cross-entropy with weighted constraint penalties, hierarchical scalarized CEM with hand-tuned weights, and constrained cross-entropy (CCE) which separates feasibility from task score but treats all constraints jointly. Lexicographic and hierarchical methods exist for optimization and humanoid control, but they were not directly built into CEM elite selection.
TierCEM filters sampled candidate trajectories sequentially from highest- to lowest-priority constraint using margin functions. If a filter empties the candidate set, it steps back to the last nonempty set and ranks those candidates by smallest violation of the blocking constraint, preserving all higher-priority constraints already satisfied. If all filters pass, it ranks the remaining candidates by margin of the lowest-priority constraint. The selected elites then refit the Gaussian sampling distribution through the standard CEM update, with no per-constraint weights.
In a 2D navigation task with 20 random seeds, TierCEM reached the goal in 20/20 episodes for both task-first priority orders, with zero violations of the higher-priority spatial constraint and 20/20 violations of the lower-priority constraint (34 and 32 average steps). CCE reached 0/20 goals while preserving both constraints, and soft-constraint CEM reached 20/20 but violated the higher-priority constraint in 20 of 20 episodes in one order. In exact-state Push-T across 20 seeds, TierCEM with task>obstacle>lane gave 20.63±16.17 px position error, 0.5±1.5% obstacle violations, and 64.8±34.3% lane violations; reversing to task>lane>obstacle gave 22.34±12.23 px error, 44.0±15.9% obstacle violations, and 10.3±9.8% lane violations. CCE had 21.29±18.13 px error with near-zero violations at the nominal goal but error grew to 87.80±36.79 px when the goal moved farther, while TierCEM stayed at 30.96±34.31 px. With learned DINO-WM latents over 20 episodes, TierCEM task>obstacle>lane had 57.95±11.09 px error with 10.4±17.4% obstacle and 66.4±27.3% lane violations; task>lane>obstacle had 45.32±7.63 px error with 54.3±20.9% obstacle and 3.2±7.7% lane violations. CCE under the learned model had 105.11±17.54 px error and near-zero violations, while soft-constraint CEM had 21.61±6.26 px error but no priority control.
The authors note that TierCEM depends on learned dynamics and margin models, and safety-critical deployment would require additional guarantees. Evaluation is in simulation only with exact and learned world models, no real-robot trials. The method assumes a known priority ordering and margin functions; it needs enough samples to reach nonempty candidate sets. No code release is reported. Experiments used 1200 samples and 10 CEM iterations, so real-time feasibility on embedded hardware is not established.
Robot planners and control stacks that already use CEM or MPPI—for example autonomous vehicle motion planning, industrial manipulation, and mobile robots—could adopt TierCEM to handle conflicting rules explicitly without tuning penalty weights. In research or non-safety-critical products it can be tested now; for certified autonomous driving or robotaxi deployments, 1–3 years is more realistic, contingent on real-robot validation, reliable learned constraint predictors, and safety guarantees.
The full text is not republished here because the paper's license does not allow it. Read the original on arXiv.