Author name cluster

Bojie Shen

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.

11 papers

2 author rows

AAAI Conference 2026 Conference Paper

EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding

Jinchun Du
Bojie Shen
Muhammad Aamir Cheema

The Euclidean Shortest Path Problem (ESPP) is a classic problem which requires finding the shortest path in a Euclidean plane with polygonal obstacles. The state-of-the-art solution, Euclidean Hub Labeling (EHL), offers ultra-fast query performance but comes with significant memory overhead, requiring up to tens of gigabytes of storage on large maps, limiting its use in memory-constrained environments like mobile phones. Additionally, EHL's memory usage can only be determined after index construction, and while it provides a memory-runtime tradeoff, it does not fully optimize memory utilization. In this work, we introduce an improved version of EHL, called EHL*, which overcomes these limitations. A key contribution of EHL* is its ability to create an index that adheres to a specified memory budget while optimizing query runtime performance. Moreover, EHL* can leverage pre-known query distributions, a common scenario in many real-world applications, to further enhance runtime efficiency. Our results show that EHL* can reduce memory usage by up to 10-20 times without much impact on query runtime performance compared to EHL, making it a highly effective solution for optimal pathfinding in memory-constrained environments. We also present a theoretical analysis comparing EHL* with EHL, providing insights into their indexing and query processing cost.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Dynamic Replanning for Improved Public Transport Routing

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.

PDF Details DOI

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

IJCAI Conference 2023 Conference Paper

Efficient Object Search in Game Maps

Jinchun Du
Bojie Shen
Shizhe Zhao
Muhammad Aamir Cheema
Adel Nadjaran Toosi

Video games feature a dynamic environment where locations of objects (e. g. , characters, equipment, weapons, vehicles etc. ) frequently change within the game world. Although searching for relevant nearby objects in such a dynamic setting is a fundamental operation, this problem has received little research attention. In this paper, we propose a simple lightweight index, called Grid Tree, to store objects and their associated textual data. Our index can be efficiently updated with the underlying updates such as object movements, and supports a variety of object search queries, including k nearest neighbors (returning the k closest objects), keyword k nearest neighbors (returning the k closest objects that satisfy query keywords), and several other variants. Our extensive experimental study, conducted on standard game maps benchmarks and real-world keywords, demonstrates that our approach has up to 2 orders of magnitude faster update times for moving objects compared to state-of-the-art approaches such as navigation mesh and IR-tree. At the same time, query performance of our approach is similar to or better than that of IR-tree and up to two orders of magnitude faster than the other competitor.

PDF Details DOI

SoCS Conference 2023 Conference Paper

Tracking Progress in Multi-Agent Path Finding (Student Abstract)

Bojie Shen

In this work, we introduce a set of methodological and visualisation tools to track progress and state-of-the-art performance in the area of Multi-Agent Path Finding (MAPF). Our objectives are to lower the barriers of entry for new researchers and to further promote the study of MAPF.

Details

AAAI Conference 2023 Conference Paper

Ultrafast Euclidean Shortest Path Computation Using Hub Labeling

Jinchun Du
Bojie Shen
Muhammad Aamir Cheema

Finding shortest paths in a Euclidean plane containing polygonal obstacles is a well-studied problem motivated by a variety of real-world applications. The state-of-the-art algorithms require finding obstacle corners visible to the source and target, and need to consider potentially a large number of candidate paths. This adversely affects their query processing cost. We address these limitations by proposing a novel adaptation of hub labeling which is the state-of-the-art approach for shortest distance computation in road networks. Our experimental study conducted on the widely used benchmark maps shows that our approach is typically 1-2 orders of magnitude faster than two state-of-the-art algorithms.

PDF Details DOI

AIJ Journal 2022 Journal Article

Fast optimal and bounded suboptimal Euclidean pathfinding

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

We consider optimal and suboptimal algorithms for the Euclidean Shortest Path Problem (ESPP) in two dimensions. For optimal path planning, 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 (CPD), a speedup technique for pathfinding on grids and spatial networks, which we exploit to efficiently compute candidate paths, in order to construct a completely novel ESPP algorithm, End Point Search (EPS). In a range of experiments and empirical comparisons we show that: (i) the auxiliary data structures required by EPS 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 performance. For suboptimal path planning, we extend the CPD such that it computes and compresses first move data of a larger number of selected candidate nodes covering every point in the Euclidean space. Our approach is search-free, simultaneously fast, and returns a path within a fixed bound of the optimal solution. In a range of empirical results, we show that: (i) our approach outperforms both offline/online optimal and suboptimal ESPP algorithms proposed in the literature; (ii) our approach demonstrates excellent path quality, better than all existing suboptimal ESPP algorithms; and (iii) the approach offers flexibility by allowing a trade-off between the CPD construction cost (space and time) and the suboptimality bound.

Details DOI

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

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

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