publications

2023

1. Efficient Object Search in Game Maps

   Jinchun Du, Bojie Shen, Shizhe Zhao, and 2 more authors

   In Proceedings of International Joint Conference on Artificial Intelligence, IJCAI, 2023
2. Reducing Redundant Work in Jump Point Search

   Shizhe Zhao, Daniel Harabor, and Peter J. Stuckey

   In Proceedings of the 16th International Symposium on Combinatorial Search, SOCS 2023, 2023

   Abs

   Despite the existence of various fast preprocessing-based approaches for single-agent pathfinding on gridmaps, online approaches are still preferable in dynamic environments where obstacles may appear or disappear on the map between different queries.
   Jump Point Search (JPS) is a state-of-the-art algorithm for online pathfinding on grids. It utilises a local pruning policy and a successor generation policy to accelerate A* search by two orders of magnitude. However, JPS may exhibit pathological behaviors and become inefficient in certain map topologies that are common in dynamic environments.
   In this work, we investigate the root cause of JPS’s pathological behaviors and propose a new reasoning technique based on geometric constraints to address these issues on-the-fly. The new approach, called Constrained JPS, can achieve up to a 7x speedup, and this improvement can be up to 14x in pathological setups. An interesting direction for future research is to apply Constrained JPS to high-dimensional grid-based pathfinding problems. For example, in drone navigation problems, environments are sometimes modeled as 3D voxel gridmaps. JPS encounters similar pathological behaviors in this type of environment. In multi-agent pathfinding problems, a low-level single-agent planner needs to handle temporal obstacles, where obstacles can move, and the environment changes during the query.

2021

1. Customised Shortest Paths Using a Distributed Reverse Oracle

   Arthur Maheo, Shizhe Zhao, Afzaal Hassan, and 3 more authors

   In Proceedings of the Eleventh International Symposium on Combinatorial Search, SOCS, 2021

2020

1. Bounded Suboptimal Path Planning with Compressed Path Databases

   Shizhe Zhao, Mattia Chiari, Adi Botea, and 4 more authors

   In Proceedings of the 30th International Conference on Automated Planning and Scheduling, 2020

2019

1. Cutting the Size of Compressed Path Databases With Wildcards and Redundant Symbols

   Mattia Chiari, Shizhe Zhao, Adi Botea, and 5 more authors

   In Proceedings of the 29th International Conference on Automated Planning and Scheduling, 2019

   Abs

   Single agent path planning on gridmaps is a long studied problem in robotics and computer games. In certain application scenarios, it is critical to reduce first-move lag, i.e., an agent needs to wait until it knows in which direction to move. Compressed Path Databases (CPDs) are a state-of-the-art approach (in terms of speed) for optimal pathfinding on gridmaps. Each CPD is simply a data structure that provides an optimal first move: from any cell s towards any cell t of the gridmap. Created during an offline preprocessing step, and exploited during a subsequent online phase, CPDs can be used to compute shortest paths or optimal first move quickly. A major drawback of CPDs is the potentially large size of the preprocessed data. In this work, we introduced an additional reasoning step in the first-move extraction process, which enabled us to further compress and prune the preprocessed data. Results show significant reductions in CPD size. For instance, on a map with 200k nodes, an uncompressed first move matrix requires 50GB, the previous work requires 500MB, while our approach only requires 9MB. Such size reduction allows us to deploy CPDs on edge devices (e.g., robots) instead of relying on a centralised planner. In subsequent studies, we enabled a trade-off between size and optimality and extended the application scenario to road networks with dynamic traffic.

2018

1. Fast k-Nearest Neighbor on a Navigation Mesh

   Shizhe Zhao, David Taniar, and Daniel Damir Harabor

   In Proceedings of the Eleventh International Symposium on Combinatorial Search, SOCS 2018, Stockholm, Sweden - 14-15 July 2018, 2018

   Abs

   This work focuses on studying the k-nearest neighbor problem in a 2D Euclidean plane with obstacles (OkNN). An efficient OkNN algorithm can serve as a low-level solver to provide spatial information for a high-level task planner. For example, in an industrial warehouse setting, a robot may need to determine the k-closest storage locations where a specific inventory item can be found. A naive approach to solve this problem is to employ a single-source pathfinding algorithm to compute the shortest distance to all objects. However, with an increasing number of objects and the size of the map, two main challenges arise:
   (1) Pruning unpromising candidates during the query processing;
   (2) Efficiently computing the distance to multiple objects, especially when k is large.
   Traditional approaches rely on an incremental visibility graph, but they suffer from costly graph building and visibility checking. In this work, we developed a new algorithm that addresses the aforementioned challenges by representing the traversable space as a collection of convex polygons, known as a Navigation Mesh. We then adapted an optimal navigation mesh algorithm from the single-source single-target setting to the multi-target case. The new algorithm demonstrates orders of magnitude faster performance compared to visibility graph-based algorithms.
   In a subsequent study, we further considered moving objects and extended our method to more complex application scenarios, e.g., autonomous sea-cleaning robots.