Recent advancements in bidirectional heuristic search have yielded significant theoretical insights and novel algorithms. While most previous work has concentrated on optimal search methods, this paper focuses on bounded-suboptimal bidirectional search, where a bound on the suboptimality of the solution cost is specified. We build upon the state-of-the-art optimal bidirectional search algorithm, BAE*, designed for consistent heuristics, and introduce several variants of BAE* specifically tailored for the bounded-suboptimal context. Through experimental evaluation, we compare the performance of these new variants against other bounded-suboptimal bidirectional algorithms as well as the standard weighted A* algorithm. Our results demonstrate that each algorithm excels under distinct conditions, highlighting the strengths and weaknesses of each approach.

In Bi-Objective Search (BOS), the task is to compute the Pareto-optimal frontier of paths in a graph with two cost values per edge. Recent work introduced a general BOS framework that classifies search nodes and studies how ordering functions affect expansion order. In this paper, we continue this line of research. We further refine the classes of nodes and show that many nodes that were added to the open list and are classified as never-expand nodes still need to be extracted and further examined. Additionally, we introduce a method that enables constant-time dominance checks for the MIN and MAX ordering functions. This allows a practical usage of these ordering functions, as we demonstrate in our experimental section.

The Multi-Agent Path Finding problem (MAPF) aims to find conflict-free paths for a group of agents, leading each agent to its respective goal. MAPF is applicable in navigating autonomous robots and vehicles to their destination. In this paper, we study the requirement of finding all optimal solutions in MAPF. We discuss the representation of all optimal solutions, propose four algorithms for finding them, and perform an extensive empirical evaluation of the proposed algorithms.

The multi-agent pathfinding problem (MAPF) of finding conflict-free paths for multiple agents has attracted a large number of researchers in the past. The cost of the solution is commonly measured by the sum-of-costs (SOC) cost function or, less commonly, by Makespan. In this paper, we focus on the Fuel cost function, which is the number of physical steps the agents traverse. While Fuel was mentioned in many previous papers, our paper is the first to deepen into it. We introduce an A*-based algorithm and a CBS-based algorithm for Fuel. We study Fuel theoretically, showing that it can be (perhaps non-intuitively) more complex than SOC. Finally, we experimentally compare both algorithms against each other and against their SOC counter parts, studying their advantages and disadvantages.

Recent advancements in bidirectional heuristic search have yielded significant theoretical insights and novel algorithms. While most previous work has concentrated on optimal search methods, this paper focuses on bounded-suboptimal bidirectional search, where a bound on the suboptimality of the solution cost is specified. We build upon the state-of-the-art optimal bidirectional search algorithm, BAE*, designed for consistent heuristics, and introduce several variants of BAE* specifically tailored for the bounded-suboptimal context. Through experimental evaluation, we compare the performance of these new variants against other bounded-suboptimal bidirectional algorithms as well as the standard weighted A* algorithm. Our results demonstrate that each algorithm excels under distinct conditions, highlighting the strengths and weaknesses of each approach.

The Multi-Agent Path Finding problem (MAPF) aims to find conflict-free paths for a group of agents leading each agent to its respective goal. In this paper, we study the requirement of finding all optimal solutions in MAPF. We discuss the representation of all optimal solutions, propose three algorithms for finding them, and compare the algorithms experimentally.

We address the challenge of finding a shortest path in a graph with unknown obstacles where the exploration cost to detect whether a state is free or blocked is very high (e.g., due to sensor activation for obstacle detection). The main objective is to solve the problem while minimizing the number of explorations. To achieve this, we propose MXA∗, a novel heuristic search algorithm based on A∗. The key innovation in MXA∗ lies in modifying the heuristic calculation to avoid obstacles that have already been revealed. Furthermore, this paper makes a noteworthy contribution by introducing the concept of a dynamic heuristic. In contrast to the conventional static heuristic, a dynamic heuristic leverages information that emerges during the search process and adapts its estimations accordingly. By employing a dynamic heuristic, we suggest enhancements to MXA∗ based on real-time information obtained from both the open and closed lists. We demonstrate empirically that MXA∗ finds the shortest path while significantly reducing the number of explored states compared to traditional A∗. The code is available at https: //github.com/bernuly1/MXA-Star.

The FastMap algorithm has been proposed as an inexpensive metric embedding which provides admissible distance estimates between all vertices in an embedding. As an embedding, it also supports additional operations such as taking the median location of two vertices, which is important in some problems. This paper studies several aspects of FastMap embeddings, showing the relationship of FastMap to general additive heuristics. As an admissible heuristic, FastMap is not as strong as previous suggested. However, by combining FastMap with the ideas of differential heuristics, we can significantly improve the performance of FastMap heuristics. We show the impact of these ideas in both single-agent pathfinding and the Multi-Agent Meeting problem, where the performance of algorithms using our improved FastMap embedding is improved by up to a factor of two.

This extended abstract presents a theoretical analysis of node expansions in Multi-Objective Search. We define three categories of nodes, Must-Expand Nodes, Maybe-Expand Nodes, and Never-Expand Nodes. Our analysis establishes that regardless of the Ordering Function or Multi-Objective Search algorithm used, any Multi-Objective Search algorithm must expand all Must-Expand Nodes, some or none of Maybe-Expand Nodes, and none of Never-Expand Nodes. In addition, we conduct experimental evaluations of various Ordering Functions, revealing that they all expand the same number of nodes and compare their efficiency at finding solutions at various stages of the search.

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

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.

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.

There are many settings that extend the basic shortest path search problem. In Bounded-Cost Search, we are given a constant bound and the task is to find a solution within the bound. In Bi-Objective Search, each edge is associated with two costs (objectives) and the task is to minimize both objectives. In this paper, we combine both these settings into a new setting of Bounded-Cost Bi-Objective Search. We are given two bounds, one for each objective and the task is to find a solution within these bounds. We provide a scheme for normalizing the two objectives. We then introduce several algorithms for this new setting and compare them experimentally.

To transmit information or transfer an object, two agents may need to reach the same location and meet. Often, such two agents operate in two separate environments and they can only meet at border locations. For example, a ship, sailing in the sea, needs to meet a truck traveling on land. These two agents are able to meet only at the shoreline. We call this problem the Meeting at the Border problem (MATB). In MATB, the optimal meeting location at the border is required, where the cost of a meeting location is the sum of the two shortest paths to that location. We show how to optimally solve MATB with heuristic search and suggest a novel heuristic function that estimates the cost of meeting at the border. Indeed, our new heuristic significantly enhances search algorithms in 2D and 3D domains.

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that every agent reaches its goal and the agents do not collide. Most prior work on MAPF were on grids, assumed agents' actions have uniform duration, and that time is discretized into timesteps. In this work, we propose a MAPF algorithm that do not assume any of these assumptions, is complete, and provides provably optimal solutions. This algorithm is based on a novel combination of Safe Interval Path Planning (SIPP), a continuous time single agent planning algorithms, and Conflict-Based Search (CBS). We analyze this algorithm, discuss its pros and cons, and evaluate it experimentally on several standard benchmarks.

This paper solves the Watchman Route Problem (WRP) on a general discrete graph with Heuristic Search. Given a graph, a line-of-sight (LOS) function, and a start vertex, the task is to (offline) find a (shortest) path through the graph such that all vertices in the graph will be visually seen by at least one vertex on the path. WRP is reminiscent but different from graph covering and mapping problems, which are done online on an unknown graph. We formalize WRP as a heuristic search problem and solve it optimally with an A*-based algorithm. We develop a series of admissible heuristics with increasing difficulty and accuracy. Our heuristics abstract the underlying graph into a disjoint line-of-sight graph (GDLS) which is based on disjoint clusters of vertices such that vertices within the same cluster have LOS to the same specific vertex. We use solutions for the Minimum Spanning Tree (MST) and the Traveling Salesman Problem (TSP) of GDLS as admissible heuristics for WRP. We theoretically and empirically investigate these heuristics. Then, we show how the optimal methods can be modified (by intelligently pruning away large sub-trees) to obtain various suboptimal solvers with and without bound guarantees. These suboptimal solvers are much faster and expand fewer nodes than the optimal solver with only minor reduction in the quality of the solution.

Multi-Agent Meeting (MAM) is the problem of finding a meeting location for multiple agents and paths to that location. Recently, a Multi-Directional Heuristic Search algorithm, called MM*, was introduced. MM* is a state-of-the-art MAM optimal solver that searches from multiple directions (one for each agent) and is guided by a heuristic function. Practically, a solution to MAM may contain conflicting paths. A related problem that plans conflict-free paths to a given set of goal locations is the Multi-Agent Path Finding problem (MAPF). In this paper, we solve the Conflict-Free Multi-Agent Meeting problem (CF-MAM). In CF-MAM, we find a meeting location for multiple agents (as in MAM) as well as conflict-free paths (as in MAPF) to that location. We introduce two novel algorithms, which combine MAM and MAPF solvers, for optimally solving CF-MAM. We compare both algorithms experimentally, showing the pros and cons of each algorithm.

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.

In many real-world scenarios, the time it takes for a mobile agent, e.g., a robot, to move from one location to another may vary due to exogenous events and be difficult to predict accurately. Planning in such scenarios is challenging, especially in the context of Multi-Agent Pathfinding (MAPF), where the goal is to find paths to multiple agents and temporal coordination is necessary to avoid collisions. In this work, we consider a MAPF problem with this form of time uncertainty, where we are only given upper and lower bounds on the time it takes each agent to move. The objective is to find a safe solution, which is a solution that can be executed by all agents and is guaranteed to avoid collisions. We propose two complete and optimal algorithms for finding safe solutions based on well-known MAPF algorithms, namely, A* with Operator Decomposition (A* + OD) and Conflict-Based Search (CBS). Experimentally, we observe that on several standard MAPF grids the CBS-based algorithm performs better. We also explore the option of online replanning in this context, i.e., modifying the agents' plans during execution, to reduce the overall execution cost. We consider two online settings: (a) when an agent can sense the current time and its current location, and (b) when the agents can also communicate seamlessly during execution. For each setting, we propose a replanning algorithm and analyze its behavior theoretically and empirically. Our experimental evaluation confirms that indeed online replanning in both settings can significantly reduce solution cost.

In the Multi-Agent Meeting problem (MAM), the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Heuristic Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding an optimal meeting location for multiple agents. Several admissible heuristics are proposed, and experiments demonstrate the benefits of MM*.

In the Multi-Agent Meeting (MAM) problem, the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding optimal meeting locations for multiple agents. A number of admissible heuristics are proposed and experiments demonstrate the benefits of MM*.

Multi-Agent Path Finding (MAPF) is the problem of finding non-colliding paths for multiple agents. The classical problem assumes that all agents are homogeneous, with a fixed size and behavior. However, in reality agents are heterogeneous, with different sizes and behaviors. In this paper, we generalize MAPF to G-MAPF for the case of heterogeneous agents. We then show how two previous settings of large agents and k-robust agents are special cases of G-MAPF. Finally, we introduce G-CBS, a variant of the Conflict-Based Search (CBS) algorithm for G-MAPF, which does not cause significant extra overhead.

Multi-agent path-finding (MAPF) is the problem of finding a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. In this work, we propose a holistic solution for MAPF that is robust to such unexpected delays. First, we introduce the notion of a k-robust MAPF plan, which is a plan that can be executed even if a limited number (k) of delays occur. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we propose several robust execution policies. An execution policy is a policy for agents executing a MAPF plan. An execution policy is robust if following it guarantees that the agents reach their goals even if they encounter unexpected delays. Several classes of such robust execution policies are proposed and evaluated experimentally. Finally, we present robust execution policies for cases where communication between the agents may also be delayed. We performed an extensive experimental evaluation in which we compared different algorithms for finding robust MAPF plans, compared different ro- bust execution policies, and studied the interplay between having a robust plan and the performance when using a robust execution policy.

Multi-agent pathfinding (MAPF) is the problem of moving a group of agents to a set of target destinations while avoiding collisions. In this work, we study the online version of MAPF where new agents appear over time. Several variants of online MAPF are defined and analyzed theoretically, showing that it is not possible to create an optimal online MAPF solver. Nevertheless, we propose effective online MAPF algorithms that balance solution quality, runtime, and the number of plan changes an agent makes during execution.

Multi-agent path finding (MAPF) is the problem of moving a set of agents from their individual start locations to their individual goal locations, without collisions. This problem has practical applications in video games, traffic control, robotics, and more. In MAPF we assume that agents occupy one location each time step. However, in real life some agents have different size or shape. Hence, a standard MAPF solution may be not suited in practice for some applications. In this paper, we describe a novel algorithm, based on the CBS algorithm, that finds a plan for moving a set of train-agents, i.e., agents that occupy a sequence of two or more locations, such as trains, buses, planes, or even snakes. We prove that our solution is optimal and show experimentally that indeed such a solution can be found. Finally, we explain how our solution can also apply to agents with any geometric shape.

In a multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. Guaranteeing that collisions will never occur may be impossible. An important task is to find a plan that is very likely to succeed, even though unexpected delays may occur. We propose an algorithm for finding a plan in which the probability that no collisions will occur is at least a given parameter p (p-robust plan). We show that finding an optimal p-robust plan is significantly more difficult than finding an optimal standard plan. As a practical solution, we propose a greedy algorithm based on the Conflict-Based Search framework. Our experiments show that it finds p-robust plans with cost that is relatively close to the optimal cost of the standard, non-robust plans.

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' actions costs. These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult for establishing appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. This paper aims to fill this gap and facilitate future research and practitioners by providing a unifying terminology for describing the common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks. In particular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms.

Multi-agent pathfinding is the problem of finding a non-interfering paths for a set of agents, such that if the agents follow these paths then each agent will reach its desired destination. Recent years have shown tremendous advances in this field, with optimal and suboptimal algorithms that are able to plan paths for over 100 agents in reasonable time. However, autonomous mobile agents are prime targets for cyber-security attacks, where an adversary may take control over an agent to disrupt the agents execution of their plan. This threat raises two questions. The first question is how much damage can an agent do if it does not follow its plan. The second question is how can one plan a-priori to be as robust as possible to such cyber-attacks. In this work, We provide an answer to both questions. To compute the maximal amount of damage that an adversary agent can do, we define a corresponding graph search problem and solve this problem with A*. Then, we provide a very simple method to choose a solution that is robust to such damages. We demonstrate both algorithms in simulation over standard multi-agent pathfinding domains.

In the multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. We explore the notion of k-robust MAPF, where the task is to find a plan that can be followed even if a limited number of such delays occur. k-robust MAPF is especially suitable for agents with a control mechanism that guarantees that each agent is within a limited number of steps away from its pre-defined plan. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we show the benefit of using a k-robust plan during execution, and for finding plans that are likely to succeed.

Finding the minimax value of a game is an important problem in a variety of fields, including game theory, decision theory, statistics, philosophy, economics, robotics, and security. Classical algorithms such as the Minimax algorithm can be used to find the minimax value, but require iterating over the entire game tree, which is in many cases too large. Alpha-Beta pruning identifies portions of the game tree that are not necessary for finding the minimax value, but in many cases the remaining part of the game tree is still too large to search in reasonable time. For such cases, we propose a class of algorithms that accepts a parameter e and returns a value that is guaranteed to be at most e away from the true minimax value. We lay the theoretical foundation for building such algorithms and present one such algorithm based on Alpha-Beta. Experimentally, we show that our algorithm allows controlling this runtime/solution quality tradeoff effectively.

In the multi-agent path-finding (MAPF) problem a plan is needed to move a set of agents from their initial location to their goals without collisions. In this paper we introduce and study the k-robust MAPF problem, where we seek a plan that is robust to k unexpected delays per agent.