Temporal Planning with Clock-Based SMT Encodings

Jussi RintanenIJCAI 2017 · DOI

TL;DR

This paper introduces more efficient ways to encode temporal planning problems for SMT solvers, using "clocks" to represent time and resource usage. This leads to significantly smaller encodings and faster planning, especially for complex problems with many steps and resource constraints.

What Problem Does This Paper Address?

Temporal planning, a crucial area in AI for tasks like robotics and logistics, involves finding a sequence of actions to achieve a goal over time. Traditionally, these problems are encoded for Satisfiability Modulo Theories (SMT) solvers. However, existing SMT encodings for temporal planning, particularly those handling effect delays and resource constraints, suffer from performance issues due to their large size. Specifically, the number of "steps" (time points) and the way resource allocations are represented can lead to quadratic or even worse complexity, making it difficult for SMT solvers to handle realistic problems. This paper aims to reduce the size of these encodings to improve the scalability and performance of SMT-based temporal planners.

Methods

The paper proposes two main contributions to improve SMT encodings for temporal planning:

  • Clock-Based Encodings for Effect Delays and Resources: Instead of explicitly representing every time point where an effect might occur or a resource is used, the authors introduce "clocks." These clocks are SMT variables that track time or resource usage.
  • Effect Delays: Clocks are used to represent the time elapsed since an action started. This allows effects with delays to be triggered more efficiently, reducing the encoding size from quadratic to linear.
  • Resource Constraints: Clocks are also employed to model resource allocations. This approach aims to avoid the quadratic complexity of pairwise action comparisons for resource conflicts, leading to more compact encodings.
  • Relaxed Scheme for Steps: The paper introduces a new scheme that reduces the number of explicit "steps" (time points) required in the SMT encoding. Instead of needing a step for every action start and every discrete change, this scheme allows a single step to summarize multiple preceding time points. This is achieved by relaxing effect axioms to trigger when a clock value falls within a certain range, rather than requiring an exact time match.

Datasets

Not discussed in the paper. The paper evaluates its approach on standard benchmark problems for temporal planning, as evidenced by Table 1 and the experimental setup.

Key Insights and Ideas

  • Clocks as a General Abstraction: The core insight is that "clocks" can serve as a powerful and flexible abstraction for managing temporal information, including effect delays and resource allocations, within SMT encodings.
  • Linearizing Quadratic Complexity: By using clocks, the authors demonstrate how to transform encodings that were previously quadratic in the number of steps or actions into linear ones, a significant win for scalability.
  • Relaxing Step Requirements: The idea that not every discrete change needs its own explicit time step is crucial. By allowing steps to summarize multiple events, the overall number of constraints and variables can be drastically reduced.
  • Trade-offs in Planning: The relaxed step scheme introduces a trade-off between the number of steps and the makespan (total plan duration), as illustrated in Figure 2. This highlights that optimizing for one metric might impact another.

Key Results

The proposed clock-based encodings and relaxed step scheme significantly improve the performance of SMT-based temporal planners:

  • Scalability: The new encodings solve "dozens more of the standard benchmark problems" compared to previous SMT-based methods.
  • Performance: Runtimes are sometimes improved by "two orders of magnitude."
  • Plan Quality: While not always matching the speed of specialized planners like ITSAT, the proposed method produces plans with better quality (makespans closer to optimal) compared to ITSAT, which can generate plans twice as long as optimal. For example, Figure 3 shows ITSAT makespans are often close to twice those of the proposed method (labeled 'R').

Limitations and Future Work

  • Plan Quality vs. Speed: The paper acknowledges that while their approach improves plan quality significantly over ITSAT, it doesn't always match ITSAT's raw speed. Future work could focus on further optimizing the encodings and implementation to bridge this gap.
  • Handling Temporal Dependencies: The authors suggest further investigation into schemes for reducing the complexity of handling temporal dependencies between actions.
  • Implementation Technologies: Exploring better implementation technologies for temporal planning, inspired by successes in classical planning, is also proposed as a future direction.
  • Specific Cases: While clocks are generally effective, the paper notes that there are specific cases (e.g., when actions allocate the same state resource with different states or for different durations) where clocks might be insufficient, and fallback strategies like formula (9) are still needed.

Summary updated

BibTeX
@inproceedings{rintanen2017temporal,
  author = {Jussi Rintanen},
  title = {{Temporal Planning with Clock-Based SMT Encodings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/103},
}

Loading related content...

Figure