What Makes a Good Symbol for Hybrid Discrete–Continuous Planning?

Yiyuan Pan; Changliu Liu; Jiayuan Mao

What Makes a Good Symbol for Hybrid Discrete–Continuous Planning?

Yiyuan Pan¹Changliu Liu¹Jiayuan Mao²

¹ Carnegie Mellon University² University of Pennsylvania

The physical world has continuous state and action spaces, yet planning often benefits from hybrid discrete–continuous formulations that expose combinatorial structure: contact modes such as fixed and sliding contacts, or symbolic relations such as holding and in. These symbols give a planner discrete choices to reason about.

But what makes a symbol good for planning?

To build intuition, consider a finite-horizon decision-making problem in continuous space. With deterministic dynamics, we can write it as trajectory optimization: x collects the states and actions over the horizon, and an energy E(x) gives their total cost, with infeasible trajectories assigned infinite energy. Planning means finding a feasible trajectory with the lowest energy.

One way to tackle this global search is to decompose the trajectory space into regions. A discrete symbol assignment ψ selects a region X_ψ—for example, trajectories that pass an obstacle on the left. The planner searches over these discrete choices and solves a continuous optimization problem within each region.

A good symbol makes the remaining continuous problem easy to solve.

minx ∈ X E(x)continuous search = minψ ∈ Ψsymbolic search minx ∈ X_ψ E(x)solve within a region

Continuous searchrandom restarts land in different basins

low Ehigh

A decomposition preserves the problem; a good decomposition simplifies it. If the regions cover the feasible trajectory space X, the equality above holds. But an arbitrary partition can still leave difficult optimization problems inside its regions, or create so many regions that discrete search becomes expensive. A useful symbol exposes the choices that make the remaining solve easier.

The landscape illustrates the difference. Each point represents a candidate trajectory, and its colour represents energy E(x). Without the partition, only 2 of 24 random restarts reach the lowest basin in this example. Two cuts divide the landscape into three regions; one confined descent per region finds three candidate solutions, and the best recovers the optimum.

We call this solver sufficiency. Symbols are useful relative to a solver: fixing their values should leave a subproblem that the solver can handle cheaply, while comparing the regional solutions preserves solution quality. We study this principle in piecewise-affine planning and learned neural energies, and invent symbols automatically by refining a partition when the solver reveals a failure.

Q1Solver-sufficient symbols

Which decompositions make planning easier? We characterize symbols by the continuous problems that remain once their values are fixed.

Q2Which discrete choices matter?

The symbols a task needs mark its irreducible discrete decisions, and they explain which human-defined concepts matter for planning.

Q3Interpretable and steerable

Invented symbols name behaviours, such as passing an obstacle on the left or the right. Fixing a symbol steers the robot.

What makes a symbol solver-sufficient?

The key is what remains after a discrete choice is fixed. Too many symbol assignments make discrete search expensive; too few can leave hard continuous subproblems. We seek a compact set of commitments that makes each remaining solve tractable. We formalize this in two settings: exact LP relaxations for piecewise-affine systems, and descent-faithful regions for learned neural energies.

Regions where one descent is enough

Problem. Instantiate the trajectory energy E(x) as a learned policy energy h_s(x) over action chunks x in state s, as in diffusion, flow-matching or energy-based policies.

Symbols. Linear cuts u^⊤x ≥ b; each symbol value ψ is a region of the action space.

τ-descent faithful. From any start inside a region, some path that never climbs more than τ above the lowest energy reached so far leads to within τ of the region's minimum.

What it buys. Keeping the best of one confined descent per region lands within τ of the global optimum, with no random restarts. In practice the regions coincide with behaviours, such as passing on the left or on the right, so fixing ψ steers the robot.

Pick a region, drop a descent

The robot must pass three rows of obstacles. A trained diffusion policy scores every 16-step action chunk with an energy h, and at the start one invented symbol decides the side of the first obstacle. Click a point in either region: a descent confined to that region slides downhill, and the robot executes the chunk it finds, then keeps replanning on its own.

Interactive demo (needs JavaScript). At the start state the energy of a trained diffusion policy has two symbol regions: a descent confined to region ψ = 0 finds a chunk that passes the first obstacle on the left, one in region ψ = 1 passes it on the right; the robot executes the chunk and keeps replanning until the goal line.

Energy h at t = 0

Simulation Drag to rotate

How are solver-sufficient symbols invented?

By counterexample-guided partition refinement (CPR). Starting with no symbols, each round verifies the current regions, repairs a failure without a new symbol when it can, and adds a symbol only for a failure that no repair removes. The same loop runs on MILPs, with a total-unimodularity oracle in place of the sampled landscape.

Sample graph. Random-start descents on h_s give the graph nodes; edges join consecutive steps and nearest neighbours, scored by the highest energy along them, which is the barrier a descent must climb.

Verify. Flooding the graph from its minima finds basins Φ₁, Φ₂, Φ₃. Leaving Φ₂ or Φ₃ costs more than τ: the region is not faithful.

Sparsify. New descents seeded at the flagged saddle reveal a low path between Φ₁ and Φ₂: there exists a τ-descent faithful path between them, so Φ₁ ← Φ₁ ∪ Φ₂, at no symbolic cost.

Split. The remaining barrier is real. A cut through its lowest pass, along the gradient flip, invents one symbol, ψ ∈ {0, 1}.

Q1Can solver-sufficient symbols cut computation cost?

Yes, at similar success rates. On six contact-rich manipulation tasks, three of them dexterous in-hand reorientation, symbol-guided planning runs 1.3–4.8× faster than re-solving the full MILP at every step. On five diffusion-policy tasks, two on a real robot, symbols need 1–2.4 descents to reach a near-optimal plan with 99.9% probability, where random restarts of the same policy need up to 10.3.

Shadow Hand Block, solve time per episode (sum of per-decision medians over 5 runs, one-time setup excluded)

Setting

Decisions

Full MILP

Ours

Episode 1

10

492 ms

146 ms

Episode 2

12

334 ms

192 ms

Episode 3

13

421 ms

245 ms

Dexterous in-hand cube reorientation with a Shadow Hand, three task settings. Both solvers take the same steps to the goal; each row moves one step per decision its solver returns, so playback time is proportional to solve time (one-time model setup not counted). Below, we quantify this speed-up across all tasks and baselines.

Piecewise-affine tasks

Success rate vs. speed-up over re-solving the full MILP at every step (log scale). Up and right is better.

Neural-policy tasks

Descents needed to reach a near-optimal plan (within τ) with 99.9% probability, log scale. Lower is better.

Full tables

Piecewise-affine (MILP) tasks: success rate / speed-up over re-solving the full MILP at every step (full MILP = 1.00×)
Method	MPushT	Hook	Packing	Block	Cuboid	Pen
CoCo	0.75 / 3.57×	0.63 / 3.18×	0.75 / 1.39×	0.69 / 2.70×	0.81 / 1.61×	0.75 / 1.28×
GBD-MPC	0.94 / 0.12×	0.94 / 0.06×	0.81 / 0.09×	0.94 / 0.32×	0.88 / 0.21×	0.88 / 0.06×
PDDLStream	0.88 / 0.77×	0.81 / 0.36×	0.69 / 0.42×	0.81 / 0.67×	0.81 / 0.38×	0.75 / 0.17×
PGS	0.81 / 0.08×	0.69 / 0.37×	0.75 / 0.16×	0.75 / 0.15×	0.69 / 0.13×	0.81 / 0.04×
IVNTR	0.88 / 0.15×	0.81 / 0.22×	0.75 / 0.12×	0.94 / 0.10×	0.75 / 0.10×	0.81 / 0.03×
pix2pred	0.88 / 0.03×	0.88 / 0.09×	0.94 / 0.08×	0.94 / 0.05×	0.88 / 0.04×	0.75 / 0.01×
Ours	1.00 / 4.81×	1.00 / 3.07×	0.94 / 2.77×	0.88 / 1.53×	0.94 / 1.34×	0.88 / 1.94×

Neural-policy tasks: success rate / descents needed to reach a near-optimal plan with 99.9% probability
Method	Avoiding	Pushing	Aligning	Sorting (real)	Matching (real)
DDPM	1.00 / 7.03	0.90 / 1.00	0.94 / 10.31	0.75 / 5.15	0.88 / 1.68
ACT	0.91 / 833.69	0.91 / 5.93	0.91 / 9.25	0.69 / 173.45	0.63 / 259.67
BESO	0.97 / 329.03	0.63 / 198.57	0.75 / 338.03	0.75 / 87.48	0.69 / 147.85
IBC	0.81 / 690.34	0.63 / 312.70	0.63 / 349.94	0.63 / 340.78	0.69 / 562.95
BeT	0.72 / 495.50	0.30 / 105.63	0.53 / 94.66	0.56 / 936.83	0.75 / 1325.94
DDPM + symbols	1.00 / 2.00	0.91 / 1.00	0.84 / 2.41	0.75 / 1.20	0.88 / 1.00

Q2Can solver-sufficient symbols explain human-defined concepts?

Largely. We scored 127 human-defined binary factors, from nine MILP formulations of a four-pusher Push-T task, on two axes: solver necessity, how often our symbols pin the factor down, and task necessity, how much success drops without it. Factors that our symbols always pin down matter 6.5× more to the task than those pinned down less than half the time (7.2 vs 1.1).

Push-T factors grouped by solver necessity (SN): average task necessity (TN) and share of factors. The push at a corner of the bar (z1) falls in SN [0, 0.5); the push at the bottom of the stem (z2) has SN = 1.0.

SN

TN

Share of factors

[0, 0.5)

1.1

12%

[0.5, 1)

4.1

42%

1.0

7.2

46%

A factor that the solver cannot relax away encodes a real discrete decision, so the task cannot do without it. A push at the bottom of the stem (z₂) cannot be replaced, while a push at a corner of the bar (z₁) can be taken over by its neighbouring pushes.

Q3Can solver-sufficient symbols be interpreted and steered?

Yes. Each invented symbol names a behaviour, and fixing its value selects it. In simulation, 94–100% of successful runs pass the first obstacle on the side that the symbol fixes; on a real robot, the symbol decides which block is sorted first.

Sorting, real robot: ψ = 0 puts the red block away first; ψ = 1 puts the blue block away first.

Avoiding: ψ = 0 passes the first obstacle on the left; ψ = 1 passes it on the right.

Aligning: ψ = 0 descends early and pushes the box from outside; ψ = 1 keeps height and pushes from inside.

BibTeX

@article{pan2026good,
  title   = {What Makes a Good Symbol for Hybrid Discrete--Continuous Planning?},
  author  = {Pan, Yiyuan and Liu, Changliu and Mao, Jiayuan},
  journal = {arXiv preprint arXiv:2610.23010},
  year    = {2026}
}

What Makes a Good Symbol for Hybrid Discrete–Continuous Planning?

Q1Solver-sufficient symbols

Q2Which discrete choices matter?

Q3Interpretable and steerable

What makes a symbol solver-sufficient?

Regions where one descent is enough

Commitments that leave an exact LP

Pick a region, drop a descent Reset

How are solver-sufficient symbols invented?

Q1Can solver-sufficient symbols cut computation cost?

Piecewise-affine tasks

Neural-policy tasks

Q2Can solver-sufficient symbols explain human-defined concepts?

Q3Can solver-sufficient symbols be interpreted and steered?

BibTeX

Pick a region, drop a descent