Is interleaving the same as concurrency?

No. Concurrency concerns overlapping activities; interleaving can represent their steps as a sequential ordering and can also occur without actual overlap.

Can interleaving make planning harder?

Yes. More possible orderings can increase the search space, even when some interleaving is necessary for a solution.

What is a valid linearization of a partial-order plan?

It is a complete action ordering that respects the plan's required ordering constraints and relevant validity conditions.

AI Glossary / Graphs and symbolic AI / Intermediate

Interleaving

Definition

Interleaving is the arrangement of steps from different activities within one combined sequence. In AI planning, it can mean mixing actions from different subplans; in acting systems, it can also mean alternating planning, execution and observation rather than completing all planning before acting.

What it means

The shared idea is that one activity is not necessarily finished before another begins. A planner may prepare part of one task, perform a necessary step for another task and then return to finish the first.

Interleaving is not automatically simultaneous execution. A single worker or processor can perform an interleaved sequence one step at a time. The important issue is the order and dependencies between steps.

Context should identify what is interleaved. Mixing two subplans concerns how their actions fit together. Alternating planning with acting concerns when computation occurs relative to execution. Both use the same broad idea, but they answer different design questions.

How it works

Identify each activity's steps and the order constraints that must be preserved. Add dependencies between activities, including conditions one step establishes for another and conditions a later step could destroy.

Construct a combined sequence that respects these requirements. A partial-order plan can leave unrelated steps unordered until a concrete execution sequence is needed. A proposed interleaving must still satisfy action preconditions and resource constraints; mixing steps does not make conflicts disappear.

For planning-and-acting interleaving, the system plans far enough to choose an action, executes it, observes the result and updates the next planning problem. This can support adaptation when the environment is not fully known. It also requires deciding how much computation to perform before each action and what to do when observations differ from expectations.

Three practical examples

A workflow planner mixes preparation steps from two jobs whose completion stages depend on each other's preparations.
A mobile agent alternates local route planning with movement and new observations in an unfamiliar environment.
A simulated assistant revises a multi-step plan after each tool result rather than assuming all earlier predictions remain correct.

Think of it this way

Think of preparing two dishes by moving between their steps: start one preparation, do a necessary step for the other, then return. Each dish retains its required internal order even though the overall sequence is mixed.

The analogy explains sequencing. Real AI plans require explicit preconditions and effects; intuition about cooking does not establish that an arbitrary rearrangement is valid.

Worked example

Two jobs that cannot be completed as separate blocks

Suppose job A contains PrepareA followed by FinishA, and job B contains PrepareB followed by FinishB. FinishA additionally requires PrepareB to have occurred; FinishB additionally requires PrepareA. Preparations remain valid once completed, and assume there are no other constraints.

Completing A as a block before B would give PrepareA, FinishA, PrepareB, FinishB. This fails because PrepareB has not occurred when FinishA is attempted. Completing B first similarly fails because FinishB requires PrepareA.

An interleaved plan PrepareA, PrepareB, FinishA, FinishB works. So does PrepareB, PrepareA, FinishB, FinishA. Both preparations occur before either completion step.

If we preserve only each job's internal order, there are six ways to merge its two steps with the other's two steps. The cross-job dependencies rule out the two block-by-block sequences, leaving four valid sequences: either preparation can come first, and after both preparations either finishing step can come first.

All four actions still occur sequentially. The example demonstrates the need to mix subplans, not a speedup from parallel execution or a reduction in the number of actions.

Illustrative case study

The fictional Cedar Workflow team builds a planner that completes one subtask before considering the next. It works on independent jobs but fails on a workflow where each job needs something prepared by the other.

Reviewers represent the cross-job requirements explicitly and allow the planner to combine steps while preserving their dependencies. They use the four-action example to verify that a valid plan exists despite both block-by-block orders failing.

Cedar separately considers whether any steps can run concurrently, because that requires resource and timing information absent from the simple model. The case illustrates a sequencing limitation and its repair. It does not claim that unrestricted interleaving is always efficient or that every interleaved plan is valid.

Common misconceptions and mistakes

Interleaving means performing all activities simultaneously. It can be entirely sequential.
Any mixture of steps is allowed. Internal order, preconditions and cross-activity constraints still apply.
Completing each subgoal independently always yields a complete plan. Interactions can require steps from subplans to be mixed.
Interleaving planning and acting removes the need for a plan. It changes when planning occurs, not whether decisions need supporting computation.

Business use

The concept helps explain why a workflow that looks simple as separate checklists can fail when the lists interact. Making dependencies explicit supports better sequencing and more informative failure explanations.

For AI agents that act while still planning, define observation points and the conditions that trigger revision. A tool result may invalidate a later assumption, so a system should not treat an earlier tentative plan as an unchangeable script. Conversely, replanning after every trivial step can add cost. The appropriate granularity depends on uncertainty, action consequences and available computation.

Check your understanding

Why do both block-by-block schedules fail in the worked example?

Answer: Each job's finishing step requires the other job's preparation. Finishing either job before starting the other violates that cross-job precondition.

Related terms

Partial-order planning
Online search
subplan
action precondition
dependency
replanning
concurrency
linearization

Learn next

Add a constraint that FinishA must occur before FinishB. List the remaining valid sequences from the worked example, then identify whether the added constraint changes the number of actions or only their permitted ordering.

Sources

Chapman's original work studies conjunctive goals and the constraints underlying partial-order planning: https://www.sciencedirect.com/science/article/pii/0004370287900920

AIMA's author algorithm collection includes online-search agents that combine actions with continuing computation: https://aima.eecs.berkeley.edu/algorithms.pdf

The original research Learning for Adaptive Real-time Search discusses interleaving planning and acting: https://arxiv.org/abs/cs/0407016

The four-action workflow and Cedar Workflow case are original examples. The entry distinguishes the two planning-related uses of interleaving.

Previous: Interleaved (HWC) layout Next: Interleaving distance