In classical artificial intelligence, problem-solving is treated as a strict, two-phase sequence: first, an agent deliberates offline to compute a complete sequence of actions; second, it executes that plan in the physical world.
This "plan-then-act" paradigm breaks down in real-world environments. Deliberation takes time. In high-pressure scenarios, an agent can suffer from "analysis paralysis," spending valuable time computing a perfect plan while the environment changes around it. As Paolo Traverso et al. point out, treating planning as an offline pre-process ignores the fact that reasoning itself is a time-consuming activity that can fail or become obsolete before the first action is even taken.
Interleaved planning and execution fundamentally re-frames this relationship. Instead of treating thinking and doing as sequential blocks, it unifies them into a concurrent control loop. By generating partial plans, executing immediate steps, and refining subsequent actions in the background, agents can minimize latency, drastically reduce search spaces, and gracefully adapt to uncertainty.
Overlapping Timelines: Thinking and Doing in Parallel
The primary intuition behind interleaving is a simple optimization of time. In high-pressure scenarios, an agent's success is determined by its total time—the sum of its deliberation time and its physical execution time. As Ethan Andrew Burns argues, agents achieve better performance by initiating preliminary actions before a complete plan is finalized, effectively overlapping the thinking and doing phases to reduce overall latency.
Traditional: [--- Planning Time ---][--- Execution Time ---] = Total Time
Interleaved: [- Plan 1 -][--- Execution 1 (Physical Movement) ---]
[- Plan 2 -][--- Execution 2 ---] = Shorter Total Time
This concurrent strategy manifests across different domains:
- Pathfinding and Search: In real-time heuristic search, algorithms like TBA (Time-Bounded A), developed by Yngvi Björnsson et al., "time-slice" a single search graph. This allows video game characters or robots to begin moving toward a goal while the underlying A* search continues to compute the remainder of the path in the background.
- Multi-Agent Coordination: In Multi-Agent Path Finding (MAPF), the PIE framework by Yue Zhang et al. (SOCS 2024) initiates agent movement based on a rapidly generated, suboptimal plan. The system treats the time spent during physical execution as a computational resource, utilizing an anytime optimizer to iteratively improve the long-term plan while the agents are already in motion.
- Language Model Workflows: This pipelining principle extends to modern generative AI. Sehoon Kim et al. developed LLMCompiler, which orchestrates parallel function calling by executing early tasks while the LLM planner is still generating the remainder of the task sequence, significantly reducing end-to-end latency.
Search Space Reduction via Physical Commitment
Interleaving planning and execution does not just save time; it fundamentally alters the mathematical complexity of the search problem.
When an agent attempts to plan a complete sequence to a distant goal, the search tree branches exponentially. However, when an agent executes an initial action, it physically commits to a state. As Richard Goodwin notes, this commitment reduces the complexity of the remaining search space by eliminating all future paths that are inconsistent with the actions already performed.
To balance the benefits of early action with the risk of making unrecoverable mistakes, modern frameworks rely on two core concepts:
- Commitment Windows: Frameworks like PIE-D, introduced by Yue Zhang et al. (aaai 2025), utilize short commitment windows to balance path computation with frequent state updates. By restricting the execution window, the system can rapidly incorporate feedback (such as unexpected agent delays) before desynchronization accumulates.
- Partial Planning and Deferred Subgoals: Instead of generating a granular end-to-end plan, agents commit to high-level procedures and defer the specification of subgoals until execution. Michael P. Georgeff et al. (1989) demonstrated this in the Procedural Reasoning System (PRS), showing that partial planning allows real-time environmental data to guide low-level refinement, preventing the brittleness of static long-term plans. Craig A. Knoblock formalized this by treating unexecuted or currently executing actions as open "flaws" within a partial-order planning framework, meaning a plan is only considered complete when all actions have successfully finished.
Resolving Uncertainty through Active Sensing
In partially observable or non-deterministic environments, offline planning forces an agent to engage in exhaustive contingency planning—building massive search trees to account for every possible environmental state it might encounter.
Interleaving solves this by replacing mental simulation with active sensing. Instead of wondering what lies around a corner, the agent executes a partial plan to go look.
Michael R. Genesereth et al. pioneered this with the Deferred Planning Algorithm (DPA). The agent generates a partial plan designed specifically to gather information rather than reaching the final goal immediately. After executing these steps and receiving sensory feedback, the agent updates its knowledge base and resumes planning from a position of certainty.
Offline Contingency Planning:
[Current State] ---> [Plan Choice A] ---> If Obstacle? ---> [Plan A1]
---> If Clear? ---> [Plan A2] (Massive Tree)
Interleaved Active Sensing:
[Current State] ---> [Execute Move to Corner] ---> [Sense Reality] ---> [Plan Next Step] (Linear Tree)
This "situated" approach is formalized by Sven Koenig as agent-centered search. By alternating between a small look-ahead search and immediate physical action, the agent only plans for states that actually occur, bypassing the combinatorial explosion of non-deterministic modeling.
In modern applications, this mechanism allows embodied agents to navigate partial observability efficiently. For instance, Karan Mirakhor demonstrates that interleaving object search with task execution allows an agent to update its internal graph representations dynamically, adjusting its trajectory the moment a missing object or a blocked path is discovered. Similarly, in generative decision-making, Fan Feng utilizes an interleaved sampling strategy that alternates between partially denoising a trajectory and updating estimates of latent environmental factors, allowing the agent to sense and adjust simultaneously.
Maintaining Reactivity and Handling Disruptions
A common concern with interleaving is that an agent might become so engrossed in its background planning that it fails to react to sudden threats. To prevent this, architectures must tightly couple deliberative reasoning with reactive control.
One approach is the use of asynchronous production rules. John E. Laird et al. demonstrated within the Soar cognitive architecture that continuously matching environmental sensor data against a global set of production rules allows high-priority reactive behaviors to immediately override or abort active planning subgoals. This ensures the agent remains responsive to immediate stimuli even during deep look-ahead searches.
Furthermore, agents can utilize their execution windows to proactively insulate themselves against disruptions. Paul Breimyer et al. show that executing contingency planning as a background process allows an agent to utilize idle time during physical movement to compute backup routes ("Plan B") for likely deviations. If an action fails, the agent can pivot instantly without delaying the mission to replan from scratch.
Ultimately, interleaving shifts the role of AI planning from a static blueprint generator to an active, adaptive component of the execution cycle. By treating computation and action as deeply intertwined resources, autonomous systems achieve the fluid, responsive behavior required to navigate the complexities of the real world.
Key Foundational Work
Planning And Execution in Incompletely Specified Environments (1975) — contributed 2 concept elements to this direction.
Planning And Execution in Incompletely Specified Environments (1975) — contributed 2 concept elements to this direction.
PANDORA: A Program for Doing Commonsense Planning in Complex Situations (1982) — contributed 2 concept elements to this direction.