KR&R Group: Publications

We present new methods to efficiently answer complex queries over biomedical ontologies and databases considering the relevant parts of these knowledge resources, and to generate shortest explanations to justify these answers. Both algorithms rely on the high-level representation and efficient solvers of Answer Set Programming. We apply these algorithms to find answers and explanations to some complex queries related to drug discovery, over PHARMGKB, DRUGBANK, BIOGRID, CTD and SIDER.

We embed knowledge representation and automated reasoning in each level of the classical 3-layer robot control architecture, in such a way as to tightly integrate these layers. At the high-level, we represent not only actions and change but also commonsense knowledge in the action description language C+. Geometric reasoning is lifted to the high-level by embedding motion planning in the domain description, using external predicates. Then a discrete plan is computed for each robot, using the causal reasoner CCALC. At the mid-level, if a continuous trajectory is not computed by a motion planner because the discrete plan is not feasible at the continuous-level, then formal queries are asked to the causal reasoner to find a different plan subject to some (temporal) conditions represented as formulas. At the low-level, if the plan execution fails, then a new continuous trajectory is computed by a motion planner at the mid-level or a new discrete plan is computed using an automated reasoner at the high-level. We apply this tightly integrated robot control architecture in a housekeeping domain with multiple autonomous robots, and illustrate this application with a simulation.

For some computational problems (e.g., product configuration, planning, diagnosis, query answering, phylogeny reconstruction) computing a set of similar/diverse solutions may be desirable for better decision-making. With this motivation, we have studied several decision/optimization versions of this problem in the context of Answer Set Programming (ASP), analyzed their computational complexity, and introduced offline/online methods to compute similar/diverse solutions of such computational problems with respect to a given distance function. All these methods rely on the idea of computing solutions to a problem by means of finding the answer sets for an ASP program that describes the problem. The offline methods compute all solutions of a problem in advance using the ASP formulation of the problem with an existing ASP solver, like Clasp, and then identify similar/diverse solutions using some clustering methods (possibly in ASP as well). The online methods compute similar/diverse solutions of a problem following one of the three approaches: by reformulating the ASP representation of the problem to compute similar/diverse solutions at once using an existing ASP solver; by computing similar/diverse solutions iteratively (one after other) using an existing ASP solver; by modifying the search algorithm of an ASP solver to compute similar/diverse solutions incrementally. All these methods are sound; the offline method and the first online method are complete whereas the others are not. We have modified Clasp to implement the last online method and called it Clasp-NK. In the first two online methods, the given distance function is represented in ASP; in the last one however it is implemented in C++. We have showed the applicability and the effectiveness of these methods using Clasp or Clasp-NK on two sorts of problems with different distance measures: on a real-world problem in phylogenetics (i.e., reconstruction of similar/diverse phylogenies for Indo-European languages), and on several planning problems in a well-known domain (i.e., Blocks World). We have observed that in terms of computational efficiency (both time and space) the last online method outperforms the others; also it allows us to compute similar/diverse solutions when the distance function cannot be represented in ASP (e.g., due to some mathematical functions not supported by the ASP solvers) but can be easily implemented in C++.

We formalize actions and change in a housekeeping domain with multiple cleaning robots, and commonsense knowledge about this domain, in the action language C+. Geometric reasoning is lifted to high-level representation by embedding motion planning in the domain description using external predicates. With such a formalization of the domain, a plan can be computed using the causal reasoner CCALC for each robot to tidy some part of the house. We introduce a planning and monitoring algorithm for safe execution of these plans, so that it can recover from plan failures due to collision with movable objects whose presence and location are not known in advance or due to heavy objects that cannot be lifted alone. We illustrate the applicability of this algorithm with a simulation of a housekeeping domain.

We present a formal framework that combines high-level representation and causality-based reasoning with low-level geometric reasoning and motion planning. The framework features bilateral interaction between task and motion planning, and embeds geometric reasoning in causal reasoning, thanks to several advantages inherited from its underlying components. In particular, our choice of using a causality-based high-level formalism for describing action domains allows us to represent ramifications and state/transition constraints, and embed in such formal domain descriptions externally defined functions implemented in some programming language (e.g., C++). Moreover, given such a domain description, the causal reasoner based on this formalism (i.e., the Causal Calculator) allows us to compute optimal solutions (e.g., shortest plans) for elaborate planning/prediction problems with temporal constraints. Utilizing these features of high-level representation and reasoning, we can combine causal reasoning, motion planning and geometric planning to find feasible kinematic solutions to task-level problems. In our framework, the causal reasoner guides the motion planner by finding an optimal task-plan; if there is no feasible kinematic solution for that task-plan then the motion planner guides the causal reasoner by modifying the planning problem with new temporal constraints. Furthermore, while computing a task-plan, the causal reasoner takes into account geometric models and kinematic relations by means of external predicates implemented for geometric reasoning (e.g., to check some collisions); in that sense the geometric reasoner guides the causal reasoner to find feasible kinematic solutions. We illustrate an application of this framework to robotic manipulation, with two pantograph robots on a complex assembly task that requires concurrent execution of actions.

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.

The Association for the Advancement of Artificial Intelligence, in cooperation with Stanford University.s Department of Computer Science, presented the 2011 Spring Symposium Series Monday through Wednesday, March 21.23, 2011 at Stanford University. The titles of the eight symposia were AI and Health Communication, Artificial Intelligence and Sustainable Design, AI for Business Agility, Computational Physiology, Help Me Help You: Bridging the Gaps in Human-Agent Collaboration, Logical Formalizations of Commonsense Reasoning, Multirobot Systems and Physical Data Structures, and Modeling Complex Adaptive Systems As If They Were Voting Processes. This report summarizes the eight symposia.

In many applications, faults are triggered by events that occur in a particular order. Based on the assumption that most bugs are caused by the interaction of a low number of events, Kuhn et al. recently introduced sequence covering arrays (SCAs) as suitable designs for event sequence testing. In practice, directly applying SCAs for testing is often impaired by additional constraints, and SCAs have to be adapted to it application-specific needs. Modifying precomputed SCAs to account for problem variations can be problematic, if not impossible, and developing dedicated algorithms is costly. In this paper, we propose answer-set programming (ASP), a well-known knowledge-representation formalism from the area of artificial intelligence based on logic programming, as a declarative paradigm for computing SCAs. Our approach allows to concisely state complex coverage criteria in an elaboration tolerant way, i.e., small variations of a problem specification require only small modifications of the ASP representation.

For many computational problems, the main concern is to find a best solution (e.g., a most preferred product configuration, a shortest plan, a most parsimonious phylogeny) with respect to some well-described criteria. On the other hand, in many real-world applications, computing a subset of good solutions that are similar/diverse may be desirable for better decision-making. For one reason, the given computational problem may have too many good solutions, and the user may want to examine only a few of them to pick one; in such cases, finding a few similar/diverse good solutions may be useful. Also, in many real-world applications the users usually take into account further criteria that are not included in the formulation of the optimization problem; in such cases, finding a few good solutions that are close to or distant from a particular set of solutions may be useful. With this motivation, we have studied various computational problems related to finding similar/diverse (resp. close/distant) solutions with respect to a given distance function, in the context of Answer Set Programming (ASP). We have introduced novel offline/ online computational methods in ASP to solve such computational problems. We have modified an ASP solver according to one of our online methods, providing a useful tool (CLASP-NK) for various ASP applications. We have showed the applicability and effectiveness of our methods/tools in three domains: phylogeny reconstruction, AI planning, and biomedical query answering. Motivated by the promising results, we have developed computational tools to be used by the experts in these areas.

In AI planning the aim is to plan the actions of an agent to achieve the given goals from a given initial state. We use AI planning to solve two challenging problems: the genome rearrangement problem in computational biology and the decoupled planning problem in multi-robot systems. Motivated by the reconstruction of phylogenies, the genome rearrangement problem seeks to find the minimum number of rearrangement events (i.e., genome-wide mutations) between two given genomes. We introduce a novel method (called GENOMEPLAN) to solve this problem for single chromosome circular genomes with unequal gene content and/or duplicate genes, by formulating the pairwise comparison of entire genomes as an AI planning problem and using the AI planner TL Plan to compute solutions. The idea is to plan genome rearrangement events to transform one genome to the other. To improve computational efficiency, GENOMEPLAN embeds several heuristics in the descriptions of these events. To better understand the evolutionary history of species and to find more plausible solutions, GENOMEPLAN allows assigning costs and priorities to rearrangement events. The applicability of GENOMEPLAN is shown by some experiments on real data sets as well as randomly generated instances. In multi-robot systems, multiple teams of heterogeneous robots work in separate workspaces towards different goals. The teams are allowed to lend robots to one another. The goal is to find an overall plan of minimum length where each team completes its assigned task. We introduce an intelligent algorithm to solve this problem. The idea is, on the one hand, to allow each team to autonomously find its own plan and, on the other hand, to allow a central agent to communicate with the representatives of the teams to find an optimal decoupled plan.We prove the soundness and completeness of our decoupled planning algorithm, and analyze its computational complexity. We show the applicability of our approach on an intelligent factory scenario, using the action description language C+ for representing the domain and the causal reasoner CCalc for reasoning about the domain.

We describe a software system, called BIOQUERY-ASP, that finds answers and generates explanations to complex biomedical queries over the available knowledge resources, such as, PHARMGKB, DRUGBANK, CTD, SIDER, BIOGRID, using the computational methods/tools of Answer Set Programming.

We present a computational method to generate explanations to answers of complex queries over biomedical ontologies and databases, using the high-level representation and efficient automated reasoners of Answer Set Programming. We show the applicability of our approach with some queries related to drug discovery over PHARMGKB, DRUGBANK, BIOGRID, CTD and SIDER.

We summarize some applications of Answer Set Programming (ASP) in phylogenetics systematics, focusing on the challenges, how they are handled using computational methods of ASP, the usefulness of the ASP-based methods/tools both from the point of view of phylogenetic systematics and from the point of view of ASP.

We consider a housekeeping domain with multiple cleaning robots and represent it in the action language C+. With such a formalization of the domain, a plan can be computed using the causal reasoner CCALC for each robot to tidy some part of the house. However, to find a plan that characterizes a feasible trajectory that does not collide with obstacles, we need to consider geometric reasoning as well. For that, we embed motion planning in the domain description using external predicates. For safe execution of feasible plans, we introduce a planning and monitoring algorithm so that the robots can recover from plan execution failures due to heavy objects that cannot be lifted alone. The coordination of robots to help each other is considered for such a recovery. We illustrate the applicability of this algorithm with a simulation of a housekeeping domain.

Protein structure determination is crucial to understand a protein's function and to develop drugs against diseases. Nuclear Magnetic Resonance (NMR) spectroscopy is an experimental technique that allows one to study protein structure in solution. In NMR Structure-based assignment problem, the aim is to assign experimentally observed peaks to the specific nuclei of the target molecule by using a template protein and it is an important computational challenge. NVR-BIP is a tool that utilizes a scoring function based on NVR's framework and computes assignments for given NMR data. In this paper, we incorporate HADAMAC experiment---which helps predict an amino acid class for each peak--- with NVRBIP's scoring function. Experiments show that the new scoring function results in higher assignment accuracies compared to the previous approaches

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.

To quantify semantic inconsistency in UMLS concepts from the perspective of their hierarchical relations and to show through examples how semantically-inconsistent concepts can help reveal erroneous synonymy relations. Methods: Inconsistency is defined in reference to concepts from the UMLS Metathesaurus. Consistency is evaluated by comparing the semantic groups of the two concepts in each pair of hierarchically-related concepts. A limited number of inconsistent concepts was inspected manually. Results: 81,512 concepts are inconsistent due to the differences in semantic groups between a concept and its parent. Four examples of wrong synonymy are presented. Conclusions: A vast majority of incon-sistent hierarchical relations are not indicative of any errors. We discovered an interesting semantic pattern along hierarchies, which seems associated with wrong synonymy.

Nuclear Magnetic Resonance (NMR) spectroscopy is an important experimental technique that allows one to study protein structure in solution. An important challenge in NMR protein structure determination is the assignment of NMR peaks to corresponding nuclei. In structure-based assignment (SBA), the aim is to perform the assignments with the help of a homologous protein. NVR-BIP is a tool that uses Nuclear Vector Replacement’s (NVR) scoring function and binary integer programming to solve SBA problem. In this work, we introduce a method to improve NVR-BIP’s assignment accuracy with amino acid typing. We use CRAACK that takes the chemical shifts of C, N and H atoms and returns the possible amino acids along with their confidence scores. We obtain improved assignment accuracies and our results show the effectiveness of integrating amino acid typing with NVR.

Incorporating new information into a knowledge base is an important problem which has been widely investigated. In this paper, we study this problem in a formal framework for reasoning about actions and change. In this framework, action domains are described in an action language whose semantics is based on the notion of causality. Unlike the formalisms considered in the related work, this language allows straightforward representation of non-deterministic effects and indirect effects of (possibly concurrent) actions, as well as state constraints; therefore, the updates can be more general than elementary statements. The expressivity of this formalism allows us to study the update of an action domain description with a more general approach compared to related work. First of all, we consider the update of an action description with respect to further criteria, for instance, by ensuring that the updated description entails some observations, assertions, or general domain properties that constitute further constraints that are not expressible in an action description in general. Moreover, our framework allows us to discriminate amongst alternative updates of action domain descriptions and to single out a most preferable one, based on a given preference relation possibly dependent on the specified criteria. We study semantic and computational aspects of the update problem, and establish basic properties of updates as well as a decomposition theorem that gives rise to a divide and conquer approach to updating action descriptions under certain conditions. Furthermore, we study the computational complexity of decision problems around computing solutions, both for the generic setting and for two particular preference relations, viz. set-inclusion and weight-based preference. While deciding the existence of solutions and recognizing solutions are PSPACE-complete problems in general, the problems fall back into the polynomial hierarchy under restrictions on the additional constraints. We finally discuss methods to compute solutions and approximate solutions (which disregard preference). Our results provide a semantic and computational basis for developing systems that incorporate new information into action domain descriptions in an action language, in the presence of additional constraints.

We introduce a new method to find semantic inconsistencies (i.e., concepts with erroneous synonymity) in the Unified Medical Language System (UMLS). The idea is to identify the inconsistencies by comparing the semantic groups of hierarchically-related concepts using Answer Set Programming. With this method, we identified several inconsistent concepts in UMLS and discovered an interesting semantic pattern along hierarchies, which seems associated with wrong synonymy.

We study integration of task planning and motion planning in a general execution monitoring framework. We show the applicability of this framework, on a modified version of Tower of Hanoi where the orientations of rings matter and rotations of rings maybe required while being moved. We represent this problem as a planning problem in the action language C+, and compute a shortest task plan using the reasoning system CCALC. A collision-free trajectory for the task plan (if one exists) is computed by a motion planning algorithm, using Rapidly exploring Random Trees. The monitoring agent invokes replanning upon two kinds of failures: when a continuous trajectory for a task plan cannot be computed, and when the execution of the plan fails due to external intervention. We demonstrate the effectiveness of our approach by implementing it using two robotic manipulators on a physical experimental setup.

Evolutionary relationships between species can be modeled as a tree (called a phylogeny) whose nodes represent the species, internal vertices represent their ancestors and edges represent genetic relationships. If there are borrowings between species, then a small number of edges that denote such borrowings can be added to phylogenies turning them into (phylogenetic) networks. However, there are too many such trees/networks for a given family of species but no phylogenetic system to automatically analyze them. This thesis fulfills this need in phylogenetics, by introducing novel computational methods and tools for computing weighted phylogenies/networks, using Answer Set Programming (ASP). The main idea is to define a weight function for phylogenies/networks that characterizes their plausibility, and to reconstruct phylogenies/networks whose weights are over a given threshold using ASP solvers. We have studied computational problems related to reconstructing weighted phylogenies/networks based on the compatibility criterion, analyzed their computational complexity, and introduced two sorts of ASP-based methods (representation-based and search-based) for computing weighted phylogenies/networks. Utilizing these methods, we have introduced a novel divide-and-conquer algorithm for computing large weighted phylogenies, and implemented a phylogenetic system (Phylo-ASP) based on it. We have also implemented a phylogenetic system (PhyloNet-ASP) for reconstructing weighted networks. We have shown the applicability and the effectiveness of our methods by performing experiments on two real datasets: Indo European languages, and Quercus species in Turkey. Moreover, we have extended our methods to computing weighted solutions in ASP and modified an ASP solver accordingly, providing a useful tool (Clasp-W) for various ASP applications.

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.

Answer Set Programming (ASP) is a declarative programming paradigm oriented towards solving NP-hard problems. Due to the expressive representation language and efficient solvers, ASP can be useful for a wide-range of knowledgeintensive applications from different fields. In ASP, the idea is to provide a declarative representation of the problem as an ASP program whose models (called answer sets) correspond to solutions. Since many problems have numerous solutions, instead of computing all solutions, it is sometimes desirable to compute a subset of preferred solutions. With this motivation, we present novel methods to quantify answer sets in ASP for extracting preferred solutions only. We show the effectiveness of these methods on real world applications.

We present a formal framework to find answers and explanations to complex queries over biomedical ontologies and databases, using the high-level representation and efficient automated reasoners of Answer Set Programming. Over this framework, we develop an intelligent user-interface that allows users to enter biomedical queries in a natural language, and that presents the answers also in that natural language. We show the applicability of our approach with some queries over PharmGKB, DrugBank, CTD and Sider.

For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to solutions, and then pick the ones whose weights are over (resp. below) a threshold. This paper studies computing weighted solutions to such problems in Answer Set Programming. We investigate two sorts of methods for computing weighted solutions: one suggests modifying the representation of the problem and the other suggests modifying the search procedure of the answer set solver. We show the applicability and the effectiveness of these methods in reconstructing weighted phylogenies for Indo-European languages. We also compare these methods in terms of computational efficiency; the experimental results show that the search-based method is better.

We present a logic-based framework to provide robots with high-level reasoning, such as planning. This framework uses the action description language C+ to represent actions and changes, and the system CCALC to reason about them. In particular, we can represent action domains that involve concurrent actions and additive fluents; based on this description, we can compute shortest plans to a planning problem that involves cost constraints. We show the applicability of this framework on two LEGO MINDSTORMS NXT robots: we compute a discrete task plan (possibly with concurrency) with a cost less than a specified value, and transform this plan into a continuous collision-free trajectory.

We study finding similar or diverse solutions of a given computational problem, in answer set programming, and introduce offline methods and online methods to compute them using answer set solvers.We analyze the computational complexity of some problems that are related to finding similar or diverse solutions, and show the applicability and effectiveness of our methods in phylogeny reconstruction.

Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations, we have access to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure. With these biological motivations, we study haplotype inference -- determining the haplotypes that form a given set of genotypes -- using Answer Set Programming; we call our approach HAPLO-ASP. This note summarizes the range of problems that can be handled by HAPLO-ASP, and its applicability and effectiveness on real data in comparison with the other existing approaches.

We introduce a controlled natural language for biomedical queries, called BIOQUERYCNL, and present an algorithm to convert a biomedical query in this language into a program in answer set programming (ASP) --- a formal framework to automate reasoning about knowledge. BIOQUERYCNL allows users to express complex queries (possibly containing nested relative clauses and cardinality constraints) over biomedical ontologies; and such a transformation of BIOQUERYCNL queries into ASP programs is useful for automating reasoning about biomedical ontologies by means of ASP solvers. We precisely describe the grammar of BIOQUERYCNL, implement our transformation algorithm, and illustrate its applicability to biomedical queries by some examples.

We present a formal framework where the action description language C+ is used to provide multiple robots with high-level reasoning in the style of cognitive robotics. We show the applicability of this framework on two LEGO MINDSTORMS NXT robots, in an action domain that involves concurrent execution of actions by multiple agents.

For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to solutions, and then pick the ones whose weights are over (resp. below) a threshold. This paper studies computing weighted solutions to such problems in Answer Set Programming. We investigate two sorts of methods for computing weighted solutions: one suggests modifying the representation of the problem and the other suggests modifying the search procedure of the answer set solver. We show the applicability and the effectiveness of these methods in phylogeny reconstruction.

We study two declarative programming languages namely Answer Set Programming (ASP) and Constraint Programming (CP) on four grid puzzles: Akari, Kakuro, Nurikabe, and Heyawake. We represent these problems in both formalisms in a systematic way and compute their solutions using ASP system Clasp and CP system Comet. We compare the ASP approach with the CP approach both from the point of view of knowledge representation and from the point of view of computational time and memory.

This note summarizes the use of Answer Set Programming to solve various computational problems to infer phylogenetic trees and phylogenetic networks, and discusses its applicability and effectiveness on some real taxa.

We study three declarative programming paradigms, Answer Set Programming (ASP), Constraint Programming (CP), and Integer Linear Programming (ILP), on two challenging applications: wire routing and haplotype inference. We represent these problems in each formalism in a systematic way, compare the formulations both from the point of view of knowledge representation (e.g., how tolerant they are to elaborations) and from the point of view of computational efficiency (in terms of computation time and program size). We discuss possible ways of improving the computational efficiency, and other reformulations of the problems based on different mathematical models.

Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations, we have access to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure. With these biological motivations, we study a computational problem, called Haplotype Inference by Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. HIPP has been studied using integer linear programming, branch and bound algorithms, SAT-based algorithms, or pseudo-boolean optimization methods. We introduce a new approach to solving HIPP, using Answer Set Programming (ASP). According to our experiments with a large number of problem instances (some automatically generated and some real), our ASP-based approach solves the most number of problems compared with other approaches. Due to the expressivity of the knowledge representation language of ASP, our approach allows us to solve variations of HIPP, e.g., with additional domain specific information, such as patterns/parts of haplotypes observed for some gene family, or with some missing genotype information. In this sense, the ASP-based approach is more general than the existing approaches to haplotype inference.

Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. Although we have access to genotype data (genetic makeup of an individual), determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure due to technological limitations. With these biological motivations, we study a computational prob- lem, called Haplotype Inference with Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. We introduce a novel approach to solving HIPP, using Answer Set Programming (ASP). Ac- cording to our experiments with a large number of problem instances (some automatically generated and some real), our ASP-based approach solves the most number of problems compared to other approaches based on, e.g., integer linear programming, branch and bound algorithms, SAT-based al- gorithms, or pseudo-boolean optimization methods.

Consider an agent executing a plan with nondeterministic actions, in a dynamic environment, which might fail. Suppose that she is given a description of this action domain, including specifications of effects of actions, and a set of trajectories for the execution of this plan, where each trajectory specifies a possible execution of the plan in this domain. After executing some part of the plan, suppose that she obtains information about the current state of the world, and notices that she is not at a correct state relative to the given trajectories. How can she find an explanation (a point of failure) for such a discrepancy? An answer to this question can be useful for different purposes. In the context of execution monitoring, points of failure can determine some checkpoints that specify when to check for discrepancies, and they can sometimes be used for recovering from discrepancies that cause plan failures. At the modeling level, points of failure may provide useful insight into the action domain for a better understanding of the domain, or reveal errors in the formalization of the domain. We study the question above in a general logic-based knowledge representation framework, which can accommodate nondeterminism and concurrency. In this framework, we define a discrepancy and an explanation for it, and analyze the computational complexity of detecting discrepancies and finding explanations for them. We introduce a method for computing explanations, and report about a realization of this method using DLVK, which is a logic-programming based system for reasoning about actions and change.

We introduce a new method for integrating relevant parts of knowledge extracted from biomedical ontologies and answering complex queries related to drug safety and discovery, using Semantic Web technologies and answer set programming. The applicability of this method is illustrated in detail on some parts of existing biomedical ontologies. Its effectiveness is demonstrated by computing an answer to a real-world biomedical query that requires the integration of NCBI Entrez Gene and the Gene Ontology.

In this paper, we study the following basic problem: After having executed a sequence of actions, find a sequence of actions that brings the agent back to the state just before this execution. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. A prototypical scenario is in the context of plan execution in a nondeterministic environment: Upon detecting that after executing some steps of the plan, an unintended state has been reached, backtracking to an earlier state by taking appropriate undo actions can be useful for recovery. In this paper, we consider the problem of undoing the effects of an action sequence by means of a reverse plan. Intuitively, by executing a reverse plan for an action sequence AS at the state S' reached after AS, the agent can always reach the state S she was at just before executing AS, possibly subject to conditions on the current state and S. Notably, this problem is different from a vanilla planning problem, since the state we have to get back to is in general unknown. We study this problem in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. We formally define the notion of a reverse plan and determine the computational complexity of the existence and the recognition of such a plan. Guided by these results, we then present algorithms for constructing reverse plans. Unsurprisingly, the problem is intractable in general, and we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be adapted for expressive action languages such as C+ or K.

Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as cal C+ or cal K.

We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g., temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible.

We study four challenging grid puzzles, Nurikabe, Heyawake, Masyu, Bag Puzzle, interesting for answer set programming (ASP) from the viewpoints of representation and computation: they show expressivity of ASP, they are good examples of a representation methodology, and they form a useful suite of benchmarks for evaluating/improving computational methods for nontight programs.

The focus of this paper is on action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As applications of this approach, we study updating action descriptions and identifying elaboration tolerant action descriptions, with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We further study computational issues, and give a characterization of the computational complexity of computing the semantic measures.

Forgetting irrelevant/problematic actions in a domain description can be useful in solving reasoning problems, such as query answering, planning, conflict resolution, prediction, postdiction, etc.. Motivated by such applications, we study what forgetting is, how forgetting can be done, and for which applications forgetting can be useful and how, in the context of reasoning about actions. We study these questions in the action language cal C (a formalism based on causal explanations), and relate it to forgetting in classical logic and logic programming.

We present a general method to formalize action domains with numeric-valued fluents whose values are incremented or decremented by executions of actions, and show how it can be applied to the action description language C+ and to the concurrent situation calculus. This method can handle nonserializable concurrent actions, as well as ramifications on numeric-valued fluents, which are described in terms of some new causal structures, called contribution rules.

We study resolving conflicts between an action description and a set of conditions (possibly obtained from observations), in the context of action languages. In this formal framework, the meaning of an action description can be represented by a transition diagram, a directed graph whose nodes correspond to states and whose edges correspond to transitions describing action occurrences. This allows us to characterize conflicts by means of states and transitions of the given action description that violate some given conditions. We introduce a basic method to resolve such conflicts by modifying the action description, and discuss how the user can be supported in obtaining more preferred solutions. For that, we identify helpful questions the user may ask (e.g., which specific parts of the action description cause a conflict with some given condition), and we provide answers to them using properties of action descriptions and transition diagrams. Finally, we discuss the computational complexity of these questions in terms of related decision problems.

We consider action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As an application of this approach, we study the problem of updating action descriptions with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We conclude with computational issues, and characterize the complexity of computing the semantic measures.

The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages.

The genome rearrangement problem is to find the most economical explanation for observed differences between the gene orders of two genomes. Such an explanation is provided in terms of events that change the order of genes in a genome. We present a new approach to the genome rearrangement problem, according to which this problem is viewed as the problem of planning rearrangement events that transform one genome to the other. This method differs from the existing ones in that we can put restrictions on the number of events, specify the cost of events with functions, possibly based on the length of the gene fragment involved, and add constraints controlling search. With this approach, we have described genome rearrangements in the action description language ADL, and studied the evolution of Metazoan mitochondrial genomes and the evolution of Campanulaceae chloroplast genomes using the planner TLplan. We have observed that the phylogenies reconstructed using this approach conform with the most widely accepted ones.

We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g. temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible.

How can an intelligent agent update her knowledge base about an action domain, relative to some conditions (possibly obtained from earlier observations)? We study this question in a formal framework for reasoning about actions and change, in which the meaning of an action domain description can be represented by a directed graph whose nodes correspond to states and whose edges correspond to action occurrences. We define the update of an action domain description in this framework, and show among other results that a solution to this problem can be obtained by a divide-and-conquer approach in some cases. We also introduce methods to compute a solution and an approximate solution to this problem, and analyze the computational complexity of these problems. Finally, we discuss techniques to improve the quality of solutions.

We propose a situation calculus formalization of action domains that include numeric-valued fluents (so-called additive or measure fluents) and concurrency. Our approach allows formalizing concurrent actions whose effect s increment/decrement the value of additive fluents. For describing indirect effects, we employ mathematical equations in a manner that is inspired by recent work on causality and structural equations.

This paper introduces a logic-based framework for monitoring plan execution relative to a given set of trajectories. According to this framework, a monitoring agent can tell when things go wrong by checking the compatibility of the plan execution with the given trajectories, considering the current state information. She finds an explanation for these detected discrepancies by examining the given trajectories against possible evolutions of the current state from the initial state. Such an explanation provides information about possible points of failure that may be useful in two ways. First, points of failure can be used to determine some checkpoints (specifying when to check for discrepancies), and this may be useful if the plan is executed many times. Second, they can be used for recovering from discrepancies. For instance, the agent can undo the plan execution until a point of failure, from which the remainder of the plan can be (re)executed, thus avoiding an expensive (re)planni ng step. In this paper, we present formal specifications for discrepancies and explanations for them in a general action representation framework, which can accommodate nondeterminism, concurrency, and dynamic worlds. We describe two ways of finding explanations for detected discrepancies, and study their properties. Moreover, we analyze the computational complexity of detecting discrepancies and finding explanations for them, and describe how these computational problems can be solved.

When an agent has executed a single action or a sequence of actions, it may sometimes be desirable that the effects of this execution are undone and the agent gets back to the previous state. A prototypical scenario for this is in the context of plan execution in a nondeterministic environment. Upon detecting that after some steps an unintended state has been reached, backtracking by taking appropriate undo actions can be useful for error recovery. In this paper, we thus consider the problem of undoing the effects of an action sequence by means of a reverse plan, in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. Intuitively, by executing a reverse plan for an action sequence ASat the state Sreached after AS, she can always reach the state Sshe was at before executing AS. We formally define the notion of a reverse plan in terms of a logical specification and determine the computational complexity of the major reasoning tasks on it, namely the existence and recognition problem. Guided by these results, we then present algorithms for constructing reverse plans. Since this is intractable in general, we develop a knowledge compilation approach in which a reverse plan library is built offline by finding reverse plans for action sequences, and then a reverse plan for a given action sequence is efficiently constructed online using this library. For the former part, we describe methods based on conformant planning; for the latter, we present a polynomial time algorithm.

In this paper, we introduce a new method to recover from discrepancies in a general monitoring framework where the agent finds some explanations (points of failure) for discrepancies. According to this method, the agent finds a reverse plan to backtrack to a diagnosed point of failure and subsequently continues with the original plan. This method is appealing given that such a reverse plan is short with respect to the overall plan to be executed. While a reverse plan could be computed online by solving a planning problem, we present a potentially more efficient method: We first build offline a reverse plan library by finding reverse plans for action sequences, and then use this library online to construct reverse plans. The former part is done by reducing the problem of finding pairs of action sequences and reverse plans (of a certain length) to a conformant planning problem; for the latter, we present a polynomial time algorithm. Furthermore, we analyze the complexity of finding reverse plans, and obtain that the presented reduction is reasonable in general.

We introduce a new method for Rectilinear Steiner Tree (RST) construction in a graph, using answer set programming. This method provides a formal representation of the problem as a logic program whose answer sets correspond to solutions. The answer sets for a logic program can be computed by special systems called answer set solvers. We describe the method for RST construction in the context of VLSI routing where multiple pins in a given placement of a chip are connected by an RST. Our method is different from the existing methods mainly in three ways. First, it always correctly determines whether a given RST routing problem is solvable, and it always produces a solution if one exists. Second, some enhancements of the basic problem, in which lengths of wires connecting the source pin to sink pins are restricted, can be easily represented by adding some rules. Our method guarantees to find a tree if one exists, even when the total wire length is not minimum. Third, routing problems with the presence of obstacles can be solved. With this approach, we have computed solutions to some RST routing problems using the answer set solver cmodels.

This note is about the relationship between two theories of negation as failure---one based on program completion, the other based on stable models, or answer sets. Francois Fages showed that if a logic program satisfies a certain syntactic condition, which is now called ``tightness,'' then its stable models can be characterized as the models of its completion. We extend the definition of tightness, and Fages' theorem, to programs with nested expressions in the bodies of rules, and study tight logic programs containing the definition of the transitive closure of a predicate.

The evolutionary history of languages can be modeled as a tree, called a phylogeny, where the leaves represent the extant languages, the internal vertices represent the ancestral languages, and the edges represent the genetic relations between the languages. Languages not only inherit characteristics from their ancestors but also sometimes borrow them from other languages. Such borrowings can be represented by additional non-tree edges. This paper addresses the problem of computing a small number of additional edges that turn a phylogeny into a ``perfect phylogenetic network''. To solve this problem, we use answer set programming, which represents a given computational problem as a logic program whose answer sets correspond to solutions. Using the answer set solver SMODELS, with some heuristics and optimization techniques, we have generated a few conjectures regarding the evolution of Indo-European languages.

Answer set programming (ASP) is a new form of declarative logic programming. ASP interprets a logic program as a constraint on sets of literals, just as a propositional formula can be viewed as a constraint on assignments of truth values to atoms. The concept of an answer set was originally proposed as a semantics of negation as failure in Prolog. Instead of traditional Prolog systems, ASP uses answer set solvers. The input of Prolog consists of a logic program and a query, and Prolog computes answer substitutions; the input of an answer set solver is a logic program, and the solver computes the program's answer sets. The idea of ASP is to represent a given computational problem as a logic program whose answer sets correspond to solutions, and to use an answer set solver to find an answer set. We have investigated the application of ASP to several combinatorial search problems, including planning, wire routing, and phylogeny reconstruction. Planning is the problem of finding a sequence of actions that leads to a given goal. Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Phylogeny reconstruction is the problem of constructing and labeling an evolutionary tree for a set of taxa (taxonomic units), which describes the evolution of the taxa in that set from their most recent common ancestor. In our work on phylogeny reconstruction, we have generated several conjectures about the evolutionary history of Indo-European languages. The work on the use of ASP for planning has led us to the investigation of some theoretical questions related to answer sets. One is the problem of equivalent transformations of logic programs: under what conditions can we replace a program by an equivalent program that can be processed by an answer set solver more efficiently? Another problem is related to completion--a process that can translate a logic program into a set of formulas of classical logic. In some cases, the interpretations satisfying the completion of a program are also the answer sets for that program. In such cases, we can use propositional solvers--systems that compute a model of a given set of clauses--to find the program's answer sets. For some problems, propositional solvers are more efficient than answer set solvers. Therefore, we have investigated under what conditions we can use propositional solvers to find the program's answer sets.

We extend a theorem by Francois Fages about the relationship between the completion semantics and the answer set semantics of logic programs to a class of programs with nested expressions permitted in the bodies of rules. Fages' theorem is important from the perspective of answer set programming: whenever the two semantics are equivalent, answer sets can be computed by propositional solvers, such as sato, instead of answer set solvers, such as smodels. The need to extend Fages' theorem to programs with nested expressions is related to the use of choice rules in the input language of smodels.

We prove that the usual logic programming definition of transitive closure is correct under the answer set semantics, and investigate under what conditions it is correct under the completion semantics. That definition is allowed here to be combined with an arbitrary set of rules that may contain negation as failure, not merely with a set of facts. This work is motivated by applications to answer set programming.

We generalize a theorem by Francois Fages that describes the relationship between the completion semantics and the answer set semantics for logic programs with negation as failure. The study of this relationship is important in connection with the emergence of answer set programming. Whenever the two semantics are equivalent, answer sets can be computed by a satisfiability solver, and the use of answer set solvers such as SMODELS and DLV is unnecessary. A logic programming representation of the blocks world due to Ilkka Niemela is discussed as an example.

Inductive logic programming (ILP) systems use some declarative bias to constrain the hypothesis space. We introduce a new declarative bias, called construction modes, capturing the required dataflow of a relation, and design a language for expressing such construction modes . Their semantics is captured via the notion of admissibility. Experiments with the ILP systems SYNAPSE and DIALOGS have established the usefulness of construction modes. Since the new bias is orthogonal to the existing search biases, it can be used in conjunction with the existing biases.

Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Since the wires cannot intersect with each other, they are competing for limited spaces, thus making routing a difficult combinatorial optimization problem. We present a new approach to wire routing that uses action languages and satisfiability planning. Its idea is to think of each path as the trajectory of a robot, and to understand a routing problem as the problem of planning the actions of several robots whose paths are required to be disjoint. The new method differs from the algorithms implemented in the existing routing systems in that it always correctly determines whether a given problem is solvable, and it produces a solution whenever one exists.

We prove two properties of logic programs under the answer set semantics that may be useful in connection with applications of logic programming to representing causality and to planning. One theorem is about the use of disjunctive rules to express that an atom is exogenous. The other provides an alternative way of expressing that a plan does not include concurrently executed actions.

We consider part of the problem of schema-biased inductive synthesis of recursive logic programs from incomplete specifications, such as clausal evidence (for instance, but not necessarily, ground positive and negative examples). After synthesizing the base clause and introducing recursive call(s) to the recursive clause, it remains to combine the overall result from the partial results obtained through recursion, so as to complete the recursive clause. Evidence for this combination relation can be abduced from the initially given evidence for the top-level relation. A program for this combination relation can be anything, from a single clause performing a unification (such as for lastElem) to multiple guarded clauses performing unifications (such as for filtering programs) to recursive programs (such as for naive reverse). Existing methods cannot induce guarded clause programs for this combination relation from the abduced evidence. Some existing methods cannot even detect that the combination program itself may have to be recursive and thus they then do not recursively invoke themselves the overall recursive program synthesizer. We introduce our Program Completion Method as a suitable extension and generalization of the existing methods.

The classical least generalization of a set C of clauses is a single clause. Such a unique clause is sometimes too general wrt some over-generality criterion, and this undesired situation may lead to memorization of the clauses in C at the end of learning process. Current ILP systems apply some heuristic algorithms to refine this situation where the classical definition of least generalization is used as an operator in a search space throughout the learning. Our approach to this problem is different: we use the classical least generalization of C in a more declarative way to narrow the search-space at the very beginning of the learning algorithm, that is, we define the concept of least generalization of a set C of clauses in a different way as being a minimal-sized set of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to the over-generality criterion admissibility. We give an efficient algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility: these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result.

This report summarizes experiments with the systems SMODELS and DLV applied to some planning problems. The planning problems are presented to SMODELS and DLV as logic programs. Plans correspond to answer sets for these programs, in the spirit of answer set programming.

The classical definition of the concept of least generalization of a clause set C is that it is a _single_ clause. Since such a unique clause is sometimes over-general, we re-define this concept as being a minimal-sized _set_ of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to some over-generality criterion. We give an algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. The criterion for over-generality is problem-specific. We introduce a new such criterion: two clauses are compatible, i.e., their classical least generalization is not over-general, if this least generalization is admissible wrt a construction mode capturing the required dataflow of each involved relation. We design a language for expressing such construction modes, and we define a powerful admissibility criterion. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility (our over-generality criterion): these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result.

SYNAPSE2 is an upgraded version of SYNAPSE (developed by Flener [1995]), which is an implementation of an inductive synthesis mechanism that semi-automatically synthesizes divide-and-conquer logic algorithms in a schema-guided way, from non-incrementally given examples and properties of an intended relation. SYNAPSE2 goes through six steps, instantiating the place-holders of a chosen divide-and-conquer logic algorithm schema. At Step 5, the MSG-Method is used as a tool. The MSG-Method is used to infer a logic algorithm of an intended relation, if it is possible to get a logic algorithm using only =/2 predicate in the body. In this project, our aim is to simplify and extend the existing MSG-Method (introduced by Flener [1995]) independent of the place-holder and its schema, and to re-implement Step 5 of SYNAPSE2, which corresponds to the steps 5 and 6 of SYNAPSE. In this report, the main concepts are introduced as preliminaries in Section 1, the synthesis mechanism is explained with an example (in SYNAPSE2) in Section 2, the MSG-Method is focused on in Section 3, after then Step 5 is explained in Section 4, finally the project is discussed in Section 5.