Since the early days of Artificial Intelligence, it has been recognized that problem reformulation is central to human reasoning and the ability of computer systems to reason effectively in complex domains. Reformulations have been used in a variety of problem-solving settings including automatic programming, constraint satisfaction, design, diagnosis, machine learning, planning, qualitative reasoning, scheduling and theorem proving. The primary use in such settings has been to overcome computational intractability by decreasing the combinatorial costs associated with searching large spaces. In addition, reformulation techniques are useful for knowledge acquisition and explanation generation in complex domains.
The considerable interest in reformulation has led to a series of successful workshops over the last few years. AAAI workshops in 1990 and 1992 focused on selecting, constructing and using abstractions and approximations, while a series of workshops in 1989, 1990 and 1992 focused on problem reformulations. There was considerable intersection in the set of attendees and topics of the two separate workshop series, and this lead to holding merged workshops in 1994, 1995, 1998 and 2000 (entitled "Symposia on Abstraction, Reformulation, and Approximation").
We are preparing a special issue of the journal Artificial Intelligence to bring together papers describing and extending the current state of the art in problem reformulation. Topics will include but not be limited to the following:
β’ techniques for automatically generating problem reformulations;
β’ methods for selecting which of several reformulations are best for a given problem;
β’ frameworks that unify and classify reformulation techniques;
β’ theoretical and/or empirical studies of the costs and benefits of reformulation;
β’ applications of reformulation: -