TL;DR
This paper introduces Limited Discrepancy Search (LDS), a novel tree search algorithm that intelligently explores paths deviating slightly from a heuristic's guidance. LDS offers a more effective way to find solutions when heuristics occasionally falter, outperforming traditional backtracking and random sampling methods.
What Problem Does This Paper Address?
Many real-world problems, like scheduling and planning, are solved using tree search. These methods rely on heuristics to guide the search towards promising areas of the solution space. While these heuristics are often very good, they aren't perfect and can sometimes lead the search down unproductive paths, causing it to miss solutions. When a heuristic fails, traditional approaches like chronological backtracking can be inefficient, either getting stuck exploring dead ends or randomly sampling the search space without leveraging the heuristic's partial success. This paper addresses the challenge of what to do when these powerful heuristics make a few "wrong turns."
Methods
The core contribution is Limited Discrepancy Search (LDS). The intuition behind LDS is that a failing heuristic might have succeeded if it had only made a small number of "wrong turns" (discrepancies) from its preferred path. LDS systematically explores paths that deviate from the heuristic's path by a limited number of discrepancies.
Here's how it works:
- Discrepancy Limit: LDS operates with a "discrepancy limit," starting at zero.
- Iterative Deepening: The algorithm iteratively increases this limit.
- Limit 0: This is equivalent to simply following the heuristic (like "1-samp").
- Limit 1: The search explores all paths that differ from the heuristic's path at exactly one decision point.
- Limit 2, 3, ...: The search expands to paths with two, three, or more discrepancies.
- LDS-PROBE: A recursive function that performs a depth-first search, keeping track of the number of discrepancies encountered.
- Guaranteed Termination: By increasing the discrepancy limit up to the maximum depth of the tree, LDS is guaranteed to find a solution if one exists and to terminate if none do.
LDS is compared against:
- 1-samp: Simply following the heuristic and giving up if it fails.
- Iterative Sampling (isamp): Randomly probing paths from the root until a solution is found.
- Chronological Backtracking (DPS): Backtracking to the most recent decision point when a dead end is reached.
Datasets
The paper evaluates LDS on a set of thirteen job shop scheduling problems taken from a survey of operations research techniques. These problems involve scheduling tasks with dependencies and resource constraints. The authors note that these problems are encoded using constraint satisfaction techniques, where variables represent resource contention (e.g., which job uses a machine first).
Key Insights and Ideas
- The "Wrong Turn" Hypothesis: The core idea that a few deviations from a good heuristic are often the reason for failure is a powerful insight. This reframes the problem from "the heuristic failed" to "the heuristic almost succeeded."
- Systematic Exploration of Near-Misses: LDS provides a principled way to explore these "near-miss" paths, offering a more intelligent alternative to random sampling or brute-force backtracking.
- Efficiency Gains: The iterative nature of LDS, combined with the fact that later iterations are much more expensive than earlier ones, means that finding a solution with a small number of discrepancies can yield significant computational savings.
- Heuristic Dependence: LDS's effectiveness is directly tied to the quality of the heuristic. Better heuristics lead to fewer discrepancies and faster solutions.
Key Results
- Theoretical Advantage: For problems with a good heuristic (high probability of correct choices), LDS can find solutions with significantly fewer nodes expanded compared to iterative sampling. For example, in a problem of height 100, LDS with a discrepancy limit of 20 found a solution in 2,000 nodes, while iterative sampling needed 2.6 million nodes for a 50% chance of success.
- Experimental Superiority: On the job shop scheduling benchmark, LDS consistently outperformed chronological backtracking and iterative sampling across various node limits.
- Combined Approaches: Combining LDS with bounded backtrack search (LDS-BBS) yielded the best performance among the tested systematic and nonsystematic methods, achieving results comparable to dedicated scheduling programs.
Limitations and Future Work
- Heuristic Quality: The paper acknowledges that LDS's performance is highly dependent on the quality of the heuristic. If the heuristic is poor, LDS may not offer significant advantages.
- Combinatorial Complexity: While LDS is guaranteed to find a solution, the cost of later iterations (higher discrepancy limits) can become very high. The authors suggest that in practice, only the early iterations (low discrepancy limits) are likely to be useful.
- Non-Boolean Problems: The paper primarily focuses on binary search trees (implicitly, due to the "two children" assumption). Extending LDS to problems with variables having domain sizes larger than 2 requires careful consideration of how to handle multiple alternative choices at each node.
- Future Work: The authors suggest exploring combinations of LDS with other techniques (like variable reordering, different heuristics, or bounded backtrack search) to craft more effective search procedures for specific real-world problems. They also note that further improvements in heuristics will likely benefit LDS significantly.
Summary updated