15. – 20. September 2002, Dagstuhl Seminar 02381
Nonmonotonic Reasoning, Answer Set Programming and Constraints
Auskunft zu diesem Dagstuhl Seminar erteilt
Scientific Highlights of the Event
Answer set programming is an emerging programming/problem solving paradigm. The fundamental underlying idea is to describe a problem declaratively in such a way that models of the description provide solutions to problems. One particular instance of this paradigm are logic programs under stable model semantics (respectively answer set semantics if an extended class of logic programs is used). Tremendous progress has been made recently in this area concerning both the theoretical foundations of the approach and implementation issues. Several highly efficient systems are available now which make it possible to investigate some serious applications.
The talks of the workshop were centered around the following main research topics:
- Useful language extensions and their theoretical foundations, with a particular focus on cardinality, weight and other types of constraints.
- Preferences in answer set programming and their implementation, where the preferences considered are among rules, among literals, or among disjuncts in heads of rules.
- Implementation techniques for answer set solvers. Several new methods or improvements of existing methods were presented, some of them based on highly efficient existing satisfiability solvers.
- New attempts to handle programs with variables. Existing solvers produce the ground instantiation of a program before computing answer sets and disallow function symbols. More flexible and less space consuming techniques are needed for large applications.
- Applications of the answer set paradigm in planning, scheduling, linguistics etc.
In addition to the talks a system competition took place during the workshop. Five systems participated in the competition, namely dlv (TU Vienna/Univ. Calabria), Smodels (Helsinki UT), ASSAT (UST HongKong), cmodels (UT Austin) and aspps (University of Kentucky). In a meeting at the beginning of the seminar the participants agreed about the benchmark problems to be used in the competition. The problems were encoded and tested and results presented in a plenary session at the end of the week.
Another topic of interest was standardization. There was an panel on the subject followed by open discussion. A general feeling was that the matter of standardization is a topic that requires a thorough attention on the part of the community in the near future.
Among the participants of the workshop were 11 young researchers, most of them PhD students. The students were allotted the same amount of time as everybody else for their talks to make sure they received enough attention from senior scientists. For many of the students it was the first time they presented their results/projects to an international audience. The students had a chance to discuss with world leading researchers in their area. This will certainly have an impact on their future work.
European added value
It is fair to say that in the field of answer set programming, and in particular in implementing advanced answer set solvers, Europe is currently on par with research in North America, if not leading. There is a number of European research groups active in this area. The EC just started to fund a Working Group on Answer Set Programming. The major goals of the Working group are the further advancement of the theoretical understanding of ASP (this includes the investigation of new potentially useful language constructs and their semantics), the further development of efficient advanced reasoning systems which make ASP techniques widely available (this includes the development of front ends for specific application problems), and the investigation of the applicability of ASP to areas such as planning, configuration, encryption, verification, knowledge extraction and others.
During the seminar the kickoff meeting of the working group took place, and the members had an excellent opportunity to get first hand information about current research developments in each group.
Given the numerous application areas for which promising answer set programming solutions already exist today, we expect tremendous economic benefit of this research. The seminar was important to keep Europe at the forefront of research in this area.
Answer set programming is a new declarative programming methodology. The basic idea is that programmers, rather than having to specify how a computer should solve a problem, just describe what the problem is. Each model of the problem description then provides a possible solution to the problem. The exact notion of a model used here depends on the language used for describing problems, but in all cases the models (also called answer sets in this context) can be thought of as sets of facts representing what is true and what is false.
Although theoretical foundations have been laid and some highly efficient implemented systems are available, there are still numerous challenging scientific questions which need to be answered: improved implementation techniques, extensions of the declarative languages which facilitate the problem description, methods for applying these techniques to problems like planning, scheduling, configuration etc. Contributions to all of these topics were presented and discussed during the seminar.