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

What Makes a Good Symbol for Hybrid Discrete-Continuous Planning?. By Yiyuan Pan and two others, from Carnegie Mellon University and the University of Pennsylvania. Published on the sixteenth of October. No code repository is linked to it.

The physical world runs on continuous states and continuous actions. Robot planning nonetheless often does better with a hybrid formulation, one that lays bare a discrete, combinatorial structure inside the continuous problem: which contact mode is active, or which discrete primitive action is chosen. Those discrete pieces are symbols. Existing methods usually take the symbol set from a human, or derive it from language supervision. Neither asks the question in the title: what makes a symbol computationally useful?

The answer offered takes the inference algorithm's point of view. A good symbol is one that exposes the discrete commitments that make the original planning problem simpler to solve. Usefulness is defined by what the symbol does for the solver, not by whether it is meaningful to a person. The formal name for this is solver-sufficient symbolization.

The argument proceeds in two moves. First, the authors study finite-horizon piecewise-affine systems, a class in which solver sufficiency can be characterized precisely. On that firm ground they develop a counterexample-guided algorithm for inventing symbols. Second, they carry the principle outward, to optimization objectives parameterized by general neural networks acting as energy functions. Even there, they show, solver-sufficient symbols can still be induced, drawn from the continuous optimization landscapes of those networks.

The exact characterization belongs to the first setting only: finite horizon, piecewise-affine dynamics. The extension to neural energy functions keeps the principle but induces symbols from optimization landscapes rather than characterizing them precisely. The empirical side is experiments on simulated and real-robot tasks, where the invented symbols reduce solving cost while preserving solution quality, and also improve interpretability and steerability.

The work ends by turning back toward people. The same theoretical and algorithmic insights help explain why certain symbols that humans defined by hand turn out to be computationally useful. A criterion built from the solver's side ends up accounting for some of the intuitions people already had.