Browsing by Subject "Answer set programming (ASP)"
Now showing 1 - 7 of 7
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 Answering questions about dynamic domains from natural language using ASP(2011-08) Todorova, Yana; Gelfond, Michael; Watson, Richard; Zhang, YuanlinAnswer Set Programming (ASP) is a knowledge representation methodology that has well-established theoretical foundations and good practical uses. The goal of my dissertation was to build an automatic system for answering non-trivial questions from texts in natural language. This is an important task, because the results are very useful in many areas. The final result of this work is an elaboration tolerant question answering system MQA capable of giving provably correct answers. We also used this research to test our reasoning techniques, such as reasoning in dynamic domains, where movement is involved, and reasoning about changes in cardinalities. The original discourse was written in our controlled language MCL , which allowed us to remove a variety of natural language phenomena and to focus on limited grammar rules and on a restricted vocabulary. For the actual reasoning, we used ASP, because of its nonmonotonic features, and its ability to represent defaults and dynamic domains. Thus, given a discourse and a question in our controlled natural language MCL, we first generated a new logic form representation. We represented the knowledge using action language ALM and we included background information not found in the original text. After that, we performed commonsense reasoning using ASP axioms. Finally, we obtained the correct and expected answer to the question.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 Logos Ex Machina: A reasoned approach toward Cancer(2012-05) Avila, Andrew; Gollahon, Lauren; Strauss, Richard E.; Rice, Sean H.; Butler, Boyd; Watson, RichardLimitations in our current ability to integrate a diverse spectrum of genetic information in an effort to elucidate the underlying causes of cancer has spawned the need for a novel cancer modeling approach. Public repositories of biological pathways and gene expression experiments were combined in order to provide a systems biology approach toward cancer. Furthermore, by unifying these sources of knowledge, the ability to predict expression levels of unmeasured genes was developed. This technique was then applied to a variety of cancer types in order to resolve commonalities between heretofore divergent (or disparate) cancers. The results generated in this manner revealed characteristics that challenge the current prevailing paradigm of cancer. Specifically, the predicted results, according to the Somatic Mutation Theory of Cancer, of a significant upregulation of oncogenes and a significant downregulation of tumor suppressor genes was not found. In contrast, it was found that oncogenes were significantly downregulated and tumor suppressor genes were upregulated among the cancers examined. Furthermore, the results demonstrate the differential expression, in cancer cells, of genes involved in the cellular differentiation and wound healing processes. These results were used as a springboard to develop a novel oncogenesis hypothesis, named Umbracesis. In short, the Umbracesis hypothesis proposes that disruption of the wound healing process via carcinogens, occurs in such a way as to prevent organismic homeostasis from being recovered or prevent full re-differentiation of dedifferentiated cells. The former concept is implicated in inflammatory cancers. Whereas the latter concept, is implicated in cancers that show characteristics associated with embryonic tissues. It was concluded, that the instrumental use of the modeling approach, developed within this study, has implications beyond cancer and may be of use within other areas of biomedical concern.Item Towards Answer Set Programming Based Architectures for Intelligent Agents(2010-12) Chintabathina, Sandeep; Watson, Richard; Gelfond, Michael; Zhang, Yuanlin; Balduccini, MarcelloThe design of intelligent agents is an important research area in the field of Artificial Intelligence. Research in this area has led to the development of agent architectures that support various tasks such as reasoning, planning, diagnosis etc. One such architecture is based on the agent repeatedly executing the observe-think-act loop. In this architecture a dynamic system is viewed as a transition diagram whose nodes represent possible physical states of the system and whose arcs are labeled by actions. One of the approaches to describing these diagrams is a theory based on action languages, which are high-level languages for reasoning about actions and their effects. One such action language is AL. A theory in AL describes a transition diagram that contains all possible trajectories of a given dynamic system. However, it was not designed to reason about properties of a domain that change continuously with time. In this dissertation we present action language H which extends AL with the ability to reason about continuous change. We design this language by extending the signature of AL with a collection of numbers for representing continuous time and a collection of functions defined over time (processes). Like AL, H is based on transition diagram based semantics. We model a variety of examples in H to demonstrate that H is very useful for knowledge representation. We compared H with other approaches and discovered that action descriptions of H are simpler, concise and elaboration tolerant. We studied timed automata and discovered that H expands timed automata. An action description of AL is implemented by translating it into a program of answer set programming (ASP) and computing answer sets of the resulting program. Thus, various tasks of the agent can be reduced to asking questions about answer sets of programs. In this dissertation, we came up with an encoding of action descriptions of H into a variant of ASP called AC. Using this encoding, several agent tasks can be reduced to asking questions about answer sets of AC programs. With the help of existing solvers we are able to run our encodings and confirm that the resulting answer sets are the ones we expected.