Joint and LPA*: Combination of Approximation and Search

Daniel Ratner, Ira PohlAAAI 1986

Abstract

Finding optimal solutions for NP-hard combinatorial problems, such as the N-puzzle or the Traveling Salesman Problem, is often computationally prohibitive. Traditional approaches typically force a choice between fast but suboptimal approximation algorithms and slow but optimal heuristic searches. This paper introduces a middle-ground strategy through two algorithms: Joint and Local Path A (LPA). These methods utilize an initial approximated path as a "rough draft" and apply localized A* searches to refine and shorten the path. Experimental results on the 15-puzzle demonstrate that this hybrid approach can produce high-quality solutions with a fraction of the computational cost required by global optimal solvers.

Introduction

In the realm of combinatorial optimization, researchers frequently encounter a trade-off between solution quality and computational feasibility. Approximation algorithms offer polynomial-time performance but often yield excessively long or "messy" paths. Conversely, heuristic search algorithms like A* guarantee optimality but suffer from exponential growth in time and memory requirements as problem complexity increases.

Presented at AAAI-86, Ratner and Pohl's work addresses this gap. They propose that instead of seeking global optimality from scratch, one can start with a "good enough" solution and use targeted local searches to polish it. This approach ensures that the total computation remains bounded by a polynomial function of the problem size while significantly improving the quality of the final output.

Methodology

The core of the proposed strategy involves treating an approximated path as a baseline for local optimization. The authors introduce two primary algorithms to implement this philosophy.

Local Path A (LPA)

LPA employs a sliding window mechanism. It traverses the initial approximated path, selecting segments of a fixed maximum length, $d_{max}$. For each segment, it performs a local A search to find a shorter alternative. If a shortcut is found, the original segment is replaced. A parameter $\delta_{anchor}$ controls the step size of the sliding window, determining how far the search advances after each iteration.

The Joint Algorithm

The Joint algorithm is based on the observation that in many approximation schemes—such as those using macro-operators—the most significant inefficiencies occur at "joints," the points where the algorithm transitions between different sub-goals. The algorithm first partitions the path into optimal segments of length $d_{max}$. It then focuses its local search efforts specifically on the nodes connecting these segments, smoothing out the transitions to eliminate unnecessary moves.

The Joint algorithm identifies "joints" in the approximated path and performs local searches to replace inefficient segments with shorter paths.

Post-Processing and Initial Approximation

To further refine results, a "Squeeze" process is used to identify and remove trivial cycles (e.g., a sequence of moves that returns the puzzle to a previous state). For the initial approximation, the authors utilize Korf’s Macro-Operator algorithm, which solves the puzzle by reaching a sequence of sub-goals. While fast, this method typically results in very long paths that are ripe for optimization.

Experimental Results

The algorithms were benchmarked using a standard set of 50 randomly generated 15-puzzle problems. Two admissible heuristics were tested: $h_1$ (Manhattan distance) and $h_2$ (Manhattan distance plus a penalty for tile reversals).

The hybrid approach yielded impressive gains in both efficiency and path quality. While an optimal solver like Iterative Deepening A might expand upwards of 50 million nodes to solve a single 15-puzzle instance, the Joint and LPA algorithms achieved high-quality results by expanding only 6,000 to 12,000 nodes.

Performance metrics for the LPA* algorithm using the $h_2$ heuristic, showing solution length and node expansion across various $d_{max}$ and $\delta_{joint}$ settings.

Key insights from the experiments include:

  • Path Quality: Initial macro-operator paths averaged 143 moves. After applying the "Squeeze" and local search optimizations, average path lengths dropped to approximately 86 moves.
  • Heuristic Impact: The more informed $h_2$ heuristic roughly halved the number of nodes expanded compared to $h_1$ without compromising solution quality.
  • Reliability: Unlike other heuristic methods of the time, such as HPA, which often failed to find solutions within time limits, Joint and LPA* consistently produced "reasonable" paths.

Conclusion

The Joint and LPA* algorithms represent a powerful paradigm for practical problem-solving. By localizing the NP-hardness of search to small, constant-distance segments, the authors transform a globally exponential problem into a series of manageable local tasks. While the final solution quality depends on the initial approximation and the topology of the state-space graph, these methods offer a robust alternative for applications where speed and "good enough" solutions are prioritized over absolute optimality. Future work may involve automating parameter tuning for $d_{max}$ and exploring applications in domains with different graph characteristics.

Summary updated

BibTeX
@inproceedings{ratner1986joint,
  author = {Daniel Ratner and Ira Pohl},
  title = {{Joint and LPA*: Combination of Approximation and Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure