This research, originally presented at IJCAI-16, bridges a critical gap between two powerful search paradigms: Limited Discrepancy Search (LDS) and AND/OR search spaces. By generalizing LDS to operate within the structured environment of AND/OR trees, the authors provide a more robust and efficient framework for solving complex optimization problems in Graphical Models.
The Challenge: Fragility in Heuristic Search
Many high-stakes AI problems—including genetic linkage analysis, resource scheduling, and probabilistic planning—are modeled as optimization tasks over Graphical Models. Traditionally, these are tackled using Depth-First Search (DFS) guided by a heuristic, which acts as a "best guess" for the next move.
However, DFS is notoriously fragile. If a heuristic makes an incorrect choice at the top of a search tree, the algorithm can spend hours exploring a fruitless branch before realizing its mistake. Limited Discrepancy Search (LDS) was developed to mitigate this by systematically allowing a small number of "discrepancies" (moves that go against the heuristic) early in the search process.
The limitation of standard LDS is that it operates on OR trees, where every node represents a decision. This approach ignores the inherent structure of many real-world problems that can be decomposed into independent sub-problems. While AND/OR trees capture this "divide and conquer" structure, applying discrepancy logic to them was not straightforward until this work.
Methods: Introducing LDSAO
The authors propose LDSAO (Limited Discrepancy AND/OR search), which brings the robustness of LDS to the efficiency of AND/OR tree decompositions. The core innovation lies in the redefinition of discrepancies for structured trees:
- AND/OR Structure: In this model, an OR node represents a choice (e.g., a variable assignment), while an AND node represents a decomposition into independent sub-problems that must all be solved.
- Defining Discrepancies: In an AND/OR tree, a solution is itself a tree rather than a single path. The authors define the discrepancy of a solution as the maximum number of right turns (moves against the heuristic) found on any single path from the root to a leaf.
- The Multiplicative Effect: In a standard OR tree, one discrepancy allows for one alternative path. In an AND/OR tree, because sub-problems are independent, a single discrepancy budget allows the algorithm to explore alternatives in every independent branch simultaneously. This allows LDSAO to visit a much larger and more diverse region of the search space for the same computational "cost."
Experimental Evaluation
The authors evaluated LDSAO against standard LDS using six diverse benchmarks from the Graphical Models field, including satellite scheduling (SPOT5), combinatorial auctions, and complex biological inheritance models (Type4 Pedigrees). These instances were drawn from the UAI and Pascal competition sets.
Key Results
The experiments demonstrated a significant advantage for the AND/OR approach:
- Superior Solution Quality: In nearly all benchmarks, LDSAO found higher-quality solutions (lower upper-bounds for min-sum problems) than standard LDS within the same one-hour CPU time limit.
- Increased Iteration Speed: LDSAO completed its search iterations much faster. For instance, in the
Spot5benchmark, LDSAO finished its third iteration ($k=3$) in just 20 seconds, compared to 400 seconds for standard LDS. - Search Breadth: LDSAO acts as a more powerful version of the original algorithm; it visits all assignments that LDS would, plus many more, without adding significant overhead.
Conclusion and Future Directions
LDSAO successfully leverages problem structure to "hedge its bets" across multiple sub-problems early in the search, making it less likely to get trapped in a single bad branch. While the current version requires a static variable ordering (a "pseudo-tree"), future work may explore dynamic ordering or "breadth rotation" schemes to prevent difficult sub-problems from stalling the overall search. The authors suggest that this AND/OR discrepancy logic could be widely applicable to other domains, such as probabilistic planning, where independent sub-structures are common.
Summary updated