Browsing by Subject "Logic programming"
Now showing 1 - 11 of 11
Results Per Page
Sort Options
Item Answer set based design of highly autonomous, rational agents(Texas Tech University, 2005-12) Balduccini, MarcelloAnswer set programming is a knowledge representation methodology that combines a high level of abstraction and direct computability. This dissertation shows how complex rational agents can be built with the answer set programming methodology and the associated languages. We describe the design of agents capable of fairly sophisticated reasoning, including planning, diagnosis, inductive learning. More precisely, we show reasoning algorithms that, given a formal description of the domain, allow the agent to: * generate plans, expected to achieve the agent's goal under reasonable assumptions; * monitor the execution of actions and detect unexpected observations; * explain unexpected observations by: - hypothesizing that some event occurred, unobserved, in the past; - modifying the original description of the domain to match the observations. The reasoning approach is model-based, with the domain model written in action language AL, and shared by all the reasoning components. The ability to use a single model for all the types of reasoning demonstrates the flexibility deriving from the use of answer set programming. Moreover, having a single model increases the ease of development, update and reuse of the domain description. For the actual computation, the domain model is translated into A-Prolog using a novel encoding from AL into A-Prolog. The encoding differs from the previous ones in that it extracts, from the model in AL, information that support not only planning and diagnosis, but also learning. Two sets of reasoning components are presented. The first set is developed using A-Prolog. We demonstrate that the components in this set are capable of fairly sophisticated reasoning. Next, we show how the approach can be extended to substantially improve the quality of reasoning. For this, we develop CR-Prolog, a language in which A-Prolog is augmented by consistency-restoring rules (cr-rules) and preferences. The new constructs allow the encoding of qualitative preferences on the solutions of reasoning problems. The second set of reasoning components is obtained by extending the basic ones to allow the specification of preferences. This allows to reason, for example, about plans satisfying, if at all possible, a collection of requirements, about most likely diagnoses, and about most reasonable modifications of domain models. We demonstrate how the quality of reasoning performed by this set of components is substantially higher than that of the basic ones. Since the reasoning techniques sometimes depend on whether the domain model is deterministic or non-deterministic, we also present a sufficient condition for the determinism of action descriptions. We show that the condition can be checked in polynomial time, and describe an A-Prolog program that performs the test.Item Answer set based design of highly autonomous, rational agents(2005-12) Balduccini, Marcello; Gelfond, Michael; Baral, Chitta; Barry, Matthew; Lifschitz, Vladimir; Watson, RichardAnswer set programming is a knowledge representation methodology that combines a high level of abstraction and direct computability. This dissertation shows how complex rational agents can be built with the answer set programming methodology and the associated languages. We describe the design of agents capable of fairly sophisticated reasoning, including planning, diagnosis, inductive learning. More precisely, we show reasoning algorithms that, given a formal description of the domain, allow the agent to: * generate plans, expected to achieve the agent's goal under reasonable assumptions; * monitor the execution of actions and detect unexpected observations; * explain unexpected observations by: - hypothesizing that some event occurred, unobserved, in the past; - modifying the original description of the domain to match the observations. The reasoning approach is model-based, with the domain model written in action language AL, and shared by all the reasoning components. The ability to use a single model for all the types of reasoning demonstrates the flexibility deriving from the use of answer set programming. Moreover, having a single model increases the ease of development, update and reuse of the domain description. For the actual computation, the domain model is translated into A-Prolog using a novel encoding from AL into A-Prolog. The encoding differs from the previous ones in that it extracts, from the model in AL, information that support not only planning and diagnosis, but also learning. Two sets of reasoning components are presented. The first set is developed using A-Prolog. We demonstrate that the components in this set are capable of fairly sophisticated reasoning. Next, we show how the approach can be extended to substantially improve the quality of reasoning. For this, we develop CR-Prolog, a language in which A-Prolog is augmented by consistency-restoring rules (cr-rules) and preferences. The new constructs allow the encoding of qualitative preferences on the solutions of reasoning problems. The second set of reasoning components is obtained by extending the basic ones to allow the specification of preferences. This allows to reason, for example, about plans satisfying, if at all possible, a collection of requirements, about most likely diagnoses, and about most reasonable modifications of domain models. We demonstrate how the quality of reasoning performed by this set of components is substantially higher than that of the basic ones. Since the reasoning techniques sometimes depend on whether the domain model is deterministic or non-deterministic, we also present a sufficient condition for the determinism of action descriptions. We show that the condition can be checked in polynomial time, and describe an A-Prolog program that performs the test.Item Detecting suspicious input in intelligent systems using answer set programming(Texas Tech University, 2005-05) Gianoutsos, Nicholas; Gelfond, Michael; Rushton, J. Nelson; Watson, RichardWhen presented with bad information people tend to make bad decisions. Even a rational person is unable to consistently make good decisions when presented with unsound information. The same holds true for intelligent agents. If at any point an agent accepts bad information into his reasoning process, the soundness of his decision making ability will begin to corrode. The purpose of this work is to develop programming methods that give intelligent systems the ability to handle potentially false information in a reasonable manner. In this research, we propose methods for detecting unsound information, which we call outliers, and methods for detecting the sources of these outliers. An outlier is informally defined as an observation or any combination of observations that are outside the realm of plausibility of a given state of the environment. With such reasoning ability, an intelligent agent is capable of not only learning about his environment, but he is also capable of learning about the reliability of the sources reporting the information. Throughout this work we introduce programming methods that enable intelligent agents to detect outliers in input information, as well as, learn about the accuracy of the sources submitting information.Item Detecting suspicious input in intelligent systems using answer set programming(2005-05) Gianoutsos, Nicholas; Gelfond, Michael; Rushton, J. Nelson; Watson, RichardWhen presented with bad information people tend to make bad decisions. Even a rational person is unable to consistently make good decisions when presented with unsound information. The same holds true for intelligent agents. If at any point an agent accepts bad information into his reasoning process, the soundness of his decision making ability will begin to corrode. The purpose of this work is to develop programming methods that give intelligent systems the ability to handle potentially false information in a reasonable manner. In this research, we propose methods for detecting unsound information, which we call outliers, and methods for detecting the sources of these outliers. An outlier is informally defined as an observation or any combination of observations that are outside the realm of plausibility of a given state of the environment. With such reasoning ability, an intelligent agent is capable of not only learning about his environment, but he is also capable of learning about the reliability of the sources reporting the information. Throughout this work we introduce programming methods that enable intelligent agents to detect outliers in input information, as well as, learn about the accuracy of the sources submitting information.Item Efficient SAT-based answer set solver(Texas Tech University, 2007-12) Lin, ZhijunRecent research shows that SAT (propositional satisfiability) techniques can be employed to build efficient systems to compute answer sets for logic programs. ASSAT and CMODELS are two well-known such systems that work on normal logic programs. They find an answer set from the full models for the completion of the input program, which is (iteratively) augmented with loop formulas. Making use of the fact that, for non-tight programs, during the model generation, a partial assignment may be extensible to a full model but may not grow into any answer set, we propose to add answer set extensibility checking on partial assignments. Furthermore, given a partial assignment, we identify a class of loop formulas that are "active'' on the assignment. These "active'' formulas can be used to prune the search space. We also provide an efficient method to generate these formulas. These ideas can be implemented with a moderate modification on SAT solvers. We have developed a new answer set solver SAG on top of the SAT solver MCHAFF. Empirical studies on well-known benchmarks show that in most cases it is faster than the state-of-the-art answer set solvers, often by an order of magnitude. For disjunctive logic programs, the existing SAT-based solvers translate them into propositional formulas based on a complex completion definition, and then make use of loop formulas and SAT solvers to find answer set. In this paper we present a new approach that allows the translation of a program into a formula that is weaker but less complex than the completion. It performs answer set checking on partial assignments. In case a partial assignment is inextensible to an answer set, we use support formulas, which is a generalization of loop formula, to prevent the repetition of the same mistake. Empirical studies on disjunctive logic programs confirm the performance advantage of the new approach.Item IMPROVING EFFICIENCY OF SOLVING COMPUTATIONAL PROBLEMS WITH ASP(2010-12) Morales, Ricardo; Gelfond, Michael; Watson, Richard; Zhang, YuanlinAnswer 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.Item Integrating ASP and CLP systems: computing answer sets from partially ground programs(Texas Tech University, 2007-12) Mellarkod, Veena S.; Gelfond, Michael; Watson, Richard; Zhang, Yuanlin; Son, Tran CaoAnswer set programming (ASP) has emerged as a declarative paradigm for knowledge representation and reasoning. In this approach, a logic program is used to represent the knowledge of the domain and various tasks are reduced to computing answer sets of this program. ASP languages A-Prolog and CR-Prolog have been proven as powerful tools for constructing complex reasoning systems. Constraint logic programming (CLP) emerged as an alternate paradigm through the fusion of logic programming and constraint solving. A CLP solver thus integrates resolution techniques from logic programming and constraint solving techniques from constraint satisfaction. While ASP is expressive for knowledge representation and reasoning, CLP solvers are efficient in reasoning with numerical constraints. Every state-of-the-art ASP solver computes answer sets of programs from their ground equivalents. Though these systems solve large industrial problems, the ground programs become huge and unmanageable. This is especially true when programs contain variables that range over large numerical domains; huge memory requirements eventually force the solvers to fail. The goal of this research is to address this issue by integrating different types of reasoning techniques to compute answer sets of programs. First, we investigate the integration of answer set reasoning, a form of abduction, and constraint solving techniques. We design a collection of languages, V(C), parameterized over a class C of constraints. An instance ACo from this family is studied as a knowledge representation tool. An algorithm to compute answer sets of ACo programs is developed. An ACo solver is built that computes answer sets from partially ground programs. The use of this language and the efficiency of the solver are demonstrated. We extend our investigation to develop methods to include resolution techniques. We design a collection of languages AC(C) parameterized over a class C of constraints. We develop an algorithm to compute answer sets of AC(C) programs from their partial ground instances by integrating the four reasoning techniques and prove correctness. A solver is built to compute answer sets for a class of AC(C) programs. Our work is a significant step to declaratively solve problems that cannot be solved by pure ASP or CLP solvers. The solvers built are the first to tightly integrate different reasoning techniques to compute answer sets from partial ground programs.Item Integrating top-down and bottom-up approaches in inductive logic programming: applications in natural language processing and relational data mining(2003) Tang, Lap Poon Rupert; Mooney, Raymond J. (Raymond Joseph)Item Optimizing the computation of stable models using merged rules(Texas Tech University, 2002-05) Mellarkod, Veena S.Recently, logic programs under the stable model semantics, have emerged as a new paradigm for declarative programming. In this new approach, a logic program is used to represent the knowledge of the domain, and various tasks are reduced to computing the stable models of this program. This paradigm has been successfully used in a wide range of applications including planning, diagnostics, graph problems, etc. The basic algorithm for computing stable models is implemented by several efficient systems. The most efficient implementation to date is called Smodels. Even though Smodels was demonstrated to be capable of solving several large industrial problems, there are some simple logic programs for which Smodels' performance is unexpectedly slow. This problem is not related to the implementation. Rather, it is the result of the one rule at a time inference used by the basic algorithm. The goal of this work is to improve the efficiency of the basic algorithm extending the set of inference rules with a new rule called the Extended Evaluation Rule (EER). EER efficiently retrieves information spread across several rules of a program. An algorithm, newsmodels, was developed incorporating the EER. A system Surya, based on the newsmodels algorithm was implemented. It was found that the EER considerably improves the efficiency of the system.Item Representing actions in logic-based languages(2014-05) Yang, Fangkai; Lifschitz, VladimirKnowledge about actions is an important part of commonsense knowledge studied in Artificial Intelligence. For decades, researchers have been developing methods for describing how actions affect states of the world and for automating reasoning about actions. In recent years, significant progress has been made. In particular, the frame problem has been solved using nonmonotonic knowledge representation formalisms, such as logic programming under the answer set semantics. New theories of causality have allowed us to express causal dependencies between fluents, which has proved essential for solving the ramification problem. It has been shown that reasoning about actions described by logic programs and causal theories can be automated using answer set programming. Action description languages are high level languages that allow us to represent knowledge about actions more concisely than when logic programs are used. Many action description languages have been described in the literature, including B, C, and C+. Reasoning about dynamic domains described in languages C and C+ can be performed automatically using the Causal Calculator (CCalc), which employs SAT solvers for search, and the systems coala and cplus2asp, which employ answer set solvers such as clingo. The dissertation addresses problems of three kinds. First, we study some mathematical properties of expressive action languages based on nonmonotonic causal logic that were not well understood until now. This includes causal rules expressing synonymy, nondefinite causal rules, and nonpropositional causal rules. We generalize existing translations from nonmonotonic causal theories to logic programming under the answer set semantics. This makes it possible to automate reasoning with a wider class of causal theories by calling answer set solvers. Second, we design and study a new action language BC, which is more expressive in some ways than the existing and previously proposed languages. We develop a framework that combines the most useful expressive features of the languages B and C+, and use program completion to characterize the effects of actions described in these languages. Third, we illustrate the possibilities of the new action language by two practical applications: to the dynamic domain of the Reactive Control System of the space shuttle, and to the task planning of mobile robots.Item SAT-based answer set programming(2010-05) Lierler, Yuliya; Lifschitz, Vladimir; Boyer, Robert; Gal, Anna; Stone, Peter; Truszczynski, MiroslawAnswer set programming (ASP) is a declarative programming paradigm oriented towards difficult combinatorial search problems. Syntactically, ASP programs look like Prolog programs, but solutions are represented in ASP by sets of atoms, and not by substitutions, as in Prolog. Answer set systems, such as Smodels, Smodelscc, and DLV, compute answer sets of a given program in the sense of the answer set (stable model) semantics. This is different from the functionality of Prolog systems, which determine when a given query is true relative to a given logic program. ASP has been applied to many areas of science and technology, from the design of a decision support system for the Space Shuttle to graph-theoretic problems arising in zoology and linguistics. The "native" answer set systems mentioned above are based on specialized search procedures. Usually these procedures are described fairly informally with the use of pseudocode. We propose an alternative approach to describing algorithms of answer set solvers. In this approach we specify what "states of computation" are, and which transitions between states are allowed. In this way, we define a directed graph such that every execution of a procedure corresponds to a path in this graph. This allows us to model algorithms of answer set solvers by a mathematically simple and elegant object, graph, rather than a collection of pseudocode statements. We use this abstract framework to describe and prove the correctness of the answer set solver Smodels, and also of Smodelscc, which enhances the former using learning and backjumping techniques. Answer sets of a tight program can be found by running a SAT solver on the program's completion, because for such a program answer sets are in a one-to-one correspondence with models of completion. SAT is one of the most widely studied problems in computational logic, and many efficient SAT procedures were developed over the last decade. Using SAT solvers for computing answer sets allows us to take advantage of the advances in the SAT area. For a nontight program it is still the case that each answer set corresponds to a model of program's completion but not vice versa. We show how to modify the search method typically used in SAT solvers to allow testing models of completion and employ learning to utilize testing information to guide the search. We develop a new SAT-based answer set solver, called Cmodels, based on this idea. We develop an abstract graph based framework for describing SAT-based answer set solvers and use it to represent the Cmodels algorithm and to demonstrate its correctness. Such representations allow us to better understand similarities and differences between native and SAT-based answer set solvers. We formally compare the Smodels algorithm with a variant of the Cmodels algorithm without learning. Abstract frameworks for describing native and SAT-based answer set solvers facilitate the development of new systems. We propose and implement the answer set solver called SUP that can be seen as a combination of computational ideas behind Cmodels and Smodels. Like Cmodels, solver SUP operates by computing a sequence of models of completion of the given program, but it does not form the completion. Instead, SUP runs the Atleast algorithm, one of the main building blocks of the Smodels procedure. Both systems Cmodels and SUP, developed in this dissertation, proved to be competitive answer set programming systems.