Limited Discrepancy Search and Weighted Discrepancy Search
In solving a very large problem heuristics, or rules of thumb, are
used. Heuristics guide the search toward regions of the space that
are likely to contain solutions. Heuristic search is subject to the
"e;early mistakes"e; problem. Traditional backtracking
strategies, like Depth First Search, usually do not recover from early
mistakes in time. If the number of wrong turns is small, they can be
discovered by systematically searching all paths that differ from the
heuristic path in at most a small number of decision points or
discrepancies. LDS searches the space in order of increasing
discrepancy count, i.e., it searches the heuristic path first, then
all paths that disagree with the heuristic in at most one decision,
then two, etc. until it finally explores the whole search space.
Because LDS eventually explores the whole search space, LDS is
guaranteed to find a solution to the problem or prove that no solution
exists. LDS can be applied to any search problem where one branch
from each node is preferred to its siblings. In the case of a
non-binary tree, every child that is not preferred by the heuristic is
a discrepancy.
CIRL
Limited Discrepancy Search was discovered at CIRL. It has been proven
that LDS has a much greater chance of finding a solution in a limited
amount of time than alternative approaches. LDS has been the subject
of numerous papers by other researchers in the field. LDS has been
generalized to the case where the heuristic preference is a fractional
weight instead of just a 0-1 decision. In weighted discrepancy
search, the space is searched in order of decreasing weight instead of
increasing number of discrepancies. Only nodes with weight greater
than or equal to the cutoff are explored in each iteration. We have
derived a method to obtain optimal cutoff policies for WDS.
LDS and WDS are part of an application software developed at CIRL to
schedule the assembly of aircraft for Mc Donnell Douglas (now Boeing).
We have found the shortest known schedule for this problem using a
scheduler which combines LDS with a technique called
schedule packing.
Pointers
-
Limited Discrepancy Search.
- This article presents Limited Discrepancy Search a heuristic search
backtracking method, developed by Will Harvey and Matt Ginsberg. Appeared in
Proc. IJCAI in 1995. Compressed postscript document.
-
Nonsystematic Backtracking Search
- This thesis by Will Harvey describes not only LDS but also other
backtracking search techniques. PhD Thesis, Stanford
University, 1995. Compressed postscript document.
- Parent areas:
- Systematic Methods
- Implementation:
- Aircraft Assembly
Back to the CIRL Overview Page.