Arrow Research search

Author name cluster

Daniel Harabor

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.

70 papers
2 author rows

Possible papers

70

AAAI Conference 2025 Conference Paper

Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities

  • Yue Zhang
  • Zhe Chen
  • Daniel Harabor
  • Pierre Le Bodic
  • Peter J. Stuckey

In multi-agent systems, when we account for the possibility of delays during execution, online planning becomes more complicated, as both execution and planning should be able to handle delays when agents are moving. Lifelong Multi-Agent Path Finding (LMAPF) is the problem of (re)planning the collision-free moves of agents to their goals in a shared space, while agents continuously receive new goals. PIE (Planning and Improving while Executing) is a recent approach to LMAPF which concurrently replans later parts of agents' trajectories while execution occurs. However, the execution is assumed to be perfect. Existing approaches either use policy-based methods to quickly coordinate agents every timestep with instant delay feedback, or deploy an execution policy to adjust a solution for delays on the fly. These approaches may introduce large amounts of unnecessary delays to agents due to their planner guarantees or simple delay-handling policies. In this paper, we extend PIE to define a framework for solving the lifelong MAPF problem with execution delays. We instantiate our framework with different execution and replanning strategies, and experimentally evaluate them. Overall, we find that this framework can substantially improve the throughput by up to a factor 3 for lifelong MAPF, compared to approaches that handle delays with simple execution policies.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

  • Hongzhi Zang
  • Yulun Zhang
  • He Jiang
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Jiaoyang Li

We study the problem of optimizing a guidance policy capable of dynamically guiding the agents for lifelong Multi-Agent Path Finding based on real-time traffic patterns. Multi-Agent Path Finding (MAPF) focuses on moving multiple agents from their starts to goals without collisions. Its lifelong variant, LMAPF, continuously assigns new goals to agents. In this work, we focus on improving the solution quality of PIBT, a state-of-the-art rule-based LMAPF algorithm, by optimizing a policy to generate adaptive guidance. We design two pipelines to incorporate guidance in PIBT in two different ways. We demonstrate the superiority of the optimized policy over both static guidance and human-designed policies. Additionally, we explore scenarios where task distribution changes over time, a challenging yet common situation in real-world applications that is rarely explored in the literature.

PDF Details DOI

JAIR Journal 2025 Journal Article

Prioritised Planning: Completeness, Optimality, and Complexity

  • Jonathan Morag
  • Yue Zhang
  • Daniel Koyfman
  • Zhe Chen
  • Ariel Felner
  • Daniel Harabor
  • Roni Stern

Prioritised Planning (PP) is a popular approach for multi-agent and multi-robot navigation. In PP, collision-free paths are computed for one agent at a time, following a total order over the agents, called a priority ordering. Many MAPF algorithms follow this approach or use it in some way, including several state-of-the-art MAPF algorithms, although it is known that PP is neither complete nor optimal. In this work, we characterise the space of problems a PP algorithm can solve, and define the search problem of identifying whether a given MAPF problem is in that space. We call this search problem Prioritised MAPF (P-MAPF) and investigate its computational complexity, showing that it is generally NP-hard. Then, we develop a novel efficient search algorithm called Path and Priority Search (PaPS), which solves P-MAPF, providing guarantees of completeness and optimality. We next observe that PP algorithms operate with two primary degrees of freedom – the choice of priority ordering, and the choice of individual paths for agents. Accordingly, we further divide P-MAPF into two planning problems corresponding to the two degrees of freedom. We call them Priority-Function Constrained MAPF (PFC-MAPF), where the path choice is fixed while the priority ordering is not, and Priority Constrained MAPF (PC-MAPF), where the priority ordering is fixed while the path choice is not. We analyse these problems as well, and show how PaPS can be easily adapted to create algorithms that solve these problems optimally. We experiment with our algorithms in a range of settings, including comparisons with existing PP baselines. Our results show how the different degrees of freedom of PP-based algorithms affect their behaviour, and provide the first-known results for solution-quality optimality for PP-based algorithms on a popular MAPF benchmark set. The latter can be used as a lower bound for any PP algorithm.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search

  • Shao-Hung Chan
  • Zhe Chen
  • Dian-Lun Lin
  • Yue Zhang
  • Daniel Harabor
  • Sven Koenig
  • Tsung-Wei Huang
  • Thomy Phan

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for multiple agents in a shared environment while improving the solution quality. The state-of-the-art anytime MAPF algorithm is based on Large Neighborhood Search (MAPF- LNS), which is a combinatorial search algorithm that iteratively destroys and repairs a subset of collision-free paths. In this paper, we propose Destroy-Repair Operation Parallelism for MAPF-LNS (DROP-LNS), a parallel framework that performs multiple destroy and repair operations concurrently to explore more regions of the search space and improve the solution quality. Unlike MAPF-LNS, DROP-LNS is able to exploit multiple threads during the search. The results show that DROP-LNS outperforms the state-of-the-art anytime MAPF algorithms, namely MAPF-LNS and LaCAM*, with respect to solution quality when terminated at the same runtime.

PDF

SoCS Conference 2024 Conference Paper

Avoiding Node Re-Expansions Can Break Symmetry Breaking

  • Mark Carlson
  • Daniel Harabor
  • Peter J. Stuckey

Symmetry breaking and weighted-suboptimal search are two popular speed up techniques used in pathfinding search. It is a commonly held assumption that they are orthogonal and easily combined. In this paper we illustrate that this is not necessarily the case when combining a number of symmetry breaking methods, based on Jump Point Search, with Weighted A*, a bounded suboptimal search approach which does not require node re-expansions. Surprisingly, the combination of these two methods can cause search to fail, finding no path to a target node when clearly such paths exist. We demonstrate this phenomena and show how we can modify the combination to always succeed with low overhead.

Details

SoCS Conference 2024 Conference Paper

Efficient and Exact Public Transport Routing via a Transfer Connection Database

  • Abdallah Abu-Aisha
  • Mark Wallace 0001
  • Daniel Harabor
  • Bojie Shen

We explore the earliest arrival time problem in public transport journey planning. A journey typically consists of multiple scheduled public transport legs. The actual time required to transfer between these legs can substantially influence route planning. Therefore, we properly model transfers by incorporating their exact costs. We then introduce a novel oracle-based routing algorithm that constructs an efficient transfer database, considering the proposed transfer model. The database is leveraged online to quickly reconstruct the optimal journey in response to an earliest arrival time query. Our experimental results show that neglecting exact transfer costs often lead to either infeasible or suboptimal route plans. Furthermore, the findings highlight the efficiency of our algorithm in handling queries, demonstrated by response times within mere microseconds.

Details

ICAPS Conference 2024 Conference Paper

Exact Multi-objective Path Finding with Negative Weights

  • Saman Ahmadi
  • Nathan R. Sturtevant
  • Daniel Harabor
  • Mahdi Jalili

The point-to-point Multi-objective Shortest Path (MOSP) problem is a classic yet challenging task that involves finding all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies have shown that employing A* search can lead to state-of-the-art performance in solving MOSP instances with non-negative costs. This paper proposes a novel A*-based multi-objective search framework that not only handles graphs with negative costs and even negative cycles but also incorporates multiple speed-up techniques to enhance the efficiency of exhaustive search with A*. Through extensive experiments, our algorithm demonstrates remarkable success in solving difficult MOSP instances, outperforming leading solutions by several factors.

Details

SoCS Conference 2024 Conference Paper

Planning and Exection in Multi-Agent Path Finding: Models and Algorithms (Extended Abstract)

  • Yue Zhang 0048
  • Zhe Chen 0016
  • Daniel Harabor
  • Pierre Le Bodic
  • Peter J. Stuckey

In applications of Multi-Agent Path Finding (MAPF), it is often the sum of planning and execution times that needs to be minimised (i. e. , the Goal Achievement Time). Yet current methods seldom optimise for this objective. Optimal algorithms reduce execution time, but may require exponential planning time. Non-optimal algorithms reduce planning time, but at the expense of increased path length. To address these limitations we introduce PIE (Planning and Improving while Executing), a new framework for concurrent planning and execution in MAPF. We first show how PIE for one-shot MAPF improves practical performance compared to sequential planning and execution. We then adapt PIE to Lifelong MAPF, a popular application setting where agents are continuously assigned new goals and where additional decisions are required to ensure feasibility. We examine a variety of different approaches to overcome these challenges and we conduct comparative experiments vs. recently proposed alternatives. Results show that PIE substantially outperforms existing methods for One-shot and Lifelong MAPF.

Details

ICAPS Conference 2024 Conference Paper

Planning and Execution in Multi-Agent Path Finding: Models and Algorithms

  • Yue Zhang 0048
  • Zhe Chen 0016
  • Daniel Harabor
  • Pierre Le Bodic
  • Peter J. Stuckey

In applications of Multi-Agent Path Finding (MAPF), it is often the sum of planning and execution times that needs to be minimised (i. e. , the Goal Achievement Time). Yet current methods seldom optimise for this objective. Optimal algorithms reduce execution time, but may require exponential planning time. Non-optimal algorithms reduce planning time, but at the expense of increased path length. To address these limitations we introduce PIE (Planning and Improving while Executing), a new framework for concurrent planning and execution in MAPF. We show how different instantiations of PIE affect practical performance, including initial planning time, action commitment time and concurrent vs. sequential planning and execution. We then adapt PIE to Lifelong MAPF, a popular application setting where agents are continuously assigned new goals and where additional decisions are required to ensure feasibility. We examine a variety of different approaches to overcome these challenges and we conduct comparative experiments vs. recently proposed alternatives. Results show that PIE substantially outperforms existing methods for One-shot and Lifelong MAPF.

Details

SoCS Conference 2024 Conference Paper

Prioritised Planning with Guarantees

  • Jonathan Morag
  • Yue Zhang 0048
  • Daniel Koyfman
  • Zhe Chen 0016
  • Ariel Felner
  • Daniel Harabor
  • Roni Stern

Prioritised Planning (PP) is a family of incomplete and sub-optimal algorithms for multi-agent and multi-robot navigation. In PP, agents compute collision-free paths in a fixed order, one at a time. Although fast and usually effective, PP can still fail, leaving users without explanation or recourse. In this work, we give a theoretical and empirical basis for better understanding the underlying problem solved by PP, which we call Priority Constrained MAPF (PC-MAPF). We first investigate the complexity of PC-MAPF and show that the decision problem is NP-hard. We then develop Priority Constrained Search (PCS), a new algorithm that is both complete and optimal with respect to a fixed priority ordering. We experiment with PCS in a range of settings, including comparisons with existing PP baselines, and we give first-known results for optimal PC-MAPF on a popular benchmark set.

Details

AAAI Conference 2024 Conference Paper

Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding

  • Zhe Chen
  • Daniel Harabor
  • Jiaoyang Li
  • Peter J. Stuckey

Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents, all moving across a shared map. Although many works appear on this topic, all current algorithms struggle as the number of agents grows. The principal reason is that existing approaches typically plan free-flow optimal paths, which creates congestion. To tackle this issue, we propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations. Empirically, we report large improvements in solution quality for one-short MAPF and in overall throughput for lifelong MAPF.

PDF Details DOI

SoCS Conference 2024 Conference Paper

Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (Extended Abstract)

  • Zhe Chen 0016
  • Daniel Harabor
  • Jiaoyang Li 0001
  • Peter J. Stuckey

Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents, all moving across a shared map. Existing scalable approaches struggle as the number of agents grows, as they typically plan free-flow optimal paths, which creates congestion. To tackle this issue, we propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. Empirically, we report large improvements in overall throughput for lifelong MAPF while coordinating more than ten thousand agents.

Details

ICAPS Conference 2023 Conference Paper

Beyond Pairwise Reasoning in Multi-Agent Path Finding

  • Bojie Shen
  • Zhe Chen 0016
  • Jiaoyang Li 0001
  • Muhammad Aamir Cheema
  • Daniel Harabor
  • Peter J. Stuckey

In Multi-Agent Path Finding (MAPF), we are asked to plan collision-free paths for teams of moving agents. Among the leading methods for optimal MAPF is Conflict-Based Search (CBS), an algorithmic family which has received intense attention in recent years and for which large advancements in efficiency and effectiveness have been reported. Yet all of the recent CBS gains come from reasoning over pairs of agents only. In this paper, we show how to further improve CBS by reasoning about more than two agents at the same time. Our new cluster reasoning techniques allow us to generate stronger bounds for CBS and to identify more bypasses (alternative cost-equivalent paths), which reduce the number of nodes in the CBS conflict tree.

Details

SoCS Conference 2023 Conference Paper

Efficient Multi Agent Path Finding with Turn Actions

  • Yue Zhang 0048
  • Daniel Harabor
  • Pierre Le Bodic
  • Peter J. Stuckey

Current approaches for real-world Multi-Agent Path Finding (MAPF) usually start with a simplified MAPF model and modify the resulting plans so they are kinematically feasible. We investigate one such problem, called MAPF with turn actions MAPF_T, and show that ignoring the kinematic constraints significantly increases solution cost. A first modification of the popular Conflict-Based Search algorithm to MAPF_T yields significantly better plans but comes at the cost of substantial decreases in scalability. We then introduce several techniques that can improve the performance of CBS for MAPF_T, including stronger and generalised versions of existing symmetry-breaking constraints and a novel pruning technique that eliminates redundant branches in the CBS constraint tree. Experimental results on six popular MAPF domains show convincing improvements for CBS success rate and substantial reductions in node expansions and runtime.

Details

ICAPS Conference 2023 Conference Paper

Exact Anytime Multi-Agent Path Finding Using Branch-and-Cut-and-Price and Large Neighborhood Search

  • Edward Lam 0001
  • Daniel Harabor
  • Peter J. Stuckey
  • Jiaoyang Li 0001

Given a set of agents on a grid, the multi-agent path finding problem aims to find a path that moves each agent from its given start location to its target location such that they do not collide and that the sum of arrival times is minimized. LNS2 is a state-of-the-art algorithm for anytime, suboptimal solving. It is an upper-bounding algorithm that repeatedly adjusts an existing solution and, being a local search, is oblivious to optimality. BCP is a state-of-the-art algorithm for exact solving. It is a lower-bounding tree search that attempts to tighten the lower bound until a solution appears. As BCP operates on the lower bound, the first solution it finds is optimal or nearly optimal, and therefore has poor anytime behavior. This paper proposes to tightly couple LNS2 and BCP to achieve better anytime, suboptimal solving while retaining the optimality guarantee of BCP. Experiments indicate that the combination achieves better anytime behavior than BCP in general and better suboptimal performance than LNS2 on congested maps.

Details

SoCS Conference 2023 Conference Paper

Reducing Redundant Work in Jump Point Search

  • Shizhe Zhao
  • Daniel Harabor
  • Peter J. Stuckey

JPS (Jump Point Search) is a state-of-the-art optimal algorithm for online grid-based pathfinding. Widely used in games and other navigation scenarios, JPS nevertheless can exhibit pathological behaviours which are not well studied: (i) it may repeatedly scan the same area of the map to find successors; (ii) it may generate and expand suboptimal search nodes. In this work, we examine the source of these pathological behaviours, show how they can occur in practice, and propose a purely online approach, called Constrained JPS (CJPS), to tackle them efficiently. Experimental results show that CJPS has low overheads and is often faster than JPS in dynamically changing grid environments: by up to 7x in large game maps and up to 14x in pathological scenarios.

Details

SoCS Conference 2023 Conference Paper

Voxel Benchmarks for 3D Pathfinding: Sandstone, Descent, and Industrial Plants

  • Thomas K. Nobes
  • Daniel Harabor
  • Michael Wybrow
  • Stuart D. C. Walsh

Voxel grids are an increasingly common enabler for pathfinding in 3D spaces. Currently in this area there exists only a limited number of publicly available benchmarks. This makes it difficult to establish state-of-the-art performance and to compare the strengths and weaknesses of competing search techniques. In this work, we introduce three new and diverse sets of voxel benchmarks intended to help fill this gap. We further describe our methodology for generating and selecting a representative set of pathfinding queries. Our dataset comprises 46 distinct voxel maps and 92, 000 problem instances. The data is drawn from distinct application domains: computer video games, industrial plant layouts and sandstone porosity scans. Featuring distinctive geometric properties and a variety of challenging query types, these new datasets allow practitioners to evaluate algorithmic performance across a variety of settings encountered when pathfinding in practice.

Details

SoCS Conference 2022 Conference Paper

Benchmarks for Pathfinding Search: Iron Harvest

  • Daniel Harabor
  • Ryan Hechenberger
  • Thomas Jahn

Pathfinding is a central topic in AI for games, with many approaches having been suggested. But comparing different algorithms is tricky, because design choices stem from different practical considerations; e. g. , some pathfinding systems are grid-based, others rely on a navigation mesh or visibility graph and so on. Current benchmarks mirror this trend, focusing on one set of assumptions while ignoring the rest. In this work we present a new unified benchmark using data from the game Iron Harvest. For 35 different levels in the game we generate several complementary map representations (grid, mesh and obstacle-set) and we provide a common set of challenging instances. We describe and analyse the new benchmark and then compare several leading pathfinding algorithms that begin from different assumption sets. Our goal is to allow researchers and practitioners to better understand the relative strengths and weakness of competing techniques.

Details

SoCS Conference 2022 Conference Paper

Dual Euclidean Shortest Path Search (Extended Abstract)

  • Ryan Hechenberger
  • Peter J. Stuckey
  • Pierre Le Bodic
  • Daniel Harabor

The Euclidean Shortest Path Problem (ESPP) asks us to find a minimum length path between two points on a 2D plane while avoiding a set of polygonal obstacles. Existing approaches for ESPP, based on Dijkstra or A* search, are primal methods that gradually build up longer and longer valid paths until they reach the target. In this paper we define an alternative algorithm for ESPP which can avoid this problem. Our approach starts from a path that ignores all obstacles, and generates longer and longer paths, each avoiding more obstacles, until eventually the search finds an optimal valid path.

Details

SoCS Conference 2022 Conference Paper

Fast Traffic Assignment by Focusing on Changing Edge Flows (Extended Abstract)

  • Ali Davoodi
  • Mark Wallace 0001
  • Daniel Harabor

This paper presents a novel algorithm for solving the traffic assignment problem (TAP). Contrary to traditional algorithms, which use the one-to-all shortest path algorithm to solve the problem for all origin destinations (OD) pairs, this algorithm tracks the changes of the edges and (at certain iterations) solves the problem only for critical edges whose flows have changed substantially using a state-of-the-art edge p2p shortest path algorithm. When additionally, only OD pairs with larger flows are considered, this enhancement halves the time needed to optimize the solution with a very small error in a large-scale network.

Details

AAAI Conference 2022 Conference Paper

Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding

  • Shao-Hung Chan
  • Jiaoyang Li
  • Graeme Gange
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents that minimize the sum of path costs. EECBS is a leading two-level algorithm that solves MAPF bounded-suboptimally, that is, within some factor w of the minimum sum of path costs C∗. It uses focal search to find bounded-suboptimal paths on the low level and Explicit Estimation Search (EES) to resolve collisions on the high level. EES keeps track of a lower bound LB on C∗ to find paths whose sum of path costs is at most w · LB in order to solve MAPF bounded-suboptimally. However, the costs of many paths are often much smaller than w times their minimum path costs, meaning that the sum of path costs is much smaller than w ·C∗. In this paper, we therefore propose Flexible EECBS (FEECBS), which uses a flex(ible) distribution of the path costs (that relaxes the requirement to find bounded-suboptimal paths on the low level) in order to reduce the number of collisions that need to be resolved on the high level while still guaranteeing to solve MAPF bounded suboptimally. We address the drawbacks of flex distribution via techniques such as restrictions on the flex distribution, restarts of the high-level search with EECBS, and low-level focal-A* search. Our empirical evaluation shows that FEECBS substantially improves the efficiency of EECBS on MAPF instances with large maps and large numbers of agents.

PDF Details

ICAPS Conference 2022 Conference Paper

Improving Time-Dependent Contraction Hierarchies

  • Bojie Shen
  • Muhammad Aamir Cheema
  • Daniel Harabor
  • Peter J. Stuckey

Computing time-optimal shortest paths, in road networks, is one of the most popular applications of Artificial Intelligence. This problem is tricky to solve because road congestion affects travel times. The state-of-the-art in this area is an algorithm called Time-dependent Contraction Hierarchies (TCH). Although fast and optimal, TCH still suffers from two main drawbacks: (1) the usual query process uses bi-directional Dijkstra search to find the shortest path, which can be time-consuming; and (2) the TCH is constructed w. r. t. the entire time domain T, which complicates the search process for queries q that start and finish in a smaller time period Tq ⊂ T. In this work, we improve TCH by making use of time-independent heuristics, which speed up optimal search, and by computing TCHs for different subsets of the time domain, which further reduces the size of the search space. We give a full description of these methods and discuss their optimality-preserving characteristics. We report significant query time improvements against a baseline implementation of TCH.

Details

AAAI Conference 2022 Conference Paper

MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search

  • Jiaoyang Li
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of planning collision-free paths for multiple agents in a shared environment. In this paper, we propose a novel algorithm MAPF- LNS2 based on large neighborhood search for solving MAPF efficiently. Starting from a set of paths that contain collisions, MAPF-LNS2 repeatedly selects a subset of colliding agents and replans their paths to reduce the number of collisions until the paths become collision-free. We compare MAPF- LNS2 against a variety of state-of-the-art MAPF algorithms, including Prioritized Planning with random restarts, EECBS, and PPS, and show that MAPF-LNS2 runs significantly faster than them while still providing near-optimal solutions in most cases. MAPF-LNS2 solves 80% of the random-scenario instances with the largest number of agents from the MAPF benchmark suite with a runtime limit of just 5 minutes, which, to our knowledge, has not been achieved by any existing algorithms.

PDF Details

ICAPS Conference 2022 Conference Paper

Multi-Agent Path Finding with Temporal Jump Point Search

  • Shuli Hu
  • Daniel Harabor
  • Graeme Gange
  • Peter J. Stuckey
  • Nathan R. Sturtevant

Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.

Details

SoCS Conference 2022 Conference Paper

Multi-Train Path Finding Revisited

  • Zhe Chen 0016
  • Jiaoyang Li 0001
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Train Path Finding (MTPF) is a coordination problem that asks us to plan collision-free paths for a team of moving agents, where each agent occupies a sequence of locations at any given time. MTPF is useful for planning a range of real-world vehicles, including rail trains and road convoys. MTPF is closely related to another coordination problem known as k-Robust Multi-Agent Path Finding (kR-MAPF). Although similar in principle, the performance of optimal MTPF algorithms in practice lags far behind that of optimal kR-MAPF algorithms. In this work, we revisit the connection between them and reduce the performance gap. First, we show that, in many cases, a valid kR-MAPF plan is also a valid MTPF plan, which leads to a new and faster approach for collision resolution. We also show that many recently introduced improvements for kR-MAPF, such as lower-bounding heuristics and symmetry reasoning, can be extended to MTPF. Finally, we explore a new type of pairwise symmetry specific to MTPF. Our experiments show that these improvements yield large efficiency gains for optimal MTPF.

Details

SoCS Conference 2022 Conference Paper

The JPS Pathfinding System in 3D

  • Thomas K. Nobes
  • Daniel Harabor
  • Michael Wybrow
  • Stuart D. C. Walsh

The ability to quickly compute shortest paths in 3D grids is a technological enabler for several applications such as pipe routing and computer video games. The main challenge is how to deal with the many symmetric permutations of each shortest path. We tackle this problem by adapting Jump Point Search (JPS), a well-known symmetry breaking technique developed for fast pathfinding in 2D grids. We give a rigorous reformulation of the JPS pathfinding system into 3D and we prove that our new algorithm, JPS-3D, is optimality preserving. We also develop a novel method for limiting scan depth during jump operations, which can further reduce search time. Experimental results show significant improvements versus online A* search and previous attempts at generalising JPS. We demonstrate that searching with adaptive scan limits can yield additional speedups of over an order of magnitude.

Details

SoCS Conference 2022 Conference Paper

Weight Constrained Path Finding with Bidirectional A

  • Saman Ahmadi
  • Guido Tack
  • Daniel Harabor
  • Philip Kilby

Weight constrained path finding, known as a challenging variant of the classic shortest path problem, aims to plan cost optimum paths whose weight/resource usage is limited by a side constraint. Given the bi-criteria nature of the problem (i. e. , the presence of cost and weight), solutions to the Weight Constrained Shortest Path Problem (WCSPP) have some properties in common with bi-objective search. This paper leverages the state-of-the-art bi-objective search algorithm BOBA* and presents WC-BA*, an exact A*-based WCSPP method that explores the search space in different objective orderings bidirectionally. We also enrich WC-BA* with two novel heuristic tuning approaches that can significantly reduce the number of node expansions in the exhaustive search of A*. The results of our experiments on a large set of realistic problem instances show that our new algorithm solves all instances and outperforms the state-of-the-art WCSPP algorithms in various scenarios.

Details

IJCAI Conference 2021 Conference Paper

Anytime Multi-Agent Path Finding via Large Neighborhood Search

  • Jiaoyang Li
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for multiple agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms that can solve large problems but usually find low-quality solutions. In this paper, we consider a third approach that combines the best of both worlds: anytime algorithms that quickly find an initial solution using efficient MAPF algorithms from the literature, even for large problems, and that subsequently improve the solution quality to near-optimal as time progresses by replanning subgroups of agents using Large Neighborhood Search. We compare our algorithm MAPF-LNS against a range of existing work and report significant gains in scalability, runtime to the initial solution, and speed of improving the solution.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Anytime Multi-Agent Path Finding via Large Neighborhood Search

  • Jiaoyang Li
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for a cooperative team of moving agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms (including prioritized and rule-based algorithms) that can solve very large practical problems but usually find low-quality solutions. In this paper, we consider a third approach that combines both advantages: anytime algorithms that quickly find an initial solution, including for large problems, and that subsequently improve the solution to near-optimal as time progresses. To improve the solution, we replan subsets of agents using Large Neighborhood Search, a popular meta-heuristic often applied in combinatorial optimization. Empirically, we compare our algorithm MAPF-LNS to the state-of-the-art anytime MAPF algorithm anytime BCBS and report significant gains in scalability, runtime to the first solution, and speed of improving solutions.

PDF

SoCS Conference 2021 Conference Paper

Bi-Objective Search with Bi-directional A* (Extended Abstract)

  • Saman Ahmadi
  • Guido Tack
  • Daniel Harabor
  • Philip Kilby

Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art bi-objective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.

Details

ICAPS Conference 2021 Conference Paper

Contracting and Compressing Shortest Path Databases

  • Bojie Shen
  • Muhammad Aamir Cheema
  • Daniel Harabor
  • Peter J. Stuckey

Compressed Path Databases (CPD) are powerful database-driven methods for shortest path extraction in grids and in spatial networks. Yet CPDs have two main drawbacks: (1) constructing the database requires an offline all-pairs precompute, which can sometimes be prohibitive and; (2) extracting a path requires a number of database lookups equal to its number of edges, which can be costly in terms of time. In this work, we consider how CPD methods can be improved and enhanced by: (i) contracting the input graph before preprocessing and; (ii) limiting the preprocessing step to only a selected subset of graph nodes. We also describe a new bi-directional path extraction algorithm which we call CH-CPD. In a range of experiments on road networks, we show that CH-CPD substantially improves on conventional CPDs in terms of preprocessing costs and online performance. We also report convincing query time improvements against a range of methods from the recent literature.

Details

SoCS Conference 2021 Conference Paper

Customised Shortest Paths Using a Distributed Reverse Oracle

  • Arthur Mahéo
  • Shizhe Zhao
  • Hassan Afzaal
  • Daniel Harabor
  • Peter J. Stuckey
  • Mark Wallace 0001

We consider the design and implementation of a centralised oracle that provides commuters with customised and congestion-aware driving directions. Computing directions for a single journey is straightforward, but doing so at city-scale, in real-time, and under changing conditions is extremely challenging. In this work we describe a new type of centralised oracle which combines fast database-driven path planning with a query management system that distributes work across a small commodity cluster of networked machines. Our system allows large-scale changes to the underlying graph metric, from one query to the next, and it supports a variety of query types including optimal, bounded suboptimal, time-budgeted and k-prefix. Simulated experiments show strong results: we can provide real-time routing for all peak-hour commuter trips in the city of Melbourne, Australia.

Details

SoCS Conference 2021 Conference Paper

ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding

  • Shao-Hung Chan
  • Jiaoyang Li 0001
  • Graeme Gange
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.

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

ICAPS Conference 2021 Conference Paper

Jump Point Search with Temporal Obstacles

  • Shuli Hu
  • Daniel Harabor
  • Graeme Gange
  • Peter J. Stuckey
  • Nathan R. Sturtevant

In 4-connected grid-based path planning one often needs to account for temporal and moving obstacles: ones that appear, disappear and which can prevent the agent from reaching its target. Such problems are common in a variety of settings (games, robotics etc.) and they can be surprisingly challenging to solve. First, because the temporal aspect increases the size of the search space; second because the search space contains many symmetric paths, indistinguishable from one another except by the order in which grid moves appear. To tackle such problems we consider a new optimal algorithm – in the style of Jump Point Search – which can identify and break these symmetries and thus improves performance; from several factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.

Details

SoCS Conference 2021 Conference Paper

Multi-Target Search in Euclidean Space with Ray Shooting

  • Ryan Hechenberger
  • Daniel Harabor
  • Muhammad Aamir Cheema
  • Peter J. Stuckey
  • Pierre Le Bodic

The shortest path problem (SPP) asks us to find a minimum length path between two points, usually on a graph. In a Euclidean environment the points are in a 2D plane and here the path must avoid a set of polygonal obstacles. Solution methods for this Euclidean SPP (ESPP) typically convert the continuous 2D map into a discretised representation, like a graph or navigation mesh. RayScan is a recent and fast ESPP algorithm which avoids the preprocessing step by using a combination of "ray shooting" and polygon scanning. In this paper we improve the performance of RayScan using spatial reasoning and ray caching techniques. We also extend the algorithm, from single-target search to a multi-target setting. Comparative game map experiments show a substantial speedup.

Details

AIJ Journal 2021 Journal Article

Pairwise symmetry reasoning for multi-agent path finding search

  • Jiaoyang Li
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma
  • Graeme Gange
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that asks us to plan collision-free paths for a team of cooperative agents. In this work, we show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry, which occurs when two agents have many different paths to their target locations, all of which appear promising, but every combination of them results in a collision. We identify several classes of pairwise symmetries and show that each one arises commonly in practice and can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes for current state-of-the-art (bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning techniques that detect the symmetries efficiently as they arise and resolve them by using specialized constraints to eliminate all permutations of pairwise colliding paths in a single branching step. We implement these ideas in the context of a leading optimal MAPF algorithm CBS and show that the addition of the symmetry reasoning techniques can have a dramatic positive effect on its performance — we report a reduction in the number of node expansions by up to four orders of magnitude and an increase in scalability by up to thirty times. These gains allow us to solve to optimality a variety of challenging MAPF instances previously considered out of reach for CBS.

Details DOI

JAIR Journal 2021 Journal Article

Regarding Goal Bounding and Jump Point Search

  • Yue Hu
  • Daniel Harabor
  • Long Qin
  • Quanjun Yin

Jump Point Search (JPS) is a well known symmetry-breaking algorithm that can substantially improve performance for grid-based optimal pathfinding. When the input grid is static further speedups can be obtained by combining JPS with goal bounding techniques such as Geometric Containers (instantiated as Bounding Boxes) and Compressed Path Databases. Two such methods, JPS+BB and Two-Oracle Path PlannING (Topping), are currently among the fastest known approaches for computing shortest paths on grids. The principal drawback for these algorithms is the overhead costs: each one requires an all-pairs precomputation step, the running time and subsequent storage costs of which can be prohibitive. In this work we consider an alternative approach where we precompute and store goal bounding data only for grid cells which are also jump points. Since the number of jump points is usually much smaller than the total number of grid cells, we can save up to orders of magnitude in preprocessing time and space. Considerable precomputation savings do not necessarily mean performance degradation. For a second contribution we show how canonical orderings, partial expansion strategies and enhanced intermediate pruning can be leveraged to improve online query performance despite a reduction in preprocessed data. The combination of faster preprocessing and stronger online reasoning leads to three new and highly performant algorithms: JPS+BB+ and Two-Oracle Pathfinding Search (TOPS) based on search, and Topping+ based on path extraction. We give a theoretical analysis showing that each method is complete and optimal. We also report convincing gains in a comprehensive empirical evaluation that includes almost all current and cutting-edge algorithms for grid-based pathfinding.

PDF Details DOI

ICAPS Conference 2021 Conference Paper

Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

  • Jiaoyang Li 0001
  • Zhe Chen 0016
  • Yi Zheng 0010
  • Shao-Hung Chan
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma 0001
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale rail networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF or, in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.

Details

SoCS Conference 2021 Conference Paper

Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

  • Jiaoyang Li 0001
  • Zhe Chen 0016
  • Yi Zheng 0010
  • Shao-Hung Chan
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma 0001
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale railway networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF, or in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.

Details

ICAPS Conference 2020 Conference Paper

Bounded Suboptimal Path Planning with Compressed Path Databases

  • Shizhe Zhao
  • Mattia Chiari
  • Adi Botea
  • Alfonso Emilio Gerevini
  • Daniel Harabor
  • Alessandro Saetti
  • Peter J. Stuckey

Compressed Path Databases (CPDs) are a state-of-the-art method for path planning. They record, for each start position, an optimal first move to reach any target position. Computing an optimal path with CPDs is extremely fast and requires no state-space search. The main disadvantages are overhead related: building a CPD usually involves an all-pairs precomputation, and storing the result often incurs prohibitive space overheads. Previous research has focused on reducing the size of CPDs and/or improving their online performance. In this paper we consider a new type of CPD, which can also dramatically reduce preprocessing times. Our idea involves computing first-move data for only selected target nodes; chosen in such a way as to guarantee that the cost of any extracted path is within a fixed bound of the optimal solution. Empirical results demonstrate that our new bounded suboptimal CPDs improve preprocessing times by orders of magnitude. They further reduce storage costs, and compute paths more quickly – all in exchange for only a small amount of suboptimality.

Details

IJCAI Conference 2020 Conference Paper

Euclidean Pathfinding with Compressed Path Databases

  • Bojie Shen
  • Muhammad Aamir Cheema
  • Daniel Harabor
  • Peter J. Stuckey

We consider optimal and anytime algorithms for the Euclidean Shortest Path Problem (ESPP) in two dimensions. Our approach leverages ideas from two recent works: Polyanya, a mesh-based ESPP planner which we use to represent and reason about the environment, and Compressed Path Databases, a speedup technique for pathfinding on grids and spatial networks, which we exploit to compute fast candidate paths. In a range of experiments and empirical comparisons we show that: (i) the auxiliary data structures required by the new method are cheap to build and store; (ii) for optimal search, the new algorithm is faster than a range of recent ESPP planners, with speedups ranging from several factors to over one order of magnitude; (iii) for anytime search, where feasible solutions are needed fast, we report even better runtimes.

PDF Details DOI

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

SoCS Conference 2020 Conference Paper

From Multi-Agent Pathfinding to 3D Pipe Routing

  • Gleb Belov
  • Wenbo Du 0004
  • Maria Garcia de la Banda
  • Daniel Harabor
  • Sven Koenig
  • Xinrui Wei

The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal positions in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance in automated warehousing (such as those operated by Amazon) and in other contemporary application areas. In this paper, we demonstrate that some recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on real-world PR instances. This opens up a new direction of industrial relevance for the MAPF research community.

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

ICAPS Conference 2020 Conference Paper

New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding

  • Jiaoyang Li 0001
  • Graeme Gange
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma 0001
  • Sven Koenig

We consider two new classes of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage in opposite directions. The second, target symmetry, arises when the shortest path of one agent passes through the target location of a second agent after the second agent has already arrived at it. These symmetries can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes even for state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We propose to break these symmetries using new reasoning techniques that: (1) detect each class of symmetry and (2) resolve them by introducing specialized constraints. We experimentally show that our techniques can, in some cases, more than double the success rate of CBS and improve its runtime by one order of magnitude.

Details

SoCS Conference 2020 Conference Paper

New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding

  • Jiaoyang Li 0001
  • Graeme Gange
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma 0001
  • Sven Koenig

We consider two new types of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage but in opposite directions. The second, target symmetry, arises when the shortest path of one agent requires the target location of a second agent after the second agent has already arrived. These symmetries can produce an exponential blowup in the space of possible collision resolutions, leading to timeout failure even for state-of-the-art algorithms such as Conflict-Based Search. We propose to break symmetries using new reasoning techniques that: (1) detect each type of situation and, (2) resolve them by introducing specialized constraints. We implement our ideas in the context of Conflict-Based Search where, in a range of experiments, we report up to an order-of-magnitude improvement in runtime performance and, in some cases, more than a doubling in success rate.

Details

ICAPS Conference 2020 Conference Paper

Online Computation of Euclidean Shortest Paths in Two Dimensions

  • Ryan Hechenberger
  • Peter J. Stuckey
  • Daniel Harabor
  • Pierre Le Bodic
  • Muhammad Aamir Cheema

We consider the online version of Euclidean Shortest Path (ESP): a problem that asks for distance minimal trajectories between traversable pairs of points in the plane. The problem is made challenging because each trajectory must avoid a set of non-traversable obstacles represented as polygons. To solve ESP practitioners will often preprocess the environment and construct specialised data structures, such as visibility graphs and navigation meshes. Pathfinding queries on these data structures are fast but the preprocessed data becomes invalidated when obstacles move or change. In this work we propose RayScan, a new algorithmic approach for ESP which is entirely online. The central idea is simple: each time we expand a node we also cast a ray toward the target. If an obstacle intersects the ray we scan its perimeter for a turning point; i. e. a vertex from which a new ray can continue unimpeded towards the target. RayScan is fast, optimal and entirely online. Experiments show that it can significantly improve upon current state-of-the-art methods for ESP in cases where the set of obstacles is dynamic.

Details

ICAPS Conference 2019 Conference Paper

Cutting the Size of Compressed Path Databases with Wildcards and Redundant Symbols

  • Mattia Chiari
  • Shizhe Zhao
  • Adi Botea
  • Alfonso Emilio Gerevini
  • Daniel Harabor
  • Alessandro Saetti
  • Matteo Salvetti
  • Peter J. Stuckey

Path planning on gridmaps is a common problem in AI and a popular topic in application areas such as computer games. Compressed Path Databases (CPDs) represent a state-of-theart approach to the problem, in terms of the speed of computing full optimal paths and also individual optimal moves. Despite significant improvements in recent years, the memory required to store a CPD can still be a bottleneck for large game maps. In this work we present a new compression approach that can reduce the size of CPDs. Our approach uses an extended notion of wildcards and a novel concept called a redundant symbol. We implement our ideas on top of a state-of-the-art CPD system and, in a range of experiments, we demonstrate a substantial reduction in the size of CPDs.

Details

ICAPS Conference 2019 Conference Paper

Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search

  • Jiaoyang Li 0001
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma 0001
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the planning problem of finding collision-free paths for a team of agents. We focus on Conflict-Based Search (CBS), a two-level tree-search state-of-the-art MAPF algorithm. The standard splitting strategy used by CBS is not disjoint, i. e. , when it splits a problem into two subproblems, some solutions are shared by both subproblems, which can create duplication of search effort. In this paper, we demonstrate how to improve CBS with disjoint splitting and how to modify the low-level search of CBS to take maximal advantage of it. Experiments show that disjoint splitting increases the success rates and speeds of CBS and its variants by up to 2 orders of magnitude.

Details

SoCS Conference 2019 Conference Paper

Extended Abstract: Searching with Consistent Prioritization for Multi-Agent Path Finding

  • Hang Ma 0001
  • Daniel Harabor
  • Peter J. Stuckey
  • Jiaoyang Li 0001
  • Sven Koenig

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.

Details

ICAPS Conference 2019 Conference Paper

Improving the Combination of JPS and Geometric Containers

  • Yue Hu 0016
  • Daniel Harabor
  • Long Qin
  • Quanjun Yin
  • Cong Hu

The JPS family of grid-based pathfinding algorithms can be improved with preprocessing methods such as Geometric Containers. However, such enhancements require a Dijkstra search for every node in the grid and the space and time costs of all this additional computation can be prohibitive. In this work we consider an alternative approach where we run Dijkstra only from every node where a jump point is located. We also compute and store geometric containers only for those outgoing edges which are consistent with the diagonal-first ordering in JPS. Since the number of jump points on a grid is usually much smaller than the total number of grid cells, we can save up to orders of magnitude of time and space. In addition to improving preprocessing overheads, we also present a partial expansion strategy which can improve the performance of online search by reducing the total number of operations on the open list.

Details

ICAPS Conference 2019 Conference Paper

Lazy CBS: Implicit Conflict-Based Search Using Lazy Clause Generation

  • Graeme Gange
  • Daniel Harabor
  • Peter J. Stuckey

Conflict-based Search (CBS) is a effective approach to optimal multi-agent path finding. However, performance of CBS approaches degrade rapidly in highly-contended graphs with many agents. One of the reasons this occurs is that CBS does not detect independent subproblems; i. e. it can re-solve the same conflicts between the same pairs of agents up to exponentially many times, each time along a different branch. Constraint programming approaches with nogood learning avoid this kind of duplication of effort by storing nogoods that record the reasons for conflicts. This can exponentially reduce search in constraint programming. In this work, we present Lazy CBS, a new approach to multi-agent pathfinding which replaces the high-level solver of CBS with a lazily constructed constraint programming model with nogoods. We use core-guided depth-first search to explore the space of conflicts and we detect along each branch reusable nogoods which help to quickly identify feasible solutions. Our experiments show that Lazy CBS can significantly improve on the state-of-the-art for optimal MAPF problems under the sumof-costs metric, especially in cases where there exists significant contention.

Details

AAAI Conference 2019 Conference Paper

Searching with Consistent Prioritization for Multi-Agent Path Finding

  • Hang Ma
  • Daniel Harabor
  • Peter J. Stuckey
  • Jiaoyang Li
  • Sven Koenig

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.

PDF Details

AAAI Conference 2019 Conference Paper

Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding

  • Jiaoyang Li
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma
  • Sven Koenig

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.

PDF Details

SoCS Conference 2019 Conference Paper

Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding

  • Jiaoyang Li 0001
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma 0001
  • Sven Koenig

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.

Details

SoCS Conference 2018 Conference Paper

Fast k-Nearest Neighbor on a Navigation Mesh

  • Shizhe Zhao
  • David Taniar
  • Daniel Harabor

We consider the k-Nearest Neighbour problem in a two-dimensional Euclidean plane with obstacles (OkNN). Existing and state of the art algorithms for OkNN are based on incremental visibility graphs and as such suffer from a well known disadvantage: costly and online visibility checking with quadratic worst-case running times. In this work we develop a new OkNN algorithm which avoids these disadvantages by representing the traversable space as a collection of convex polygons; i. e. a Navigation Mesh. We then adapt an recent and optimal navigation mesh algorithm, Polyanya, from the single-source single-target setting to the the multi-target case. We also give two new heuristics for OkNN. In a range of empirical comparisons we show that our approach can be orders of magnitude faster than competing methods that rely on visibility graphs.

Details

SoCS Conference 2018 Conference Paper

Forward Search in Contraction Hierarchies

  • Daniel Harabor
  • Peter J. Stuckey

Contraction hierarchies are graph-based data structure developed to speed up shortest path search in road networks. Built during an offline pre-processing step, contraction hierarchies are always paired with an online query algorithm which is a variation on bi-directional Dijkstra search. Though effective and highly popular this combination can sometimes be difficult to extend, for example in order to leverage goal-directed heuristics or other forward-driven pruning techniques. In this paper we deconstruct the bi-directional query algorithm of contraction hierarchies and derive a new algorithmic schema which is compatible with standard uni-directional or bi-directional search. We then develop a variety of new uni-directional query algorithms to find optimal paths in contraction hierarchies. These are based on the combination of A* search and Geometric Containers, a well known and successful edge-pruning technique. Empirical results show that our approach can improve search times by an order of magnitude vs bi-directional Dijkstra, albeit at the cost of additional memory and pre-processing time.

Details

ICAPS Conference 2018 Conference Paper

Two-Oracle Optimal Path Planning on Grid Maps

  • Matteo Salvetti
  • Adi Botea
  • Alfonso Emilio Gerevini
  • Daniel Harabor
  • Alessandro Saetti

Path planning on grid maps has progressed significantly in recent years, partly due to the Grid-based Path Planning Competition GPPC. In this work we present an optimal approach which combines features from two modern path planning systems, SRC and JPS+, both of which were among the strongest entrants at the 2014 edition of the competition. Given a current state s and a target state t, SRC is used as an oracle to provide an optimal move from s towards t. Once a direction is available we invoke a second JPS-based oracle to tell us for how many steps that move can be repeated, with no need to query the oracles between these steps. Experiments on a range of grid maps demonstrate a strong improvement from our combined approach. Against SRC, which remains an optimal solver with state-of-the-art speed, the performance improvement of our new system ranges from comparable to more than one order of magnitude faster.

Details

AAAI Conference 2015 Conference Paper

Complexity Results for Compressing Optimal Paths

  • Adi Botea
  • Ben Strasser
  • Daniel Harabor

In this work we give a first tractability analysis of Compressed Path Databases, space efficient oracles used to very quickly identify the first arc on a shortest path. We study the complexity of computing an optimal compressed path database for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms which yield optimal compression results for trees.

PDF Details

JAIR Journal 2015 Journal Article

Compressing Optimal Paths with Run Length Encoding

  • Ben Strasser
  • Adi Botea
  • Daniel Harabor

We introduce a novel approach to Compressed Path Databases, space efficient oracles used to very quickly identify the first edge on a shortest path. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix. One variant of our implemented system was, by a convincing margin, the fastest entry in the 2014 Grid-Based Path Planning Competition. We give a first tractability analysis for the compression scheme used by our algorithm. We study the complexity of computing a database of minimum size for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms with linear running time which yield optimal compression results for trees.

PDF Details DOI

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.

Details

SoCS Conference 2014 Conference Paper

Fast First-Move Queries through Run-Length Encoding

  • Ben Strasser
  • Daniel Harabor
  • Adi Botea

We introduce a novel preprocessing-based algorithm to solve the problem of determining the first arc of a shortest path in sparse graphs. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix.

Details

ICAPS Conference 2014 Conference Paper

Improving Jump Point Search

  • Daniel Harabor
  • Alban Grastien

We give online and offline optimisation techniques to improve the performance of Jump Point Search (JPS): a recent and very effective symmetry-breaking algorithm that speeds up pathfinding in computer games. First, we give a new and more efficient procedure for online symmetry breaking by manipulating "blocks'' of nodes at a single time rather than individual nodes. Second, we give a new offline pre-processing technique that can identify jump points apriori in order to further speed up pathfinding search. Third, we enhance the pruning rules of JPS, allowing it to ignore many nodes that must otherwise be expanded. On three benchmark domains taken from real computer games we show that our enhancements can improve JPS performance by anywhere from several factors to over one order of magnitude. We also compare our approaches with SUB: a very recent state-of-the-art offline pathfinding algorithm. We show that our improvements are competitive with this approach and often faster.

Details

ICAPS Conference 2013 Conference Paper

An Optimal Any-Angle Pathfinding Algorithm

  • Daniel Harabor
  • Alban Grastien

Any-angle pathfinding is a common problem from robotics and computer games: it requires finding a Euclidean shortest path between a pair of points in a grid map. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require supra-linear space and preprocessing time. In this paper we describe Anya: a new optimal any-angle pathfinding algorithm which searches over sets of states represented as intervals. Each interval is identified online. From each we select a representative point to derive a corresponding f-value for the set. Anya always returns an optimal path. Moreover it does so entirely online, without any preprocessing or memory overheads. This result answers an open question from the areas of Artificial Intelligence and Game Development: is there an any-angle pathfinding algorithm which is online and optimal? The answer is yes.

Details

ICAPS Conference 2013 Conference Paper

Moving Target Search with Compressed Path Databases

  • Adi Botea
  • Jorge A. Baier
  • Daniel Harabor
  • Carlos Hernández Ulloa

Moving target search, where the goal state changes during a search, has recently seen a revived interest. Incremental Anytime Repairing A* (I-ARA*) is a very recent, state-ofthe-art algorithm for moving target search in a known terrain. In this work, we address the problem using compressed path databases (CPDs) in moving target search. CPDs have previously been used in standard, fixed-target pathfinding. They encode all-pairs shortest paths in a compressed form and require preprocessing and memory to store the database. In moving-target search, our speed results are orders of magnitude better than state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. The number of hunter moves is very good, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA*, our method is simple to understand and implement.

Details

ICAPS Conference 2013 Conference Paper

Path Planning with Compressed All-Pairs Shortest Paths Data

  • Adi Botea
  • Daniel Harabor

All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.

Details

SoCS Conference 2012 Conference Paper

The JPS Pathfinding System

  • Daniel Harabor
  • Alban Grastien

We describe a pathfinding system based on Jump Point Search (JPS): a recent and very successful search strategy that performs symmetry breaking to speed up optimal pathfinding on grid maps. We first modify JPS for grid maps where corner-cutting moves are not allowed. We then describe JPS+: a new derivative search strategy that reformulates an input graph into an equivalent symmetry-reduced form that can be searched more efficiently. JPS and JPS+ were both submitted to the 2012 Grid-based Path Planning Competition.

Details

IJCAI Conference 2011 Conference Paper

Graph Pruning and Symmetry Breaking on Grid Maps

  • Daniel Harabor

My research proposes to speed up grid-based pathfinding by identifying and eliminating symmetric path segments from the search space. Two paths are said to be symmetric if they are identical save for the order in which the individual moves (or steps) occur. To deal with path symmetries I decompose an arbitrary grid map into a set of empty rectangles and remove from each rectangle all interior nodes and possibly some from along the perimeter. A series of macro edges are then added between selected pairs of remaining nodes in order to facilitate provably optimal traversal through each rectangle. The new algorithm, Rectangular Symmetry Reduction (RSR), can speed up A* search by up to 38 times on a range of uniform cost maps taken from the literature. In addition to being fast and optimal, RSR requires no significant extra memory and is largely orthogonal all existing speedup techniques. When compared to the state of the art, RSR often shows significant improvement across a range of benchmarks.

PDF Details DOI

AAAI Conference 2011 Conference Paper

Online Graph Pruning for Pathfinding On Grid Maps

  • Daniel Harabor
  • Alban Grastien

Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A* by an order of magnitude and more and report significant improvement over the current state of the art.

PDF Details