Abstract
Selecting the initial state for replanning while an agent is in motion is a critical challenge in online AI planning. If a planner starts from the agent's current position, the resulting plan may be obsolete by the time search concludes. We present the Multiple Initial State Technique (MIST), an approach that seeds the search with multiple potential future states. By employing a time-aware evaluation function that accounts for execution time, search cost, and the risk of "overshooting" a state, MIST allows the planner to determine the most efficient starting point during the search itself. Experimental results across various International Planning Competition domains demonstrate that MIST significantly reduces total goal achievement time compared to traditional fixed-latency or stop-and-plan baselines.
Introduction
In dynamic environments, autonomous agents frequently receive new goals while already executing a plan. A delivery robot, for instance, might need to incorporate a new high-priority pickup request mid-route. This necessitates online replanning. However, because planning is not instantaneous, the agent's state changes during the search. If the planner assumes the agent's state at the start of the search as the initial state, the resulting plan may be invalid by the time it is ready for execution.
This "initial state selection problem" is typically addressed by ad-hoc methods: stopping the agent to think (inefficient), finishing the current plan before starting the new one (slow), or guessing a fixed "look-ahead" time (unreliable). Because planning difficulty varies wildly, a fixed guess is often either too short, causing the agent to pass the start state before the plan is ready, or too long, causing the agent to travel further than necessary on an outdated path.
The Multiple Initial State Technique (MIST)
The Multiple Initial State Technique (MIST) addresses this by initializing the search "open list" with several reference states sampled from the agent's current trajectory. This allows the search process itself to decide which starting point offers the best trade-off between planning time and execution efficiency.
The core of MIST is a time-aware evaluation function ($f$) that guides the search. It considers the time to reach a reference state, the estimated cost to the goal ($g+h$), the time already spent planning ($\gamma$), and an "overshot" penalty ($os$). The $os$ function becomes infinite if the planner estimates that the agent will pass the reference state before the search concludes, effectively acting as a dynamic deadline. For "recoverable" tasks where an agent can backtrack (e.g., a warehouse robot), a variant called MISTrec is used, which replaces the infinite penalty with a time penalty for returning to the overshot state.
Experimental Evaluation
The researchers implemented MIST in the Fast Downward planner and evaluated it using modified benchmarks from the International Planning Competition (IPC), including domains such as Elevators, Logistics, Rovers, Transport, and VisitAll. They also utilized a "Tidybot" domain specifically adapted to test recoverability. The primary metric was Goal Achievement Time (GAT)—the total time from the arrival of a new goal to its completion.
Results and Discussion
As shown in the experimental results, MIST consistently outperformed standard strategies across all tested domains. On average, it reduced GAT by 8.6% compared to stopping immediately and 6.8% compared to finishing the old plan first.
Notably, MIST also outperformed baselines that attempted to predict planning time in advance by 5.1%, proving that reasoning about the start state during the search is more effective than guessing before it starts. The technique proved robust regardless of whether the replanning task was "easy" or "hard," whereas fixed-latency baselines failed significantly when their hard-coded guesses were inaccurate.
Conclusion
MIST provides a principled solution to the initial state selection problem in online replanning. By integrating the decision of where to start the plan into the search process, it achieves superior execution efficiency. Future work includes reducing the dependency on heuristic accuracy for the overshot function and extending the model to handle non-interruptible actions and the automated discovery of recovery sequences.
Summary updated