Teaching Neural Planners to Emit Parallel Steps with a Concurrency-Balanced Curriculum

Classical planners that work by translating a planning problem into a satisfiability formula found long ago that the formula gets much smaller when several independent actions share one time step. Two such actions might be loading two different trucks, or painting a wall while mowing a lawn. This parallel action encoding cuts the number of time steps the solver must reason over, often by half or more. Neural plan generators, which take a problem description and write out a plan the way a language model writes text, have ignored this idea. They are trained on strictly sequential action lists. As a result they must produce long outputs, they never learn which actions interfere with each other, and they fail sharply when a task actually requires concurrency. We propose to train a transformer that writes plans as a sequence of steps, where each step is a set of mutually non-interfering actions. The training labels come from a formally verified parallel SAT encoder.

The central difficulty is the training curriculum, meaning the order and mixture in which training problems are shown. The obvious schedule shows small or sequential-looking problems first and highly parallel ones later. Prior work suggests this is the wrong schedule. Models trained on a narrow band of easy, redundant examples have to reorganize their parameters abruptly when structurally different examples arrive. Our claim is that the right notion of diversity for a parallel planner is the interference structure of its training plans. That structure covers how wide the steps are, how much the sequential plan shrinks under parallel packing, and how dense the conflicts between applicable actions are. We claim that a self-paced curriculum which forces coverage across these concurrency groups from the first epoch will produce higher validity and shorter parallel makespans than size-ordered, loss-ordered, or uniformly mixed training. Makespan here means the number of parallel steps.

Core Claim and What Is New

Three ingredients are combined here, and none of the papers we found combines them. The first is a parallel output format: a plan is written as $T$ steps, each an unordered set of actions satisfying ∀-step semantics. Under ∀-step semantics every ordering of the actions inside a step is a valid sequential execution, so the format is checkable and needs no within-step ordering decision. The second is that the training labels are optimal-horizon ∀-step plans from a correct encoder. The third is that the curriculum's diversity term is defined over concurrency groups computed from the solver's own output, not over instance size or learned embeddings.

The closest neural-planning work goes a different way on each point. Plansformer fine-tunes a code language model on sequential optimal plans from FastDownward and has no curriculum. A*-CoAt bootstraps a neural heuristic through a size curriculum inside sequential A* search. The learned SAT local-search heuristic also uses a size curriculum, but on generic SAT formulas rather than planning formulas. DPCER is the only work in our file that pairs "parallel" with "curriculum," but its parallelism means distributed actor processes, and its scheduler is a bandit over fixed subtasks. It does not change the action representation.

Why the Two Directions Need Each Other

The parallel-planning literature supplies both the target representation and the reason to want it. Transition Constraints for Parallel Planning shows a parallel constraint encoding solving 165 of 213 IPC instances against 131 for an earlier parallel encoding. Relaxed Exists-Step Plans in Planning as SMT needs fewer than half the steps of competing numeric planners. For a generator, fewer steps means a shorter output to get right.

One paper constrains how we generate labels. Formally Verified SAT-Based AI Planning reports that the widely used Madagascar encoder injects incorrect mutex constraints, which are the pairwise "these two actions cannot share a step" clauses introduced in Reachability, Relevance, Resolution. Training a model on parallel plans from such an encoder would teach it wrong interference facts. We therefore use the verified ∀-step encoder with Kissat for all labels, and we accept the roughly tenfold encoding slowdown that paper reports, because it is an offline cost.

The curriculum literature supplies the method and the motivating failure. Self-Paced Learning with Diversity (SPLD) adds a negative group-sparsity penalty that forces the selected easy samples to spread across groups. It reports 12.1 versus 9.6 mean average precision over plain self-paced learning on TRECVID MED13. Easy Questions First? finds that strict easy-to-hard ordering causes large parameter restructuring when hard examples arrive, and that diversity-aware selection reduces it (77.85% vs 75.03% on Memory Networks).

Robotouille gives the evidence that concurrency is a separate axis of difficulty rather than more of the same. GPT-4o falls from 47% on synchronous tasks to 11% on asynchronous ones. SPLD's stated weakness also matters here: it degrades when groups are not meaningful. That weakness is exactly why we derive groups from solver-certified plan structure instead of clustering embeddings.

Research Program

Data. For each IPC domain we generate many instances across a range of sizes. We solve each with the verified ∀-step encoder by increasing the horizon until the formula is satisfiable, which gives the optimal parallel horizon $T^*$ and a parallel plan. For each instance we compute a concurrency signature with three quantities:

  1. the compression ratio $n/T^*$, where $n$ is the action count after sequentializing the plan;
  2. the mean and maximum step width;
  3. the mutex density, the fraction of simultaneously applicable action pairs that interfere.

Signatures are clustered within each domain into $K$ concurrency groups.

Model. A CodeT5-sized encoder–decoder, matching Plansformer's scale, reads the problem and writes steps separated by a delimiter token. Actions inside a step are sorted canonically, which is lossless because ∀-step semantics makes within-step order irrelevant.

Curriculum. We run SPLD over these groups. Let $v_i\in[0,1]$ weight training instance $i$, $L_i(w)$ be its sequence loss under parameters $w$, and $G_1,\dots,G_K$ be the concurrency groups. Then

$$\min_{w,v}\ \sum_i v_i L_i(w) \;-\; \lambda \sum_i v_i \;-\; \gamma \sum_{k=1}^{K} \lVert v_{G_k} \rVert_2 .$$

Here $\lambda$ sets the loss threshold for admitting a sample, it grows each epoch, and $\gamma$ rewards spreading selections across groups. The weights are updated with SPLD's sort-and-threshold algorithm every epoch.

Inference. Decoding is constrained so that a step cannot contain two actions that are mutex in the grounded task. Outputs are checked by a plan validator, both after sequentialization and against the ∀-step condition.

Secondary use. The generated step count is used as the starting horizon for the SAT planner. Choosing that starting horizon is listed as open in the transition-constraints paper.

Baselines

The naive reference point trains the same parallel-output model on the same instances with uniform shuffling and no curriculum. Any curriculum must beat this, or the curriculum is unnecessary.

The strongest existing neural generator is Plansformer, retrained on our instance pool with sequential FastDownward plans, using the same model size, token budget, and hyperparameter search budget. On Blocksworld, Towers of Hanoi, Grippers and Driverlog it reports 83.64% plan validity and 73.27% optimality. We will reproduce it on those four domains before extending it. Beating it means matching or exceeding its validity while producing fewer parallel steps, and doing so specifically on larger and higher-concurrency held-out instances.

The strongest existing curriculum is the size curriculum used by A-CoAt and by the learned SAT local-search heuristic, applied to our parallel model. Instances are ordered by object count. A-CoAt reports 80% success on 7-box Sokoban against 45% for SymBA*, but on sequential search. We found no reported result on Lacuna for a size curriculum on a parallel-plan generator.

Three ablations isolate the key ingredient, which is the choice of grouping. The first keeps SPLD but defines groups by size bucket. The second keeps SPLD but defines groups by k-means on the model's encoder embeddings, as in the original SPLD setup. The third keeps SPLD but assigns groups randomly. We also test plain self-paced learning with $\gamma=0$, and exclusive-lasso balancing from Balanced Self-Paced Learning as an alternative diversity penalty.

All arms see the same total number of gradient steps. All arms receive equal tuning budgets for their curriculum hyperparameters, chosen on a shared validation split. Every arm is run with five seeds.

For the solver warm-start check, the reference is the verified encoder with Kissat starting from $T=1$. We found no reported Lacuna result for its IPC coverage in a form we can quote, so we will measure it ourselves.

Why not just…?

Why not just use a size curriculum? In many IPC domains size and concurrency are correlated, so this is a fair challenge. They come apart in some places, though. In Blocksworld a large tower stack is nearly sequential, while in Logistics a small instance with many trucks is wide. Robotouille's 47% to 11% drop shows that concurrency causes failures independently of horizon length. The size-grouped ablation answers the question directly. If it ties concurrency grouping on the high-concurrency held-out bucket, the claim is wrong.

Why not just shuffle everything uniformly? This is the most serious threat. With enough data, uniform mixing already covers all groups, and curricula frequently fail to beat it. Our prediction is narrower than "curriculum helps." We expect the advantage to appear in low-data regimes and in parameter stability when wide-step instances enter training, measured as net parameter change in the style of Easy Questions First. We will sweep training-set size. If uniform mixing matches SPLD at every size, we will report the parallel output format alone as the contribution.

Why not just generate sequential plans and parallelize them afterward? Post-hoc compression, as with the temporal plan graphs in SSSP or online parallelization in AltAlt$^p$, is cheap and keeps Plansformer's validity. It is a real competitor. Its weakness is that greedy deordering of a fixed sequential plan inherits that plan's action choices, so its makespan can exceed $T^*$. The sequential decoder must also emit the full long output. We will run Plansformer plus greedy ∀-step deordering as an additional arm. The parallel model has to win on makespan gap to $T^*$ or on validity at long horizons. Otherwise the representation change is not worth it.

Why not just call the SAT planner? For correctness, one should. The neural model is useful because it is fast, with Plansformer reporting about 200 times faster than FastDownward. The warm-start experiment also tests whether the model makes the solver itself cheaper.

Proposed Experiments

Domains. Training and evaluation use Blocksworld, Grippers, Driverlog, Logistics, Rover, Satellite and Depots. Towers of Hanoi is kept as a negative control. It admits essentially no parallelism, so concurrency groups collapse to one, and the curriculum should give no gain there. A gain on Hanoi would point to a confound.

Splits. Each domain has an in-distribution test split and two held-out splits: larger instances, and instances from the top concurrency group. The top group is never sampled at above-average rates during training.

Metrics. We measure sequentialized validity with a plan validator, ∀-step validity, and the makespan gap $T-T^*$ on valid plans. We also report accuracy within each concurrency group and the net parameter change at the epoch when each group first receives substantial weight.

Decisive checks. The first decisive check is whether concurrency-grouped SPLD beats both size-grouped and embedding-grouped SPLD on the high-concurrency held-out split, with the confidence interval over five seeds excluding zero. The second is whether the parallel model beats Plansformer-plus-deordering on makespan gap without losing more than a few points of validity. The third is whether the solver, when started at the model's predicted horizon, solves more instances within a fixed time limit than when ramping up from $T=1$.

If the first check fails while the second succeeds, the result is still useful: neural planners should emit parallel steps, but they need no special curriculum to learn to.