Daniel Harabor
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Daniel Harabor has a total of 54 co-authors. Here are the top co-authors by number of shared publications:
- Peter James Stuckey
Monash University
19 shared publications - Jiaoyang Li
Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA
10 shared publications - Zhe Chen
School of Economics and Management, Beihang University, Beijing, China
9 shared publications - Mark Wallace
Monash University
6 shared publications - Sven Koenig
University of California
4 shared publications - Bojie Shen
Faculty of Information Technology, Monash University, Melbourne, Australia
3 shared publications
Latest Publications
- Open Access
- 31 August 2026
- Published by Elsevier in Journal of Public Transportation
- Vol. 28
An exact system optimum model for the schedule-based transit assignment problem
- 31 August 2026
- Published by Elsevier in Journal of Public Transportation
- Vol. 28
Open AccessAn exact system optimum model for the schedule-based transit assignment problem
- Open Access
- 13 February 2026
- Published by Elsevier in Transportation Research Part C: Emerging Technologies
- Vol. 185
Personalised incentives for demand management of congested public transport systems: A reverse-engineering approach and application
- 13 February 2026
- Published by Elsevier in Transportation Research Part C: Emerging Technologies
- Vol. 185
Open AccessPersonalised incentives for demand management of congested public transport systems: A reverse-engineering approach and application
- 11 November 2025
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 84
Prioritised Planning: Completeness, Optimality, and Complexity
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.
- 11 November 2025
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 84
Prioritised Planning: Completeness, Optimality, and Complexity
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
- 16 September 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 35 (1) , 131-139
Parallelizing Multi-objective A* Search
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.
- 16 September 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 35 (1) , 131-139
Open AccessParallelizing Multi-objective A* Search
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
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 10, 8430-8437
Dynamic Replanning for Improved Public Transport Routing
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.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 10, 8430-8437
Open AccessDynamic Replanning for Improved Public Transport Routing
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
- 19 July 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Symposium on Combinatorial Search
- Vol. 18, 196-200
Real-Time LaCAM for Real-Time MAPF
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.
- 19 July 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Symposium on Combinatorial Search
- Vol. 18, 196-200
Open AccessReal-Time LaCAM for Real-Time MAPF
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
- 19 July 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Symposium on Combinatorial Search
- Vol. 18, 38-46
Sub-Microsecond Grid Path Planning, at What Cost?
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.
- 19 July 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Symposium on Combinatorial Search
- Vol. 18, 38-46
Open AccessSub-Microsecond Grid Path Planning, at What Cost?
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
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 AccessDynamic Replanning for Improved Public Transport Routing
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
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (14) , 14726-14735
Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding
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.
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (14) , 14726-14735
Open AccessOnline Guidance Graph Optimization for Lifelong Multi-Agent Path Finding
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.
- 10 December 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms
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 .
- 10 December 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms
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 .