Author name cluster

Thomas K. Nobes

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.

3 papers

1 author row

SoCS Conference 2023 Conference Paper

Pipe-Routing and Pathfinding in 3D (Student Abstract)

Thomas K. Nobes

Pipe-routing in 3D is a common problem in the design of industrial plant layouts. Here, we aim to minimise the structural cost of the plant (which can have multi-billion dollar budgets), while maintaining safety and engineering constraints. We tackle this problem by developing efficient methods for optimal 3D search. We contribute an adaption of Jump Point Search, a well-known symmetry-breaking technique for 2D grids, into 3D: in contrast to related work, our algorithm preserves path feasibility. In combination with a novel method for limiting over-scanning, we report search time speedups of up to an order of magnitude on benchmarks in the literature. We further develop three new and varied voxel benchmark data sets sourced from 3D applications in the literature in order to provide better opportunities for differentiating competing techniques. Towards pipe-routing, this work also identifies several remaining issues for translating the size of industrial domains and their associated constraints into 3D search.

Details

SoCS Conference 2023 Conference Paper

Voxel Benchmarks for 3D Pathfinding: Sandstone, Descent, and Industrial Plants

Thomas K. Nobes
Daniel Harabor
Michael Wybrow
Stuart D. C. Walsh

Voxel grids are an increasingly common enabler for pathfinding in 3D spaces. Currently in this area there exists only a limited number of publicly available benchmarks. This makes it difficult to establish state-of-the-art performance and to compare the strengths and weaknesses of competing search techniques. In this work, we introduce three new and diverse sets of voxel benchmarks intended to help fill this gap. We further describe our methodology for generating and selecting a representative set of pathfinding queries. Our dataset comprises 46 distinct voxel maps and 92, 000 problem instances. The data is drawn from distinct application domains: computer video games, industrial plant layouts and sandstone porosity scans. Featuring distinctive geometric properties and a variety of challenging query types, these new datasets allow practitioners to evaluate algorithmic performance across a variety of settings encountered when pathfinding in practice.

Details

SoCS Conference 2022 Conference Paper

The JPS Pathfinding System in 3D

Thomas K. Nobes
Daniel Harabor
Michael Wybrow
Stuart D. C. Walsh

The ability to quickly compute shortest paths in 3D grids is a technological enabler for several applications such as pipe routing and computer video games. The main challenge is how to deal with the many symmetric permutations of each shortest path. We tackle this problem by adapting Jump Point Search (JPS), a well-known symmetry breaking technique developed for fast pathfinding in 2D grids. We give a rigorous reformulation of the JPS pathfinding system into 3D and we prove that our new algorithm, JPS-3D, is optimality preserving. We also develop a novel method for limiting scan depth during jump operations, which can further reduce search time. Experimental results show significant improvements versus online A* search and previous attempts at generalising JPS. We demonstrate that searching with adaptive scan limits can yield additional speedups of over an order of magnitude.

Details