Title: Lazy model expansion: Interleaving grounding with search
Authors: De Cat, Broes # ×
Denecker, Marc
Stuckey, Peter #
Bruynooghe, Maurice #
Issue Date: Feb-2015
Publisher: AI Access Foundation
Series Title: The Journal of Artificial Intelligence Research vol:52 pages:235-286
Abstract: Finding satisfying assignments for the variables involved in a
set of constraints can be cast as a (bounded) model generation
problem: search for (bounded) models of a theory in some
logic. The state-of-the-art approach for bounded model generation
for rich knowl- edge representation languages like Answer Set
Programming (ASP) and FO(·) and a CSP modeling language such as
Zinc, is ground-and-solve: reduce the theory to a ground or
propositional one and apply a search algorithm to the resulting
theory. An important bottleneck is the blow-up of the size of
the theory caused by the grounding phase. Lazily grounding the
theory during search is a way to overcome this bottleneck. We
present a theoretical framework and an implementation in the
context of the FO(·) knowledge representation language. Instead
of grounding all parts of a theory, justifications are derived
for some parts of it. Given a partial assignment for the grounded
part of the theory and valid justifications for the formulas of
the non-grounded part, the justifications provide a recipe to
construct a complete assignment that satisfies the non-grounded
part. When a justification for a particular formula becomes
invalid during search, a new one is derived; if that fails, the
formula is split in a part to be grounded and a part that can be
justified. Experimental results illustrate the power and
generality of this approach.
ISSN: 1076-9757
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
lazygrounding.pdfOA article Published 643KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science