Computing weighted solutions in ASP: representation-based method vs. search-based method

Çakmak, Duygu and Erdem, Esra and Erdoğan, Halit (2011) Computing weighted solutions in ASP: representation-based method vs. search-based method. Annals of Mathematics and Artificial Intelligence (SI), 62 (3-4). pp. 219-258. ISSN 1012-2443 (Print) 1573-7470 (Online)

This is the latest version of this item.

[thumbnail of amai10_1aug10_v8.pdf] PDF
Restricted to Repository staff only

Download (375kB) | Request a copy


For some problems with too many solutions, one way to obtain the more desirable solutions is to assign each solution a weight that characterizes its importance quantitatively, and then compute the solutions whose weights are over (resp. below) a given threshold. This paper studies computing weighted solutions for a given computational problem, in the context of Answer Set Programming (ASP). In particular, we investigate two sorts of methods for computing weighted solutions: one method suggests modifying the ASP representation of the problem to compute weighted solutions using an existing ASP solver and the other suggests modifying the search algorithm of the answer set solver to compute weighted solutions incrementally. The applicability of these methods are shown on two sorts of problems: reconstructing weighted phylogenies (for Indo-European languages and for Quercus species) and finding weighted plans (for Blocks World planning problems). In the experiments with the representation-based method, the answer set solver clasp is used and weight functions are represented in ASP. For the search-based method, the algorithm of clasp is modified (the modified solver is called CLASP-W) and weight functions are implemented in C++. For phylogenies, two weight functions are introduced by incorporating domain-specific information about groupings of species; one of them cannot be represented in ASP due to some mathematical functions not supported by the ASP solvers. For plans, we define a weight function that characterizes the total cost of executing actions in a plan. In these experiments the following are observed. With weight measures that can be represented in ASP, the search-based method outperforms the representation-based method in terms of computational efficiency (both time and space). With weight functions that cannot be represented in ASP, the search-based method provides a tool for computing weighted solutions in ASP. The search-based method can be applied to different domains, without modifying the algorithm of CLASP-W; in that sense, the search-based method is modular and can be useful to other ASP applications. With either method, plausible phylogenies among many can be found without computing all phylogenies and requiring historical linguists to go over them manually, and less costly plans can be found without computing all plans; in that sense, our methods contribute to phylogenetics and AI planning studies as well.
Item Type: Article
Uncontrolled Keywords: Weighted solutions; Answer set programming; Weighted phylogenies; Weighted plans
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Esra Erdem
Date Deposited: 28 Dec 2011 12:28
Last Modified: 26 Apr 2022 08:53

Available Versions of this Item

Actions (login required)

View Item
View Item