To Encode or not to Encode - I: Linear Planning

IJCAI 1999

TL;DR

This paper introduces LPSP, a novel linear planner that applies stochastic local search (SLS) directly to the planning problem's action space, rather than encoding it as a SAT problem. LPSP demonstrates superior performance by exploiting the inherent structure of planning problems, outperforming traditional "encode-and-solve" SAT-based approaches on several benchmark domains.

What Problem Does This Paper Address?

The field of Artificial Intelligence planning has seen great success with the "encode-and-solve" paradigm, particularly the "planning as satisfiability" (PAS) approach. This involves translating a planning problem into a propositional satisfiability (SAT) problem, which is then solved using powerful SAT solvers, often employing stochastic local search (SLS) techniques. While effective, this indirect approach might be suboptimal because it discards the rich structure of the original planning domain. The authors hypothesize that applying SLS directly to the planning problem's own search space, leveraging domain-specific heuristics and operators, could lead to better performance. This paper investigates this hypothesis by developing and evaluating a planner, LPSP, that operates directly on linear plans.

Methods

The core innovation is the LPSP planner, which employs SLS directly on the space of linear plans. Instead of manipulating truth assignments for SAT variables, LPSP manipulates sequences of actions.

  • Search Space: LPSP searches through fixed-length linear plans.
  • Scoring: Plans are penalized based on "flaws," which occur when an action's precondition is not met by a preceding action's effect. The penalty is a weighted sum of these flaws, with weights often related to the distance between the influencing actions. A valid plan has zero penalty.
  • Operators: LPSP uses specialized operators for navigating the plan space:
  • Best-Replacement: Replaces a single action in the current plan with another action to reduce flaws.
  • Flaw-Repair: Identifies a flaw and attempts to repair it by replacing an action between the "clobberer" (action providing the effect) and the "consumer" (action requiring the precondition), or by replacing the consumer itself.
  • Reorder-1 & Reorder-2: These operators reorder actions within the plan, guided by producer-consumer relationships and "threats" (actions that might interfere with preconditions). Reorder-1 uses a graph-based approach, while Reorder-2 partitions actions into ranks.
  • Initialization: A stochastic bi-directional search is used to generate an initial plan.
  • Reachability Analysis: A fast heuristic analysis prunes actions that cannot possibly contribute to a solution, reducing the search space.

Datasets

The paper evaluates LPSP on benchmark instances from three well-known planning domains:

  • Blocks World: Standard instances used in prior SAT-based planning research.
  • Logistics: Instances involving packages and cities, where the challenge lies in moving items.
  • D1S1: A domain noted for being difficult for SATPLAN.

Key Insights and Ideas

  • Direct Search is Powerful: Applying SLS directly to the planning problem's structure (linear plans) can be more efficient than encoding it into a SAT problem. This is because LPSP can exploit domain-specific knowledge and structures that are lost or obscured in the SAT encoding.
  • Specialized Operators Matter: The novel reordering and flaw-repair operators in LPSP are crucial for its success. They are designed to directly address planning-specific issues and navigate the action-sequence space effectively.
  • SAT Encoding Trade-offs: While SAT solvers are powerful, the overhead of encoding, simplification, and parameter tuning for SAT-based approaches can be significant, especially in domains where parallel plans are not much shorter than linear ones.
  • Linear Planning's Niche: LPSP excels in domains where linear plans are reasonably short or where concurrency offers little advantage. It struggles in domains where highly parallel plans are significantly shorter than linear ones.

Key Results

LPSP consistently outperforms PAS (Planning as Satisfiability) approaches using both stochastic (WALKSAT) and deterministic (SATZ) solvers across the tested domains.

  • Blocks World: LPSP is 3 to 13 times faster than PAS/WALKSAT.
  • Logistics: LPSP is 15 to 80 times faster than PAS/WALKSAT. This is particularly notable as logistics domains often favor parallel plans, yet LPSP's direct approach still dominates.
  • D1S1: LPSP shows better performance than PAS/WALKSAT, with one instance being solved by simplification alone.
  • General Trend: For PAS/WALKSAT, the time spent on formula simplification often dominates the overall execution time, highlighting the cost of the encoding step.

Limitations and Future Work

  • Linearity Assumption: LPSP is currently limited to linear plans. The authors acknowledge that extending it to handle parallel plans would be a significant next step, and they hypothesize that the direct search approach would still be beneficial.
  • Parameter Tuning: While LPSP requires less overall tuning than PAS approaches, its performance is still sensitive to parameter settings, and further optimization is possible.
  • Domain Specificity: The success of LPSP relies on its ability to exploit domain structure. The authors suggest that identifying and leveraging such structures more generally could lead to even better planners.
  • Comparison to Other Planners: The paper focuses on comparing LPSP to PAS/SAT approaches. While it mentions BLACKBOX as a strong SAT-based planner, a more comprehensive comparison with other state-of-the-art planners (both SAT-based and direct search) would be valuable.
  • "Scruffy" vs. "Clean": The authors describe LPSP as a "scruffy" planner, implying that a more principled and general planner based on SLS techniques would be desirable. They also note that while their operators are interesting, integrating them into plan reuse and repair algorithms could be fruitful.

Summary updated

BibTeX
@inproceedings{1999encode,
  title = {{To Encode or not to Encode - I: Linear Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure