The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities. This paper was published at AAAI 2019.

We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time. This paper was published at AAAI 2019.

Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a two-level tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e.g., a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as “large” agents because they can occupy multiple points at the same time. In this paper, we formalize and study LAMAPF, i.e., MAPF for large agents. We first show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MC-CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

We describe a new way of reasoning about symmetric collisions for Multi-Agent Path Finding (MAPF) on 4-neighbor grids. We also introduce a symmetry-breaking constraint to resolve these conflicts. This specialized technique allows us to identify and eliminate, in a single step, all permutations of two currently assigned but incompatible paths. Each such permutation has exactly the same cost as a current path, and each one results in a new collision between the same two agents. We show that the addition of symmetry-breaking techniques can lead to an exponential reduction in the size of the search space of CBS, a popular framework for MAPF, and report significant improvements in both runtime and success rate versus CBSH and EPEA* – two recent and state-of-the-art MAPF algorithms.

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.

It is known that seemingly small details such as tie-breaking among nodes with the same f-cost can significantly affect the performance of a best-first search algorithm on many domains (Asai and Fukunaga 2017). In this paper, we show that low-level algorithmic details of domain-independent planning heuristics can have a surprisingly large impact on search performance. As a case study, we consider the well-known FF heuristic (hff ) (Hoffmann and Nebel 2001).

We present BRIGITTE, a new path-finding algorithm for 8-connected grids. It is based on the notion bridge that we define here, i.e., a high-level description of paths between all pairs of points from two convex regions that allows fast distance query and fast generation of the prefix and suffix of these paths. BRIGITTE uses a pre-processing step to first partition the map into convex regions and then compute a sufficient set of bridges between every pair of regions. Path-finding is then performed by looking up the regions of the source and target cells and then iterating over the bridges of the pair of regions to determine which one yields the shortest path. BRIGITTE competes favourably compared to CH-SG-R and Copp, although this currently comes at a price of an extensive pre-processing.

Multi-Agent Pathfinding (MAPF) over grids is the problem of finding n non-conflicting paths that lead n agents from a given initial cell to a given goal cell. Cost-optimal MAPF in addition minimizes the total number of actions performed by each agent before stopping at the goal. Being a combinatorial problem in nature, a number of compilations from MAPF to Answer Set Programming (ASP) exist. In this paper we propose a new one, which unlike existing ASP approaches (1) produces cost-optimal solutions, (2) exploits information that can be pre-computed quickly using Dijkstra's algorithm, and (3) when grounded, produces a number of clauses that grows linearly with the number of agents. In our empirical evaluation, in which we use the clasp solver, we show that our approach is superior to heuristic-search-based algorithms in various settings.

Empirically, this optimization lead to 0.5 - 2.5% savings on expansions in our experiments A fundamental concern in real-time planning is the presence (Cserna, Gall, and Ruml 2019). of dead-ends in the state space, from which no goal is reachable. SafeRTS interleaves exploration and safety proofs during Providing real-time heuristic search algorithms that are its planning phase. As a direct consequence, it attempts complete in domains with dead-end states is a challenging safety proofs on nodes that become internal to the LSS by problem. Recently, the SafeRTS algorithm was proposed for the end of the search iteration. As shown in Cserna, Gall, and searching in such spaces (Cserna et al. 2018). SafeRTS exploits Ruml (2019), it would be equally or less difficult to achieve a user-provided predicate to identify safe states, from the same or better safety coverage by doing safety proofs after which a goal is likely reachable, and attempts to maintain a all the LSS expansions. SafeRTS has an anytime behavior backup plan for reaching a safe state at all times.

Most real-world project have a deadline and consist of completing tasks. In our setting, each task needs to be executed by a single supplier, chosen from a subset of suppliers that have the required proficiency to handle that task. The suppliers differ in their execution times, which are stochastically taken from known distributions. The Supplier Assignment for Meeting a Deadline (SAMD) problem is the problem of assigning a supplier to each task in a manner that maximizes the chance to meet the overall project deadline. We propose an A*-based approach, along with an efficient admissible heuristic function, that guarantees an optimal solution for this problem. Experimentally, we compare our A*-based approach to an exhaustive brute-force approach and several heuristic methods. The results show that our A*-based approach compares favorably with the heuristic methods, and is orders of magnitude faster than the exhaustive alternative.