Esra Erdem

IJCAI Conference 2024 Conference Paper

Hybrid planning for challenging construction problems: An Answer Set Programming approach (Abstract Reprint)

• Faseeh Ahmad
• Volkan Patoglu
• Esra Erdem

We study construction problems where multiple robots rearrange stacks of prefabricated blocks to build stable structures. These problems are challenging due to ramifications of actions, true concurrency, and requirements of supportedness of blocks by a surface or a robot and stability of the overall structure at all times. We propose a general elaboration tolerant method to solve a wide range of construction problems, based on the knowledge representation and reasoning paradigm of Answer Set Programming. This method not only (i) determines a stable final configuration of the structure, but also (ii) computes the order of manipulation tasks for multiple autonomous robots to build the structure from an initial configuration, (iii) while simultaneously ensuring the requirements of supportedness and stability at all times. We prove the soundness and completeness of our method with respect to these properties. We introduce a set of challenging construction benchmark instances, including construction of (uneven) bridges and overhangs, and discuss the usefulness of our framework over these instances. Furthermore, we perform experiments to investigate the computational performance of our hybrid method, and demonstrate the applicability of our method using a bimanual Baxter robot.

AIJ Journal 2023 Journal Article

Hybrid planning for challenging construction problems: An Answer Set Programming approach

• Faseeh Ahmad
• Volkan Patoglu
• Esra Erdem

JAIR Journal 2023 Journal Article

Qualitative Reasoning about 2D Cardinal Directions using Answer Set Programming

• Yusuf Izmirlioglu
• Esra Erdem

We introduce a formal framework (called NCDC-ASP) for representing and reasoning about cardinal directions between extended spatial objects on a plane, using Answer Set Programming (ASP). NCDC-ASP preserves the meaning of cardinal directional relations as in Cardinal Directional Calculus (CDC), and provides solutions to all consistency checking problems in CDC under various conditions (i.e., for a complete/incomplete set of basic/disjunctive CDC constraints over connected/disconnected spatial objects). In particular, NCDC-ASP models a discretized version of the consistency checking problem in ASP, over a finite grid (rather than a plane), where we provide new lower bounds on the grid size to guarantee that it correctly characterizes solutions for the consistency checking in CDC. In addition, NCDC-ASP has the following two novelties important for applications. NCDC-ASP introduces default CDC constraints to represent and reason about background or commonsense knowledge that involves default qualitative directional relations (e.g., "the ice cream truck is by default to the north of the playground" or "the keyboard is normally placed in front of the monitor"). NCDC-ASP introduces inferred CDC constraints to allow inference of missing CDC relations and to provide them as explanations. We illustrate the uses and usefulness of NCDC-ASP with interesting scenarios from the real-world. We design and develop a variety of benchmark instances, and comprehensively evaluate NCDC-ASP from the perspectives of computational efficiency.

AAAI Conference 2018 Conference Paper

Qualitative Reasoning About Cardinal Directions Using Answer Set Programming

• Yusuf Izmirlioglu
• Esra Erdem

We propose a novel method for representing and reasoning about an incomplete set of constraints about basic/disjunctive qualitative direction relations over simple/connected/disconnected regions, using Answer Set Programming, and prove its correctness with respect to cardinal direction calculus. We extend this method further with default qualitative direction constraints, and discuss its usefulness with some sample scenarios.

AAAI Conference 2014 Conference Paper

Coordination of Multiple Teams of Robots for an Optimal Global Plan

• Zeynep Saribatur
• Esra Erdem
• Volkan Patoglu

We consider multiple teams of heterogeneous robots, where each team is given a feasible task to complete in its workspace on its own, and where teams are allowed to transfer robots between each other. We study the problem of finding a coordination of robot transfers between teams to ensure an optimal global plan (with minimum makespan) so that all tasks can be completed as soon as possible by helping each other. We propose to solve this problem using answer set programming.

AAAI Conference 2013 Conference Paper

A General Formal Framework for Pathfinding Problems with Multiple Agents

• Esra Erdem
• Doga Kisa
• Umut Oztok
• Peter Schüller

Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, going around obstacles. Pathfinding for multiple agents also aims to plan such routes for each agent, subject to different constraints, such as restrictions on the length of each path or on the total length of paths, no self-intersecting paths, no intersection of paths/plans, no crossing/meeting each other. It also has variations for finding optimal solutions, e. g. , with respect to the maximum path length, or the sum of plan lengths. These problems are important for many real-life applications, such as motion planning, vehicle routing, environmental monitoring, patrolling, computer games. Motivated by such applications, we introduce a formal framework that is general enough to address all these problems: we use the expressive high-level representation formalism and efficient solvers of the declarative programming paradigm Answer Set Programming. We also introduce heuristics to improve the computational efficiency and/or solution quality. We show the applicability and usefulness of our framework by experiments, with randomly generated problem instances on a grid, on a real-world road network, and on a real computer game terrain.

AAAI Conference 2011 Conference Paper

Finding Answers and Generating Explanations for Complex Biomedical Queries

• Esra Erdem
• Yelda Erdem
• Halit Erdogan
• Umut Oztok

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, DRUG- BANK, BIOGRID, CTD and SIDER.

AAAI Conference 2011 Conference Paper

Generating Explanations for Complex Biomedical Queries

• Umut Öztok
• Esra Erdem

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, BI- OGRID, CTD and SIDER.

AAAI Conference 2010 Conference Paper

Finding Semantic Inconsistencies in UMLS using Answer Set Programming

• Halit Erdogan
• Olivier Bodenreider
• Esra Erdem

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.

AAAI Conference 2010 Conference Paper

Genome Rearrangement: A Planning Approach

• Tansel Uras
• Esra Erdem

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.

AIJ Journal 2010 Journal Article

Updating action domain descriptions

• Thomas Eiter
• Esra Erdem
• Michael Fink
• Ján Senko

AAAI Conference 2008 Conference Paper

Efficient Haplotype Inference with Answer Set Programming

• Esra Erdem

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, SATbased 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.

IJCAI Conference 2007 Conference Paper

• Thomas Eiter
• Esra Erdem
• Wolfgang Faber

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 action1 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 C+ or K.

AAAI Conference 2007 Conference Paper

Forgetting Actions in Domain Descriptions

• Esra Erdem

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 C (a formalism based on causal explanations), and relate it to forgetting in classical logic and logic programming.

AAAI Conference 2005 Conference Paper

Cumulative Effects of Concurrent Actions on Numeric-Valued Fluents

• Esra Erdem

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 effects 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.

AAAI Conference 2005 Conference Paper

Genome Rearrangement and Planning

• Esra Erdem

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.

IJCAI Conference 2005 Conference Paper

Updating Action Domain Descriptions

• Thomas Eiter
• Esra Erdem
• Michael Fink
• Ján

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.