Ghent University Academic Bibliography

Advanced

Foundations of fuzzy answer set programming

Jeroen Janssen UGent (2011)
abstract
Answer set programming (ASP) is a declarative language that is tailored towards combinatorial search problems. Although ASP has been applied to many problems, such as planning, configuration and verification of software, and database repair, it is less suitable for describing continuous problems. In this thesis we therefore studied fuzzy answer set programming (FASP). FASP is a language that combines ASP with ideas from fuzzy logic -- a class of many-valued logics that are able to describe continuous problems. We study the following topics: 1. An important issue when modeling continuous optimization problems is how to cope with overconstrained problems. In many cases we can opt to allow imperfect solutions, i.e. solutions that do not satisfy all constraints, but are sufficiently acceptable. However, the question which one of these imperfect solutions is most suitable then arises. Current approaches to fuzzy answer set programming solve this problem by attaching weights to the rules of the program. However, it is often not clear how these weights should be chosen and moreover weights do not allow to order different solutions. We improve upon this technique by using aggregators, which eliminate the aforementioned problems. This allows a richer modeling language and bridges the gap between FASP and other techniques such as valued constraint satisfaction problems. 2. The wishes of users and implementers of a programming language are often in direct conflict with each other. Users prefer a rich language that is easy to model in, whereas implementers prefer a small language that is easy to implement. We reconcile these differences by identifying a core language for FASP, called core FASP (CFASP), that only consists of non-constraint rules with monotonically increasing functions and negators in the body. We show that CFASP is capable of simulating constraint rules, monotonically decreasing functions, aggregators, S-implicators and classical negation. Moreover we remark that the simulations of constraints and classical negation bear a great resemblance to their simulations in classical ASP, which provides further insight into the relationship between ASP and FASP. 3. As a first step towards the creation of an implementation method for FASP we research whether it is possible to translate a FASP program to a fuzzy SAT problem. We introduce the concept of the completion of a FASP program and show that for programs without loops the models of the completion coincide with the answer sets. Furthermore we show that if a program has loops, we can translate the program to a fuzzy SAT problem by generalizing the concept of loop formulas. We illustrate this on a continuous version of the k-center problem. Such a translation is important because it allows us to solve FASP programs by means of solvers for fuzzy SAT. Under the appropriate conditions it is for example possible to solve FASP programs by means of off-the-shelf solvers for mixed integer programming (MIP).
Please use this url to cite or link to this publication:
author
promoter
Dirk Vermeir, UGent and UGent
organization
year
type
dissertation (monograph)
subject
keyword
fuzzy logic, answer set programming, fuzzy answer set programming
pages
220 pages
publisher
Ghent University. Faculty of Sciences ; Vrije Universiteit Brussel. Faculty of Science
place of publication
Ghent ; Brussels, Belgium
defense location
Gent : Campus Sterre (S9, auditorium A2)
defense date
2011-06-27 17:00
language
English
UGent publication?
yes
classification
D1
copyright statement
I have retained and own the full copyright for this publication
id
1844565
handle
http://hdl.handle.net/1854/LU-1844565
date created
2011-06-28 17:03:06
date last changed
2011-06-29 09:37:50
@phdthesis{1844565,
  abstract     = {Answer set programming (ASP) is a declarative language that is tailored towards combinatorial search problems. Although ASP has been applied to many problems, such as planning, configuration and verification of software, and database repair, it is less suitable for describing continuous problems. In this thesis we therefore studied fuzzy answer set programming (FASP). FASP is a language that combines ASP with ideas from fuzzy logic -- a class of many-valued logics that are able to describe continuous problems. We study the following topics:
 1. An important issue when modeling continuous optimization problems is how to cope with overconstrained problems. In many cases we can opt to allow imperfect solutions, i.e. solutions that do not satisfy all constraints, but are sufficiently acceptable. However, the question which one of these imperfect solutions is most suitable then arises. Current approaches to fuzzy answer set programming solve this problem by attaching weights to the rules of the program. However, it is often not clear how these weights should be chosen and moreover weights do not allow to order different solutions. We improve upon this technique by using aggregators, which eliminate the aforementioned problems. This allows a richer modeling language and bridges the gap between FASP and other techniques such as valued constraint satisfaction problems.
 2. The wishes of users and implementers of a programming language are often in direct conflict with each other. Users prefer a rich language that is easy to model in, whereas implementers prefer a small language that is easy to implement. We reconcile these differences by identifying a core language for FASP, called core FASP (CFASP), that only consists of non-constraint rules with monotonically increasing functions and negators in the body. We show that CFASP is capable of simulating constraint rules, monotonically decreasing functions, aggregators, S-implicators and classical negation. Moreover we remark that the simulations of constraints and classical negation bear a great resemblance to their simulations in classical ASP, which provides further insight into the relationship between ASP and FASP.
 3. As a first step towards the creation of an implementation method for FASP we research whether it is possible to translate a FASP program to a fuzzy SAT problem. We introduce the concept of the completion of a FASP program and show that for programs without loops the models of the completion coincide with the answer sets.
 Furthermore we show that if a program has loops, we can translate the program to a fuzzy SAT problem by generalizing the concept of loop formulas. We illustrate this on a continuous version of the k-center problem. Such a translation is important because it allows us to solve FASP programs by means of solvers for fuzzy SAT. Under the appropriate conditions it is for example possible to solve FASP programs by means of off-the-shelf solvers for mixed integer programming (MIP).},
  author       = {Janssen, Jeroen},
  keyword      = {fuzzy logic,answer set programming,fuzzy answer set programming},
  language     = {eng},
  pages        = {220},
  publisher    = {Ghent University. Faculty of Sciences ; Vrije Universiteit Brussel. Faculty of Science},
  school       = {Ghent University},
  title        = {Foundations of fuzzy answer set programming},
  year         = {2011},
}

Chicago
Janssen, Jeroen. 2011. “Foundations of Fuzzy Answer Set Programming”. Ghent ; Brussels, Belgium: Ghent University. Faculty of Sciences ; Vrije Universiteit Brussel. Faculty of Science.
APA
Janssen, Jeroen. (2011). Foundations of fuzzy answer set programming. Ghent University. Faculty of Sciences ; Vrije Universiteit Brussel. Faculty of Science, Ghent ; Brussels, Belgium.
Vancouver
1.
Janssen J. Foundations of fuzzy answer set programming. [Ghent ; Brussels, Belgium]: Ghent University. Faculty of Sciences ; Vrije Universiteit Brussel. Faculty of Science; 2011.
MLA
Janssen, Jeroen. “Foundations of Fuzzy Answer Set Programming.” 2011 : n. pag. Print.