Author name cluster

Ryan Hechenberger

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.

4 papers

1 author row

SoCS Conference 2022 Conference Paper

Benchmarks for Pathfinding Search: Iron Harvest

Daniel Harabor
Ryan Hechenberger
Thomas Jahn

Pathfinding is a central topic in AI for games, with many approaches having been suggested. But comparing different algorithms is tricky, because design choices stem from different practical considerations; e. g. , some pathfinding systems are grid-based, others rely on a navigation mesh or visibility graph and so on. Current benchmarks mirror this trend, focusing on one set of assumptions while ignoring the rest. In this work we present a new unified benchmark using data from the game Iron Harvest. For 35 different levels in the game we generate several complementary map representations (grid, mesh and obstacle-set) and we provide a common set of challenging instances. We describe and analyse the new benchmark and then compare several leading pathfinding algorithms that begin from different assumption sets. Our goal is to allow researchers and practitioners to better understand the relative strengths and weakness of competing techniques.

Details

SoCS Conference 2022 Conference Paper

Dual Euclidean Shortest Path Search (Extended Abstract)

Ryan Hechenberger
Peter J. Stuckey
Pierre Le Bodic
Daniel Harabor

The Euclidean Shortest Path Problem (ESPP) asks us to find a minimum length path between two points on a 2D plane while avoiding a set of polygonal obstacles. Existing approaches for ESPP, based on Dijkstra or A* search, are primal methods that gradually build up longer and longer valid paths until they reach the target. In this paper we define an alternative algorithm for ESPP which can avoid this problem. Our approach starts from a path that ignores all obstacles, and generates longer and longer paths, each avoiding more obstacles, until eventually the search finds an optimal valid path.

Details

SoCS Conference 2021 Conference Paper

Multi-Target Search in Euclidean Space with Ray Shooting

Ryan Hechenberger
Daniel Harabor
Muhammad Aamir Cheema
Peter J. Stuckey
Pierre Le Bodic

The shortest path problem (SPP) asks us to find a minimum length path between two points, usually on a graph. In a Euclidean environment the points are in a 2D plane and here the path must avoid a set of polygonal obstacles. Solution methods for this Euclidean SPP (ESPP) typically convert the continuous 2D map into a discretised representation, like a graph or navigation mesh. RayScan is a recent and fast ESPP algorithm which avoids the preprocessing step by using a combination of "ray shooting" and polygon scanning. In this paper we improve the performance of RayScan using spatial reasoning and ray caching techniques. We also extend the algorithm, from single-target search to a multi-target setting. Comparative game map experiments show a substantial speedup.

Details

ICAPS Conference 2020 Conference Paper

Online Computation of Euclidean Shortest Paths in Two Dimensions

Ryan Hechenberger
Peter J. Stuckey
Daniel Harabor
Pierre Le Bodic
Muhammad Aamir Cheema

We consider the online version of Euclidean Shortest Path (ESP): a problem that asks for distance minimal trajectories between traversable pairs of points in the plane. The problem is made challenging because each trajectory must avoid a set of non-traversable obstacles represented as polygons. To solve ESP practitioners will often preprocess the environment and construct specialised data structures, such as visibility graphs and navigation meshes. Pathfinding queries on these data structures are fast but the preprocessed data becomes invalidated when obstacles move or change. In this work we propose RayScan, a new algorithmic approach for ESP which is entirely online. The central idea is simple: each time we expand a node we also cast a ray toward the target. If an obstacle intersects the ray we scan its perimeter for a turning point; i. e. a vertex from which a new ray can continue unimpeded towards the target. RayScan is fast, optimal and entirely online. Experiments show that it can significantly improve upon current state-of-the-art methods for ESP in cases where the set of obstacles is dynamic.

Details