Proceedings

Limited Discrepancy Search

Download BibTeX Cite

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 607-614.

© 1995 International Joint Conferences on Artificial Intelligence

Abstract

Many problems of practical interest can be solved using tree search methods because carefully tuned successor ordering heuristics guide the search toward regions of the space that are likely to contain solutions. For some problems, the heuristics often lead directly to a solutionbut not always. Limited discrepancy search addresses the problem of what to do when the heuristics fail. Our intuition is that a failing heuristic might well have succeeded if it were not for a small number of "wrong turns" along the way. For a binary tree of height d, there are only d ways the heuristic could make a single wrong turn, and only d( d; 1 l ways it could make two. A small number of wrong turns can be overcome by systematically searching all paths that differ from the heuristic path in at most a small number of decision points, or "discrepancies." Limited discrepancy search is a backtracking algorithm that searches the nodes of the tree in increasing order of such discrepancies. We show formally and experimentally that limited discrepancy search can be expected to outperform existing approaches.

  1. [Cheng and Smith, 1994] C. Cheng and S. Smith. Gen- erating feasible schedules under complex metric con- straints. In Proc. of the Twelvth National Conference on Artificial Intelligence, 1994.
  2. [Crawford and Auton, 1993] J. Crawford and L. Auton. Experimental results on the crossover point in satisfi- ability problems. In Proc. 11th AAAI, 1993.
  3. [Crawford and Baker, 1994] J. Crawford and A. Baker. Experimental results on the application of satisfiabil- ity algorithms to scheduling problems. In Proc. 12th AAAI, 1994.
  4. [Harvey, 1994] W . Harvey. Search and job shop schedul- ing. Technical Report CIRL TR 94-1, CIRL, Univer- sity of Oregon, 1994.
  5. [Harvey, 1995] W. Harvey. Nonsystematic Backtracking Search. PhD thesis, Stanford University, 1995.
  6. [Langley, 1992] P. Langley. Systematic and nonsystem- atic search strategies. In Artificial Intelligence Plan- ning Systems: Proceedings of the First International Conference, 1992.
  7. [Smith and Cheng, 1993] S. Smith and C. Cheng. Slack- based heuristics for constraint satisfaction scheduling. In Proc. of the Eleventh National Conference on Ar- tificial Intelligence, 1993.
  8. [Vaessens et al., 1994] R. Vaessens, E. Aarts, and J. Lenstra. Job shop scheduling by local search. Tech- nical Report COSOR 94-05, Eindhoven University of Technology, 1994.
  9. [Wilkins, 1988] D. Wilkins. Practical Planning: Ex- tending the Classical AI Planning Paradigm. Morgan Kaufman, San Mateo, California, 1988.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards