Online graph pruning for pathfinding on grid maps

Daniel Harabor, Alban Grastien

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A*by an order of magnitude and more and report significant improvement over the current state of the art.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence
Place of PublicationMenlo Park, Calif
PublisherAAAI Press
Pages1114-1119
Number of pages6
Volume2
ISBN (Print)9781577355090
Publication statusPublished - 2011
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2011 - Hyatt Regency, San Francisco, United States of America
Duration: 7 Aug 201111 Aug 2011
Conference number: 25th
http://www.aaai.org/Conferences/AAAI/aaai11.php

Conference

ConferenceAAAI Conference on Artificial Intelligence 2011
Abbreviated titleAAAI 2011
CountryUnited States of America
CitySan Francisco
Period7/08/1111/08/11
Internet address

Cite this

Harabor, D., & Grastien, A. (2011). Online graph pruning for pathfinding on grid maps. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (Vol. 2, pp. 1114-1119). Menlo Park, Calif: AAAI Press.
Harabor, Daniel ; Grastien, Alban. / Online graph pruning for pathfinding on grid maps. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. Vol. 2 Menlo Park, Calif : AAAI Press, 2011. pp. 1114-1119
@inproceedings{8bd329ebc45c44c0b0e6a63f53e78c5c,
title = "Online graph pruning for pathfinding on grid maps",
abstract = "Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A*by an order of magnitude and more and report significant improvement over the current state of the art.",
author = "Daniel Harabor and Alban Grastien",
year = "2011",
language = "English",
isbn = "9781577355090",
volume = "2",
pages = "1114--1119",
booktitle = "Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence",
publisher = "AAAI Press",

}

Harabor, D & Grastien, A 2011, Online graph pruning for pathfinding on grid maps. in Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. vol. 2, AAAI Press, Menlo Park, Calif, pp. 1114-1119, AAAI Conference on Artificial Intelligence 2011, San Francisco, United States of America, 7/08/11.

Online graph pruning for pathfinding on grid maps. / Harabor, Daniel; Grastien, Alban.

Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. Vol. 2 Menlo Park, Calif : AAAI Press, 2011. p. 1114-1119.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Online graph pruning for pathfinding on grid maps

AU - Harabor, Daniel

AU - Grastien, Alban

PY - 2011

Y1 - 2011

N2 - Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A*by an order of magnitude and more and report significant improvement over the current state of the art.

AB - Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A*by an order of magnitude and more and report significant improvement over the current state of the art.

UR - http://www.scopus.com/inward/record.url?scp=80055060442&partnerID=8YFLogxK

M3 - Conference Paper

SN - 9781577355090

VL - 2

SP - 1114

EP - 1119

BT - Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence

PB - AAAI Press

CY - Menlo Park, Calif

ER -

Harabor D, Grastien A. Online graph pruning for pathfinding on grid maps. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. Vol. 2. Menlo Park, Calif: AAAI Press. 2011. p. 1114-1119