Author name cluster

Steve Rabin

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

2 author rows

IJCAI Conference 2016 Conference Paper

Canonical Orderings on Grids

Nathan R. Sturtevant
Steve Rabin

Jump Point Search, an algorithm developed for fast search on uniform cost grids, has successfully improved the performance of grid-based search. But, the approach itself is actually a set of diverse ideas applied together. This paper decomposes the algorithm and gradually reconstructs it, showing the component pieces from which the algorithm is constructed. In this process, we are able to define a spectrum of new algorithms that borrow and repurpose ideas from Jump Point Search. This decomposition opens the door for applying the ideas from Jump Point Search in other grid domains with significantly different characteristics from two dimensional grids.

PDF Details

AAAI Conference 2016 Conference Paper

Combining Bounding Boxes and JPS to Prune Grid Pathfinding

Steve Rabin
Nathan Sturtevant

Pathﬁnding is a common task across many domains and platforms, whether in games, robotics, or road maps. Given the breadth of domains, there are also a wide variety of representations used for pathﬁnding, and there are many techniques which have been shown to improve performance. In the last few years, the state-of-the-art in grid-based pathﬁnding has been signiﬁcantly improved with domain-speciﬁc techniques such as Jump Point Search (JPS), Subgoal Graphs, and Compressed Path Databases. In this paper we look at a speciﬁc implementation of the general idea of Geometric Containers, showing that, while it is effective on grid maps, when combined with JPS+ it provides state-of-the-art performance.

PDF Details

SoCS Conference 2015 Invited Paper

The Grid-Based Path Planning Competition: 2014 Entries and Results

Nathan R. Sturtevant
Jason M. Traish
James R. Tulip
Tansel Uras
Sven Koenig
Ben Strasser
Adi Botea
Daniel Harabor

The Grid-Based Path Planning Competition has just completed its third iteration. The entriesused in the competition have improved significantly during this time, changing the view ofthe state of the art of grid-based pathfinding. Furthermore, the entries from the competition have beenmade publicly available, improving the ability of researchers to compare their work. Thispaper summarizes the entries to the 2014 competition, presents the 2014 competition results, and talks about what has been learned and where there is room for improvement.

Details