Lazy Grounding algorithms for Answer Set Programming
ID
MSCA-2020-BBogaerts01
Supervisors
Project description
Answer set programming (ASP) is a formalism in which combinatorial (optimization) problems can be modeled easily, due to a well- developed first-order modeling language. For this language, efficient solvers have been developed. Most of these solvers work in two phases: first the first-order variables are eliminated by a technique called grounding, second, a search algorithm for variable-free ASP is deployed to find the actual solutions to the original problem. While this often works well, recently the awareness grew of the fact that many problems exist in which the first step is not feasible (the grounding is too large and only small parts of it are relevant), calling for different solutions. One solution that stands out is integrating the two phases and only grounding those parts of the problem that are relevant for the search algorithm. This is referred to as lazy grounding.
Some lazy grounding solutions have been developed, but on many traditional problems they turn out to be far from efficient enough to compete with the traditional approach. The state-of-the art not just lacks competitive lazy grounding algorithms, but also a fundamental understanding of why there is such a big difference in speed. I want to analyze where those differences in speed come from and develop novel algorithms that overcome these weaknesses, thereby achieving the next big jump in answer set programming.
About the research Group
Artificial Intelligence Lab
The Artificial Intelligence Lab, founded in 1983 by Prof. Dr. Luc Steels, is the first AI lab on the European mainland. It is headed by Prof. Dr. Ann Nowé and Prof. Dr. Bernard Manderick. During its history of more than three decades, the VUB AI Lab has been following two main routes towards the understanding of intelligence: both the symbolic route (classical AI) as the dynamics route (complex systems science).
Since its foundation, more than 50 people have received a PhD degree at the Artificial Intelligence Lab, of which 18 in the past 5 years only. The total amount of publications sums up to more than 850 publications which are cited more than 24.000 times, 8500 times in the last 5 years. The lab also has experience in setting up of spin-offs (5 since its beginning). The research group is provided with standard hardware and software utilities and departmental services (secretary and ICT support). The COMO group of the AI-lab focuses on the one hand on the modeling of natural phenomena, and on the other hand on developing algorithms for complex problem solving inspired by these natural phenomena. The lab has experience in a wide range of learning techniques such as: Reinforcement Learning, Genetic Algorithms, Neural Networks, Support Vector Machines, Graphical models including Bayesian Networks, Genetic algorithms etc.