OMiGA - an open minded grounding on-the-fly answer set solver

Abstract

Answer Set Programming (ASP) is nowadays a well known and well acknowledged declarative problem solving paradigm. ASP originates from the area of artificial intelligence and is often used in knowledge-based reasoning and logic programming, where its main purpose is solving search and optimization problems. There are many solvers that solve ASP in a two-step manner, where they first ground the input program and then in the second step solve the resulting grounded program. From this approach one problem arises: the exponential blowup. In order to face this problem some answer set solvers use a grounding on-the-fly approach where rules are only grounded when needed during solving. Solvers that use this approach show that they indeed can solve some instances where standard solvers run out of memory. But on problem instances where exponential blow up is no issue, these solvers are much slower than standard solvers, because they have troubles finding applicable rules. Within this thesis we present the OMiGA solver, which combines the grounding on-the-fly approach with a Rete network, that enables us to efficiently find those rules and therefore outperform other grounding on-the-fly solvers and even compare to standard solvers on certain instances.