On the application of least-commitment and heuristic search in temporal planning

TL;DR

This paper introduces a novel two-stage search approach for temporal AI planning, combining a relaxed plan generation with a least-commitment heuristic search. This method significantly improves scalability and plan quality for complex temporal problems compared to traditional Graphplan-based backward search, while still offering competitive results against other state-of-the-art planners.

What Problem Does This Paper Address?

Modern AI planning systems are increasingly tasked with handling more realistic scenarios, including actions with durations (durative actions) and the ability to execute actions concurrently. Traditional temporal planning methods, often based on Graphplan's backward search, struggle with the complexity introduced by these features. Specifically, Graphplan's backward search faces inefficiencies when dealing with large temporal problems, leading to a vastly increased search space and degraded performance. This is exacerbated by issues like redundant exploration of symmetric problems and a lack of reusability of search effort when a branch fails. The paper aims to overcome these limitations by developing a more scalable and efficient search strategy for temporal planning.

Methods

The paper proposes a new two-stage search process to replace the traditional Graphplan backward search.

  1. Generation of an Initial Relaxed Plan: This stage uses the information from a temporal planning graph (TG) to create an initial "relaxed plan." This plan is a partially ordered set of actions where goals and action conditions are met, but without considering mutex relationships between actions or committing to their exact start times. This process is similar to the FF planner's relaxed plan generation but adapted for durative actions. It involves identifying actions that support problem goals and selecting them based on minimizing mutexes, aiming for a good initial structure.
  2. Planning and Allocating of Actions (Least-Commitment Heuristic Search): This stage takes the relaxed plan and allocates specific start times to actions. It employs a least-commitment strategy, meaning actions are only definitively placed in the plan when they are applicable and don't conflict with already allocated actions. This is achieved through a forward-chaining process that iteratively selects actions from the relaxed plan based on a heuristic "allocation priority." This priority considers factors like the action's importance for supporting future goals and its potential for concurrency. If an action is mutex with allocated actions, it's either postponed or removed from consideration if it's not obligatory. This approach avoids the exhaustive search of Graphplan and aims to produce good-quality, non-optimal plans efficiently.

Datasets

Not discussed in the paper. The authors use standard AI planning domains like the "ferry" and "gripper" problems, as well as problems from the IPC-2002 (International Planning Competition) simple-time track, including "driverlog," "zenotravel," "satellite," and "rovers."

Key Insights and Ideas

  • The inefficiency of pure backward search in temporal planning: The paper clearly demonstrates how Graphplan's backward search struggles with temporal features like action durations and concurrency, leading to wasted effort and poor scalability, especially in symmetric domains.
  • The power of a relaxed plan as a skeleton: Using an initial relaxed plan as a blueprint for the final solution significantly prunes the search space. This plan captures essential action dependencies without getting bogged down in temporal constraints too early.
  • Least-commitment for temporal allocation: Deferring the exact timing of actions until they are applicable and non-conflicting is a crucial heuristic. This allows for greater exploitation of action concurrency and avoids premature, potentially wrong, decisions.
  • Heuristic-driven allocation priority: The proposed allocation priority function effectively guides the search towards promising actions, balancing factors like goal support, successor actions, and action duration. This is key to achieving good plan quality without exhaustive search.
  • Scalability improvement: The new approach demonstrably scales much better than Graphplan backward search, particularly in domains with high symmetry.

Key Results

  • Improved Scalability: The proposed least-commitment search (tpsys-LC) significantly outperforms the Graphplan backward search (tpsys-GP) in terms of speed and the number of problems solved, especially in symmetric domains like "gripper."
  • Competitive Plan Quality: tpsys-LC generates plans with competitive makespans and numbers of actions compared to state-of-the-art planners like LPG and Mips. In some cases, it produces optimal plans where others do not, by effectively exploiting action parallelism.
  • Faster Execution: For many problems, tpsys-LC is considerably faster than tpsys-GP, with tests censored at 300 seconds showing substantial differences.
  • Handling Durative Actions: The approach effectively handles durative actions and their start/end effects, a key challenge in temporal planning.

Limitations and Future Work

  • Not Complete Preserving: The primary acknowledged limitation is that the new approach is not "complete preserving." This means it might not find a solution even if one exists, due to the heuristic nature of the allocation stage.
  • Heuristic Refinement: The authors suggest refining the heuristic functions to further improve plan quality, performance, and to mitigate some of the inconveniences of the greedy search.
  • Bottlenecks in Implementation: The initial stages of the algorithm (TG generation and relaxed plan extraction) are identified as potential bottlenecks that could be drastically reduced with further optimization.
  • Exploiting More Complex Mutexes: While the approach uses a more precise model of action mutexes than some previous methods, there's potential to exploit even more complex mutex relationships.

Summary updated

BibTeX
@inproceedings{2003application,
  title = {{On the application of least-commitment and heuristic search in temporal planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure