Publications

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

F. Ahmed, V. Patoglu and E. Erdem

Journal of Artificial Intelligence (2023)

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

Y. Izmirlioglu and E. Erdem

Journal of Artificial Intelligence Research (2023)

Successful plan generation for autonomous systems is necessary but not sufficient to guarantee reaching a goal state by an execution of a plan. Various discrepancies between an expected state and the observed state may occur during the plan execution (e.g., due to unexpected exogenous events, changes in the goals, or failure of robot parts) and these discrepancies may lead to plan failures. For that reason, autonomous systems should be equipped with execution monitoring algorithms so that they can autonomously recover from such discrepancies. We introduce a plan execution monitoring algorithm that operates under partial observability. This algorithm relies on novel formal methods for hybrid prediction, diagnosis and explanation generation, and planning. The prediction module generates an expected state after the execution of a part of the plan from an incomplete state to check for discrepancies. The diagnostic reasoning module generates meaningful hypotheses to explain failures of robot parts. Unlike the existing diagnosis methods, the previous hypotheses can be revised, based on new partial observations, increasing the accuracy of explanations as further information becomes available. The replanning module considers these explanations while computing a new plan that would avoid such failures. All these reasoning modules are hybrid in that they combine high-level logical reasoning with low-level feasibility checks based on probabilistic methods. We experimentally show that these hybrid formal reasoning modules improve the performance of plan execution monitoring.

G. Coruhlu, E. Erdem and V. Patoglu

IEEE Transactions on Robotics (2021)

The Stable Roommates problem with Ties and Incomplete lists (SRTI) is a matching problem characterized by the preferences of agents over other agents as roommates, where the preferences may have ties or be incomplete. SRTI asks for a matching that is stable and, sometimes, optimizes a domain-independent fairness criterion (e.g. Egalitarian). However, in real-world applications (e.g. assigning students as roommates at a dormitory), we usually consider a variety of domain-specific criteria depending on preferences over the habits and desires of the agents. With this motivation, we introduce a knowledge-based method to SRTI considering domain-specific knowledge and investigate its real-world application for assigning students as roommates at a university dormitory.

M. Fidan and E. Erdem

Theory and Practice of Logic Programming (2021)

Conditional planning is concerned with reaching goals from an initial state, in the presence of incomplete knowledge and partial observability, by considering all contingencies and by utilizing sensing actions to gather relevant knowledge when needed. We introduce a parallel offline algorithm, called HCPlan, for computing hybrid conditional plans.

A. Nouman, V. Patoglu, E. Erdem

International Journal of Robotics Research (2020)

We propose a novel method for collaborative assembly planning under uncertainty, that utilizes hybrid conditional planning extended with commonsense reasoning and a rich set of communication actions for collaborative tasks.

M. Rizwan, V. Patoglu, E. Erdem

Theory and Practice of Logic Programming (2020)

We introduce a formal framework, called SRTI-ASP, utilizing the logic programming paradigm Answer Set Programming, that is provable and general enough to solve many of such variations of the Stable Roommates problem.

E. Erdem, M. Fidan. D. F. Manlove, P. Prosser

Theory and Practice of Logic Programming (2020)

We propose a novel formal framework (called 3D-NCDC-ASP) to represent and reason about cardinal directions between extended objects in 3-dimensional space, using Answer Set Programming.

Y. Izmirlioglu, E. Erdem

Theory and Practice of Logic Programming (2020)

We consider a general version of the multi-agent path finding (MAPF) problem , called mMAPF, that involves multi-modal transportation modes (e.g., due to velocity constraints) and consumption of different types of resources (e.g., batteries). We focus on explainability, and introduce a method for generating explanations for queries regarding the feasibility and optimality of solutions, the nonexistence of solutions, and the observations about solutions.

A. Bogatarkan, E. Erdem

Theory and Practice of Logic Programming (2020)

We investigate the use of Answer Set Programming to solve variations of gossip problems, by modeling them as epistemic planning problems.

Esra Erdem, Andreas Herzig

ICLP Technical Communications (2020)

We study a dynamic version of multi-agent path finding problem (called D-MAPF) where existing agents may leave and new agents may join the team at different times. We introduce a new method to solve D-MAPF based on conflict-resolution.

B. Atiq, V. Patoglu, E. Erdem

ICLP Technical Communications (2020)

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 modeling each team’s workspace taking into account capabilities of heterogeneous robots, embedding continuous external computations into discrete symbolic representation and reasoning, not only optimizing the makespans of local plans but also minimizing the total cost of robotic actions. To find an optimal global plan, we propose a semi-distributed approach that does not require exchange of information between teams but yet achieves on an optimal coordination of teams that can help each other.

Z. G. Saribatur, V. Patoglu, E. Erdem

Autonomous Robots (2019)

We introduce a novel method to answer natural language queries about rehabilitation robotics, over the formal ontology RehabRobo-Onto. We introduce a novel method to answer natural language queries about rehabilitation robotics, over the formal ontology RehabRobo-Onto. To facilitate the use of our method by experts, we develop an intelligent, interactive query answering system, called RehabRobo-Query, using Semantic Web technologies, and make it available on the cloud via Amazon web services.

Z. Dogmus, E. Erdem, V. Patoglu

Semantic Web (2019)

The multi-agent path finding (MAPF) problem is a combinatorial search problem that aims at finding paths for multiple agents such that no two agents collide with each other. We study a dynamic variant of MAPF, called D-MAPF, which allows changes in the environment (e.g., some existing obstacles may be removed from the environment or moved to some other location, or new obstacles may be included in the environment), and/or changes in the team (e.g., some existing agents may leave and some new agents may join the team) at different times. We introduce a new method to solve D-MAPF, using answer set programming.

A. Bogatarkan, V. Patoglu, E. Erdem

Global Conference on Artificial Intelligence (2019)

Course scheduling or timetabling is a well-known problem that is generally studied from the perspective of schools; the goal is to schedule the courses, considering, e.g., the expected number of students, the sizes of the available classrooms, time conflicts between courses of the same category. We study a complementary problem to help the students during the course registration periods; the goal is to plan personalized course schedules for students, considering, e.g., their preferences over sections, instructors, distribution of the courses. We present a declarative method to compute personalized course schedules, and an application of this method using answer set programming, and discuss promising results of some preliminary user evaluations via surveys.

Muhammed Kerem Kahraman, Esra Erdem

International Symposium on Practical Aspects of Declarative Languages (2018)

We discuss applications of ASP in robotic planning, considering (1) full observability and complete knowledge and (2) with incomplete knowledge and partial observability. We emphasize the strengths of ASP as a useful knowledge representation and reasoning paradigm to integrate AI and robotics, as well as its flexibility to provide different levels of integration of feasibility checks with planning.

Esra Erdem, Volkan Patoglu

KI - Künstliche Intelligenz (2018)

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

Yusuf Izmirlioglu, Esra Erdem

AAAI Conference on Artificial Intelligence (2018)

We introduce a parallel offline algorithm for computing hybrid conditional plans, called HCP-ASP, oriented towards robotics applications. HCP-ASP relies on modeling actuation actions and sensing actions in an expressive nonmonotonic language of answer set programming (ASP), and computation of the branches of a conditional plan in parallel using an ASP solver.

I. F. Yalciner, A. Nouman, V. Patoglu, E. Erdem

Theory and Practice of Logic Programming (2017)

In this work, non-monotonic computational logic, answer set programming in particular, is applied to industrial-scale automotive product configuration problems.

Y. Izmirlioglu, B. A. Pehlivan, M. Turp, E. Erdem

IEEE International Conference on Robotics and Automation (2017)

In this work, non-monotonic computational logic, answer set programming in particular, is applied to industrial-scale automotive product configuration problems.

E Gencay, P. Schuller, E. Erdem

Journal of Intelligent Manufacturing (2017)

We provide a systematic analysis of levels of integration between discrete high-level reasoning and continuous low-level feasibility checks to address hybrid planning problems in robotic applications. We identify four distinct strategies for such an integration; a) low-level checks are done for all possible cases in advance and the results are used during plan generation, b) low-level checks are done exactly when they are needed during the search for a plan, c) low-level checks are done after a plan is computed, and if the plan is found infeasible then a new plan is computed, d) similar to the previous strategy but the results of previous low-level checks are used during computation of a new plan. We analyze the usefulness of these strategies and their combinations by experiments on hybrid planning problems in different robotic application domains, in terms of computational efficiency and plan quality (relative to its feasibility).

Esra Erdem, Volkan Patoglu, Peter Schuller

AI Communications (2016)

ASP has been applied fruitfully to a wide range of areas in AI and in other fields, both in academia and in industry, thanks to the expressive representation languages of ASP and the continuous improvement of ASP solvers. We present some of these ASP applications, in particular, in knowledge representation and reasoning, robotics, bioinformatics and computational biology as well as some industrial applications. We discuss the challenges addressed by ASP in these applications and emphasize the strengths of ASP as a useful AI paradigm.

Esra Erdem, Michael Gelfond, Nicola Leone

AI Magazine (2016)

For the past decade, robotics has mostly focused on low-level sensing and control tasks such as sensor fusion, path planning, and manipulator design and control. At the same time, the field of Cognitive Robotics made significant progress in equipping robots and software agents with high-level cognitive functions such as reasoning over actions, goals and environments, as well as behaviour planning. Cognitive robots must, for example, be able to reason about goals, space, events, actions and time, when to perceive and what to look for, the cognitive states of other agents, explain observations, perform (collaborative) task execution, etc.

Mehul Bhatt, Esra Erdem, Fredrik Heintz, Michael Spranger

Journal of Experimental and Theoretical Artificial Intelligence (2016)

Please visit Google Scholar for a complete list of publications

E. Erdem

Publications List in Google Scholar

Please visit Google Scholar for a complete list of publications

V. Patoglu

Publications List in Google Scholar