On the Discovery and Generation of Certain Heuristics

Judea Pearl

Abstract


This paper explores the paradigm that heuristics are discovered by consulting simplified models of the problem domain. After describing the features of typical heuristics on some popular problems, we demonstrate that these heuristics can be obtained by the process of deleting constraints from the original problem and solving the relaxed problem which ensues. We then outline a scheme for generating such heuristics mechanically, which involves systematic refinement and deletion of constraints from the original problem specification until a semidecomposable model is identified. The solution to the latter constitutes a heuristic for the former.

Full Text:

PDF


DOI: http://dx.doi.org/10.1609/aimag.v4i1.385

Copyright © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.