ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Trying Again to Fail-First

J. Christopher Beck, Patrick Prosser, Richard Wallace

In ECAI 1998 Smith and Grant performed a study of the fail-first principle of Haralick and Elliott. The fail-first principle states that ``To succeed, try first where you are most likely to fail.'' For constraint satisfaction problems, Haralick and Elliott realized this principle by minimizing branch depth. Smith and Grant hypothesized that if failing first is a good thing, then more of it should be better. They devised a range of variable ordering heuristics, each in turn trying harder to fail first. They showed that trying harder to fail-first does not guarantee a reduction in search effort. We failed in our attempt to repeat that study. This was due to a implementation error for one of their heuristics. However, with this fix applied we show that Smith and Grant's conclusions were indeed correct: failing first does not invariably lead to greater overall efficiency. This is because minimizing branch depth sometimes involves large increases in the branching factor. We also show that the effects of trying harder to fail-first are algorithm dependent. Our results indicate that trying to fail is an important principle in search, and they suggest an alternative failure strategy that seeks to minimize the number of nodes in a subtree.

Keywords: search, constraint satisfaction

Citation: J. Christopher Beck, Patrick Prosser, Richard Wallace: Trying Again to Fail-First. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.959-960.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).