Arrow Research search

Author name cluster

Eli Boyarski

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

Possible papers

27

AAMAS Conference 2023 Conference Paper

Optimally Solving the Multiple Watchman Route Problem with Heuristic Search

  • Yaakov Livne
  • Dor Atzmon
  • Shawn Skyler
  • Eli Boyarski
  • Amir Shapiro
  • Ariel Felner

In the Watchman Route Problem (WRP), the task is to find a path for a watchman agent such that all locations in the given map will be visually seen by the watchman at least once during the path traversal. Recently, the problem has been optimally solved on a grid map using heuristic search. In this paper, we extend this work to the case of multiple agents. We call this problem the Multiple Watchman Route Problem (MWRP). In MWRP, the task is to find a path for each watchman such that each location on the map will be seen by at least one watchman. We optimally solve MWRP with heuristic search for two different objective functions with a number of A*-based variants, including an enhanced branching mechanism. We then provide an experimental study on these methods and on other attributes of this problem.

PDF

JAIR Journal 2022 Journal Article

Migrating Techniques from Search-based Multi-Agent Path Finding Solvers to SAT-based Approach

  • Pavel Surynek
  • Roni Stern
  • Eli Boyarski
  • Ariel Felner

In the multi-agent path finding problem (MAPF) we are given a set of agents each with respective start and goal positions. The task is to find paths for all agents while avoiding collisions, aiming to minimize a given objective function. Many MAPF solvers were introduced in the past decade for optimizing two specific objective functions: sum-of-costs and makespan. Two prominent categories of solvers can be distinguished: search-based solvers and compilation-based solvers. Search-based solvers were developed and tested for the sum-of-costs objective, while the most prominent compilation-based solvers that are built around Boolean satisfiability (SAT) were designed for the makespan objective. Very little is known on the performance and relevance of solvers from the compilation-based approach on the sum-of-costs objective. In this paper, we start to close the gap between these cost functions in the compilation-based approach. Our main contribution is a new SAT-based MAPF solver called MDD-SAT, that is directly aimed to optimally solve the MAPF problem under the sum-of-costs objective function. Using both a lower bound on the sum-of-costs and an upper bound on the makespan, MDD-SAT is able to generate a reasonable number of Boolean variables in our SAT encoding. We then further improve the encoding by borrowing ideas from ICTS, a search-based solver. In addition, we show that concepts applicable in search-based solvers like ICTS and ICBS are applicable in the SAT-based approach as well. Specifically, we integrate independence detection, a generic technique for decomposing an MAPF instance into independent subproblems, into our SAT-based approach, and we design a relaxation of our optimal SAT-based solver that results in a bounded suboptimal SAT-based solver. Experimental evaluation on several domains shows that there are many scenarios where our SAT-based methods outperform state-of-the-art sum-of-costs search-based solvers, such as variants of the ICTS and ICBS algorithms.

PDF Details DOI

SoCS Conference 2022 Conference Paper

On Merging Agents in Multi-Agent Pathfinding Algorithms

  • Eli Boyarski
  • Shao-Hung Chan
  • Dor Atzmon
  • Ariel Felner
  • Sven Koenig

In Multi-Agent Pathfinding (MAPF), the task is to find non-colliding paths for a set of agents. This paper focuses on search-based MAPF algorithms from the Conflict-Based Framework, which is introduced here. A common technique in such algorithms is to merge a group of dependent agents into a meta-agent and plan non-colliding paths for the meta-agent using a low-level MAPF sub-solver. We analyze the patterns that emerge when agents are merged in an arbitrary order. We then introduce policies for choosing which agents or meta-agents to merge to achieve improved efficiency in three algorithms: Independence Detection (ID) and Improved Conflict-Based Search (ICBS), which are optimal, and Priority-Based Search (PBS), which is a fast suboptimal algorithm. Experimental results show a significant improvement in efficiency

Details

SoCS Conference 2022 Conference Paper

Online Multi-Agent Path Finding: New Results

  • Jonathan Morag
  • Ariel Felner
  • Roni Stern
  • Dor Atzmon
  • Eli Boyarski

Online MAPF extends the classical Multi-Agent Path Finding problem (MAPF) by considering a more realistic problem in which new agents may appear over time. As online solvers are not aware of which agents will join in the future, the notion of snapshot-optimal was defined, where only current knowledge is considered. In this paper, we perform an extensive comparison between oracle-optimal solutions (where the solver is preinformed of future agents), snapshot-optimal solutions, and suboptimal solutions obtained by prioritised planning.

Details

SoCS Conference 2022 Conference Paper

Optimally Solving the Multiple Watchman Route Problem with Heuristic Search (Extended Abstract)

  • Yaakov Livne
  • Dor Atzmon
  • Shawn Skyler
  • Eli Boyarski
  • Amir Shapiro
  • Ariel Felner

In the Watchman Route Problem (WRP), the task is to find a path for a watchman agent such that all locations in the given map will be visually seen by the watchman at least once during the path traversal. Recently, the problem has been optimally solved on a grid map using heuristic search. In this paper, we extend this work to the case of multiple agents. We call this problem the Multiple Watchman Route Problem (MWRP). In MWRP, the task is to find a path for each watchman such that each location on the map will be seen by at least one watchman. We optimally solve MWRP with heuristic search for two different objective functions with a number of A*-based variants, including an enhanced branching mechanism. We then provide an experimental study on these methods and on other attributes of this problem.

Details

SoCS Conference 2021 Conference Paper

Experimental Evaluation of Classical Multi Agent Path Finding Algorithms

  • Omri Kaduri
  • Eli Boyarski
  • Roni Stern

Modern optimal multi-agent path finding (MAPF) algorithms can scale to solve problems with hundreds of agents. To facilitate comparison between these algorithms, a benchmark of MAPF problems was recently proposed. We report a comprehensive evaluation of a diverse set of state-of-the-art optimal MAPF algorithms over the entire benchmark. The results show that in terms of coverage, the recently proposed LazyCBS algorithm outperforms all others significantly, but it is usually not the fastest algorithm. This suggests algorithm selection methods can be beneficial. Then, we characterize different setups for algorithm selection in MAPF, and evaluate simple baselines for each setup. Finally, we propose an extension of the existing MAPF benchmark in the form of different ways to distribute the agents’ source and target locations.

Details

AAAI Conference 2021 Conference Paper

f-Aware Conflict Prioritization & Improved Heuristics For Conflict-Based Search

  • Eli Boyarski
  • Ariel Felner
  • Pierre Le Bodic
  • Daniel D. Harabor
  • Peter J. Stuckey
  • Sven Koenig

Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF). The main step of CBS is to expand nodes by resolving conflicts (where two agents collide). Choosing the ‘right’ conflict to resolve can greatly speed up the search. CBS first resolves conflicts where the costs (g-values) of the resulting child nodes are larger than the cost of the node to be split. However, the recent addition of high-level heuristics to CBS and expanding nodes according to f = g + h reduces the relevance of this conflict prioritization method. Therefore, we introduce an expanded categorization of conflicts, which first resolves conflicts where the f-values of the child nodes are larger than the f-value of the node to be split, and present a method for identifying such conflicts. We also enhance all known heuristics for CBS by using information about the cost of resolving certain conflicts with only a small computational overhead. Finally, we experimentally demonstrate that both the expanded categorization of conflicts and the improved heuristics contribute to making CBS even more efficient.

PDF Details

SoCS Conference 2021 Conference Paper

Further Improved Heuristics For Conflict-Based Search

  • Eli Boyarski
  • Ariel Felner
  • Pierre Le Bodic
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF). At its high level, CBS expands nodes by resolving conflicts. In recent years, admissible heuristics were added to the high level of CBS. We enhance all known heuristic functions for CBS by using information about the cost of resolving certain conflicts, with only a small computational overhead. We experimentally demonstrate that the improved heuristics contribute to making CBS even more efficient.

Details

SoCS Conference 2021 Conference Paper

Improving Continuous-time Conflict Based Search

  • Anton Andreychuk
  • Konstantin S. Yakovlev
  • Eli Boyarski
  • Roni Stern

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for n agents in a graph such that each agent reaches its goal vertex and the agents do not collide with each other while moving along these paths. While different problem statements of MAPF exist, we are focused on MAPFr (Walker, Sturtevant, and Felner 2018), in which actions’ durations can be non-uniform, agents have geometric shapes, and time is continuous. Continuous-time conflict-based search (CCBS) (Andreychuk et al. 2019) is a recently proposed algorithm for finding optimal solutions to MAPFr problems. In this work, we propose several improvements to CCBS based on known improvements to the Conflictbased search (CBS) algorithm (Sharon et al. 2015) for classical MAPF, namely Disjoint Splitting (DS), Prioritizing Conflicts (PC), and high-level heuristics. We evaluate the impact of these improvements experimentally on both roadmaps and grids. Our results show that CCBS with these improvements is able to solve significantly more problems.

Details

AAAI Conference 2021 Conference Paper

Improving Continuous-time Conflict Based Search

  • Anton Andreychuk
  • Konstantin Yakovlev
  • Eli Boyarski
  • Roni Stern

Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and 2k -neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multiagent path finding in continuous-time domains.

PDF Details

SoCS Conference 2021 Conference Paper

Studying Online Multi-Agent Path Finding

  • Jonathan Morag
  • Roni Stern
  • Ariel Felner
  • Dor Atzmon
  • Eli Boyarski

Multi-agent path finding (MAPF) is the problem of planning a set of non-conflicting plans on a graph, for a set of agents. Online MAPF extends MAPF by considering a more realistic problem in which new agents may appear over time. While planning, an online solver does not know whether and which agents will join in the future. Therefore, in online problems the notion of snapshot-optimal was defined, where only current knowledge is considered. The quality of such a solution may be weaker than the quality of a solution to an equivalent offline MAPF problem (offline-optimality), where the solver is preinformed of all the agents that will appear in the future. In this paper we explore, theoretically and empirically, the quality of snapshot-optimal solutions compared to offline-optimal solutions.

Details

ICAPS Conference 2020 Conference Paper

Algorithm Selection for Optimal Multi-Agent Pathfinding

  • Omri Kaduri
  • Eli Boyarski
  • Roni Stern

The challenge of finding an optimal solution to a multi-agent path finding (MAPF) problem has attracted significant academic and industrial interest in recent years. While the problem is NP-Hard, modern optimal MAPF algorithms can scale to solve problems with hundreds of agents. Nevertheless, no single optimal MAPF algorithm dominates all benchmarks problems, and there are no clear, provable, guidelines for when each algorithm should be used. To address this, we present the first successful Algorithm Selection (AS) model for optimal MAPF. We propose two approaches for learning an AS model. The first approach uses a standard supervised learning algorithm with a set of handcrafted MAPF-specific features. The second approach, casts a MAPF problem to an image and applies a deep Convolutional Neural Network to classify it. We evaluate both approaches over a large dataset and show that using an AS model to select which algorithm to use for each instance results in solving more problems and in a shorter runtime compared to the state of the art.

Details

SoCS Conference 2020 Conference Paper

F-Cardinal Conflicts in Conflict-Based Search

  • Eli Boyarski
  • Daniel Harabor
  • Peter J. Stuckey
  • Pierre Le Bodic
  • Ariel Felner

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF) which features strong performance. In CBS, one conflict in a high-level node is resolved to generate two child nodes, until a node with no conflicts is found. Choosing the right conflict to resolve can greatly speed up the search. It is currently recommended to resolve cardinal conflicts first, resolving them yields two child nodes with a higher cost than the cost of their parent. However, since the recent addition of high-level heuristics to CBS, when resolving cardinal conflicts, the h-value of high-level child nodes often decreases by the same amount as their cost increases. This diminishes the effectiveness of the cardinal conflicts distinction. We propose an expanded categorization of conflicts into f-cardinal, g-cardinal, and non-cardinal. F-cardinal conflicts should be resolved first. Resolving f-cardinal conflicts generates child nodes with an increased f-value relative to their parent. We propose two methods for identifying f-cardinal conflicts. Finally, we demonstrate on standard benchmarks that choosing conflicts according to this expanded categorization increases the effectiveness of modern CBS.

Details

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 2019 Conference Paper

Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search

  • Jiaoyang Li
  • Ariel Felner
  • Eli Boyarski
  • Hang Ma
  • Sven Koenig

Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Path Finding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependencies between agents. Empirically, CBS with either new heuristic significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50.

PDF Details

SoCS Conference 2019 Conference Paper

Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results

  • Jiaoyang Li 0001
  • Eli Boyarski
  • Ariel Felner
  • Hang Ma 0001
  • Sven Koenig

Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Pathfinding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependency between agents. Empirically, CBS with both new heuristics significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50, yielding a new state-of-the-art CBS-based algorithm.

Details

SoCS Conference 2019 Conference Paper

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

  • Roni Stern
  • Nathan R. Sturtevant
  • Ariel Felner
  • Sven Koenig
  • Hang Ma 0001
  • Thayne T. Walker
  • Jiaoyang Li 0001
  • Dor Atzmon

The multi-agent pathfinding problem (MAPF) is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses, autonomous vehicles, and robotics. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers assume different sets of assumptions, e. g. , whether agents can traverse the same road at the same time, and have different objective functions, e. g. , minimize makespan or sum of agents

Details

ICAPS Conference 2018 Conference Paper

Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding

  • Ariel Felner
  • Jiaoyang Li 0001
  • Eli Boyarski
  • Hang Ma 0001
  • Liron Cohen 0002
  • T. K. Satish Kumar
  • Sven Koenig

Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for the multi-agent path-finding problem. However, existing variants of CBS do not use any heuristics that estimate future work. In this paper, we introduce different admissible heuristics for CBS by aggregating cardinal conflicts among agents. In our experiments, CBS with these heuristics outperforms previous state-of-the-art CBS variants by up to a factor of five.

Details

SoCS Conference 2018 Conference Paper

Sub-Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem

  • Pavel Surynek
  • Ariel Felner
  • Roni Stern
  • Eli Boyarski

In multi-agent path finding (MAPF) the task is to find nonconflicting paths for multiple agents. In this paper we focus on finding suboptimal solutions for MAPF for the sum-of-costs variant. Recently, a SAT-based approached was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we present SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant algorithms. Experimental results show that in many case the SAT-based solver significantly outperforms the search-based solvers.

Details

SoCS Conference 2017 Conference Paper

Modifying Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants

  • Pavel Surynek
  • Ariel Felner
  • Roni Stern
  • Eli Boyarski

In multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, a SAT-based approach was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we introduce SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant search-based algorithms.

Details

SoCS Conference 2017 Conference Paper

Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges

  • Ariel Felner
  • Roni Stern
  • Solomon Eyal Shimony
  • Eli Boyarski
  • Meir Goldenberg
  • Guni Sharon
  • Nathan R. Sturtevant
  • Glenn Wagner

Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.

Details

SoCS Conference 2016 Conference Paper

An Empirical Comparison of the Hardness of Multi-Agent Path Finding under the Makespan and the Sum of Costs Objectives

  • Pavel Surynek
  • Ariel Felner
  • Roni Stern
  • Eli Boyarski

In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, existing makespan optimal SAT-based solvers for MAPF have been modified for the sum-of-costs objective. In this paper, we empirically compare the hardness of solving MAPF with SAT-based and search-based solvers under the makespan and the sum-of-costs objectives in a number of domains. The experimental evaluation shows that MAPF under the makespan objective is easier across all the tested solvers and domains.

Details

AAMAS Conference 2016 Conference Paper

Boolean Satisfiability Approach to Optimal Multi-agent Path Finding Under the Sum of Costs Objective (Extended Abstract)

  • Pavel Surynek
  • Ariel Felner
  • Roni Stern
  • Eli Boyarski

This paper focuses on finding optimal solutions to the multiagent path finding (MAPF) problem over undirected graphs where the task is to find non-colliding paths for multiple agents, each with a different start and goal position. An encoding of MAPF to Boolean satisfiability (SAT) is already known to the makespan optimal variant of the problem. In this paper we present the first SAT-solver for minimizing the sum of costs enabled by introducing cardinality constraints into the SAT encoding. An experimental evaluation on grid graphs indicate promising performance of the new SAT-based method in comparison with the best variants of previous sum-of-costs search solvers.

PDF

ECAI Conference 2016 Conference Paper

Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective

  • Pavel Surynek
  • Ariel Felner
  • Roni Stern
  • Eli Boyarski

In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. In this paper we present the first SAT-solver for the sum-of-costs variant of MAPF which was previously only solved by search-based methods. Using both a lower bound on the sum-of-costs and an upper bound on the makespan, we are able to have a reasonable number of variables in our SAT encoding. We then further improve the encoding by borrowing ideas from ICTS, a search-based solver. Experimental evaluation on several domains showed that there are many scenarios where the new SAT-based method outperforms the best variants of previous sum-of-costs search solvers - the ICTS and ICBS algorithms.

Details

ICAPS Conference 2015 Conference Paper

Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding

  • Eli Boyarski
  • Ariel Felner
  • Guni Sharon
  • Roni Stern

Conflict-Based Search (CBS) is a recently introduced algorithm for Multi-AgentPath Finding (MAPF) whose runtime is exponential in the number of conflictsfound between the agents' paths. We present an improved version of CBS thatbypasses conflicts thereby reducing the CBS search tree. Experimental resultsshow that this improvement reduces the runtime by an order of magnitude in manycases.

Details

IJCAI Conference 2015 Conference Paper

ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding

  • Eli Boyarski
  • Ariel Felner
  • Roni Stern
  • Guni Sharon
  • David Tolpin
  • Oded Betzalel
  • Eyal Shimony

Conflict-Based Search (CBS) and its enhancements, Meta-Agent CBS and bypassing conflicts are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces two new improvements to CBS and incorporates them into a coherent, improved version of CBS, namely ICBS. Experimental results show that each of these improvements further reduces the runtime over the existing CBS-based approaches. When all improvements are combined, an even larger improvement is achieved, producing state-of-the art results for a number of domains.

PDF Details

SoCS Conference 2015 Conference Paper

ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding

  • Eli Boyarski
  • Ariel Felner
  • Roni Stern
  • Guni Sharon
  • Oded Betzalel
  • David Tolpin
  • Solomon Eyal Shimony

Conflict-Based Search (CBS) and its generalization, Meta-Agent CBS are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces ICBS, an improved version of CBS. ICBS incorporates three orthogonal improvements to CBS which are systematically described and studied. Experimental results show that each of these improvements reduces the runtime over basic CBS by up to 20x in many cases. When all three improvements are combined, an even larger improvement is achieved, producing state-ofthe art results for a number of domains.

Details