Temporalising Separation Logic for Planning with Search Control Knowledge

Xu Lu, Cong Tian, Zhenhua DuanIJCAI 2017 · DOI

TL;DR

This paper introduces PPTLSL, a novel spatio-temporal logic that combines separation logic for spatial reasoning with temporal logic for time-based reasoning. This new logic allows AI planners to leverage both spatial and temporal constraints for more efficient and effective planning, demonstrated by a new planner called S-TSolver.

What Problem Does This Paper Address?

Artificial Intelligence (AI) planning aims to find a sequence of actions to achieve a goal. A major challenge is the combinatorial explosion of the search space, making it difficult for planners to find solutions efficiently. Search Control Knowledge (SCK) is used to guide planners by providing domain-specific constraints, but existing approaches primarily focus on temporal constraints. However, many real-world planning domains, such as logistics or traffic management, inherently involve both spatial and temporal aspects. Traditional temporal logics are insufficient for expressing spatial relationships, leading to a gap in how SCK can be effectively utilized in these domains. This paper addresses this gap by proposing a logic that can capture both spatial and temporal constraints simultaneously.

Methods

The core contribution is the development of PPTLSL (Propositional Projection Temporal Logic with Separation Logic). This logic is created by "temporalizing" separation logic with Propositional Projection Temporal Logic (PPTL).

  • Separation Logic: This logic is used to reason about dynamically allocated data structures and their spatial relationships. In PPTLSL, a decidable fragment of separation logic is employed to describe the spatial configuration at a specific point in time.
  • Propositional Projection Temporal Logic (PPTL): This is a linear-time temporal logic that allows for expressing complex temporal properties, including those that go beyond standard LTL and CTL. PPTL's temporal operators are used in PPTLSL to capture the evolution of spatial structures over time.
  • Spatio-Temporal SCK: The paper demonstrates how to express various types of SCK that combine spatial and temporal constraints using PPTLSL. Examples include ensuring newly built roads are reachable by cars or that two paths between junctions do not share common locations.
  • Decision Procedure: The authors prove that PPTLSL is decidable. They achieve this by developing an equisatisfiable translation from PPTLSL to a restricted form called RPPTLSL, and then leveraging existing decision procedures for PPTL.
  • S-TSolver Planner: A planner named S-TSolver is implemented. It integrates a forward-chaining algorithm with an SMT solver (Z3) to handle the spatio-temporal SCK expressed in PPTLSL. The planner uses the translation and progression techniques to transform SCK into a form suitable for the SMT solver.

Datasets

The paper evaluates the proposed approach on two benchmark domains:

  • CityCar: This domain simulates road building and demolition in traffic networks, where cities are represented as graphs. It's a relevant domain because it involves dynamic changes in spatial structures over time.
  • Transport: This domain, a variant of the logistics domain, involves transporting packages using trucks on a road network. While the spatial structure is fixed, it still requires reasoning about spatial relationships and temporal actions.

The authors compare their planner's performance against top planners from the International Planning Competition (IPC) on instances from these domains.

Key Insights and Ideas

  • Bridging the Spatial-Temporal Divide: The most significant insight is that effectively guiding AI planners requires considering both spatial and temporal constraints. Simply relying on temporal SCK is insufficient for many real-world problems.
  • Leveraging Separation Logic for Planning: The paper demonstrates that separation logic, traditionally used for program verification, can be effectively adapted to express spatial configurations relevant to AI planning tasks.
  • Expressiveness of PPTLSL: The proposed logic is shown to be expressive enough to capture complex spatio-temporal relationships that are not easily expressible in existing temporal logics. This includes properties like spatial non-interference.
  • Decidability is Achievable: Despite the increased expressiveness, the authors prove that PPTLSL remains decidable, paving the way for practical implementation.

Key Results

  • Improved Plan Quality: The S-TSolver, when using spatio-temporal SCK (S-T), consistently generated plans with better quality (lower cost) compared to using only temporal SCK (T) or other state-of-the-art planners on the CityCar and Transport domains. This is attributed to the ability of spatio-temporal SCK to prune more irrelevant search space and guide the planner towards more efficient actions.
  • Comparable Performance: While S-TSolver(S-T) sometimes took longer than purely temporal versions or other specialized planners, it was capable of solving all tested instances in the CityCar domain, outperforming some IPC competitors. In the Transport domain, it achieved plan costs comparable to or better than leading planners.
  • Effectiveness of SCK: The experiments highlight the significant impact of SCK, particularly spatio-temporal SCK, in improving planning efficiency and plan quality.

Limitations and Future Work

  • Coarseness of "Nearest" Path: The paper acknowledges that the definition of "nearest" path in the Transport domain (minimum steps) can sometimes lead to longer actual road lengths. Future work could involve incorporating more detailed spatial information, such as road lengths, into the logic.
  • Computational Overhead: Using spatio-temporal SCK can introduce computational overhead compared to purely temporal SCK, as seen in the increased planning time for S-TSolver(S-T) in some cases.
  • Future Directions: The authors plan to conduct more experiments on a wider range of domains suitable for spatio-temporal SCK. They also aim to explore advanced heuristic algorithms to further improve efficiency and investigate connections to other formalisms for spatio-temporal reasoning.

Summary updated

BibTeX
@inproceedings{lu2017temporalising,
  author = {Xu Lu and Cong Tian and Zhenhua Duan},
  title = {{Temporalising Separation Logic for Planning with Search Control Knowledge}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/162},
}
Figure