ECAI-2002 Conference Paper

[full paper]

Progressive Focusing Search

Nicolas Prcovic, Bertrand Neveu

This paper deals with value ordering heuristics used in a complete tree search algorithm. Their aim is to guide the search towards a solution. First, we show the limits of the traditional prospective approach, which uses the size of the domains of the still unassigned variables. In a very advantageous context, where arc consistency is maintained and allows the time spent by the dynamic value ordering to be negligible, the speedup is poor when the problems are hard. Then, we present a new value ordering heuristic based on a learning from failure scheme. Instead of making a choice a priori, an interleaving search follows every sub-tree to gather information. After this learning phase, the algorithm focuses on the most promising one. This new algorithm, named Progressive Focusing Search, is compared to Interleaved Depth First Search and appears to be efficient for problems on the phase transition complexity peak.

Keywords: Constraint Satisfaction, Search

Citation: Nicolas Prcovic, Bertrand Neveu: Progressive Focusing Search. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.126-130.