PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yiyuan Pan, Changliu Liu, Jiayuan Mao

arXiv:2610.23010v1cs.RO

TL;DR

Hybrid planning uses symbols to expose combinatorial structure, but existing symbols are often predefined or descriptive rather than chosen for computational usefulness. This paper develops solver-sufficient symbolization and a counterexample-guided invention method for PWA systems, then extends the principle to neural energy landscapes. Across simulated and real-robot tasks, the symbols reduce solving cost while preserving solution quality and provide an interpretable interface for behavior steering.

  • Problem

    Existing symbol sets are often predefined or descriptive, leaving open what makes a symbol computationally useful for hybrid planning.

    Source: §1 · p. 1

  • Method

    The paper formalizes solver-sufficient symbols for PWA systems and extends symbol invention to neural energy landscapes.

    Source: §1 · p. 2, §2.2 · p. 4

  • Results

    Across simulated and real-robot tasks, invented symbols reduce solving cost while preserving solution quality and support interpretable behavior steering.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The framework connects symbolic abstraction to computational utility and offers a basis for inventing symbols and understanding useful human-defined concepts.

    Source: §5 · p. 9

    The formulation uses linear symbol models u⊤x, which may be restrictive unless task-relevant modes are sufficiently abstracted and linearly separable in a learned feature space.

    Source: §4.3 · p. 9

Abstract

from arXiv · show

The physical world has continuous state and action spaces, yet robot planning often benefits from hybrid discrete-continuous formulations that explicitly expose combinatorial structure, such as contact modes or discrete primitive actions. Existing methods typically rely on human-defined symbol sets or symbols derived from language supervision, without asking what makes a symbol computationally useful. In this paper, we take an inference-algorithm--centric view to define usefulness: a good symbol should expose the discrete commitments that simplify solving the original planning problem. We first introduce the concept of solver-sufficient symbolization by studying finite-horizon piecewise-affine systems, for which solver sufficiency can be precisely characterized, and develop a counterexample-guided algorithm for symbol invention. We then extend this principle to invent symbols for optimization objectives parameterized by general neural networks as energy functions, showing that solver-sufficient symbols can nevertheless be induced from their continuous optimization landscapes. Experiments on simulated and real-robot tasks show that the resulting symbols reduce solving cost while preserving solution quality, while also improving interpretability and steerability. Furthermore, our theoretical and algorithmic insights help explain why certain human-defined symbols are computationally useful.

1 INTRODUCTION

The introduction asks what makes symbols computationally useful, since existing symbols are often descriptive or heuristic. It proposes judging symbols by whether they expose commitments that simplify inference-time planning.

1 INTRODUCTION

  • Existing hybrid-planning symbols often come from labels or heuristics, which may hinder rather than simplify planning.The paper contrasts these with symbols derived from the solver's needs.Source: §1 · pp. 1–2
  • The paper defines symbol usefulness from an inference-time perspective, where symbols partition decisions into conditioned subproblems for continuous optimization.A fixed symbolic assignment induces a conditioned problem.Source: §1 · p. 2
  • Solver-sufficient symbols preserve the global optimum while reducing the cost of conditioned solving.This frames symbol invention as an optimization problem rather than a purely descriptive interface.Source: §1 · p. 2
  • Useful commitments can decouple temporal and spatial dependencies, leaving each grounded solve to handle only variables relevant to the selected commitment.The paper studies this principle first in PWA systems and then in neural energy-based settings.Source: §1 · p. 2

2 SOLVER SUFFICIENCY IN PWA SYSTEMS

The section formalizes symbols as compact discrete commitments that make continuous or mixed-integer planning subproblems easier to solve. It uses affine-TU structure and counterexample-guided refinement to construct such commitments for PWA systems.

2 SOLVER SUFFICIENCY IN PWA SYSTEMS

  • PWA planning is formulated as a MILP, but fixing every mode variable leaves an LP while searching all assignments is combinatorially expensive.The proposed symbols seek a more compact commitment set that improves tractability.Source: §2 · pp. 2–3

2.1 AFFINE-TU SYMBOLIZATION IN INTEGER PROGRAMS

  • Total unimodularity makes an integer program solvable through its LP relaxation, and affine-TU decompositions use fixed variable summaries to create TU subproblems.The affine-TU dimension is the minimum number of summary rows in such a decomposition.Source: §2.1 · p. 3

2.2 RELATIVE AFFINE-TU SYMBOLIZATION IN MILP

  • Relative affine-TU extends the summary idea to mode–trajectory coupling, with certificates that account for existing mode equalities and the discrete-continuous interface.The stated assumptions include TU mode equalities and ternary coupling coefficients.Source: §2.2 · p. 3
  • Fixing ψ = Wz groups mode assignments so z can be relaxed and the residual problem solved exactly by an LP; κ bounds the irreducible discrete dimension.The section gives rank[Bd; Ed] − rank(Ed) ≤ κ(Pjoint) ≤ nd.Source: §2.2 · p. 4

2.3 COUNTEREXAMPLE-GUIDED SYMBOL INVENTION WITH CPR

  • Because finding minimum affine-TU dimension is NP-hard, CPR checks candidate certificates and refines them by promoting a variable from a minimal non-TU obstruction to a symbol.It first sparsifies equivalent bases and splits a failed certificate to find the obstruction.Source: §2.3 · p. 4

3 SOLVER SUFFICIENCY IN NETWORK–PARAMETERIZED SYSTEMS

For neural objectives, solver sufficiency is characterized by the geometry of the optimization landscape rather than an algebraic property of a constraint matrix. The section defines faithful regions and describes a sampling-based refinement procedure for inventing symbols that expose them.

3 SOLVER SUFFICIENCY IN NETWORK–PARAMETERIZED SYSTEMS

  • Neural objectives may have multiple local minima, so conditioned solvability is framed through whether a local solver can navigate the landscape’s barriers.The energy is a state-conditioned scalar decision score, with lower values indicating more desirable decisions.Source: §3 · p. 4, §3.1 · p. 5

3.1 τ-DESCENT FAITHFUL SYMBOLIZATION IN NEURAL OBJECTIVES

  • τ-descent faithfulness certifies that every initialization in a region can reach a near-optimal point within an escape budget, without requiring convexity or a unique minimum.The guarantee concerns accessibility under the specified path model; symbol assignments partition the space into regions for confined descent.Source: §3.1 · pp. 5–6, Figure 3 · p. 5

3.2 COUNTEREXAMPLE-GUIDED SYMBOL INVENTION WITH NEURAL CPR

  • Neural CPR samples multi-start descents into a nearest-neighbor graph and uses counterexample-guided refinement to discover a symbolic partition.Resampling may merge basins separated only by undersampling; persistent separations prompt new symbols based on estimated barrier paths and gradient-direction changes.Source: §3.2 · p. 6

4 EXPERIMENTS

The experiments test whether solver-sufficient symbols reduce solving cost while preserving solution quality, explain useful human-defined symbols, and support interpretable behavior steering. They evaluate PWA and network settings, including real-world tasks.

4.1 Q1. PRESERVING OPTIMALITY WHILE REDUCING SOLVING COST

  • In PWA and network settings, symbol-guided solving largely preserves solution quality while reducing solving time or the number of descents required for near-optimal solutions.For PWA systems, the method exposes commitments needed for faithful relaxation while keeping conditioned problems LP-solvable; for neural settings, it reduces DC_10^-3 on a trained DDPM policy without changing its parameters.Source: Figure 6 · p. 7, §4.1 · p. 8, Table 2 · p. 8

4.2 Q2. EXPLAINING THE UTILITY OF HUMAN-DEFINED SYMBOLS

  • Across MPushT formulations, task necessity and the share of factors with clear human semantics increase with solver necessity.A bottom-stem push has higher task and solver necessity than a top-bar corner push, whose contact force can be replaced by neighboring pushes.Source: §4.2 · pp. 8–9, Figure 7 · p. 8

4.3 Q3. RETAINING SYMBOLIC INTERPRETABILITY AND STEERABILITY

  • Invented symbols correspond to distinct behavior basins that can be labeled and selected at inference time, yielding high task and preference success rates.The reported preferences include pushing from inside versus outside and passing an obstacle on the left versus right.Source: Figure 8 · p. 8, §4.3 · p. 9, Table 4 · p. 9
  • As planning horizons grow, required symbol dimension generally increases and success rates moderately decline, while tasks with clearer modes may need fewer symbols.Avoiding requires fewer symbols than Aligning; linear symbol models may be restrictive when task-relevant modes are not linearly separable in a learned feature space.Source: §4.3 · p. 9, Table 5 · p. 9

5 CONCLUSION

The conclusion presents solver-sufficient symbols as a way to expose discrete commitments that simplify planning, reduce solving cost, preserve solution quality, and support behavior steering. The related discussion contrasts explicit discrete partitions with learned objectives whose behavior basins are implicit.

5 CONCLUSION

  • Across simulated and real-robot tasks, invented symbols reduce solving cost while preserving solution quality and provide an interpretable interface for behavior steering.The paper connects this solver-centric view to understanding why human-defined concepts can be computationally useful.Source: §5 · p. 9

A.1 SEARCH-THEN-OPTIMIZE: FROM MILP TO ENERGY-BASED MODELS

  • For learned objectives, alternative behaviors occupy distinct basins, but initialization samples a basin rather than explicitly deciding or holding it fixed across successive solves.Existing remedies adjust generated actions to improve agreement between consecutive outputs; the paper instead supplies an explicit basin index, with exact LP relaxation for PWA systems and sampled, one-sided τ-descent certification for learned objectives.Source: §A.1 · pp. 13–14

A.2 SYMBOL INVENTION IN NEURO-SYMBOLIC PLANNING

The paper contrasts predefined symbol vocabularies and extrinsic performance scores with symbols derived from solver structure and judged by properties of conditioned problems. It relates planning efficiency to structural coupling and states assumptions for the PWA discrete interface.

A.2 SYMBOL INVENTION IN NEURO-SYMBOLIC PLANNING

  • Prior symbol-invention approaches delimit admissible symbols in advance, while measured transition likelihood or planning performance does not specify what fixing a symbol does to the remaining problem.The paper instead derives candidates from solver structure and uses conditioned-problem criteria: exact LP relaxation for PWA systems and τ-descent faithfulness for learned objectives.Source: §A.2 · p. 14

A.3 PLANNING EFFICIENCY AND STRUCTURAL COUPLING

  • Planning efficiency depends on how many steps must be searched and how much must be considered jointly, with coupling capturing decisions that cannot be made independently.The paper measures coupling by solver-relaxation faithfulness: RATdim counts commitments needed for an exact LP relaxation, while τ-descent faithfulness addresses learned objectives without declared transition structure.Source: §A.3 · pp. 14–15

B.1 STRUCTURAL ASSUMPTIONS ON THE DISCRETE INTERFACE

  • The PWA discrete-interface assumptions require a TU discrete matrix and bridge coefficients in {0, ±1}.The text says these conditions hold for common one-hot contact-mode logic and bridge constraints, and discrete coefficients can be normalized for big-M gates and signed incidence.Source: §B.1 · p. 15

B.2 NUMERICAL COMPLEXITY OF SYMBOLIC CONDITIONING

A relative affine-TU certificate lets symbolic conditioning replace a search over primitive mode assignments with LP solves over compact symbol assignments. The resulting complexity depends exponentially on the certificate’s row count, while its minimum size is bounded below by a rank difference.

B.2 NUMERICAL COMPLEXITY OF SYMBOLIC CONDITIONING

  • 2O(k log nd) poly(nd, nc, m, L) bounds exact search over symbol assignments, with one LP solved for each fixed commitment.The symbol space has size at most (2nd + 1)^k.Source: §B.2 · p. 15
  • A k-row certificate reduces the lifted program to k exact integer variables, yielding a 2O(k^3) poly(nd, nc, m, L) bound instead of 2O(nd^3) poly(·).The conditioned discrete polytope is integral, so relaxing its variables preserves optimality and permits a single LP solve.Source: §B.2 · p. 15

B.3 BOUNDS ON RELATIVE AFFINE-TU DIMENSION

  • The relative affine-TU dimension is at least rank[Bd; Ed] − rank(Ed) and at most nd.The lower bound follows because certificate rows must span the relevant directions not already represented by Ed.Source: §B.3 · p. 16

B.4 BELLMAN FACTORIZATION FOR RELATIVE AFFINE-TU

For repeated local constraints, relative affine-TU symbols factor each Bellman backup into discrete and continuous subproblems without changing its value. The appendix also details certificate construction and refinement for PWA and neural-network settings.

B.4 BELLMAN FACTORIZATION FOR RELATIVE AFFINE-TU

  • For repeated local constraints, a local relative affine-TU certificate lifts to the full horizon by reusing its rows at every step, giving k = T · k̄.The Bellman factorization requires a separable stage cost and a successor state that does not depend on the discrete mode.Source: §B.4 · p. 16
  • The Bellman backup separates into a symbol-indexed discrete term and a continuous subproblem, preserving the value function and its fixed point exactly.The factorization prunes mode branching within each backup; it does not shorten the horizon.Source: §B.4 · pp. 16–17

B.5 GUARANTEE OF A τ-FAITHFULNESS

  • If every conditioned region is τ-descent faithful, searching its symbols and running confined descents achieves the optimum within τ at a cost of |W(X)| descents.For continuous hs on compact X, such a symbol map exists.Source: §B.5 · p. 17

C DETAILS OF CPR FOR PWA SYSTEMS

  • PWA CPR initializes symbols from discrete directions not represented by E, then residualizes constraints and checks the resulting matrix with a TU oracle.A rank lower bound guides initialization, but does not guarantee its size.Source: C DETAILS OF CPR FOR PWA SYSTEMS · p. 17

VERIFY

  • On verification failure, CPR first tests alternative bases of the same symbol space; if non-TU persists, it finds a minimal obstruction and adds a commitment.The bounded re-basing search cannot certify that a larger symbol dimension is necessary.Source: C DETAILS OF CPR FOR PWA SYSTEMS · p. 17

SPARSIFY

  • In the worked PWA example, re-basing leaves the determinant-2 obstruction intact, so CPR splits by adding an explicit commitment to z3.The resulting symbols are ψ1 = z4, ψ2 = z1 − z2, and ψ3 = z3.Source: SPARSIFY · pp. 18–19

D DETAILS OF NEURAL CPR FOR NETWORK SYSTEMS

  • Neural CPR builds sampled descent graphs, flags regions with costly barriers or poor minima, adds confined descents first, then splits persistent violations unless a resource cap is reached.A flagged basin may reflect missing samples rather than a deficient symbolization, so CPR attempts this no-new-symbol repair first.Source: D DETAILS OF NEURAL CPR FOR NETWORK… · p. 19

E FURTHER EXPERIMENTAL RESULTS

The adequacy of linear symbol partitions depends on the feature space: curved basin boundaries may need more directions, while richer axes trade interpretability for expressiveness.

E.1 BEYOND LINEAR SYMBOL AXES

  • Quadratic symbol axes can reduce the number of required directions and improve success, but more expressive symbols shift complexity into the symbolic layer and weaken interpretability.Linear cuts suffice when task-relevant modes are linearly separable in the chosen feature space; curved boundaries require piecewise approximation.Source: §E.1 · p. 20

E.2 ABLATIONS ON SOLVER RESOLUTION τ

The escape budget τ controls how finely neural CPR resolves the optimization landscape. An intermediate range closes all regions while reducing symbol dimension with little loss in SR.

E.2 ABLATIONS ON SOLVER RESOLUTION τ

  • The quadratic symbol axes capture the curved decision boundary with fewer symbolic directions.Source: Figure 9 · p. 20
  • Below within-basin descent variation, CPR over-resolves noise, producing more symbols while leaving many regions unclosed; above inter-basin barriers, k = 0.Between these extremes, all regions close and k decreases progressively with little loss in SR.Source: §E.2 · pp. 20–21
  • The intermediate τ range reduces symbol dimension progressively with little loss in SR once all regions close.The results support selecting τ between within-basin variation and inter-basin separation.Source: §E.2 · pp. 20–21

E.3 ABLATIONS ON SAMPLING EVIDENCE.

Neural CPR’s inferred symbol dimension depends on the evidence available to characterize the landscape. The sampled atlas must close before its symbolic partition is treated as stable.

E.3 ABLATIONS ON SAMPLING EVIDENCE.

  • With insufficient evidence, inferred k varies with sampling while regions remain violating; at 400 initializations, the violating fraction reaches zero with k = 1.Additional evidence resolves uncertain connectivity before the resulting symbolic partition is treated as stable.Source: §E.3 · p. 21

F.1 TASK REQUIREMENTS

The appendix specifies the manipulation and in-hand tasks and their discrete MILP representations. It also varies the MPushT factorization to study the computational role of human-defined distinctions.

F.1 TASK REQUIREMENTS

  • The evaluation covers six PWA tasks and five neural-network tasks, spanning 2D manipulation, in-hand reorientation, D3IL, and real-world settings.The listed tasks include aligning, sorting, matching, MPushT, Hook, Packing, Block, Cuboid, Pen, Avoiding, and Pushing.Source: §F.1 · p. 21
  • MPushT uses four pushers to translate and rotate a T-shaped object, while Hook requires collision-free repositioning, valid hook–block contact, and sustained pulling.Source: §F.1 · p. 21
  • Packing places 4–8 heterogeneous rectangles into two stable support stacks; Block, Cuboid, and Pen require in-hand reorientation under specified contact structures.The Shadow Hand tasks use a 0.10 rad rotational-error tolerance.Source: §F.1 · p. 21
  • Avoiding has 24 collision-free route modes, and Pushing has four solution modes from two assignments and two completion orders.Source: §F.1 · p. 21

F.2 MILP SETUPS

  • The MILP setup summarizes primitive discrete variables z as mode and contact choices, with task-specific factors encoding actions, contacts, assignments, and constraints.Examples include 18 candidate MPushT contact points over eight faces and 16 binary Hook factors; the in-hand tasks use finger–face or finger-group–zone representations.Source: §F.2 · p. 22, Table 8 · p. 23, Table 9 · p. 23

F.3 MPUSHT MILP VARIATIONS

  • Nine expert-designed MPushT MILP formulations use 127 primitive contact factors in total to compare discrete factorizations while holding the task fixed.The alternatives include face-occupancy factors with face-specific lever offsets or global spin actions.Source: §F.3 · pp. 22, 24, Table 10 · p. 23
Loading 2610.23010v1…