Author name cluster

Tansel Uras

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

27 papers

2 author rows

SoCS Conference 2020 Conference Paper

Toward a String-Pulling Approach to Path Smoothing on Grid Graphs

Jihee Han
Tansel Uras
Sven Koenig

Paths found on grid graphs are often unrealistic looking in the continuous environment that the grid graph represents and often need to be smoothed after a search. The well-known algorithm for path smoothing is greedy in nature and does not necessarily eliminate all heading changes in freespace. We present a new path-smoothing algorithm based on “string pulling” and show experimentally that it consistently finds shorter paths than the greedy algorithm and produces paths with no heading changes in freespace.

SoCS Conference 2019 Conference Paper

Optimal and Bounded-Suboptimal Multi-Agent Motion Planning

Liron Cohen 0002
Tansel Uras
T. K. Satish Kumar
Sven Koenig

Multi-Agent Motion Planning (MAMP) is the task of finding conflict-free kinodynamically feasible plans for agents from start to goal states. While MAMP is of significant practical importance, existing solvers are either incomplete, inefficient or rely on simplifying assumptions. For example, Multi-Agent Path Finding (MAPF) solvers conventionally assume discrete timesteps and rectilinear movement of agents between neighboring vertices of a graph. In this paper, we develop MAMP solvers that obviate these simplifying assumptions and yet generalize the core ideas of state-of-the-art MAPF solvers. Specifically, since different motions may take arbitrarily different durations, MAMP solvers need to efficiently reason with continuous time and arbitrary wait durations. To do so, we adapt (Enhanced) Conflict-Based Search to continuous time and develop a novel bounded-suboptimal extension of Safe Interval Path Planning, called Soft Conflict Interval Path Planning. On the theoretical side, we justify the completeness, optimality and bounded-suboptimality of our MAMP solvers. On the experimental side, we show that our MAMP solvers scale well with increasing suboptimality bounds.

IJCAI Conference 2019 Conference Paper

Regarding Jump Point Search and Subgoal Graphs

Daniel D. Harabor
Tansel Uras
Peter J. Stuckey
Sven Koenig

In this paper, we define Jump Point Graphs (JP), a preprocessing-based path-planning technique similar to Subgoal Graphs (SG). JP allows for the first time the combination of Jump Point Search style pruning in the context of abstraction-based speedup techniques, such as Contraction Hierarchies. We compare JP with SG and its variants and report new state-of-the-art results for grid-based pathfinding.

SoCS Conference 2018 Conference Paper

Fast Near-Optimal Path Planning on State Lattices with Subgoal Graphs

Tansel Uras
Sven Koenig

Subgoal graphs can be constructed on top of graphs during a preprocessing phase to speed-up shortest path queries. They have an undominated query-time/memory trade-off in the Grid-Based Path Planning Competitions. While grids are useful for path planning, other kinds of graphs, such as state lattices, have to be used for motion planning. While state lattices are regular graphs like grids, subgoal graphs improve query times by a much smaller factor on state lattices than on grids. In this paper, we present a new version of subgoal graphs that forfeits its optimality guarantee for smaller query times. It guarantees completeness, and our experimental results on state lattices suggest that it can find paths that are close to optimal.

IJCAI Conference 2018 Conference Paper

The FastMap Algorithm for Shortest Path Computations

Liron Cohen
Tansel Uras
Shiva Jahangiri
Aliyah Arunasalam
Sven Koenig
T. K. Satish Kumar

We present a new preprocessing algorithm for embedding the nodes of a given edge-weighted undirected graph into a Euclidean space. The Euclidean distance between any two nodes in this space approximates the length of the shortest path between them in the given graph. Later, at runtime, a shortest path between any two nodes can be computed with an A* search using the Euclidean distances as heuristic. Our preprocessing algorithm, called FastMap, is inspired by the data-mining algorithm of the same name and runs in near-linear time. Hence, FastMap is orders of magnitude faster than competing approaches that produce a Euclidean embedding using Semidefinite Programming. FastMap also produces admissible and consistent heuristics and therefore guarantees the generation of shortest paths. Moreover, FastMap applies to general undirected graphs for which many traditional heuristics, such as the Manhattan Distance heuristic, are not well defined. Empirically, we demonstrate that A* search using the FastMap heuristic is competitive with A* search using other state-of-the-art heuristics, such as the Differential heuristic.

IJCAI Conference 2018 Conference Paper

Understanding Subgoal Graphs by Augmenting Contraction Hierarchies

Tansel Uras
Sven Koenig

Contraction hierarchies and (N-level) subgoal graphs are two preprocessing-based path-planning algorithms that have so far only been compared experimentally through the grid-based path-planning competitions, where both algorithms had undominated runtime/memory trade-offs. Subgoal graphs can be considered as a framework that can be customized to different domains through the choice of a reachability relation R that identifies pairs of nodes on a graph between which it is easy to find shortest paths. Subgoal graphs can exploit R in various ways to speed-up query times and reduce memory requirements. In this paper, we break down the differences between N-level subgoal graphs and contraction hierarchies, and augment contraction hierarchies with ideas from subgoal graphs to exploit R. We propose three different modifications, analyze their runtime/memory trade-offs, and provide experimental results on grids using canonical-freespace-reachability as R, which show that both N-level subgoal graphs and contraction hierarchies are dominated in terms of the runtime/memory trade-off by some of our new variants.

SoCS Conference 2017 Conference Paper

Feasibility Study: Subgoal Graphs on State Lattices

Tansel Uras
Sven Koenig

Search using subgoal graphs is a recent preprocessing-based path-planning algorithm that can find shortest paths on 8-neighbor grids several orders of magnitude faster than A*, while requiring little preprocessing time and memory overhead. In this paper, we first generalize the ideas behind subgoal graphs to a framework that can be specialized to different types of environments (represented as weighted directed graphs) through the choice of a reachability relation. Intuitively, a reachability relation identifies pairs of vertices for which a shortest path can be found quickly. A subgoal graph can then be constructed as an overlay graph that is guaranteed to have edges only between vertices that satisfy the reachability relation, which allows one to find shortest paths on the original graph quickly. In the context of this general framework, subgoal graphs on grids use freespace-reachability (originally called h-reachability) as the reachability relation, which holds for pairs of vertices if and only if their distance on the grid with blocked cells is equal to their distance on the grid without blocked cells (freespace assumption). We apply this framework to state lattices by using variants of freespace-reachability as the reachability relation. We provide preliminary results on (x, y, theta)-state lattices, which shows that subgoal graphs can be used to speed up path planning on state lattices as well, although the speed-up is not as significant as it is on grids.

IS Journal 2017 Journal Article

Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems

Hang Ma
Wolfgang Hönig
Liron Cohen
Tansel Uras
Hong Xu
T.K. Satish Kumar
Nora Ayanian
Sven Koenig

The authors present an overview of a hierarchical framework for coordinating task- and motion-level operations in multirobot systems. Their framework is based on the idea of using simple temporal networks to simultaneously reason about precedence/causal constraints required for task-level coordination and simple temporal constraints required to take some kinematic constraints of robots into account. In the plan-generation phase, the framework provides a computationally scalable method for generating plans that achieve high-level tasks for groups of robots and take some of their kinematic constraints into account. In the plan-execution phase, the framework provides a method for absorbing an imperfect plan execution to avoid time-consuming re-planning in many cases. The authors use the multirobot path-planning problem as a case study to present the key ideas behind their framework for the long-term autonomy of multirobot systems.

IJCAI Conference 2016 Conference Paper

Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding

Liron Cohen
Tansel Uras
T. K. Satish Kumar
Hong Xu
Nora Ayanian
Sven Koenig

Multi-Agent Path Finding (MAPF) with the objective to minimize the sum of the travel times of the agents along their paths is a hard combinatorial problem. Recent work has shown that bounded-suboptimal MAPF solvers, such as Enhanced Conflict-Based Search or ECBS(w1) for short, run often faster than optimal MAPF solvers at the cost of incurring a suboptimality factor w1, that is due to using focal search. Other recent work has used experience graphs to guide the search of ECBS(w1) and speed it up, at the cost of incurring a separate suboptimality factor w2, that is due to inflating the heuristic values. Thus, the combination has suboptimality factor w1w2. In this first feasibility study, we develop a bounded-suboptimal MAPF solver, Improved-ECBS or iECBS(w1) for short, that has sub optimality factor w1 rather than w1w2 (because it uses experience graphs to guide its search without inflating the heuristic values) and can run faster than ECBS(w1). We also develop two first approaches for automatically generating experience graphs for a given MAPF instance. Finally, we observe heavy-tailed behavior in the runtimes of these MAPF solvers and develop a simple rapid randomized restart strategy that can increase the success rate of iECBS(w1) within a given runtime limit.

SoCS Conference 2015 Conference Paper

An Empirical Comparison of Any-Angle Path-Planning Algorithms

Tansel Uras
Sven Koenig

We compare five any-angle path-planning algorithms, Theta*, Block A*, Field D*, ANYA, and Any-Angle Subgoal Graphs in terms of solution quality and runtime. Any-angle path-planning is a fairly new research area, and no direct comparison exists between these algorithms. We implement each algorithm from scratch and use similar implementations to provide a fair comparison.

SoCS Conference 2015 Conference Paper

Feasibility Study: Using Highways for Bounded-Suboptimal Multi-Agent Path Finding

Liron Cohen 0002
Tansel Uras
Sven Koenig

Multi-agent path-finding (MAPF) is important for applications such as the kind of warehousing done by Kiva systems. Solving the problem optimally is NP-hard, yet finding low-cost solutions is important. Bounded-suboptimal MAPF algorithms, such as enhanced conflict-based search (ECBS), often do not perform well in warehousing domains with many agents. We therefore develop bounded-suboptimal MAPF algorithms, called CBS+HWY and ECBS+HWY, that exploit the problem structure of a given MAPF instance by finding paths for the agents that include edges from user-provided highways, which encourages a global behavior of the agents that avoids collisions. On the theoretical side, we develop a simple approach that uses highways for MAPF and provides suboptimality guarantees. On the experimental side, we demonstrate that ECBS+HWY can decrease the runtimes and solution costs of ECBS in Kiva-like domains with many agents if the highways capture the problem structures well.

ICAPS Conference 2015 Conference Paper

Speeding-Up Any-Angle Path-Planning on Grids

Tansel Uras
Sven Koenig

Simple Subgoal Graphs are constructed from grids by placing subgoals at the corners of obstacles and connecting them. They are analogous to visibility graphs for continuous terrain but have fewer edges and can be used to quickly find shortest paths on grids. The vertices of a Simple Subgoal Graph can be partitioned into different levels to create N-Level Subgoal Graphs, which can be used to find shortest paths on grids even more quickly by ignoring subgoals that are not relevant for the search, which significantly reduces the size of the graph being searched. Search using Two-Level Subgoal Graphs was a non-dominated entry in the Grid-Based Path Planning Competitions 2012 and 2013. In this paper, we take advantage of the similarities between Subgoal Graphs and visibility graphs to show that Subgoal Graphs can be used, with small modifications, to quickly find “any-angle” paths, thus extending their applicability. Any-angle paths are usually shorter and more realistic looking than grid paths since the movement along any-angle paths is not constrained to grid edges. Our algorithm has the advantage that it is a simple extension of searching Subgoal Graphs and is up to two orders of magnitude faster than Theta* and up to an order of magnitude faster than Block A* (using 5 × 5 blocks), two of the most well-known any-angle pathplanning algorithms, while still finding any-angle paths of comparable lengths.

SoCS Conference 2015 Invited Paper

The Grid-Based Path Planning Competition: 2014 Entries and Results

Nathan R. Sturtevant
Jason M. Traish
James R. Tulip
Tansel Uras
Sven Koenig
Ben Strasser
Adi Botea
Daniel Harabor

The Grid-Based Path Planning Competition has just completed its third iteration. The entriesused in the competition have improved significantly during this time, changing the view ofthe state of the art of grid-based pathfinding. Furthermore, the entries from the competition have beenmade publicly available, improving the ability of researchers to compare their work. Thispaper summarizes the entries to the 2014 competition, presents the 2014 competition results, and talks about what has been learned and where there is room for improvement.

IROS Conference 2014 Conference Paper

A lattice-based approach to multi-robot motion planning for non-holonomic vehicles

Marcello Cirillo
Tansel Uras
Sven Koenig

Coordinating fleets of autonomous, non-holonomic vehicles is paramount to many industrial applications. While there exists solutions to efficiently calculate trajectories for individual vehicles, an effective methodology to coordinate their motions and to avoid deadlocks is still missing. Decoupled approaches, where motions are calculated independently for each vehicle and then centrally coordinated for execution, have the means to identify deadlocks, but not to solve all of them. We present a novel approach that overcomes this limitation and that can be used to complement the deficiencies of decoupled solutions with centralized coordination. Here, we formally define an extension of the framework of lattice-based motion planning to multi-robot systems and we validate it experimentally. Our approach can jointly plan for multiple vehicles and it generates kinematically feasible and deadlock-free motions.

AAAI Conference 2014 Conference Paper

Identifying Hierarchies for Fast Optimal Search

Tansel Uras
Sven Koenig

Search with Subgoal Graphs (Uras, Koenig, and Hernández 2013) was a non-dominated optimal path-planning algorithm in the Grid-Based Path Planning Competitions 2012 and 2013. During a preprocessing phase, it computes a Simple Subgoal Graph from a given grid, which is analogous to a visibility graph for continuous terrain, and then partitions the vertices into global and local subgoals to obtain a Two-Level Subgoal Graph. During the path-planning phase, it performs an A* search that ignores local subgoals that are not relevant to the search, which significantly reduces the size of the graph being searched. In this paper, we generalize this partitioning process to any undirected graph and show that it can be recursively applied to generate more than two levels, which reduces the size of the graph being searched even further. We distinguish between basic partitioning, which only partitions the vertices into different levels, and advanced partitioning, which can also add new edges. We show that the construction of Simple- Subgoal Graphs from grids and the construction of Two- Level Subgoal Graphs from Simple Subgoal Graphs are instances of generalized partitioning. We then report on experiments on Subgoal Graphs that demonstrate the effects of different types and levels of partitioning. We also report on experiments that demonstrate that our new N-Level Subgoal Graphs achieve a speed up of 1. 6 compared to Two-Level Subgoal graphs from (Uras, Koenig, and Hernández 2013) on maps from the video games StarCraft and Dragon Age: Origins.

SoCS Conference 2014 Conference Paper

Identifying Hierarchies for Fast Optimal Search

Tansel Uras
Sven Koenig

For some search problems, the graph is known beforehand and there is time to preprocess the graph to make the search faster. One such example is video games, where one can often preprocess maps before a game is released or while a map is loaded into memory. The data produced by preprocessing should use only a small amount of memory, and, in case they are generated during runtime, preprocessing should be fast. Search with Subgoal Graphs (Uras, Koenig, and Hernandez 2013) was a non-dominated optimal path-planning algorithm in the Grid-Based Path Planning Competitions 2012 and 2013. During a preprocessing phase, it computes a Simple Subgoal Graph from a given grid, which is analogous to a visibility graph for continuous terrain, and then partitions the vertices into global and local subgoals to obtain a Two-Level Subgoal Graph. During the path-planning phase, it performs an A* search over the subgoal graph that ignores local subgoals that are not relevant to the search, which significantly reduces the size of the graph being searched. This paper is an abstract of (Uras and Koenig 2014), which generalizes this partitioning process to any undirected graph and shows that it can be recursively applied to generate more than two levels, which reduces the size of the graph being searched even further. We call these graphs N-Level Graphs.

ICAPS Conference 2014 Conference Paper

Integrated Motion Planning and Coordination for Industrial Vehicles

Marcello Cirillo
Federico Pecora
Henrik Andreasson
Tansel Uras
Sven Koenig

A growing interest in the industrial sector for autonomous ground vehicles has prompted significant investment in fleet management systems. Such systems need to accommodate on-line externally imposed temporal and spatial requirements, and to adhere to them even in the presence of contingencies. Moreover, a fleet management system should ensure correctness, i. e. , refuse to commit to requirements that cannot be satisfied. We present an approach to obtain sets of alternative execution patterns (called trajectory envelopes) which provide these guarantees. The approach relies on a constraint-based representation shared among multiple solvers, each of which progressively refines trajectory envelopes following a least commitment principle.

JAAMAS Journal 2014 Journal Article

Reusing cost-minimal paths for goal-directed navigation in partially known terrains

Carlos Hernández
Tansel Uras
Pedro Meseguer

Abstract Situated agents frequently need to solve search problems in partially known terrains in which the costs of the arcs of the search graphs can increase (but not decrease) when the agents observe new information. An example of such search problems is goal-directed navigation with the freespace assumption in partially known terrains, where agents repeatedly follow cost-minimal paths from their current locations to given goal locations. Incremental heuristic search is an approach for solving the resulting sequences of similar search problems potentially faster than with classical heuristic search, by reusing information from previous searches to speed up its current search. There are two classes of incremental heuristic search algorithms, namely those that make the \(h\) -values of the current search more informed (such as Adaptive A*) and those that reuse parts of the A* search trees of previous searches during the current search (such as D* Lite). In this article, we introduce Path-Adaptive A* and its generalization Tree-Adaptive A*. Both incremental heuristic search algorithms terminate their searches before they expand the goal state, namely when they expand a state that is on a provably cost-minimal path to the goal. Path-Adaptive A* stores a single cost-minimal path to the goal state (the reusable path), while Tree-Adaptive A* stores a set of cost-minimal paths to the goal state (the reusable tree), and is thus potentially more efficient than Path-Adaptive A* since it uses information from all previous searches and not just the last one. Tree-Adaptive A* is the first incremental heuristic search algorithm that combines the principles of both classes of incremental heuristic search algorithms. We demonstrate experimentally that both Path-Adaptive A* and Tree-Adaptive A* can be faster than Adaptive A* and D* Lite, two state-of-the-art incremental heuristic search algorithms for goal-directed navigation with the freespace assumption.

ICAPS Conference 2013 Conference Paper

Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids

Tansel Uras
Sven Koenig
Carlos Hernández Ulloa

Grids are often used to represent maps in video games. In this paper, we propose a method for preprocessing eightneighbor grids to generate subgoal graphs and show how subgoal graphs can be used to find shortest paths fast. We place subgoals at the corners of obstacles (similar to visibility graphs) and add those edges between subgoals that are necessary for finding shortest paths, while ensuring that each edge connects only subgoals that are easily reachable from one another. We describe a method for finding shortest paths by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the highlevel path. Our method was one of ten entries in the Grid-Based Path Planning Competition 2012. Among all optimal path planners, ours was the fastest to find complete paths and required the least amount of memory.

ICAPS Conference 2012 Conference Paper

Incremental ARA*: An Incremental Anytime Search Algorithm for Moving-Target Search

Xiaoxun Sun
Tansel Uras
Sven Koenig
William Yeoh 0001

Moving-target search, where a hunter has to catch a moving target, is an important problem for video game developers. In our case, the hunter repeatedly moves towards the target and thus has to solve similar search problems repeatedly. We develop Incremental ARA* (I-ARA*) for this purpose, the first incremental anytime search algorithm for moving-target search in known terrain. We provide an error bound on the lengths of the paths found by I-ARA* and show experimentally in known four-neighbor gridworlds that I-ARA* can be used with smaller time limits between moves of the hunter than competing state-of-the-art moving-target search algorithms, namely repeated A*, G-FRA*, FRA*, and sometimes repeated ARA*. The hunter tends to make more moves with I-ARA* than repeated A*, G-FRA* or FRA*, which find shortest paths for the hunter, but fewer moves with I-ARA* than repeated ARA*, which finds suboptimal paths for the hunter like I-ARA*. Also, the error bounds on the lengths of the paths of the hunter tend to be smaller with I-ARA* than repeated ARA*.

SoCS Conference 2012 Conference Paper

Paper Summary: Time-Bounded Adaptive A

Carlos Hernández Ulloa
Jorge A. Baier
Tansel Uras
Sven Koenig

This paper summarizes our AAMAS 2012 paper on "Time-Bounded Adaptive A*, " which introduces the game time model to evaluate search algorithms in real-time settings, such as video games. It then extends the existing real-time search algorithm TBA* to path planning with the freespace assumption in initially partially or completely unknown terrain, resulting in Time-Bounded Adaptive A* (TBAA*). TBAA* needs fewer time intervals in the game time model than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.

SoCS Conference 2012 Conference Paper

Position Paper: Incremental Search Algorithms Considered Poorly Understood

Carlos Hernández Ulloa
Jorge A. Baier
Tansel Uras
Sven Koenig

Incremental search algorithms, such as D* Lite, reuse information from previous searches to speed up the current search and can thus solve sequences of similar search problems faster than Repeated A*, which performs repeated A* searches. In this position paper, we study goal-directed navigation in initially unknown terrain and point out that it is currently not well understood when D* Lite runs faster than Repeated A*. In general, it appears that Repeated A* runs faster than D* Lite for easy navigation problems (where the agent reaches the goal with only a small number of searches), which means that it runs faster than D* Lite quite often in practice. We draw two conclusions, namely that incremental search algorithms need to be evaluated in more diverse testbeds to improve our understanding of their properties and that they can be improved to be more competitive for easy navigation problems.

SoCS Conference 2012 Conference Paper

Subgoal Graphs for Eight-Neighbor Gridworlds

Tansel Uras
Sven Koenig
Carlos Hernández Ulloa

We propose a method for preprocessing an eight-neighbor gridworld to generate a subgoal graph and a method for using this subgoal graph to find shortest paths faster than A*, by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the high-level path.

AAMAS Conference 2012 Conference Paper

Time Bounded Adaptive A*

Carlos Hern
aacute; ndez
Jorge Baier
Tansel Uras
Sven Koenig

n this paper, we investigate real-time path planning in static terrain, as needed in video games. We introduce the game time model, where time is partitioned into uniform time intervals, an agent can execute one movement during each time interval, and search and movements are done in parallel. The objective is to move the agent from its start location to its goal location in as few time intervals as possible. For known terrain, we show experimentally that Time-Bounded A* (TBA*), an existing real-time search algorithm for undirected terrain, needs fewer time intervals than two state-of-the-art real-time search algorithms and about the same number of time intervals as A*. TBA*, however, cannot be used when the terrain is not known initially. For initially partially or completely unknown terrain, we thus propose a new search algorithm. Our Time-Bounded Adaptive A* (TBAA*) extends TBA* to on-line path planning with the freespace assumption by combining it with Adaptive A*. We prove that TBAA* either moves the agent from its start location to its goal location or detects that this is impossible - an important property since many existing realtime search algorithms are not able to detect efficiently that no path exists. Furthermore, TBAA* can eventually move the agent on a cost-minimal path from its start location to its goal location if it resets the agent into its start location whenever it reaches its goal location. We then show experimentally in initially partially or completely unknown terrain that TBAA* needs fewer time intervals than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.

ICRA Conference 2011 Conference Paper

Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation

Esra Erdem 0001
Kadir Haspalamutgil
Can Palaz
Volkan Patoglu
Tansel Uras

We present a formal framework that combines high-level representation and causality-based reasoning with low-level geometric reasoning and motion planning. The frame-work 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. A short video of this application accompanies the paper.

ICAPS Conference 2010 Conference Paper

Genome Rearrangement and Planning: Revisited

Tansel Uras
Esra Erdem 0001

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.

AAAI Conference 2010 Conference Paper

Genome Rearrangement: A Planning Approach

Tansel Uras
Esra Erdem

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