DHDaniel Harabor

Daniel Harabor

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Daniel Harabor has a total of 54 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    An exact system optimum model for the schedule-based transit assignment problem

    by Xia Zhou, Mark Wallace, Daniel D. Harabor, Zhenliang Ma

  • Prioritised Planning: Completeness, Optimality, and Complexity

    by 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.


  • Open Access

    Parallelizing Multi-objective A* Search

    by Saman Ahmadi, Nathan R. Sturtevant, Andrea Raith, Daniel Harabor, Mahdi Jalili

    The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem that aims to find all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies on multi-objective search with A* (MOA*) have demonstrated superior performance in solving difficult MOSP instances. This paper presents a novel search framework that allows efficient parallelization of MOA* with different objective orders. The framework incorporates a unique upper-bounding strategy that helps the search reduce the problem's dimensionality to one in certain cases. Experimental results demonstrate that the proposed framework can enhance the performance of recent A*-based solutions, with the speed-up proportional to the problem dimension.


  • Open Access

    Dynamic Replanning for Improved Public Transport Routing

    by Abdallah Abuaisha, Bojie Shen, Daniel D. Harabor, Peter J. Stuckey, Mark Wallace

    Delays in public transport are common, often impacting users through prolonged travel times and missed transfers. Existing solutions for handling delays remain limited; backup plans based on historical data miss opportunities for earlier arrivals, while snapshot planning accounts for current delays but not future ones. With the growing availability of live delay data, users can adjust their journeys in real-time. However, the literature lacks a framework that fully exploits this advantage for system-scale dynamic replanning. To address this, we formalise the dynamic replanning problem in public transport routing and propose two solutions: a "pull" approach, where users manually request replanning, and a novel "push" approach, where the server proactively monitors and adjusts journeys. Our experiments show that the push approach outperforms the pull approach, achieving significant speedups. The results also reveal substantial arrival time savings enabled by dynamic replanning.

  • Open Access

    Real-Time LaCAM for Real-Time MAPF

    by Runzhe Liang, Rishi Veerapaneni, Daniel Harabor, Jiaoyang Li, Maxim Likhachev

    The vast majority of Multi-Agent Path Finding (MAPF) methods with completeness guarantees require planning full-horizon paths. However, planning full-horizon paths can take too long and be impractical in real-world applications. Instead, real-time planning and execution, which only allows the planner a finite amount of time before executing and replanning, is more practical for real-world multi-agent systems. Several methods utilize real-time planning schemes but none are provably complete, which leads to livelock or deadlock. Our main contribution is Real-Time LaCAM, the first Real-Time MAPF method with provable completeness guarantees. We do this by leveraging LaCAM in an incremental fashion. Our results show how we can iteratively plan for congested environments with a cutoff time of milliseconds while still maintaining the same success rate as full-horizon LaCAM. We also show how it can be used with a single-step learned MAPF policy.


  • Open Access

    Sub-Microsecond Grid Path Planning, at What Cost?

    by Mark Carlson, Daniel Harabor, Peter J. Stuckey

    Tree Cache is a lightweight pre-processing approach to grid path finding which works by generating a shortest path tree: from a root cell to all cells in the map. During online search Tree Cache simply follows the tree: from start and target towards the root, stopping at the first common cell. Although Tree Cache is fast, the resulting paths have no solution quality guarantees. In this paper we improve Tree Cache, in terms of speed and solution quality, by combining symmetry breaking ideas from Jump Point Search. Our new algorithm, Jump Spanning Tree Search (JSTS), can usually generate paths with low average sub-optimality in under one microsecond -- up to two orders of magnitude faster than Tree Cache. We then extend JSTS to derive a new and very fast bounded suboptimal search, which guarantees solution quality in single-digit microseconds on average. Our results establish a remarkable new level of performance in the area. In particular, we show JSTS approaches and often improves upon the output complexity of an idealised oracle, which simply reads off and returns a corresponding but optimal solution path.

  • Open Access

    Dynamic Replanning for Improved Public Transport Routing

    by Abdallah Abuaisha, Bojie Shen, Daniel Harabor, Peter Stuckey, Mark Wallace

    Delays in public transport are common, often impacting users through prolonged travel times and missed transfers. Existing solutions for handling delays remain limited; backup plans based on historical data miss opportunities for earlier arrivals, while snapshot planning accounts for current delays but not future ones. With the growing availability of live delay data, users can adjust their journeys in real-time. However, the literature lacks a framework that fully exploits this advantage for system-scale dynamic replanning. To address this, we formalise the dynamic replanning problem in public transport routing and propose two solutions: a "pull" approach, where users manually request replanning, and a novel "push" approach, where the server proactively monitors and adjusts journeys. Our experiments show that the push approach outperforms the pull approach, achieving significant speedups. The results also reveal substantial arrival time savings enabled by dynamic replanning.

  • Open Access

    Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

    by 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.


  • Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms

    by Edward Lam, Peter J. Stuckey, Daniel Harabor

    Given a set of agents and a set of pickup-delivery requests located on a two-dimensional grid map, the multi-agent pickup and delivery problem assigns the requests to the agents such that every agent moves from its start location to the locations of its assigned requests and finally, to its end location without colliding into other agents and that the sum of arrival times is minimized. This paper proposes two exact branch-and-cut-and-price algorithms for the problem. The first algorithm performs a three-level search. A high-level master problem selects an optimal sequence of requests and a path for every agent from a large collection. A mid-level sequencing problem and a low-level navigation problem are solved simultaneously to incrementally enlarge the collection of request sequences and paths. The second algorithm first solves the sequencing problem to find a set of request sequences and then solves the navigation problem to determine if paths compatible with the request sequences exist. Experimental results indicate that the integrated algorithm solves more instances with higher congestion, and the deferred algorithm solves more instances with lower congestion and could scale to 100 agents and 100 requests, significantly higher than a state-of-the-art suboptimal approach. Funding: This research was supported by the Australian Research Council [Discovery Early Career Researcher Award DE240100042 and Discovery Projects DP190100013 and DP200100025] and by Amazon. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0268 .