Shiz Zh

I received my Ph.D. degree in Computer Science at Monash University in 2023, advised by Prof. Daniel Harabor and Prof. Peter Stuckey. My research focuses on heuristic search and automated planning, with strong connections to urban computing, the Internet of Things, and robotics. During my PhD research, I developed high-performance algorithms for path planning in various environments. This experience gives me a deep understanding of complex planning algorithms, creative thinking to improve them, and a broader view of research topics in AI field.

Other areas that interest me are multi-agent path planning, traffic optimisation, and general problem-solving techniques such as constraint programming, mixed integer programming, and local search. Additionally, I am open to modern techniques for data-driven tasks, such as predict+optimisation and machine learning.

Beyond research, I have also been involved in a diverse range of software projects. These experiences have equipped me with excellent engineering skills, including proficiency in implementation, problem-solving, and data analysis. As a software developer, I am proficient in C++ and Python and specialise in high-performance computing, low-level optimisation (cache-aware, SIMD, etc.), and Linux-based platforms.

CV
Full Publications

selected publications

2023

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.

2019

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

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.