Transition Based Encodings for Automated Planning

19 concepts10 papers1 proposal

In automated planning, the way we represent a problem dictates how efficiently a solver can find a solution. For decades, the dominant paradigm relied on propositional formalisms like STRIPS or PDDL. In these frameworks, the world is modeled as a collection of independent Boolean facts (e.g., TruckAtA, TruckAtB, PackageInTruck), and actions are operators that assert or deny these facts.

While conceptually simple, this binary representation introduces a severe computational bottleneck. As Jussi Rintanen argues in Impact of Modeling Languages on the Theory and Practice in Planning Research, flattening structured domains into low-level Boolean sets strips away the inherent geometry of the problem. Downstream solvers must then waste significant computational effort trying to rediscover basic domain constraints—such as the fact that a truck cannot be in two places at once.

To overcome this, a powerful alternative has emerged: representing planning problems through multi-valued state variables and modeling the problem around state-change transitions rather than static world states.

From Binary Facts to Multi-Valued States

To preserve structural richness, we can transition from binary predicates to the SAS+ formalism, which uses multi-valued variables. Instead of tracking separate Boolean flags for every possible location of an object, a single variable represents the object's state (e.g., $V_{\text{truck}} \in \{A, B, C\}$).

This simple shift fundamentally alters the state space in two ways:

  1. Dimensionality Reduction: As shown by van den Briel et al. in Loosely Coupled Formulations for Automated Planning: An Integer Programming Perspective, multi-valued variables significantly decrease the total number of variables and constraints required in optimization models, leading to much more compact encodings.
  2. Implicit Mutual Exclusion: In a Boolean representation, ensuring that a truck is only in one place requires adding $O(N^2)$ constraints to explicitly forbid pairs of locations. In contrast, a multi-valued variable can only hold one value at a time by definition.

Hsu et al. leveraged this property in Constraint Partitioning for Solving Planning Problems with Trajectory Constraints and Goal Preferences to simplify the state space for complex planning tasks with localized subproblems. Similarly, Ghooshchi et al. demonstrated in Transition Constraints for Parallel Planning that multi-valued representations reduce variable counts and simplify constraint satisfaction problems (CSPs) without losing descriptive power.

Shifting the Focus: From Actions to Transitions

The true power of multi-valued representations emerges when we change what we encode. Traditional planners focus on actions as the primary decision variables. However, an alternative approach is to focus on transitions—the atomic changes of state variables from one value to another (e.g., $V_{\text{truck}}: A \rightarrow B$).

An early exploration of this shift can be seen in CPlan: A Constraint Programming Approach to Planning, where planning states are represented using variables, and actions are handled implicitly through constraints that govern the transitions between these states. By focusing directly on how variables change, planners can bypass the complex mapping of actions to states.

Traditional (Action-Centric):
[State t: TruckAtA]  ===(Action: Drive_A_B)===>  [State t+1: TruckAtB]

Transition-Centric:
[Variable: TruckLocation]  ===(Transition: A -> B)===>  [Variable: TruckLocation]

Why it Works for Integer Programming: Tighter Relaxations

When solving planning problems via Integer Programming (IP), the choice of formulation dictates whether a solver succeeds or stalls. Early attempts simply translated SAT encodings into IP, resulting in weak Linear Programming (LP) relaxations where fractional solutions provided no useful guidance to the branch-and-bound algorithm.

Vossen et al. addressed this in On the Use of Integer Programming Models in AI Planning (and its companion work On the Use of Integer Programming Models in AI) by introducing the state-change formulation. Instead of tracking static world states at every discrete time interval, this formulation compiles away the original fluent variables and introduces auxiliary variables that explicitly track whether a fact is added, deleted, or persisted across time steps.

This transition-centric view provides a much tighter LP relaxation. Because the continuous fractional solutions are mathematically forced to respect the conservation of flow across transitions, the feasible region of the continuous relaxation closely mirrors the discrete constraints. Van den Briel et al. successfully scaled this concept in Optiplan: Unifying IP-based and Graph-based Planning, proving that tracking state transitions rather than static states allows IP solvers to be highly competitive with state-of-the-art SAT and heuristic planners.

Why it Works for SAT: Structural Compactness and Heuristic Alignment

The benefits of transition-based modeling extend directly to Planning as Satisfiability (SAT). Traditional SAT-based planners generate massive formulas because they must explicitly map every action to its preconditions and effects across every time step, alongside frame axioms to ensure unchanged facts stay the same.

Huang et al. challenged this paradigm in A Novel Transition Based Encoding Scheme for Planning as Satisfiability by introducing the SASE encoding scheme. SASE shifts the SAT formulation from STRIPS actions to SAS+ transitions. Instead of creating clauses for every action, it encodes the valid transitions of multi-valued variables.

As detailed by Chen 0001 et al. in SAS+ Planning as Satisfiability, this transition-centric approach works for two main reasons:

  • Drastic Clause Reduction: By focusing on value transitions (e.g., variable $X$ changing from $v_1$ to $v_2$), the encoding inherently captures mutual exclusions within the variable's domain. This eliminates the need for a massive web of frame axioms and conflict clauses, reducing clause counts by up to 50 times and memory usage to a fraction of traditional methods.
  • Heuristic Alignment: Modern SAT solvers rely heavily on decision heuristics like VSIDS (Variable State Independent Decaying Sum), which prioritize variables involved in recent conflicts. Transition variables represent the fundamental, atomic dynamics of the planning domain. When the SAT solver branches on these transition variables, it directly manipulates the causal structure of the plan, allowing its search heuristics to find solutions or prove unsatisfiability much faster.

By shifting the representation from "what actions are taken" to "how variables transition," this family of techniques allows general-purpose combinatorial solvers—whether based on IP, SAT, or CP—to exploit the underlying structure of planning domains natively.

Key Foundational Work

On the Use of Integer Programming Models in AI Planning (1999) — contributed 2 concept elements to this direction.
Optiplan: Unifying IP-based and Graph-based Planning (2005) — contributed 2 concept elements to this direction.
On the Use of Integer Programming Models in AI Planning (1999) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 10 papers
  2. Version 1 · 2026-10-04 · 17 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_multi_valued_state_representation_365eb89b,
  title = {multi-valued state representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-valued-state-representation/rdr_365eb89b74fa44d8b7ba7a0b1b62e49a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_multi_valued_state_representation_365eb89b_v2,
  title = {multi-valued state representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-valued-state-representation/rdr_365eb89b74fa44d8b7ba7a0b1b62e49a/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake