Mark Carlson, Daniel Harabor, Peter J. Stuckey

Sub-Microsecond Grid Path Planning, at What Cost?

Introduction

Sub-microsecond grid path planning, at what cost?. Discover Jump Spanning Tree Search (JSTS), an algorithm for sub-microsecond grid path planning. It vastly improves Tree Cache's speed and solution quality, offering fast, bounded suboptimal paths.

Abstract

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.

Review

This paper presents a significant advancement in grid path planning, directly addressing the common trade-off between search speed and solution quality. Building upon the existing Tree Cache method, known for its rapid path generation despite lacking quality guarantees, the authors introduce Jump Spanning Tree Search (JSTS). By ingeniously integrating symmetry breaking ideas derived from Jump Point Search (JPS), JSTS aims to resolve the inherent shortcomings of Tree Cache, promising improvements in both search speed and the optimality of the resulting paths. The initial proposition is compelling, suggesting a method that can deliver fast paths with better quality than its predecessor. The core of JSTS's innovation lies in its hybrid approach, leveraging the strengths of Tree Cache's pre-computation with JPS's efficient path exploration principles. The reported results are remarkably strong, indicating that JSTS can typically generate paths with low average sub-optimality in under one microsecond, representing an improvement of up to two orders of magnitude over Tree Cache. Furthermore, the paper extends JSTS to develop a bounded suboptimal search algorithm, guaranteeing solution quality within single-digit microseconds on average. These performance metrics establish a new benchmark in the field, with the authors making the bold claim that JSTS approaches and often surpasses the output complexity of an idealised oracle, which simply reads off and returns optimal paths. In response to the titular question, "Sub-Microsecond Grid Path Planning, at What Cost?", the paper convincingly argues that the "cost" in terms of solution quality is not only significantly reduced but also tightly controllable, especially with the bounded suboptimal variant. This work represents a major leap forward for applications demanding extremely rapid and reliably good pathfinding solutions, such as real-time strategy games, robotics, or high-frequency simulations. The impressive blend of speed and guaranteed sub-optimality positions JSTS as a highly impactful contribution, challenging existing paradigms and setting a new standard for efficient grid path planning.

Full Text

Comments

You need to be logged in to post a comment.