# Publications

Excellent! Next, you can

**embed**this page using one of several options.To the site owner:

**Action required!** Mendeley is changing its
API. In order to keep using Mendeley with BibBase past April
14th, you need to:

- renew the authorization for BibBase on Mendeley, and
- update the BibBase URL in your page the same way you did when you initially set up this page.

2015
(3)

ReAct!: An Interactive Educational Tool for AI Planning for Robotics.
Dogmus, Z.; Erdem, E.; and Patoglu, V.

doi bibtex abstract

*Education, IEEE Transactions on*, 58(1): 15-24. Feb 2015.doi bibtex abstract

@ARTICLE{6807834, author={Dogmus, Z. and Erdem, E. and Patoglu, V.}, journal={Education, IEEE Transactions on}, title={ReAct!: An Interactive Educational Tool for AI Planning for Robotics}, year={2015}, month={Feb}, volume={58}, number={1}, pages={15-24}, keywords={computer aided instruction;control engineering computing;control engineering education;educational courses;educational robots;interactive systems;planning (artificial intelligence);spatial reasoning;teaching;user interfaces;AI planning;ReAct;artificial intelligence planning;cognitive factories;concurrency;dynamic domains;geometric reasoning;high-level reasoning;indirect action effects;instructor teaching experience;intelligent interactive user interface;interactive educational tool;quantitative student surveys;research-oriented cognitive robotics course;robot actions;service robotics;state-transition constraints;Artificial intelligence;Cognition;Cognitive robotics;Education;Educational robots;Planning;Artificial intelligence (AI) planning;automated reasoning;hybrid planning;knowledge representation;robotics}, doi={10.1109/TE.2014.2318678}, ISSN={0018-9359}, abstract = {This paper presents ReAct!, an interactive educational tool for artificial intelligence (AI) planning for robotics. ReAct! enables students to describe robots' actions and change in dynamic domains without first having to know about the syntactic and semantic details of the underlying formalism, and to solve planning problems using state-of-the-art reasoners without having to know about their input/output language or usage. In particular, ReAct! can be used to represent sophisticated dynamic domains that feature concurrency, indirect effects of actions, and state/transition constraints. ReAct! also allows the embedding of externally defined calculations (e.g., checking for collision-free continuous trajectories) into domain representations of hybrid domains that require a tight integration of (discrete) high-level reasoning with (continuous) geometric reasoning. ReAct! also allows students to solve planning problems that involve complex temporal goals. This broad applicability, and the intelligent interactive user interface, mean that students can work on interesting and challenging domains, ranging from service robotics to cognitive factories, leading to hands-on robotic applications. The efficacy of ReAct! was evaluated from three different points of view: 1) the course outcomes that demonstrate its utility in achieving the learning objectives of a research-oriented cognitive robotics course; 2) the user friendliness and usefulness of ReAct! for students, as evaluated by quantitative student surveys; and 3) instructors' experience of teaching the course either with or without ReAct!.}, }

This paper presents ReAct!, an interactive educational tool for artificial intelligence (AI) planning for robotics. ReAct! enables students to describe robots' actions and change in dynamic domains without first having to know about the syntactic and semantic details of the underlying formalism, and to solve planning problems using state-of-the-art reasoners without having to know about their input/output language or usage. In particular, ReAct! can be used to represent sophisticated dynamic domains that feature concurrency, indirect effects of actions, and state/transition constraints. ReAct! also allows the embedding of externally defined calculations (e.g., checking for collision-free continuous trajectories) into domain representations of hybrid domains that require a tight integration of (discrete) high-level reasoning with (continuous) geometric reasoning. ReAct! also allows students to solve planning problems that involve complex temporal goals. This broad applicability, and the intelligent interactive user interface, mean that students can work on interesting and challenging domains, ranging from service robotics to cognitive factories, leading to hands-on robotic applications. The efficacy of ReAct! was evaluated from three different points of view: 1) the course outcomes that demonstrate its utility in achieving the learning objectives of a research-oriented cognitive robotics course; 2) the user friendliness and usefulness of ReAct! for students, as evaluated by quantitative student surveys; and 3) instructors' experience of teaching the course either with or without ReAct!.

RehabRobo-Onto: Design, development and maintenance of a rehabilitation robotics ontology on the cloud .
Dogmus, Z.; Erdem, E.; and Patoglu, V.

Paper doi bibtex abstract

*Robotics and Computer-Integrated Manufacturing*, 33(0): 100--109. 2015. Special Issue on Knowledge Driven Robotics and ManufacturingPaper doi bibtex abstract

@article{Dogmus2015100, title = "RehabRobo-Onto: Design, development and maintenance of a rehabilitation robotics ontology on the cloud ", journal = "Robotics and Computer-Integrated Manufacturing ", volume = "33", number = "0", pages = "100--109", year = "2015", note = "Special Issue on Knowledge Driven Robotics and Manufacturing ", issn = "0736-5845", doi = "http://dx.doi.org/10.1016/j.rcim.2014.08.010", url = "http://www.sciencedirect.com/science/article/pii/S0736584514000714", author = "Zeynep Dogmus and Esra Erdem and Volkan Patoglu", keywords = "Rehabilitation robotics", keywords = "Ontologies", keywords = "Knowledge representation ", abstract = "Abstract Representing the available information about rehabilitation robots in a structured form, as an ontology, facilitates access to various kinds of information about the existing robots, and thus it is important both from the point of view of rehabilitation robotics and from the point of view of physical medicine. Rehabilitation robotics researchers can learn various properties of the existing robots and access to the related publications to further improve the state-of-the-art. Physical medicine experts can find information about rehabilitation robots and related publications (possibly including results of clinical studies) to better identify the right robot for a particular therapy or patient population. Therefore, considering also the advantages of ontologies and ontological reasoning, such as interoperability of various heterogeneous knowledge resources (e.g., patient databases or disease ontologies), such an ontology provides the underlying mechanisms for translational physical medicine, from bench-to-bed and back, and personalized rehabilitation robotics. With these motivations, the first formal rehabilitation robotics ontology, called RehabRobo-Onto, is designed and developed, collaborating with experts in robotics and in physical medicine. A web based software (called RehabRobo-Query) with an easy-to-use intelligent user-interface is also built. RehabRobo-Query allows robot designers to add/modify information about their rehabilitation robots to/from RehabRobo-Onto. The ontology system consisting of RehabRobo-Onto and RehabRobo-Query is made available on the cloud, utilizing Amazon Web services, to provide a reliable environment for access, development and maintenance of RehabRobo-Onto by rehabilitation robot designers and physical medicine experts around the world. " }

Abstract Representing the available information about rehabilitation robots in a structured form, as an ontology, facilitates access to various kinds of information about the existing robots, and thus it is important both from the point of view of rehabilitation robotics and from the point of view of physical medicine. Rehabilitation robotics researchers can learn various properties of the existing robots and access to the related publications to further improve the state-of-the-art. Physical medicine experts can find information about rehabilitation robots and related publications (possibly including results of clinical studies) to better identify the right robot for a particular therapy or patient population. Therefore, considering also the advantages of ontologies and ontological reasoning, such as interoperability of various heterogeneous knowledge resources (e.g., patient databases or disease ontologies), such an ontology provides the underlying mechanisms for translational physical medicine, from bench-to-bed and back, and personalized rehabilitation robotics. With these motivations, the first formal rehabilitation robotics ontology, called RehabRobo-Onto, is designed and developed, collaborating with experts in robotics and in physical medicine. A web based software (called RehabRobo-Query) with an easy-to-use intelligent user-interface is also built. RehabRobo-Query allows robot designers to add/modify information about their rehabilitation robots to/from RehabRobo-Onto. The ontology system consisting of RehabRobo-Onto and RehabRobo-Query is made available on the cloud, utilizing Amazon Web services, to provide a reliable environment for access, development and maintenance of RehabRobo-Onto by rehabilitation robot designers and physical medicine experts around the world.

Integrating Hybrid Diagnostic Reasoning in Plan Execution Monitoring for Cognitive Factories with Multiple Robots.
Erdem, E.; Patoglu, V.; and Saribatur, Z. G.
In

bibtex abstract

*Proc. of ICRA*, 2015. Finalist for Best Conference Paper Award, Finalist for Best Cognitive Robotics Paper Awardbibtex abstract

@inproceedings{erdem15, title={Integrating Hybrid Diagnostic Reasoning in Plan Execution Monitoring for Cognitive Factories with Multiple Robots}, author={Esra Erdem and Volkan Patoglu and Zeynep G. Saribatur}, booktitle={Proc. of ICRA}, note={Finalist for Best Conference Paper Award, Finalist for Best Cognitive Robotics Paper Award}, pages={}, year={2015}, abstract={For reliable and fault tolerant operation of cognitive factories, we introduce an algorithm to monitor plan executions. According to this algorithm, when some changes or discrepancies are detected, appropriate decisions are given based on the causes of these changes or discrepancies. To identify these causes (e.g., broken robots or robot components), we introduce a novel diagnostic reasoning method which synergistically integrates hypothetical reasoning, geometric reasoning, and learning from earlier experiences. Based on these causes, if necessary, new hybrid plans (task plans integrated with feasibility checks) are computed to reach the manufacturing goals by allowing repairs of robots/components. The results of our experiments over reasonably-sized cognitive factory scenarios show the usefulness of (i) diagnostic reasoning for execution monitoring, (ii) allowing repair actions during replanning, and (iii) learning from experiences. We provide a video of dynamic simulation of our execution monitoring algorithm with Kuka youBots and a Nao humanoid robot as the supplementary material.} }

For reliable and fault tolerant operation of cognitive factories, we introduce an algorithm to monitor plan executions. According to this algorithm, when some changes or discrepancies are detected, appropriate decisions are given based on the causes of these changes or discrepancies. To identify these causes (e.g., broken robots or robot components), we introduce a novel diagnostic reasoning method which synergistically integrates hypothetical reasoning, geometric reasoning, and learning from earlier experiences. Based on these causes, if necessary, new hybrid plans (task plans integrated with feasibility checks) are computed to reach the manufacturing goals by allowing repairs of robots/components. The results of our experiments over reasonably-sized cognitive factory scenarios show the usefulness of (i) diagnostic reasoning for execution monitoring, (ii) allowing repair actions during replanning, and (iii) learning from experiences. We provide a video of dynamic simulation of our execution monitoring algorithm with Kuka youBots and a Nao humanoid robot as the supplementary material.

2014
(6)

Answering Natural Language Queries about Rehabilitation Robotics Ontology on the Cloud.
Dogmus, Z.; Erdem, E.; and Patoglu, V.
In

bibtex

*Proc. of KEOD*, pages 75--83, 2014.bibtex

@inproceedings{DogmusEP14, author = {Zeynep Dogmus and Esra Erdem and Volkan Patoglu}, title = {Answering Natural Language Queries about Rehabilitation Robotics Ontology on the Cloud}, booktitle = {Proc. of KEOD}, year = {2014}, pages = {75--83} }

Cognitive Factories with Multiple Teams of Heterogeneous Robots: Hybrid Reasoning for Optimal Feasible Global Plans.
Saribatur, Z. G.; Erdem, E.; and Patoglu, V.
In

bibtex abstract

*Proc. of IROS*, pages 2923--2930, 2014.bibtex abstract

@inproceedings{saribatur14, title={Cognitive Factories with Multiple Teams of Heterogeneous Robots: Hybrid Reasoning for Optimal Feasible Global Plans}, author={Zeynep G. Saribatur and Esra Erdem and Volkan Patoglu}, booktitle={Proc. of IROS}, pages={2923--2930}, year={2014}, abstract={We consider cognitive factories with multiple teams of heterogenous robots, and address two key challenges of these domains, hybrid reasoning for each team and finding an optimal global plan (with minimum makespan) for multiple teams. For hybrid reasoning, we propose (i) modeling each team's workspace taking into account capabilities of heterogeneous robots, (ii) embedding continuous external computations into discrete symbolic representation and reasoning by combining different methods of integration, (iii) not only optimizing the makespans of local plans but also minimizing the total cost of robotic actions, where costs of actions can be defined in various ways. To find a global plan with minimum makespan, we propose a semi-distributed approach: we formulate the problem of finding an optimal coordination of teams that can help each other, prove its intractability, and describe how to solve this problem using existing automated reasoners. As a case study, we show applications of our hybrid reasoning and coordination approaches on a cognitive toy factory with dynamic simulations and physical implementation utilizing KuKa youBots and Lego NXT robots (supplementary video provided). We also present experimental results to discuss the scalability of these methods.} }

We consider cognitive factories with multiple teams of heterogenous robots, and address two key challenges of these domains, hybrid reasoning for each team and finding an optimal global plan (with minimum makespan) for multiple teams. For hybrid reasoning, we propose (i) modeling each team's workspace taking into account capabilities of heterogeneous robots, (ii) embedding continuous external computations into discrete symbolic representation and reasoning by combining different methods of integration, (iii) not only optimizing the makespans of local plans but also minimizing the total cost of robotic actions, where costs of actions can be defined in various ways. To find a global plan with minimum makespan, we propose a semi-distributed approach: we formulate the problem of finding an optimal coordination of teams that can help each other, prove its intractability, and describe how to solve this problem using existing automated reasoners. As a case study, we show applications of our hybrid reasoning and coordination approaches on a cognitive toy factory with dynamic simulations and physical implementation utilizing KuKa youBots and Lego NXT robots (supplementary video provided). We also present experimental results to discuss the scalability of these methods.

A Systematic Analysis of Levels of Integration between High-Level Task Planning and Low-Level Feasibility Checks.
Erdem, E.; Patoglu, V.; and Schüller, P.
In

bibtex

*Proc. of RCRA*, 2014.bibtex

@inproceedings{rcra14, author = {Esra Erdem and Volkan Patoglu and Peter Sch\"{u}ller}, title = {A Systematic Analysis of Levels of Integration between High-Level Task Planning and Low-Level Feasibility Checks}, year = {2014}, booktitle={Proc. of RCRA} }

Geometric Rearrangement of Multiple Movable Objects on Cluttered Surfaces: A Hybrid Reasoning Approach.
Havur, G.; Ozbilgin, G.; Erdem, E.; and Patoglu, V.
In

bibtex abstract 3 downloads

*Proc. of ICRA*, pages 445--452, 2014.bibtex abstract 3 downloads

@inproceedings{icra14, author={Giray Havur and Guchan Ozbilgin and Esra Erdem and Volkan Patoglu}, title={Geometric Rearrangement of Multiple Movable Objects on Cluttered Surfaces: A Hybrid Reasoning Approach}, booktitle={Proc. of ICRA}, year={2014}, pages={445--452}, abstract={We introduce a novel computational method for geometric rearrangement of multiple movable objects on a cluttered surface, where objects can change locations more than once by pick and/or push actions. This method consists of four stages: (i) finding tentative collision-free final configurations for all objects (all the new objects together with all other objects in the clutter) while also trying to minimize the number of object relocations, (ii) gridization of the continuous plane for a discrete placement of the initial configurations and the tentative final configurations of objects on the cluttered surface, (iii) finding a sequence of feasible pick and push actions to achieve the final discrete placement for the objects in the clutter from their initial discrete place, while simultaneously minimizing the number of object relocations, and (iv) finding feasible final configurations for all objects according to the optimal task plan calculated in stage (iii). For (i) and (iv), we introduce algorithms that utilize local search with random restarts; for (ii), we introduce a mathematical modeling of the discretization problem and use the state-of-the-art ASP reasoners to solve it; for (iii) we introduce a formal hybrid reasoning framework that allows embedding of geometric reasoning in task planning, and use the expressive formalisms and reasoners of ASP. We illustrate the usefulness of our integrated AI approach with several scenarios that cannot be solved by the existing approaches. We also provide a dynamic simulation for one of the scenarios, as supplementary material.} }

We introduce a novel computational method for geometric rearrangement of multiple movable objects on a cluttered surface, where objects can change locations more than once by pick and/or push actions. This method consists of four stages: (i) finding tentative collision-free final configurations for all objects (all the new objects together with all other objects in the clutter) while also trying to minimize the number of object relocations, (ii) gridization of the continuous plane for a discrete placement of the initial configurations and the tentative final configurations of objects on the cluttered surface, (iii) finding a sequence of feasible pick and push actions to achieve the final discrete placement for the objects in the clutter from their initial discrete place, while simultaneously minimizing the number of object relocations, and (iv) finding feasible final configurations for all objects according to the optimal task plan calculated in stage (iii). For (i) and (iv), we introduce algorithms that utilize local search with random restarts; for (ii), we introduce a mathematical modeling of the discretization problem and use the state-of-the-art ASP reasoners to solve it; for (iii) we introduce a formal hybrid reasoning framework that allows embedding of geometric reasoning in task planning, and use the expressive formalisms and reasoners of ASP. We illustrate the usefulness of our integrated AI approach with several scenarios that cannot be solved by the existing approaches. We also provide a dynamic simulation for one of the scenarios, as supplementary material.

Hybrid Reasoning for Geometric Rearrangement of Multiple Movable Objects on Cluttered Surfaces.
Havur, G.; Ozbilgin, G.; Erdem, E.; and Patoglu, V.
In

bibtex

*Proc. of CogRob*, 2014.bibtex

@inproceedings{cogrob14, author={Giray Havur and Guchan Ozbilgin and Esra Erdem and Volkan Patoglu}, title={Hybrid Reasoning for Geometric Rearrangement of Multiple Movable Objects on Cluttered Surfaces}, booktitle={Proc. of CogRob}, year={2014} }

Coordination of Multiple Teams of Robots for an Optimal Global Plan.
Saribatur, Z. G.; Erdem, E.; and Patoglu, V.
In

Paper bibtex abstract 5 downloads

*Proc. of AAAI*, pages 3132--3133, 2014.Paper bibtex abstract 5 downloads

@inproceedings{saribaturEP14, author = {Zeynep Gozen Saribatur and Esra Erdem and Volkan Patoglu}, title = {Coordination of Multiple Teams of Robots for an Optimal Global Plan}, booktitle = {Proc. of AAAI}, pages = {3132--3133}, year = {2014}, url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8266}, abstract = {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.} }

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.

2013
(15)

Finding optimal plans for multiple teams of robots through a mediator: A logic-based approach.
Erdem, E.; Patoglu, V.; Saribatur, Z. G.; Schüller, P.; and Uras, T.

Paper doi bibtex

*Theory and Practice of Logic Programming*, 13: 831--846. 7 2013.Paper doi bibtex

@article{TLP:9011730, author = {Erdem, Esra and Patoglu, Volkan and Saribatur, Zeynep G. and Schüller, Peter and Uras, Tansel}, title = {Finding optimal plans for multiple teams of robots through a mediator: A logic-based approach}, journal = {Theory and Practice of Logic Programming}, volume = {13}, issue = {Special Issue 4-5}, month = {7}, year = {2013}, issn = {1475-3081}, pages = {831--846}, numpages = {16}, doi = {10.1017/S1471068413000525}, URL = {http://journals.cambridge.org/article_S1471068413000525}, }

Levels of Integration between Low-Level Reasoning and Task Planning.
Schüller, P.; Patoglu, V.; and Erdem, E.
In

bibtex

*Proc. AAAI 2013 Workshop on Intelligent Robotic Systems*, 2013.bibtex

@inproceedings{aaaiIRS13, author = {Peter Sch\"{u}ller and Volkan Patoglu and Esra Erdem}, title = {Levels of Integration between Low-Level Reasoning and Task Planning}, year = {2013}, booktitle={Proc. AAAI 2013 Workshop on Intelligent Robotic Systems} }

A Case Study on the Tower of Hanoi Challenge: Representation, Reasoning and Execution.
Havir, G.; Haspalamutgil, K.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

bibtex abstract

*IEEE International Conference on Robotics and Automation (ICRA 2013)*, 2013.bibtex abstract

@InProceedings{Havur2013a, booktitle = {IEEE International Conference on Robotics and Automation (ICRA 2013)}, author = {Giray Havir and Kadir Haspalamutgil and Can Palaz and Esra Erdem and Volkan Patoglu}, title = {A Case Study on the Tower of Hanoi Challenge{: R}epresentation, Reasoning and Execution}, year = {2013}, abstract = {The Tower of Hanoi puzzle, has recently been established as a robotics challenge as a part of EU Robotics coordination action in 2011 and IEEE IROS Conference in 2012. It provides a good standardized test bed to evaluate integration of high-level reasoning capabilities of robots together with their manipulation and perception aspects.We address this challenge within a general planning and monitoring framework: we represent the puzzle in a logic-based formalism, integrate task planning and motion planning, solve this hybrid planning problem with a state-of-the-art automated reasoner (e.g., a SAT solver), execute the computed plans under feedback control while also monitoring for failures, and recover from failures as required. We show the applicability of this framework by implementing it using two robotic manipulators on a physical experimental setup.} }

The Tower of Hanoi puzzle, has recently been established as a robotics challenge as a part of EU Robotics coordination action in 2011 and IEEE IROS Conference in 2012. It provides a good standardized test bed to evaluate integration of high-level reasoning capabilities of robots together with their manipulation and perception aspects.We address this challenge within a general planning and monitoring framework: we represent the puzzle in a logic-based formalism, integrate task planning and motion planning, solve this hybrid planning problem with a state-of-the-art automated reasoner (e.g., a SAT solver), execute the computed plans under feedback control while also monitoring for failures, and recover from failures as required. We show the applicability of this framework by implementing it using two robotic manipulators on a physical experimental setup.

Rehabilitation Robotics Ontology on the Cloud.
Dogmus, Z.; Papantoniou, A.; Kilinc, M.; Yildirim, S.; Erdem, E.; and Patoglu, V.
In

bibtex abstract

*IEEE International Conference on Rehabilitation Robotics (ICORR 2013)*, 2013.bibtex abstract

@InProceedings{Dogmus2013, booktitle = {IEEE International Conference on Rehabilitation Robotics (ICORR 2013)}, author = {Zeynep Dogmus and Agis Papantoniou and Muhammed Kilinc and Sibel Yildirim and Esra Erdem and Volkan Patoglu}, title = {Rehabilitation Robotics Ontology on the Cloud}, year = {2013}, abstract = {We introduce the first formal rehabilitation robotics ontology, called RehabRobo-Onto, to represent information about rehabilitation robots and their properties; and a software system RehabRobo-Query to facilitate access to this ontology. RehabRobo-Query is made available on the cloud, utilizing Amazon Web services, so that 1) rehabilitation robot designers around the world can add/modify information about their robots in RehabRobo-Onto, and 2) rehabilitation robot designers and physical medicine experts around the world can access the knowledge in RehabRobo-Onto by means of questions about robots, in natural language, with the guide of the intelligent user-interface of RehabRobo-Query. The ontology system consisting of RehabRobo-Onto and RehabRobo-Query is of great value to robot designers as well as physical therapists and medical doctors. On the one hand, robot designers can access various properties of the existing robots and to the related publications to further improve the state-of-the-art. On the other hand, physical therapists and medical doctors can utilize the ontology to compare rehabilitation robots and to identify the ones that serve best to cover their needs, or to evaluate the effects of various devices for targeted joint exercises on patients with specific disorders.} }

We introduce the first formal rehabilitation robotics ontology, called RehabRobo-Onto, to represent information about rehabilitation robots and their properties; and a software system RehabRobo-Query to facilitate access to this ontology. RehabRobo-Query is made available on the cloud, utilizing Amazon Web services, so that 1) rehabilitation robot designers around the world can add/modify information about their robots in RehabRobo-Onto, and 2) rehabilitation robot designers and physical medicine experts around the world can access the knowledge in RehabRobo-Onto by means of questions about robots, in natural language, with the guide of the intelligent user-interface of RehabRobo-Query. The ontology system consisting of RehabRobo-Onto and RehabRobo-Query is of great value to robot designers as well as physical therapists and medical doctors. On the one hand, robot designers can access various properties of the existing robots and to the related publications to further improve the state-of-the-art. On the other hand, physical therapists and medical doctors can utilize the ontology to compare rehabilitation robots and to identify the ones that serve best to cover their needs, or to evaluate the effects of various devices for targeted joint exercises on patients with specific disorders.

Integration of Continuous Low-Level Reasoning with Task Planning: A Systematic Analysis.
Scheuller, P.; Patoglu, V.; and Erdem, E.
In

bibtex

*IEEE International Conference on Robotics and Automation, Workshop on Combining Task and Motion Planning (TAMP 2013)*, 2013.bibtex

@InProceedings{Scheuller2013a, booktitle = {IEEE International Conference on Robotics and Automation, Workshop on Combining Task and Motion Planning (TAMP 2013)}, author = {Peter Scheuller and Volkan Patoglu and Esra Erdem}, title = {Integration of Continuous Low-Level Reasoning with Task Planning{: A} Systematic Analysis}, year = {2013}, }

ReAct! An Interactive Tool for Hybrid Planning in Robotics.
Dogmus, Z.; Patoglu, V.; and Erdem, E.
In

bibtex

*Robotics: Sience and Systems, Combined Robot Motion Planning and AI Planning for Practical Applications (RSS 2013)*, 2013.bibtex

@InProceedings{Dogmus2013b, booktitle = {Robotics: Sience and Systems, Combined Robot Motion Planning and AI Planning for Practical Applications (RSS 2013)}, author = {Zeynep Dogmus and Volkan Patoglu and Esra Erdem}, title = {{ReAct! An} Interactive Tool for Hybrid Planning in Robotics}, year = {2013}, }

A Systematic Analysis of Levels of Integration between Task Planning and Low-Level Reasoning.
Scheuller, P.; Patoglu, V.; and Erdem, E.
In

bibtex

*Robotics: Sience and Systems, Combined Robot Motion Planning and AI Planning for Practical Applications (RSS 2013)*, 2013.bibtex

@InProceedings{Scheuller2013c, booktitle = {Robotics: Sience and Systems, Combined Robot Motion Planning and AI Planning for Practical Applications (RSS 2013)}, author = {Peter Scheuller and Volkan Patoglu and Esra Erdem}, title = {A Systematic Analysis of Levels of Integration between Task Planning and Low-Level Reasoning}, year = {2013}, }

Guvenli Bilissel Hizmet Robotu CoCoA'nin Gelistirilmesi: Tasarim, Modellenme ve Dinamik Benzetim.
Coruhlu, G.; and Patoglu, V.
In

bibtex

*Otomatik Kontrol Ulusal Toplantisi (TOK 2013)*, 2013.bibtex

@InProceedings{Coruhlu2013a, title = {Guvenli Bilissel Hizmet Robotu {CoCoA'nin} Gelistirilmesi{: Tasarim}, Modellenme ve Dinamik Benzetim}, author = {Gokay Coruhlu and Volkan Patoglu}, booktitle = {Otomatik Kontrol Ulusal Toplantisi (TOK 2013)}, year = {2013}, }

ReAct! An Interactive Tool for Hybrid Planning in Robotics.
Dogmus, Z.; Esra Erdem, undefined; and Patoglu, V.
In

bibtex

*International Conference on Logic Programming (ICLP), Workshop on Knowledge Representation and Reasoning in Robotics*, 2013.bibtex

@InProceedings{Dogmusd, title = {ReAct! An Interactive Tool for Hybrid Planning in Robotics}, author = {Zeynep Dogmus and Esra Erdem, and Volkan Patoglu}, booktitle = {International Conference on Logic Programming (ICLP), Workshop on Knowledge Representation and Reasoning in Robotics}, year = {2013}, }

Integration of 3D Object Recognition and Planning for Robotics Manipulation: A Preliminary Report.
Duff, D. J.; Erdem, E.; and Patoglu, V.
In

bibtex

*International Conference on Logic Programming (ICLP), Workshop on Knowledge Representation and Reasoning in Robotics*, 2013.bibtex

@InProceedings{Erdemw1, title = {Integration of {3D} Object Recognition and Planning for Robotics Manipulation{: A} Preliminary Report}, author = {Damien Jade Duff and Esra Erdem and Volkan Patoglu}, booktitle = {International Conference on Logic Programming (ICLP), Workshop on Knowledge Representation and Reasoning in Robotics}, year = {2013}, }

A Case Study on the Tower of Hanoi Challenge: Representation, Reasoning and Execution.
Havur, G.; Erdem, E.; and Patoglu, V.
In

bibtex

*Computer Science Student Workshop (CSW 2013)*, 2013.bibtex

@InProceedings{Havur2013b, booktitle = {Computer Science Student Workshop (CSW 2013)}, author = {Giray Havur and Esra Erdem and Volkan Patoglu}, title = {A Case Study on the Tower of Hanoi Challenge: Representation, Reasoning and Execution}, year = {2013}, }

Intelligent Physical Rehabilitation using Serious Games.
Gezici, G.; Dogmus, Z.; Erdem, E.; and Patoglu, V.
In

bibtex 1 download

*Computer Science Student Workshop (CSW 2013)*, 2013.bibtex 1 download

@InProceedings{Gezici2013, booktitle = {Computer Science Student Workshop (CSW 2013)}, author = {Gizem Gezici and Zeynep Dogmus and Esra Erdem and Volkan Patoglu}, title = {Intelligent Physical Rehabilitation using Serious Games}, year = {2013}, }

Bilissel Fabrikalarda Birden Fazla Robot Takimi icin Eniyilestirilmis Ayristirilabilir Plan Hesaplanmasi.
Saribatur, Z. G.; Schueller, P.; Patoglu, V.; and Erdem, E.
In

bibtex

*IEEE Sinyal Isleme ve Iletisim Uygulamalari Kurultayi, Bilissel Robotlar ve Uygulamalari Ozel Oturumu (SIU 2013)*, 2013.bibtex

@InProceedings{Saribatur2013, booktitle = {IEEE Sinyal Isleme ve Iletisim Uygulamalari Kurultayi, Bilissel Robotlar ve Uygulamalari Ozel Oturumu (SIU 2013)}, author = {Zeynep G. Saribatur and Peter Schueller and Volkan Patoglu and Esra Erdem}, title = {Bilissel Fabrikalarda Birden Fazla Robot Takimi icin Eniyilestirilmis Ayristirilabilir Plan Hesaplanmasi}, year = {2013}, }

Cozum Kumesi Programlama Kullanarak Ortaklasa Ev Ici Hizmet Robotigi.
Aker, E.; Patoglu, V.; and Erdem, E.
In

bibtex

*IEEE Sinyal Isleme ve Iletisim Uygulamalari Kurultayi, Bilissel Robotlar ve Uygulamalari Ozel Oturumu (SIU 2013)*, 2013.bibtex

@InProceedings{Aker2013, booktitle = {IEEE Sinyal Isleme ve Iletisim Uygulamalari Kurultayi, Bilissel Robotlar ve Uygulamalari Ozel Oturumu (SIU 2013)}, author = {Erdi Aker and Volkan Patoglu and Esra Erdem}, title = {Cozum Kumesi Programlama Kullanarak Ortaklasa Ev Ici Hizmet Robotigi}, year = {2013}, }

Hanoi Kulesi'nin Robotlarla Cozumu icin Nedensel Akil Yurutme, Icra ve Icra Takibi Cercevesi.
Havur, G.; Haspalamutgil, K.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

bibtex

*IEEE Sinyal Isleme ve Iletisim Uygulamalari Kurultayi, Bilissel Robotlar ve Uygulamalari Ozel Oturumu (SIU 2013)*, 2013.bibtex

@InProceedings{Havur2013c, booktitle = {IEEE Sinyal Isleme ve Iletisim Uygulamalari Kurultayi, Bilissel Robotlar ve Uygulamalari Ozel Oturumu (SIU 2013)}, author = {Giray Havur and Kadir Haspalamutgil and Can Palaz and Esra Erdem and Volkan Patoglu}, title = {Hanoi Kulesi'nin Robotlarla Cozumu icin Nedensel Akil Yurutme, Icra ve Icra Takibi Cercevesi}, year = {2013}, }

2012
(6)

BIOQUERY-ASP: Querying Biomedical Ontologies in Natural Language using Answer Set Programming.
Erdem, E.; Erdem, Y.; Erdogan, H.; and Oztok, U.
In

Link bibtex

*Program Book of CSHALS*, 2012.Link bibtex

@inproceedings{cshals12, author = {Esra Erdem and Yelda Erdem and Halit Erdogan and Umut Oztok}, title = {BIOQUERY-ASP: Querying Biomedical Ontologies in Natural Language using Answer Set Programming}, booktitle = {Program Book of CSHALS}, year = {2012}, ee = {http://www.iscb.org/cms_addon/conferences/cshals2012/pdf/CSHALS2012-programWEB.pdf} }

Correct Reasoning -- Essays on Logic-Based AI in Honour of Vladimir Lifschitz.
Erdem, E.; Lee, J.; Lierler, Y.; and Pearce, D.
, editor
s.
Volume 7265, of Lecture Notes in Computer Science. 2012.Springer.

Link bibtex buy

Link bibtex buy

@proceedings{ErdemLLP12, editor = {Esra Erdem and Joohyung Lee and Yuliya Lierler and David Pearce}, title = {Correct Reasoning -- Essays on Logic-Based AI in Honour of Vladimir Lifschitz}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {7265}, year = {2012}, isbn = {978-3-642-30742-3}, ee = {http://dx.doi.org/10.1007/978-3-642-30743-0} }

Applications of Action Languages in Cognitive Robotics.
Erdem, E.; and Patoglu, V.
In

Link bibtex abstract

*Correct Reasoning*, pages 229--246, 2012.Link bibtex abstract

@inproceedings{ErdemP12, author = {Esra Erdem and Volkan Patoglu}, title = {Applications of Action Languages in Cognitive Robotics}, booktitle = {Correct Reasoning}, year = {2012}, pages = {229--246}, ee = {http://dx.doi.org/10.1007/978-3-642-30743-0_16}, abstract = {We summarize some applications of action languages in robotics, focusing on the following three challenges: 1) bridging the gap between low-level continuous geometric reasoning and high-level discrete causal reasoning; 2) embedding background/commonsense knowledge in high-level reasoning; 3) planning/prediction with complex (temporal) goals/constraints. We discuss how these challenges can be handled using computational methods of action languages, and elaborate on the usefulness of action languages to extend the classical 3-layer robot control architecture. } }

We summarize some applications of action languages in robotics, focusing on the following three challenges: 1) bridging the gap between low-level continuous geometric reasoning and high-level discrete causal reasoning; 2) embedding background/commonsense knowledge in high-level reasoning; 3) planning/prediction with complex (temporal) goals/constraints. We discuss how these challenges can be handled using computational methods of action languages, and elaborate on the usefulness of action languages to extend the classical 3-layer robot control architecture.

Developing and Maintaining an Ontology for Rehabilitation Robotics.
Dogmus, Z.; Gezici, G.; Erdem, E.; and Patoglu, V.
In

bibtex abstract

*Proc. of the 4'th International Conference on Knowledge Engineering and Ontology Development (KEOD 2012)*, 2012. To appearbibtex abstract

@inproceedings{keod12, author = {Zeynep Dogmus and Gizem Gezici and Esra Erdem and Volkan Patoglu}, title = {Developing and Maintaining an Ontology for Rehabilitation Robotics}, booktitle = {Proc. of the 4'th International Conference on Knowledge Engineering and Ontology Development (KEOD 2012)}, year = {2012}, note = {To appear}, abstract = {Representing the available information about rehabilitation robots in a structured form, like ontologies, facilitates access to various kinds of information about the existing robots, and thus it is important both from the point of view of rehabilitation robotics and from the point of view of physical medicine. Rehabilitation robotics researchers can learn various properties of the existing robots and access to the related publications to further improve the state-of-the-art. Physical medicine experts can find information about rehabilitation robots and related publications (possibly including results of clinical studies) to better identify the right robot for a particular therapy or patient population. Therefore, considering also the advantages of ontologies and ontological reasoning, such as interoperability of various heterogenous knowledge resources (e.g., patient databases or disease ontologies), such an ontology provides the underlying mechanisms for translational physical medicine, from bench-to-bed and back, and personalized rehabilitation robotics. With these motivations, we have designed and developed the first formal rehabilitation robotics ontology, called REHABROBO-ONTO, in OWL, collaborating with experts in robotics and in physical medicine. We have also built a software (called REHABROBO-QUERY) with an easy-to-use intelligent user-interface that allows robot designers to add/modify information about their rehabilitation robots to/from REHABROBO-ONTO.} }

Representing the available information about rehabilitation robots in a structured form, like ontologies, facilitates access to various kinds of information about the existing robots, and thus it is important both from the point of view of rehabilitation robotics and from the point of view of physical medicine. Rehabilitation robotics researchers can learn various properties of the existing robots and access to the related publications to further improve the state-of-the-art. Physical medicine experts can find information about rehabilitation robots and related publications (possibly including results of clinical studies) to better identify the right robot for a particular therapy or patient population. Therefore, considering also the advantages of ontologies and ontological reasoning, such as interoperability of various heterogenous knowledge resources (e.g., patient databases or disease ontologies), such an ontology provides the underlying mechanisms for translational physical medicine, from bench-to-bed and back, and personalized rehabilitation robotics. With these motivations, we have designed and developed the first formal rehabilitation robotics ontology, called REHABROBO-ONTO, in OWL, collaborating with experts in robotics and in physical medicine. We have also built a software (called REHABROBO-QUERY) with an easy-to-use intelligent user-interface that allows robot designers to add/modify information about their rehabilitation robots to/from REHABROBO-ONTO.

Causality-Based Planning and Diagnostic Reasoning for Cognitive Factories.
Erdem, E.; Haspalamutgil, K.; Patoglu, V.; and Uras, T.
In

bibtex abstract

*Proc. of the 17'th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2012)*, 2012. To appearbibtex abstract

@inproceedings{etfa12, author = {Esra Erdem and Kadir Haspalamutgil and Volkan Patoglu and Tansel Uras}, title = {Causality-Based Planning and Diagnostic Reasoning for Cognitive Factories}, booktitle = {Proc. of the 17'th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2012)}, year = {2012}, note = {To appear}, abstract={We propose the use of causality-based formal representation and automated reasoning methods from artificial intelligence to endow multiple teams of robots in a factory, with high-level cognitive capabilities, such as, optimal planning and diagnostic reasoning. In particular, we introduce algorithms for finding optimal decoupled plans and diagnosing the cause of a failure/discrepancy (e.g., robots may get broken or tasks may get reassigned to teams). We discuss how these algorithms can be embedded in an execution and monitoring framework effectively by allowing reusability of computed plans in case of failures, and show the applicability of these algorithms on an intelligent factory scenario. } }

We propose the use of causality-based formal representation and automated reasoning methods from artificial intelligence to endow multiple teams of robots in a factory, with high-level cognitive capabilities, such as, optimal planning and diagnostic reasoning. In particular, we introduce algorithms for finding optimal decoupled plans and diagnosing the cause of a failure/discrepancy (e.g., robots may get broken or tasks may get reassigned to teams). We discuss how these algorithms can be embedded in an execution and monitoring framework effectively by allowing reusability of computed plans in case of failures, and show the applicability of these algorithms on an intelligent factory scenario.

Answer Set Programming for Reasoning with Semantic Knowledge in Collaborative Housekeeping Robotics.
Aker, E.; Patoglu, V.; and Erdem, E.
In

bibtex abstract

*Proc. of IFAC SYROCO*, 2012. To appearbibtex abstract

@inproceedings{syroco12, author = {Erdi Aker and Volkan Patoglu and Esra Erdem}, title = {Answer Set Programming for Reasoning with Semantic Knowledge in Collaborative Housekeeping Robotics}, booktitle = {Proc. of IFAC SYROCO}, year = {2012}, note = {To appear}, abstract = {Answer Set Programming (ASP) is a knowledge representation and reasoning paradigm with high-level expressive logic-based formalism, and efficient solvers; it is applied to solve hard problems in various domains, such as, systems biology, wire routing, space shuttle control. In this paper, we present an application of ASP to housekeeping robotics, by showing how the following problems are addressed using computational methods/tools of ASP: 1) embedding commonsense knowledge automatically extracted from the commonsense knowledge base ConceptNet, into high-level representation, 2) embedding (continuous) geometric reasoning and temporal reasoning about durations of actions, into (discrete) high-level reasoning. We illustrate the applicability of ASP on several housekeeping robotics problems, and report on the computational efficiency in terms of CPU time and memory.} }

Answer Set Programming (ASP) is a knowledge representation and reasoning paradigm with high-level expressive logic-based formalism, and efficient solvers; it is applied to solve hard problems in various domains, such as, systems biology, wire routing, space shuttle control. In this paper, we present an application of ASP to housekeeping robotics, by showing how the following problems are addressed using computational methods/tools of ASP: 1) embedding commonsense knowledge automatically extracted from the commonsense knowledge base ConceptNet, into high-level representation, 2) embedding (continuous) geometric reasoning and temporal reasoning about durations of actions, into (discrete) high-level reasoning. We illustrate the applicability of ASP on several housekeeping robotics problems, and report on the computational efficiency in terms of CPU time and memory.

2011
(16)

Reports of the AAAI 2011 Spring Symposia.
Buller, M.; Cuddihy, P.; Davis, E.; Doherty, P.; Doshi-Velez, F.; Erdem, E.; Fisher, D. H.; Green, N.; Hinkelmann, K.; Maher, M. L.; McLurkin, J.; Maheswaran, R. T.; Rubinelli, S.; Schurr, N.; Scott, D.; Shell, D. A.; Szekely, P. A.; Thonssen, B.; and Urken, A.

Link bibtex abstract

*AI Magazine*, 32(3): 119--127. 2011.Link bibtex abstract

@article{BullerCDDDEFGHMMMRSSSSTU11, author = {Mark Buller and Paul Cuddihy and Ernest Davis and Patrick Doherty and Finale Doshi-Velez and Esra Erdem and Douglas H. Fisher and Nancy Green and Knut Hinkelmann and Mary Lou Maher and James McLurkin and Rajiv T. Maheswaran and Sara Rubinelli and Nathan Schurr and Donia Scott and Dylan A. Shell and Pedro A. Szekely and Barbara Thonssen and Arnold Urken}, title = {Reports of the AAAI 2011 Spring Symposia}, journal = {AI Magazine}, volume = {32}, number = {3}, year = {2011}, pages = {119--127}, ee = {http://www.aaai.org/ojs/index.php/aimagazine/article/view/2370}, abstract = {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. }}

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.

BIOQUERY-ASP: Querying Biomedical Ontologies using Answer Set Programming.
Erdem, E.; Erdogan, H.; and Oztok, U.
In

Link N bibtex abstract

*Proc. of RuleML2011@BRF Challenge*, 2011.Link N bibtex abstract

@inproceedings{ruleML11, author = {Esra Erdem and Halit Erdogan and Umut Oztok}, title = {BIOQUERY-ASP: Querying Biomedical Ontologies using Answer Set Programming}, booktitle = {Proc. of RuleML2011@BRF Challenge}, year = {2011}, ee = {http://ceur-ws.org/Vol-799/}, urlN = {ruleml11.pdf}, abstract={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 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.

Finding Answers and Generating Explanations for Complex Biomedical Queries using Answer Set Programming.
Erdem, E.

Link bibtex

*Association for Logic Programming Newsletter*, . 2011.Link bibtex

@article{erdemALP11, author={Esra Erdem}, title={Finding Answers and Generating Explanations for Complex Biomedical Queries using Answer Set Programming}, journal={Association for Logic Programming Newsletter}, ee = {http://www.cs.nmsu.edu/ALP/2011/09/finding-answers-and-generating-explanations-for-complex-biomedical-queries-using-answer-set-programming/}, year={2011} }

Housekeeping with Multiple Autonomous Robots: Knowledge Representation and Automated Reasoning for a Tightly Integrated Robot Control Architecture.
Aker, E.; Erdogan, A.; Erdem, E.; and Patoglu, V.
In

Link N bibtex abstract 2 downloads

*IROS 2011 Workshop: Knowledge Representation for Autonomous Robots*, 2011.Link N bibtex abstract 2 downloads

@inproceedings{iros11, author = {Erdi Aker and Ahmetcan Erdogan and Esra Erdem and Volkan Patoglu}, title = {Housekeeping with Multiple Autonomous Robots: Knowledge Representation and Automated Reasoning for a Tightly Integrated Robot Control Architecture}, booktitle = {IROS 2011 Workshop: Knowledge Representation for Autonomous Robots}, year = {2011}, ee = {http://www.iros2011.org/WorkshopsAndTutorialsProceedings/SW7/}, urlN = {iros11.pdf}, abstract = {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. }}

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.

Finding Similar/Diverse Solutions in Answer Set Programming.
Eiter, T.; Erdem, E.; Erdogan, H.; and Fink, M.

Link bibtex abstract 1 download

*Theory and Practice of Logic Programming (TPLP)*, . 2011. To appearLink bibtex abstract 1 download

@article{EiterEEF11, author = {Thomas Eiter and Esra Erdem and Halit Erdogan and Michael Fink}, title = {Finding Similar/Diverse Solutions in Answer Set Programming}, journal = {Theory and Practice of Logic Programming (TPLP)}, year = {2011}, note = {To appear}, ee = {http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8419989&fulltextType=RA&fileId=S1471068411000548}, abstract = {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++. } }

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

Answer-Set Programming as a New Approach to Event-Sequence Testing.
Erdem, E.; Inoue, K.; Oetsch, J.; Puehrer, J.; Tompits, H.; and Yilmaz, C.
In

N bibtex abstract

*Proc. of the 3rd International Conference on Advances in System Testing and Validation Lifecycle (VALID'11)*, 2011.N bibtex abstract

@inproceedings{valid11, urln = {valid11.pdf}, author = {Esra Erdem and Katsumi Inoue and Johannes Oetsch and Joerg Puehrer and Hans Tompits and Cemal Yilmaz}, title = {Answer-Set Programming as a New Approach to Event-Sequence Testing}, booktitle = {Proc. of the 3rd International Conference on Advances in System Testing and Validation Lifecycle (VALID'11)}, year = {2011}, abstract={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.} }

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.

Finding Similar/Diverse Solutions in Answer Set Programming: Theory and Applications.
Erdogan, H.
Master's Thesis, Sabanci University, Istanbul, Turkey, 2011.

bibtex abstract

bibtex abstract

@mastersthesis{halitErdogan11, author = {Halit Erdogan}, title = {{Finding Similar/Diverse Solutions in Answer Set Programming: Theory and Applications}}, school = {Sabanci University}, address = {Istanbul, Turkey}, year = {2011}, abstract = {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.} }

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.

Applications of AI Planning in Genome Rearrangement and in Multi-Robot Systems.
Uras, T.
Master's Thesis, Sabanci University, Istanbul, Turkey, 2011.

bibtex abstract

bibtex abstract

@mastersthesis{tanselUras11, author = {Tansel Uras}, title = {{Applications of AI Planning in Genome Rearrangement and in Multi-Robot Systems}}, school = {Sabanci University}, address = {Istanbul, Turkey}, year = {2011}, abstract = {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.} }

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.

Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method.
Cakmak, D.; Erdem, E.; and Erdogan, H.

Link N bibtex abstract

*Annals of Mathematics and Artificial Intelligence (AMAI)*, . 2011.Link N bibtex abstract

@article{amai11, ee = {http://dx.doi.org/10.1007/s10472-011-9242-1}, urln = {amai11.pdf}, author = {Duygu Cakmak and Esra Erdem and Halit Erdogan}, title = {Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method}, journal = {Annals of Mathematics and Artificial Intelligence (AMAI)}, abstract = {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.}, year = {2011} }

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.

Incorporating HADAMAC experiment into NVR for NMR Structure-Based Assignments.
Halit Erdogan, undefined; and Apaydin, M. S.
In

N bibtex abstract

*Proc. of the 6th International Symposium on Health Informatics and Bioinformatics (HIBIT'11)*, 2011.N bibtex abstract

@inproceedings{hibit11, author = {Halit Erdogan, and Mehmet Serkan Apaydin}, title = {Incorporating HADAMAC experiment into NVR for NMR Structure-Based Assignments}, booktitle = {Proc. of the 6th International Symposium on Health Informatics and Bioinformatics (HIBIT'11)}, year = {2011}, urlN ={hibit11.pdf}, abstract = {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}, }

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

Generating Explanations for Complex Biomedical Queries.
Oztok, U.; and Erdem, E.
In

N Link bibtex abstract

*Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)*, 2011.N Link bibtex abstract

@inproceedings{aaaiSA11, author = {Umut Oztok and Esra Erdem}, title = {Generating Explanations for Complex Biomedical Queries}, booktitle = {Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)}, year = {2011}, urlN = {aaaiSA11.pdf}, ee = {http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3519/4137}, abstract={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 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.

Finding Answers and Generating Explanations for Complex Biomedical Queries.
Erdem, E.; Erdem, Y.; Erdogan, H.; and Oztok, U.
In

N Link bibtex abstract 1 download

*Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)*, 2011.N Link bibtex abstract 1 download

@inproceedings{aaai11, author = {Esra Erdem and Yelda Erdem and Halit Erdogan and Umut Oztok}, title = {Finding Answers and Generating Explanations for Complex Biomedical Queries}, booktitle = {Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)}, year = {2011}, urlN = {aaai11.pdf}, ee = {http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3661/3957}, abstract={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 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.

Causal Reasoning for Planning and Coordination of Multiple Housekeeping Robots.
Aker, E.; Erdogan, A.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract 1 download

*Proc. of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11)*, 2011.N bibtex abstract 1 download

@inproceedings{lpnmr11, author = {Erdi Aker and Ahmetcan Erdogan and Esra Erdem and Volkan Patoglu}, title = {Causal Reasoning for Planning and Coordination of Multiple Housekeeping Robots}, booktitle = {Proc. of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11)}, year = {2011}, urlN = {lpnmr11.pdf}, abstract={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. }}

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.

Applications of Answer Set Programming in Phylogenetic Systematics.
Erdem, E.
In

Link N bibtex abstract buy 2 downloads

*Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond*, pages 415-431. 2011.Link N bibtex abstract buy 2 downloads

@incollection{erdem11, author={Esra Erdem}, title={Applications of Answer Set Programming in Phylogenetic Systematics}, booktitle={Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond}, pages={415-431}, year={2011}, ee={http://www.springerlink.com/content/978-3-642-20831-7/#section=888988&page=1&locus=0}, urlN={mg65.pdf}, abstract={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 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.

Housekeeping with Multiple Autonomous Robots: Representation, Reasoning and Execution.
Aker, E.; Erdogan, A.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract

*Proc. of the Tenth International Symposium on Logical Formalization on Commonsense Reasoning (Commonsense 2011)*, 2011.N bibtex abstract

@inproceedings{cs11, author = {Erdi Aker and Ahmetcan Erdogan and Esra Erdem and Volkan Patoglu}, title = {Housekeeping with Multiple Autonomous Robots: Representation, Reasoning and Execution}, booktitle = {Proc. of the Tenth International Symposium on Logical Formalization on Commonsense Reasoning (Commonsense 2011)}, year = {2011}, urlN = {cs11.pdf}, abstract={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 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.

Combining High-Level Causal Reasoning with Low-Level Geometric Reasoning and Motion Planning for Robotic Manipulation.
Erdem, E.; Haspalamutgil, K.; Palaz, C.; Patoglu, V.; and Uras, T.
In

N bibtex abstract 4 downloads

*Proc. of the 2011 IEEE International Conference on Robotics and Automation (ICRA 2011)*, 2011.N bibtex abstract 4 downloads

@inproceedings{icra11, author = {Esra Erdem and Kadir Haspalamutgil and Can Palaz and Volkan Patoglu and Tansel Uras}, title = {Combining High-Level Causal Reasoning with Low-Level Geometric Reasoning and Motion Planning for Robotic Manipulation}, booktitle = {Proc. of the 2011 IEEE International Conference on Robotics and Automation (ICRA 2011)}, year = {2011}, urlN = {icra2011.pdf}, abstract={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. } }

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.

2010
(14)

Reconstructing Weighted Phylogenetic Trees and Phylogenetic Networks Using Answer Set Programming.
Cakmak, D.
Master's Thesis, Sabanci University, Istanbul, Turkey, 2010.

bibtex abstract

bibtex abstract

@mastersthesis{duyguCakmak10, author = {Duygu Cakmak}, title = {{Reconstructing Weighted Phylogenetic Trees and Phylogenetic Networks Using Answer Set Programming}}, school = {Sabanci University}, address = {Istanbul, Turkey}, year = {2010}, abstract = {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 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.

Querying Biomedical Ontologies in Natural Language using Answer Set Programming.
Erdogan, H.; Oztok, U.; Erdem, Y.; and Erdem, E.
In

N bibtex abstract

*Proc. of the Third International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS'10)*, 2010.N bibtex abstract

@inproceedings{swat4ls10, author = {Halit Erdogan and Umut Oztok and Yelda Erdem and Esra Erdem}, title = {Querying Biomedical Ontologies in Natural Language using Answer Set Programming}, booktitle = {Proc. of the Third International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS'10)}, year = {2010}, urlN = {swat4ls10.pdf}, abstract={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.} }

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.

Updating action domain descriptions.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.

Link N bibtex abstract

*Artificial Intelligence*, 174(15): 1172-1221. 2010.Link N bibtex abstract

@article{EiterEFS10, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Updating action domain descriptions}, journal = {Artificial Intelligence}, volume = {174}, number = {15}, year = {2010}, pages = {1172-1221}, ee = {http://dx.doi.org/10.1016/j.artint.2010.07.004}, urlN = {http://people.sabanciuniv.edu/esraerdem/papers/aij10.pdf}, abstract = {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. }, }

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.

A Tight Integration of Task Planning and Motion Planning in an Execution Monitoring Framework.
Haspalamutgil, K.; Palaz, C.; Uras, T.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract 3 downloads

*Proc. of AAAI'10 Workshop, Bridging The Gap Between Task And Motion Planning (BTAMP'10)*, 2010.N bibtex abstract 3 downloads

@inproceedings{btamp10, author = {Kadir Haspalamutgil and Can Palaz and Tansel Uras and Esra Erdem and Volkan Patoglu}, title = {A Tight Integration of Task Planning and Motion Planning in an Execution Monitoring Framework}, booktitle = {Proc. of AAAI'10 Workshop, Bridging The Gap Between Task And Motion Planning (BTAMP'10)}, year = {2010}, urlN = {btamp10.pdf}, abstract={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.} }

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.

Bilissel Montaj Planlama ve Icra Takibi.
Haspalamutgil, K.; Palaz, C.; Uras, T.; Erdem, E.; and Patoglu, V.
In

N bibtex

*Proc. of the National Conference on Automatic Control (TOK'10)*, 2010. In TurkishN bibtex

@inproceedings{tok10, author = {Kadir Haspalamutgil and Can Palaz and Tansel Uras and Esra Erdem and Volkan Patoglu}, title = {Bilissel Montaj Planlama ve Icra Takibi}, booktitle = {Proc. of the National Conference on Automatic Control (TOK'10)}, year = {2010}, urlN = {tok10.pdf}, note = {In Turkish}, }

Exploiting UMLS Semantics for Checking Semantic Consistency among UMLS concepts.
Erdogan, H.; Erdem, E.; and Bodenreider, O.
In

N bibtex abstract 1 download

*Proc. of the 13th International Congress on Medical Informatics (MedInfo'10)*, 2010.N bibtex abstract 1 download

@inproceedings{medinfo10, author = {Halit Erdogan and Esra Erdem and Olivier Bodenreider}, booktitle = {Proc. of the 13th International Congress on Medical Informatics (MedInfo'10)}, year = {2010}, title = {Exploiting {UMLS} Semantics for Checking Semantic Consistency among {UMLS} concepts}, urlN = {2009-medinfo-he.pdf}, abstract = {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.}, }

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.

Using amino acid typing to improve the accuracy of NMR structure based assignments.
Halit Erdogan, undefined; and Apaydin, M. S.
In

bibtex abstract

*Proc. of the 5th International Symposium on Health Informatics and Bioinformatics (HIBIT'10)*, 2010.bibtex abstract

@inproceedings{hibit10, author = {Halit Erdogan, and Mehmet Serkan Apaydin}, booktitle = {Proc. of the 5th International Symposium on Health Informatics and Bioinformatics (HIBIT'10)}, title = {Using amino acid typing to improve the accuracy of NMR structure based assignments}, year = {2010}, abstract = {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.} }

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.

Quantifying solutions in answer set programming.
Erdogan, H.
In

N bibtex abstract

*Proc. of the 1st Computer Science Student Workshop (CSW'10)*, 2010.N bibtex abstract

@inproceedings{csw10, author = {Halit Erdogan}, booktitle = {Proc. of the 1st Computer Science Student Workshop (CSW'10)}, title = {Quantifying solutions in answer set programming}, year = {2010}, abstract = {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.}, urlN = {csw10-halit.pdf}, }

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.

Genome Rearrangement and Planning: Revisited.
Uras, T.; and Erdem, E.
In

N bibtex abstract

*Proc. of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10)*, 2010.N bibtex abstract

@inproceedings{uraserd10, author = {Tansel Uras and Esra Erdem}, title = {Genome Rearrangement and Planning: Revisited}, booktitle = {Proc. of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10)}, year = {2010}, urlN = {icaps10.pdf}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Genome rearrangement: A Planning approach.
Uras, T.
In

N bibtex

*Proc. of the 1st Computer Science Student Workshop (CSW'10)*, 2010.N bibtex

@inproceedings{csw10-tansel, author = {Tansel Uras}, booktitle = {Proc. of the 1st Computer Science Student Workshop (CSW'10)}, title = {Genome rearrangement: A Planning approach}, year = {2010}, urlN = {csw10-tansel.pdf}, }

Haplotype Inference with Polyallelic and Polyploid Genotypes.
Erdem, O.
In

N bibtex

*Proc. of the 1st Computer Science Student Workshop (CSW'10)*, 2010.N bibtex

@inproceedings{csw10-ozan, author = {Ozan Erdem}, booktitle = {Proc. of the 1st Computer Science Student Workshop (CSW'10)}, title = {Haplotype Inference with Polyallelic and Polyploid Genotypes}, year = {2010}, urlN = {csw10-ozan.pdf}, }

Finding Semantic Inconsistencies in UMLS using Answer Set Programming.
Erdogan, H.; Bodenreider, O.; and Erdem, E.
In

Link N bibtex abstract

*Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)*, 2010.Link N bibtex abstract

@inproceedings{sa10-halit, author = {Halit Erdogan and Olivier Bodenreider and Esra Erdem}, booktitle = {Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)}, title = {Finding Semantic Inconsistencies in UMLS using Answer Set Programming}, year = {2010}, ee = {http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1655/2296}, urlN = {sa10-halit.pdf}, abstract = {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 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.

Genome Rearrangement: A Planning Approach.
Uras, T.; and Erdem, E.
In

Link N bibtex abstract

*Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)*, 2010.Link N bibtex abstract

@inproceedings{sa10-tansel, author = {Tansel Uras and Esra Erdem}, booktitle = {Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)}, title = {Genome Rearrangement: A Planning Approach}, year = {2010}, ee = {http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1664/2324}, urlN = {sa10-tansel.pdf}, abstract = {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.}, }

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.

Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method.
Cakmak, D.; Erdem, E.; and Erdogan, H.
In

Link N bibtex abstract

*Proc. of the 17th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'10)*, 2010.Link N bibtex abstract

@inproceedings{rcra10, ee = {http://ceur-ws.org/Vol-616/}, urln = {rcra10.pdf}, author = {Duygu Cakmak and Esra Erdem and Halit Erdogan}, booktitle = {Proc. of the 17th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'10)}, abstract = {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.}, year = {2010}, title = {Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method}, }

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.

2009
(11)

Transforming controlled natural language biomedical queries into answer set programs.
Erdem, E.; and Yeniterzi, R.
In

N bibtex abstract

*Proc. of the Workshop on BioNLP (BioNLP'09)*, pages 117-124, 2009.N bibtex abstract

@inproceedings{1572381, author = {Erdem, Esra and Yeniterzi, Reyyan}, title = {Transforming controlled natural language biomedical queries into answer set programs}, booktitle = {Proc. of the Workshop on BioNLP (BioNLP'09)}, year = {2009}, pages = {117-124}, urlN = {W09-1315.pdf}, abstract = {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 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.

Successful Applications of Answer Set Programming.
Dovier, A.; and Erdem, E.

Link bibtex

*Association for Logic Programming Newsletter*, . 2009.Link bibtex

@article{erdemALP09, author={Agostino Dovier and Esra Erdem}, title={Successful Applications of Answer Set Programming}, journal={Association for Logic Programming Newsletter}, ee = {http://www.cs.nmsu.edu/ALP/2010/03/report-on-application-session-lpnmr09/}, year={2009} }

10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009, Potsdam, Germany, September 14-18, 2009. Proceedings.
Erdem, E.; Lin, F.; and Schaub, T.
, editor
s.
Volume 5753, of Lecture Notes in Computer Science. 2009.Springer.

Link bibtex buy

Link bibtex buy

@proceedings{DBLP:conf/lpnmr/2009, editor = {Esra Erdem and Fangzhen Lin and Torsten Schaub}, title = {10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009, Potsdam, Germany, September 14-18, 2009. Proceedings}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {5753}, year = {2009}, isbn = {978-3-642-04237-9}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6} }

Finding Similar or Diverse Solutions in Answer Set Programming.
Eiter, T.; Erdem, E.; Erdogan, H.; and Fink, M.
In

Link N bibtex abstract

*Proc. of the 25th International Conference of Logic Programming (ICLP'09)*, pages 342-356, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/iclp/EiterEEF09, author = {Thomas Eiter and Esra Erdem and Halit Erdogan and Michael Fink}, title = {Finding Similar or Diverse Solutions in Answer Set Programming}, booktitle = {Proc. of the 25th International Conference of Logic Programming (ICLP'09)}, year = {2009}, pages = {342-356}, ee = {http://dx.doi.org/10.1007/978-3-642-02846-5_29}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {iclp09.pdf}, abstract = {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.}, }

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.

Bridging the Gap between High-Level Reasoning and Low-Level Control.
Caldiran, O.; Haspalamutgil, K.; Ok, A.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

Link N bibtex abstract

*Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 342-354, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/CaldiranHOPEP09, author = {Ozan Caldiran and Kadir Haspalamutgil and Abdullah Ok and Can Palaz and Esra Erdem and Volkan Patoglu}, title = {Bridging the Gap between High-Level Reasoning and Low-Level Control}, booktitle = {Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {342-354}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_29}, urlN = {lpnmr09-cogrobo.pdf}, abstract = {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.}, }

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.

Computing Weighted Solutions in Answer Set Programming.
Cakmak, D.; Erdem, E.; and Erdogan, H.
In

Link N bibtex abstract 1 download

*Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 416-422, 2009.Link N bibtex abstract 1 download

@inproceedings{DBLP:conf/lpnmr/CakmakEE09, author = {Duygu Cakmak and Esra Erdem and Halit Erdogan}, title = {Computing Weighted Solutions in Answer Set Programming}, booktitle = {Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {416-422}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_36}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr09-wasp.pdf}, abstract = {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.}, }

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.

PHYLO-ASP: Phylogenetic Systematics with Answer Set Programming.
Erdem, E.
In

Link N bibtex abstract

*Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 567-572, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/Erdem09, author = {Esra Erdem}, title = {PHYLO-ASP: Phylogenetic Systematics with Answer Set Programming}, booktitle = {Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {567-572}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_59}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr09-phylo.pdf}, abstract = {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.}, }

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.

HAPLO-ASP: Haplotype Inference Using Answer Set Programming.
Erdem, E.; Erdem, O.; and Türe, F.
In

Link N bibtex abstract

*Proc. of the 10th International Conference of Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 573-578, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/ErdemET09, author = {Esra Erdem and Ozan Erdem and Ferhan T{\"u}re}, title = {HAPLO-ASP: Haplotype Inference Using Answer Set Programming}, booktitle = {Proc. of the 10th International Conference of Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {573-578}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_60}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr09-haplo.pdf}, abstract = {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.}, }

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.

From Discrete Task Plans to Continuous Trajectories.
Caldiran, O.; Haspalamutgil, K.; Ok, A.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract

*Proc. of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09) Workshop, Bridging The Gap Between Task And Motion Planning*, 2009.N bibtex abstract

@inproceedings{bridge, author = {O. Caldiran and K. Haspalamutgil and A. Ok and C. Palaz and E. Erdem and V. Patoglu}, title = {From Discrete Task Plans to Continuous Trajectories}, booktitle = {Proc. of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09) Workshop, Bridging The Gap Between Task And Motion Planning}, year = {2009}, urlN = {btamp09.pdf}, abstract = {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 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.

Robot Kontrolu icin Mantiksal Akil Yurutme.
Caldiran, O.; Haspalamutgil, K.; Ok, A.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

N bibtex

*Proc. of the National Conference on Automatic Control (TOK'09)*, 2009. In TurkishN bibtex

@inproceedings{akilyurut, author = {O. Caldiran and K. Haspalamutgil and A. Ok and C. Palaz and E. Erdem and V. Patoglu}, title = {Robot Kontrolu icin Mantiksal Akil Yurutme}, booktitle = {Proc. of the National Conference on Automatic Control (TOK'09)}, year = {2009}, urlN = {tok09.pdf}, note = {In Turkish}, }

Comparing ASP and CP on four grid puzzles.
Celik, M.; Erdogan, H.; Tahaoglu, F.; Uras, T.; and Erdem, E.
In

N Paper bibtex abstract 2 downloads

*Proc. of the 16th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'09)*, 2009.N Paper bibtex abstract 2 downloads

@inproceedings{rcra09, urln = {rcra09.pdf}, author = {Mehmet Celik and Halit Erdogan and Firat Tahaoglu and Tansel Uras and Esra Erdem}, url = {http://krr.sabanciuniv.edu/projects/gridpuzzle/}, booktitle = {Proc. of the 16th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'09)}, title = {Comparing ASP and CP on four grid puzzles}, year = {2009}, abstract = {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.} }

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.

2008
(6)

Efficient Haplotype Inference with Answer Set Programming.
Türe, F.; and Erdem, E.
In

N bibtex abstract

*Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)*, pages 1834-1835, 2008. Student abstractN bibtex abstract

@inproceedings{DBLP:conf/aaai/TureE08, author = {Ferhan T{\"u}re and Esra Erdem}, title = {Efficient Haplotype Inference with Answer Set Programming}, booktitle = {Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)}, year = {2008}, pages = {1834-1835}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {Identifying maternal and paternal inheritance is essential to be able to ﬁnd 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.}, urlN = {sa08.pdf}, note = {Student abstract}, }

Identifying maternal and paternal inheritance is essential to be able to ﬁnd 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.

Efficient Haplotype Inference with Answer Set Programming.
Erdem, E.; and Türe, F.
In

N bibtex abstract

*Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)*, pages 436-441, 2008.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemT08, author = {Esra Erdem and Ferhan T{\"u}re}, title = {Efficient Haplotype Inference with Answer Set Programming}, booktitle = {Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)}, year = {2008}, pages = {436-441}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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.}, urlN = {aaai08.pdf}, }

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.

Undoing the effects of action sequences.
Eiter, T.; Erdem, E.; and Faber, W.

Link bibtex abstract

*Applied Logic*, 6(3): 380-415. 2008.Link bibtex abstract

@article{DBLP:journals/japll/EiterEF08, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Undoing the effects of action sequences}, journal = {Applied Logic}, volume = {6}, number = {3}, year = {2008}, pages = {380-415}, ee = {http://dx.doi.org/10.1016/j.jal.2007.05.002}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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.}, }

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.

A Logic-Based Approach to Finding Explanations for Discrepancies in Optimistic Plan Execution.
Eiter, T.; Erdem, E.; Faber, W.; and Senko, J.

Link bibtex abstract

*Fundamenta Informaticae*, 79(1-2): 25-69. 2008.Link bibtex abstract

@article{DBLP:journals/fuin/EiterEFS08, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber and J{\'a}n Senko}, title = {A Logic-Based Approach to Finding Explanations for Discrepancies in Optimistic Plan Execution}, journal = {Fundamenta Informaticae}, volume = {79}, number = {1-2}, year = {2008}, pages = {25-69}, ee = {http://iospress.metapress.com/openurl.asp?genre=article{\&}issn=0169-2968{\&}volume=79{\&}issue=1{\&}spage=25}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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. }, }

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.

Comparing ASP, CP, ILP on two Challenging Applications: Wire Routing and Haplotype Inference.
Coban, E.; Erdem, E.; and Ture, F.
In

N bibtex abstract

*Proc. of the 2nd International Workshop on Logic and Search (LaSh 2008)*, 2008.N bibtex abstract

@INPROCEEDINGS{comparing, author = {Elvin Coban and Esra Erdem and Ferhan Ture}, title = {Comparing {ASP}, {CP}, {ILP} on two Challenging Applications: Wire Routing and Haplotype Inference}, year = {2008}, booktitle = {Proc. of the 2nd International Workshop on Logic and Search (LaSh 2008)}, abstract = {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.}, urlN = {lash08.pdf}, }

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.

A Preliminary Report on Answering Complex Queries related to Drug Discovery using Answer Set Programming.
Bodenreider, O.; Coban, Z. H.; Doganay, M. C.; Erdem, E.; and Kosucu, H.
In

N bibtex abstract

*Proc. of the 3rd International Workshop on Applications of Logic Programming to the Semantic Web and Web Services (ALPSWS'08)*, 2008.N bibtex abstract

@INPROCEEDINGS{Bodenreider_apreliminary, author = {Olivier Bodenreider and Zeynep H. Coban and Mahir C. Doganay and Esra Erdem and Hilal Kosucu}, title = {A Preliminary Report on Answering Complex Queries related to Drug Discovery using Answer Set Programming}, year = {2008}, booktitle = {Proc. of the 3rd International Workshop on Applications of Logic Programming to the Semantic Web and Web Services (ALPSWS'08)}, urlN = {alpsws.pdf}, abstract = {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.}, }

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.

2007
(5)

Forgetting Actions in Domain Descriptions.
Erdem, E.; and Ferraris, P.
In

N bibtex abstract

*Proc. of the 22nd AAAI Conference on Artificial Intelligence (AAAI'07)*, pages 409-414, 2007.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemF07, author = {Esra Erdem and Paolo Ferraris}, title = {Forgetting Actions in Domain Descriptions}, booktitle = {Proc. of the 22nd AAAI Conference on Artificial Intelligence (AAAI'07)}, year = {2007}, pages = {409-414}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {aaai07.pdf}, abstract = {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. }, }

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

On Reversing Actions: Algorithms and Complexity.
Eiter, T.; Erdem, E.; and Faber, W.
In

Link bibtex abstract

*Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07)*, pages 336-341, 2007.Link bibtex abstract

@inproceedings{DBLP:conf/ijcai/EiterEF07, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {On Reversing Actions: Algorithms and Complexity}, booktitle = {Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07)}, year = {2007}, pages = {336-341}, ee = {http://dli.iiit.ac.in/ijcai/IJCAI-2007/PDF/IJCAI07-052.pdf}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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}. }, }

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 a̧l C+ or a̧l K.

Comparing action descriptions based on semantic preferences.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.

Link bibtex abstract

*Annals of Mathematics and Artificial Intelligence*, 50(3-4): 273-304. 2007.Link bibtex abstract

@article{DBLP:journals/amai/EiterEFS07, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Comparing action descriptions based on semantic preferences}, journal = {Annals of Mathematics and Artificial Intelligence}, volume = {50}, number = {3-4}, year = {2007}, pages = {273-304}, ee = {http://dx.doi.org/10.1007/s10472-007-9077-y}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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. }, }

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.

Inferring Phylogenetic Trees Using Answer Set Programming.
Brooks, D. R.; Erdem, E.; Erdogan, S. T.; Minett, J. W.; and Ringe, D.

Link bibtex abstract 2 downloads

*Automated Reasoning*, 39(4): 471-511. 2007.Link bibtex abstract 2 downloads

@article{DBLP:journals/jar/BrooksEEMR07, author = {Daniel R. Brooks and Esra Erdem and Selim T. Erdogan and James W. Minett and Donald Ringe}, title = {Inferring Phylogenetic Trees Using Answer Set Programming}, journal = {Automated Reasoning}, volume = {39}, number = {4}, year = {2007}, pages = {471-511}, ee = {http://dx.doi.org/10.1007/s10817-007-9082-1}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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 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.

Solving Challenging Grid Puzzles with Answer Set Programming.
Cayli, M.; Karatop, A. G.; Kavlak, E.; Kaynar, H.; Ture, F.; and Erdem, E.
In

N bibtex abstract

*Proc. of ASP*, pages 175-190, 2007.N bibtex abstract

@INPROCEEDINGS{grid, author = {Merve Cayli and Ayse Gül Karatop and Emrah Kavlak and Hakan Kaynar and Ferhan Ture and Esra Erdem}, title = {Solving Challenging Grid Puzzles with Answer Set Programming}, year = {2007}, booktitle = {Proc. of ASP}, pages = {175-190}, abstract = {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.}, urlN = {puzzles-final.pdf}, }

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.

2006
(4)

Resolving Conflicts in Action Descriptions.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.
In

N bibtex abstract

*ECAI 2006, 17th European Conference on Artificial Intelligence, August 29 - September 1, 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS 2006), Proceedings*, pages 367-371, 2006.N bibtex abstract

@inproceedings{DBLP:conf/ecai/EiterEFS06, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Resolving Conflicts in Action Descriptions}, booktitle = {ECAI 2006, 17th European Conference on Artificial Intelligence, August 29 - September 1, 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS 2006), Proceedings}, year = {2006}, pages = {367-371}, urlN = {debug-ecai06-final.pdf}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Comparing Action Descriptions Based on Semantic Preferences.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.
In

Link bibtex abstract

*Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings*, pages 124-137, 2006.Link bibtex abstract

@inproceedings{DBLP:conf/jelia/EiterEFS06, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Comparing Action Descriptions Based on Semantic Preferences}, booktitle = {Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings}, year = {2006}, pages = {124-137}, ee = {http://dx.doi.org/10.1007/11853886_12}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Representing Action Domains with Numeric-Valued Fluents.
Erdem, E.; and Gabaldon, A.
In

Link bibtex abstract

*Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings*, pages 151-163, 2006.Link bibtex abstract

@inproceedings{DBLP:conf/jelia/ErdemG06, author = {Esra Erdem and Alfredo Gabaldon}, title = {Representing Action Domains with Numeric-Valued Fluents}, booktitle = {Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings}, year = {2006}, pages = {151-163}, ee = {http://dx.doi.org/10.1007/11853886_14}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Temporal phylogenetic networks and logic programming.
Erdem, E.; Lifschitz, V.; and Ringe, D.

Link bibtex abstract

*TPLP*, 6(5): 539-558. 2006.Link bibtex abstract

@article{DBLP:journals/tplp/ErdemLR06, author = {Esra Erdem and Vladimir Lifschitz and Donald Ringe}, title = {Temporal phylogenetic networks and logic programming}, journal = {TPLP}, volume = {6}, number = {5}, year = {2006}, pages = {539-558}, ee = {http://dx.doi.org/10.1017/S1471068406002729}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

2005
(4)

Genome Rearrangement and Planning.
Erdem, E.; and Tillier, E. R. M.
In

N bibtex abstract

*Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA*, pages 1139-1144, 2005.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemT05, author = {Esra Erdem and Elisabeth R. M. Tillier}, title = {Genome Rearrangement and Planning}, booktitle = {Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA}, year = {2005}, pages = {1139-1144}, urlN = {genome.pdf}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Cumulative Effects of Concurrent Actions on Numeric-Valued Fluents.
Erdem, E.; and Gabaldon, A.
In

N bibtex abstract

*Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA*, pages 627-632, 2005.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemG05, author = {Esra Erdem and Alfredo Gabaldon}, title = {Cumulative Effects of Concurrent Actions on Numeric-Valued Fluents}, booktitle = {Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA}, year = {2005}, pages = {627-632}, urlN = {additive-AAAI05.pdf}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Updating Action Domain Descriptions.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.
In

Link bibtex abstract

*IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005*, pages 418-423, 2005.Link bibtex abstract

@inproceedings{DBLP:conf/ijcai/EiterEFS05, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Updating Action Domain Descriptions}, booktitle = {IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005}, year = {2005}, pages = {418-423}, ee = {http://www.ijcai.org/papers/1167.pdf}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Character-Based Cladistics and Answer Set Programming.
Brooks, D. R.; Erdem, E.; Minett, J. W.; and Ringe, D.
In

Link bibtex abstract

*Practical Aspects of Declarative Languages, 7th International Symposium, PADL 2005, Long Beach, CA, USA, January 10-11, 2005, Proceedings*, pages 37-51, 2005.Link bibtex abstract

@inproceedings{DBLP:conf/padl/BrooksEMR05, author = {Daniel R. Brooks and Esra Erdem and James W. Minett and Donald Ringe}, title = {Character-Based Cladistics and Answer Set Programming}, booktitle = {Practical Aspects of Declarative Languages, 7th International Symposium, PADL 2005, Long Beach, CA, USA, January 10-11, 2005, Proceedings}, year = {2005}, pages = {37-51}, ee = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3350{\&}spage=37}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

2004
(4)

Diagnosing plan execution discrepancies in a logic-based action framework.
Eiter, T.; Erdem, E.; and Faber, W.
Technical Report INFSYS RR-1843-04-03, Vienna University of Technology, 2004.

Link bibtex abstract

Link bibtex abstract

@techreport{EitErdFab04-2, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Diagnosing plan execution discrepancies in a logic-based action framework}, institution = {Vienna University of Technology}, year = {2004}, number = {INFSYS RR-1843-04-03}, ee = {http://www.kr.tuwien.ac.at/research/reports/rr0403.ps.gz}, abstract = {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.} }

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.

Undoing the effects of action sequences.
Eiter, T.; Erdem, E.; and Faber, W.
Technical Report INFSYS RR-1843-04-05, Vienna University of Technology, 2004.

Link bibtex abstract

Link bibtex abstract

@techreport{EitErdFab04, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Undoing the effects of action sequences}, institution = {Vienna University of Technology}, year = {2004}, number = {INFSYS RR-1843-04-05}, ee = {http://www.kr.tuwien.ac.at/research/reports/rr0405.ps.gz}, abstract = {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.} }

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.

Rectilinear Steiner Tree Construction Using Answer Set Programming.
Erdem, E.; and Wong, M. D. F.
In

Link bibtex abstract

*Logic Programming, 20th International Conference, ICLP 2004, Saint-Malo, France, September 6-10, 2004, Proceedings*, pages 386-399, 2004.Link bibtex abstract

@inproceedings{DBLP:conf/iclp/ErdemW04, author = {Esra Erdem and Martin D. F. Wong}, title = {Rectilinear Steiner Tree Construction Using Answer Set Programming}, booktitle = {Logic Programming, 20th International Conference, ICLP 2004, Saint-Malo, France, September 6-10, 2004, Proceedings}, year = {2004}, pages = {386-399}, ee = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3132{\&}spage=386}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Plan reversals for recovery in execution monitoring.
Eiter, T.; Erdem, E.; and Faber, W.
In

Link bibtex abstract

*10th International Workshop on Non-Monotonic Reasoning (NMR 2004), Whistler, Canada, June 6-8, 2004, Proceedings*, pages 147-154, 2004.Link bibtex abstract

@inproceedings{DBLP:conf/nmr/EiterEF04, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Plan reversals for recovery in execution monitoring}, booktitle = {10th International Workshop on Non-Monotonic Reasoning (NMR 2004), Whistler, Canada, June 6-8, 2004, Proceedings}, year = {2004}, pages = {147-154}, ee = {http://www.pims.math.ca/science/2004/NMR/papers/paper20.pdf}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

2003
(2)

Reconstructing the Evolutionary History of Indo-European Languages Using Answer Set Programming.
Erdem, E.; Lifschitz, V.; Nakhleh, L.; and Ringe, D.
In

Link bibtex abstract

*Practical Aspects of Declarative Languages, 5th International Symposium, PADL 2003, New Orleans, LA, USA, January 13-14, 2003, Proceedings*, pages 160-176, 2003.Link bibtex abstract

@inproceedings{DBLP:conf/padl/ErdemLNR03, author = {Esra Erdem and Vladimir Lifschitz and Luay Nakhleh and Donald Ringe}, title = {Reconstructing the Evolutionary History of Indo-European Languages Using Answer Set Programming}, booktitle = {Practical Aspects of Declarative Languages, 5th International Symposium, PADL 2003, New Orleans, LA, USA, January 13-14, 2003, Proceedings}, year = {2003}, pages = {160-176}, ee = {http://link.springer.de/link/service/series/0558/bibs/2562/25620160.htm}, abstract = {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.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

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.

Tight logic programs.
Erdem, E.; and Lifschitz, V.

bibtex abstract

*TPLP*, 3(4-5): 499-518. 2003.bibtex abstract

@article{DBLP:journals/tplp/ErdemL03, author = {Esra Erdem and Vladimir Lifschitz}, title = {Tight logic programs}, journal = {TPLP}, volume = {3}, number = {4-5}, year = {2003}, pages = {499-518}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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. }, }

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.

2002
(1)

Theory and applications of answer set programming.
Erdem, E.
Ph.D. Thesis, Department of Computer Sciences, University of Texas at Austin, 2002.

N bibtex abstract

N bibtex abstract

@phdthesis{phdthesis, author = {Esra Erdem}, title = {Theory and applications of answer set programming}, year = {2002}, school = {Department of Computer Sciences, University of Texas at Austin}, abstract = {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.}, urlN = {dissertation.pdf}, }

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.

2001
(2)

Fages' Theorem for Programs with Nested Expressions.
Erdem, E.; and Lifschitz, V.
In

Link N bibtex abstract

*Logic Programming, 17th International Conference, ICLP 2001, Paphos, Cyprus, November 26 - December 1, 2001, Proceedings*, pages 242-254, 2001.Link N bibtex abstract

@inproceedings{DBLP:conf/iclp/ErdemL01, author = {Esra Erdem and Vladimir Lifschitz}, title = {Fages' Theorem for Programs with Nested Expressions}, booktitle = {Logic Programming, 17th International Conference, ICLP 2001, Paphos, Cyprus, November 26 - December 1, 2001, Proceedings}, year = {2001}, pages = {242-254}, ee = {http://link.springer.de/link/service/series/0558/bibs/2237/22370242.htm}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {iclp01.pdf}, abstract = {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 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.

Transitive Closure, Answer Sets and Predicate Completion.
And, E. E.; Erdem, E.; and Lifschitz, V.
In

N bibtex abstract

*Working notes of AAAI Spring Symposium*, pages 60-65, 2001.N bibtex abstract

@INPROCEEDINGS{And00transitiveclosure, author = {Esra Erdem And and Esra Erdem and Vladimir Lifschitz}, title = {Transitive Closure, Answer Sets and Predicate Completion}, booktitle = {Working notes of AAAI Spring Symposium}, year = {2001}, pages = {60-65}, urlN = {tc.pdf}, abstract = {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 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.

2000
(3)

Wire Routing and Satisfiability Planning.
Erdem, E.; Lifschitz, V.; and Wong, M. D. F.
In

Link N bibtex abstract

*Computational Logic - CL 2000, First International Conference, London, UK, 24-28 July, 2000, Proceedings*, pages 822-836, 2000.Link N bibtex abstract

@inproceedings{DBLP:conf/cl/ErdemLW00, author = {Esra Erdem and Vladimir Lifschitz and Martin D. F. Wong}, title = {Wire Routing and Satisfiability Planning}, booktitle = {Computational Logic - CL 2000, First International Conference, London, UK, 24-28 July, 2000, Proceedings}, year = {2000}, pages = {822-836}, ee = {http://link.springer.de/link/service/series/0558/bibs/1861/18610822.htm}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {cl00.pdf}, abstract = {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.}, }

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.

A New Declarative Bias for ILP: Construction Modes.
Erdem, E.; and Flener, P.
In

Link bibtex abstract

*Inductive Logic Programming, 10th International Conference, ILP 2000, Work-in-progress reports, London, UK, July 2000, Proceedings*, 2000.Link bibtex abstract

@inproceedings{DBLP:conf/ilp/ErdemF00, author = {Esra Erdem and Pierre Flener}, title = {A New Declarative Bias for ILP: Construction Modes}, booktitle = {Inductive Logic Programming, 10th International Conference, ILP 2000, Work-in-progress reports, London, UK, July 2000, Proceedings}, year = {2000}, ee = {http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-35/05-ErdemFlener.ps}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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. }, }

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.

Fages' Theorem and Answer Set Programming.
Babovich, Y.; Erdem, E.; and Lifschitz, V.
In

Link bibtex abstract

*Proc. of the 8th International Workshop on Non-Monotonic Reasoning (NMR'00)*, 2000.Link bibtex abstract

@inproceedings{DBLP:journals/corr/cs-AI-0003042, author = {Yuliya Babovich and Esra Erdem and Vladimir Lifschitz}, title = {Fages' Theorem and Answer Set Programming}, booktitle = {Proc. of the 8th International Workshop on Non-Monotonic Reasoning (NMR'00)}, year = {2000}, ee = {http://arxiv.org/abs/cs.AI/0003042}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {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.}, }

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.

1999
(4)

Transformations of Logic Programs Related to Causality and Planning.
Erdem, E.; and Lifschitz, V.
In

Link N bibtex abstract

*Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR'99, El Paso, Texas, USA, December 2-4, 1999, Proceedings*, pages 107-116, 1999.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/ErdemL99, author = {Esra Erdem and Vladimir Lifschitz}, title = {Transformations of Logic Programs Related to Causality and Planning}, booktitle = {Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR'99, El Paso, Texas, USA, December 2-4, 1999, Proceedings}, year = {1999}, pages = {107-116}, ee = {http://link.springer.de/link/service/series/0558/bibs/1730/17300107.htm}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr99.pdf}, abstract = {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 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.

Completing Open Logic Programs by Constructive Induction.
Erdem, E.; and Flener, P.

Paper bibtex abstract

*International Journal of Intelligent Systems*, 14(10): 995-1019. 1999.Paper bibtex abstract

@article{erdem-comp, author = "E. Erdem and P. Flener", title = "Completing Open Logic Programs by Constructive Induction", text = "E. Erdem and P. Flener. Completing Open Logic Programs by Constructive Induction. Submitted.", journal = {International Journal of Intelligent Systems}, number = {10}, volume = {14}, pages = {995-1019}, year = {1999}, url = {http://www3.interscience.wiley.com/journal/63501004/abstract}, abstract = {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.}, }

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.

A new heuristic to use least generalizations in ILP.
Erdem, E.
1999.
Unpublished draft

N bibtex abstract

N bibtex abstract

@misc{unpub1, author = {Esra Erdem}, title = { A new heuristic to use least generalizations in {ILP}}, note = {Unpublished draft}, urlN = {lgg.pdf}, year = {1999}, abstract = {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. }, }

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.

Applications of logic programs to planning: computational experiments.
Erdem, E.
1999.
Unpublished Draft

Paper N bibtex abstract

Paper N bibtex abstract

@misc{unpub2, author = {Esra Erdem}, title = { Applications of logic programs to planning: computational experiments}, note = {Unpublished Draft}, year = {1999}, url = {http://people.sabanciuniv.edu/esraerdem/experiments/experiments.html}, urlN = {experiments.pdf}, abstract = {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.}, }

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.

1997
(1)

A re-definition of least generalizations, and construction modes as a new declarative bias for ILP.
Erdem, E.
Technical Report BU-CEIS-9718, Bilkent University, 1997.

N bibtex abstract

N bibtex abstract

@techreport{ErdFle98, author = {Esra Erdem}, title = {A re-definition of least generalizations, and construction modes as a new declarative bias for {ILP}}, institution = {Bilkent University}, year = {1997}, number = {BU-CEIS-9718}, urlN = {ErdFle98.pdf}, abstract = {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.}, }

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.

1996
(1)

An MSG-method for inductive logic program synthesis.
Erdem, E.
1996.
Senior Project Final Report

N bibtex abstract

N bibtex abstract

@misc{senior, author = {Esra Erdem}, title = {An {MSG}-method for inductive logic program synthesis}, note = {Senior Project Final Report}, year = {1996}, urlN = {senior_project.pdf}, abstract = {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. }, }

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.

to appear
(3)

Finding Optimal Plans for Multiple Teams of Robots through a Mediator: A Logic-Based Approach.
Erdem, E.; Patoglu, V.; Saribatur, Z. G.; Schueller, P.; and Uras, T.

bibtex

*Theory and Practice of Logic Programming*, . to appear.bibtex

@Article{Erdemj2, author = {Esra Erdem and Volkan Patoglu and Zeynep Gozen Saribatur and Peter Schueller and Tansel Uras}, journal = {Theory and Practice of Logic Programming}, year = {to appear}, title = {{Finding Optimal Plans for Multiple Teams of Robots through a Mediator: A Logic-Based Approach}}, volume = {}, number = {}, }

ReAct!: An Interactive Educational Tool for AI Planning for Robotics.
Dogmus, Z.; Erdem, E.; and Patoglu, V.

bibtex

*IEEE Transactions on Education*, . to appear.bibtex

@Article{Dogmusj, author = {Zeynep Dogmus and Esra Erdem and Volkan Patoglu}, journal = {IEEE Transactions on Education}, year = {to appear}, title = {{ReAct!: An Interactive Educational Tool for AI Planning for Robotics}}, volume = {}, number = {}, }

Housekeeping with Autonomous Robots: Representation, Reasoning and Execution.
Aker, E.; Erdogan, A.; Erdem, E.; and Patoglu, V.
of Bridges between the Methodological and Practical Work of the Robotics and Cognitive Systems Communities From Sensors to Concepts, Intelligent Systems Reference Library. Springer, to appear.

bibtex buy

bibtex buy

@INBOOK{Aker_book, series = {{Bridges between the Methodological and Practical Work of the Robotics and Cognitive Systems Communities From Sensors to Concepts, Intelligent Systems Reference Library}}, title = {{Housekeeping with Autonomous Robots: Representation, Reasoning and Execution}}, year = {to appear}, author = {Erdi Aker and Ahmetcan Erdogan and Esra Erdem and Volkan Patoglu}, publisher = {Springer}, }

# Embedding in another Page

Copy&paste any of the following snippets into an existing page to embed this page. For more details see the documention.

**JavaScript**(Easiest)

```
<script src="https://bibbase.org/show?bib=cogrobo.sabanciuniv.edu/krrpublicationsnew.bib&group0=year&jsonp=1"></script>
```

**PHP**

```
<?php
$contents = file_get_contents("https://bibbase.org/show?bib=cogrobo.sabanciuniv.edu/krrpublicationsnew.bib&group0=year");
print_r($contents);
?>
```

**iFrame**

```
<iframe src="https://bibbase.org/show?bib=cogrobo.sabanciuniv.edu/krrpublicationsnew.bib&group0=year"></iframe>
```