Preface to RCRA 2008 Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion

After the enthusiasm of the fifties and early sixties, during which famous scientists predicted that computers would soon equal the human mind, Artificial Intelligence (A.I.) researchers had to face a bitter reality: many of the problems in A.I. have a combinatorial structure which requires the exploration of an exponential search space. The theory of NP-completeness added further discouragement to the great expectations of the previous decades. On the other hand, in the following years there was a plethora of new methodologies to address combinatorial problems that were published. Despite the discouraging complexity proofs based on worst-case analyses, practical algorithms were often able to address and solve real problems in reasonable time. Often, similar problems are solved with similar techniques in different branches of A.I., rediscovering the same solutions many times. Reducing this waste of energy is one of the aims of the RCRA group (Ragionamento Automatico e Rappresentazione della Conoscenza), the interest group of the Italian Association for Artificial Intelligence (AI*IA) on knowledge representation and automated reasoning, which organises its annual meetings since 1994. Since the 2005 edition it has focussed on the theme of algorithms in A.I., proposing benchmarks to compare them and evaluating the efficiency through experimental evaluation. These meetings have reached the objective to put together researchers coming from A.I. fields as diverse as constraint satisfaction, machine learning, logic languages, quanti- fied satisfiability, and planning, just to name a few. The event has gained more and more interest, first from the Italian community, then from the international one. In 2008 the workshop was co-located with the International Conference on Logic Programming and repeated the success of the previous years. This special issue proposes extended versions of a selection of the papers presented at RCRA 2008. The authors of the 18 papers selected for presentation at the workshop had the opportunity to submit to this issue and 8 were selected for publication.