In automated planning, finding a valid sequence of actions to transition a system from an initial state to a goal state is a fundamental challenge. When framing planning as a logical search problem—such as Propositional Satisfiability (SAT) or Constraint Satisfaction Problems (CSPs)—the standard approach is to unroll the problem over a fixed sequence of discrete time steps, known as the planning horizon ($T$).
However, this sequential unrolling introduces a severe bottleneck: if a plan requires 50 actions, the logical formula must replicate the entire state space 50 times. For modern solvers, this explosion in the number of variables and clauses creates an unmanageably deep search space.
The core insight of parallel action encoding is that we do not need to execute actions one after another if they do not interfere with each other. By packing multiple independent actions into a single logical time step, we can dramatically compress the planning horizon. This temporal compression shrinks the formula size, reduces the search depth, and allows solvers to find valid plans orders of magnitude faster.
The Mechanics of Non-Interference and Step Semantics
To understand why parallel action encoding works, we must look at how solvers prevent concurrent actions from causing logical chaos. If Action A unbolts a door and Action B opens it, they cannot happen at the exact same time step because Action B depends on the effects of Action A. Conversely, if Action A paints a wall in the kitchen and Action B mows the lawn outside, they are non-interfering and can safely share a temporal index.
As shown by Amol Dattatraya Mali et al., encoding non-interfering actions within the same logical step minimizes the depth of the planning horizon. To guarantee that a parallel plan remains valid when executed in the real world, the encoder must inject mutual exclusion (mutex) constraints. Ronen I. Brafman demonstrated that incorporating these mutual exclusion constraints as simple binary clauses allows general-purpose SAT solvers to efficiently prune invalid action combinations. This formulation was central to the success of systems like SATPlan, as detailed by Henry A. Kautz, where parallel action encoding fundamentally altered the scalability of SAT-based planning.
Sequential Encoding (Horizon T = 3):
Step 1: [Paint Kitchen] ──> Step 2: [Mow Lawn] ──> Step 3: [Close Gate]
Parallel Encoding (Horizon T = 2):
Step 1: [Paint Kitchen, Mow Lawn] ──> Step 2: [Close Gate]
Recently, researchers have pushed the boundaries of how strictly these parallel steps must be constrained. Traditional approaches use $\forall$-step semantics, meaning that any actions grouped into a single step must be executable in any arbitrary order. However, Bofill et al. proposed a more permissive encoding for Satisfiability Modulo Theories (SMT) called relaxed $\exists$-step plans. By relaxing the requirement that all preconditions must be met at the absolute start of the time step, more actions can be crammed into a single step, yielding even greater parallelism and shorter plan profiles. To ensure absolute reliability, Abdulaziz et al. developed the first formally verified SAT encoder using the Isabelle/HOL theorem prover, mathematically proving that parallel action transitions strictly respect mutual exclusion boundaries.
Preserving Temporal Logic via Stuttering Invariance
When planning for complex environments, goals are often not just static final states but Temporally Extended Goals (TEGs)—requirements that must hold true across the entire execution timeline, typically expressed using Linear Temporal Logic (LTL). This introduces a paradox: if parallel encoding compresses multiple steps into one, does it break the semantics of time that the goal relies on? For instance, if an LTL goal states that "State X must happen at the very next step," compressing two steps into one would violate that condition.
Mattmüller et al. solved this dilemma by restricting the temporal logic to a stuttering-invariant subset (such as LTL without the "next-time" operator).
Because the logic is stuttering-invariant, the truth value of a formula remains identical whether an independent action happens sequentially or concurrently. This mathematical guarantee allows the planner to compress the plan horizon inside the SAT formula without altering the meaning of the temporal goal, unlocking massive speedups for temporally complex planning problems.
Beyond SAT: Online Search and Multi-Agent Systems
While parallel action encoding originated largely within logic-based solvers, its underlying principle applies broadly across other planning paradigms:
- Online State-Space Search: Traditional state-space planners struggle to generate parallel plans because evaluating every combination of simultaneous actions causes an exponential explosion of the branching factor. To circumvent this, Sanchez et al. and Sanchez Nigenda et al. introduced algorithms like AltAlt$^p$. Instead of searching the parallel space directly, these systems parallelize actions online during a standard search process using a "PushUp" mechanism, reducing the final plan's execution time (makespan) by roughly half with minimal computational overhead.
- Multi-Robot Coordination: In multi-agent environments, parallelization is natural but collision avoidance is difficult. Okumura et al. designed a framework that first generates sequential single-agent paths and then post-processes them into a graph-based representation. This graph isolates the true temporal dependencies between agent movements, allowing independent actions to run in parallel and stripping away unnecessary wait times.
- Constraint Satisfaction Frameworks: Moving beyond pure propositional logic, Ghanbari Ghooshchi et al. integrated parallel action execution into a Constraint Satisfaction Problem (CSP) framework called TCPP. By leveraging Domain Transition Graphs and compact table constraints with wildcards, they showed that parallel constraint-based planners can rival or outperform top-tier heuristic search planners.
Managing the Complexity of Concurrency
If parallel action encoding is so powerful, why not maximize it everywhere? The catch lies in the cost of verifying concurrency. As the number of actions grows, checking every pairwise interaction to ensure they do not conflict introduces a steep computational tax.
Several strategies have been developed to mitigate this complexity:
- Limited Grounding: Checking concurrent interactions among fully instantiated ("ground") actions can quickly become a quadratic bottleneck. Jussi Rintanen demonstrated that by reducing ground actions to a minimal representative set of schematic invariants, planners can verify concurrent interactions in seconds rather than hours.
- Solution Order Graphs: In Hierarchical Task Network (HTN) planning, ordering constraints add another layer of difficulty. Behnke et al. introduced a method to reason about task orderings before generating the SAT formula. By capturing these relationships in a Solution Order Graph, they reduced the formula size from a prohibitive $\Theta(n^4)$ to a manageable $O(n^2)$, allowing parallel step semantics to scale effectively within hierarchical domains.
- Tractable Problem Classes: Rather than trying to optimize arbitrary domains, Bäckström et al. identified specific structural classes of planning problems (such as SAS-PUS) utilizing multi-valued state variables. For these structures, they proved that minimal, maximally parallel plans can be synthesized in polynomial time, bypassing the exponential bottlenecks entirely.
By balancing the reduction of the planning horizon against the overhead of concurrency checking, parallel action encoding changes the fundamental economics of automated planning—turning what would be an impossibly deep sequential search into a shallow, highly parallelizable optimization problem.
Key Foundational Work
Refinement-Based Planning as Satisfiability (1998) — contributed 1 concept elements to this direction.
Parallel Non-Binary Planning in Polynomial Time (1991) — contributed 1 concept elements to this direction.