In classical artificial intelligence, planning was often treated as a "stop-the-world" activity. An agent would sit perfectly still, exhaustively search for a complete sequence of actions to reach a goal, and only then begin moving. This "plan-then-act" paradigm works well in the predictable "toy worlds" of early robotics, but it fails in the messy reality of flight operations, crowded warehouses, or the open internet.
The research direction of Interleaved Planning and Execution shifts this paradigm. Instead of treating planning and acting as sequential phases, it treats them as a single, continuous, and overlapping process. By committing to immediate actions based on partial information and refining the plan while in motion, agents can navigate environments that are too complex, uncertain, or fast-moving for traditional offline search.
The Bottleneck of Total Deliberation
The fundamental problem with offline planning is the "analysis paralysis" that occurs when an agent faces incomplete information or a massive search space. As Robert T. Chien and Steven J. Weissman observed in Planning And Execution in Incompletely Specified Environments, rigid long-term plans are brittle; they break the moment an external factor changes the world state independently of the agent.
Furthermore, the computational cost of finding a "perfect" plan can be higher than the cost of the task itself. Eric Horvitz and John S. Breese framed this as the metareasoning-partition problem: how much time should an agent spend "thinking" versus "doing"? In high-pressure scenarios, Ethan Andrew Burns argues in Planning Under Time Pressure that the goal isn't the shortest path, but the shortest total time—the sum of planning and execution.
Acting to Learn: Deferred Commitment
One of the most powerful intuitions in this field is that execution is a form of sensing. Sometimes, the fastest way to resolve uncertainty isn't to think harder, but to take a step and see what happens.
Michael R. Genesereth and Illah Reza Nourbakhsh introduced the Deferred Planning Algorithm (DPA) in Time-Saving Tips for Problem Solving with Incomplete Information. DPA allows a robot to stop planning, execute a few certain steps to gather information, and then resume planning from a more informed position. Similarly, Edmund H. Durfee and Victor R. Lesser proposed using high-level abstraction hierarchies to sketch out long-term goals while detailing only the immediate operational steps. This "deferred commitment" preserves flexibility, allowing the system to repair plans incrementally as new data arrives.
Unifying Planning and Execution
To make this work, the system architecture must treat a "plan" not as a static script, but as a dynamic, evolving data structure.
In the IPEM (Integrated Planning, Execution, and Monitoring) framework, Jose A. Ambros-Ingerson and Sam Steel treated physical actions as "plan transformations." In this view, executing a step and refining a future step are semantically equivalent operations within a single control loop. R. James Firby pushed this further with Reactive Action Packages (RAPs), which allow robots to make decisions based on the current world state rather than a stale prediction, effectively turning execution into a real-time search through actual world states.
Execution Time as a Computational Resource
Modern research has found that the time an agent spends moving is not "dead time"—it is a valuable computational resource.
In Planning and Execution in Multi-Agent Path Finding, Yue Zhang and Zhe Chen introduced the PIE (Planning and Improving while Executing) framework. Instead of waiting for a perfect coordination plan for hundreds of robots, PIE generates a fast, suboptimal plan to get the robots moving immediately. While the robots are in motion, an anytime optimizer runs in the background, refining the remaining path. This overlap significantly reduces the total time to task completion by hiding the cost of complex search behind the physical duration of the movement.
From Robotics to LLM Agents
The principles of interleaved planning are now central to the development of autonomous Large Language Model (LLM) agents. As surveyed by Xu Huang in Understanding the planning of LLM agents, strategies that interleave reasoning with environmental feedback (like ReAct) are far more resilient than those that attempt to decompose a task entirely upfront.
Whether it is a robot navigating a warehouse using Exponential Deepening A* (Guni Sharon and Ariel Felner) or an LLM-based travel planner like RETAIL adjusting to weather forecasts, the core intuition remains the same: in a dynamic world, the most robust way to reach a distant goal is to start walking and keep thinking.