Author name cluster

Liron Cohen

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.

8 papers

1 author row

IJCAI Conference 2020 Conference Paper

Iterative-Deepening Conflict-Based Search

Eli Boyarski
Ariel Felner
Daniel Harabor
Peter J. Stuckey
Liron Cohen
Jiaoyang Li
Sven Koenig

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF). CBS variants typically compute MAPF solutions using some form of A* search. However, they often do so under strict time limits so as to avoid exhausting the available memory. In this paper, we present IDCBS, an iterative-deepening variant of CBS which can be executed without exhausting the memory and without strict time limits. IDCBS can be substantially faster than CBS due to incremental methods that it uses when processing CBS nodes.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Anytime Focal Search with Applications

Liron Cohen
Matias Greco
Hang Ma
Carlos Hernandez
Ariel Felner
T. K. Satish Kumar
Sven Koenig

Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a "good" solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.

PDF Details

AAMAS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results

Liron Cohen
Sven Koenig
T. K. Satish Kumar
Glenn Wagner
Howie Choset
David Chan
Nathan Sturtevant

Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.

PDF

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.

PDF Details

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.

Details DOI

IJCAI Conference 2017 Conference Paper

Summary: Multi-Agent Path Finding with Kinematic Constraints

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

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, considers kinematic constraints, provides a guaranteed safety distance between robots, and exploits slack to avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.

PDF Details

IJCAI Conference 2016 Conference Paper

Bounded Suboptimal Multi-Agent Path Finding Using Highways

Liron Cohen
Sven Koenig

The multi-agent path finding (MAPF) problem is defined as follows: Given a graph and a set of agents with unique start and goal vertices, find collision-free paths for all agents from their respective start vertices to their respective goal vertices. Our objective is to minimize the the total arrival time. MAPF has many applications such as video games, traffic control and robotics.

PDF Details

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.

PDF Details