Improving efficiency of solving computational problems with ASP

Date

2010-12

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Answer Set Programming (ASP) is a declarative programming paradigm for knowledge representation and reasoning. It can be used to represent and reason with recursive definitions, defaults and their exceptions, causal relations, beliefs, and various forms of incomplete information. ASP has been successfully used and applied to solve a variety of difficult (primarily NP-Hard) problems; however, sometimes finding solutions can be computationally expensive. Under the ASP methodology, a computational problem is encoded into a logic program that represents information relevant to the problem to be solved. The answer set semantics assigns to a program a collection of answer sets. Finding solutions to a problem is reduced to computing answer sets of the logic program that represent the problem. The goal of this research is to improve the efficiency of solving computational problems with ASP by: improving problem representation techniques and improving existing answer set solvers. We illustrate our our approaches by solving the problem of Conformant Planning. First, we developed new representation techniques for the Conformant Planning problem. Second, we identified and implemented algorithmic improvements on the prototype solver ACsolver. Conformant planning is a class of planning problems in which the planning agent is given incomplete information about the initial state of the planning domain and is asked to find a plan that will achieve a given goal regardless of the uncertainty present in the initial situation. Our proposed encoding methodology is based on the use of an approximation transition diagram, by which the resulting logic program is capable of correctly reasoning about the effects of actions in the presence of incomplete information. We show that our methodology is sound and under some circumstances complete, and that it extends the applicability and efficiency of ASP to this class of problems. In the second part of the dissertation we concentrate on improving the prototype solver ACsolver. ACsolver is a solver for the language AC(C) , an extension to ASP that combines ASP with Constraint Logic Programming (CLP). ACsolver's design allows it to solve problems that involve real number constraints. Such problems are beyond the reach of conventional ASP solvers. We investigated the algorithmic and implementation properties of ACsolver, and develop an algorithmic framework to design solvers of AC(C) that overcome the limitations of ACsolver's algorithm. We implemented an algorithm from this framework over ACsolver, to build an improved solver, luna, and demonstrated the improvements in efficiency experimentally. Furthermore, we apply both research goals to solve instances of conformant planning problems with numerical constraints.

Description

Keywords

Logic programming, Answer set programming (ASP), Confromant planning, Action languages, Constraint programming

Citation